[Courgette] Fix sorting in QSufSort's split().

courgette/third_party/paged_array_unittest.cc

 // Copyright (c) 2010 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "courgette/third_party/paged_array.h"
 
+#include <algorithm>
+
 #include "testing/gtest/include/gtest/gtest.h"
 
 class PagedArrayTest : public testing::Test {
  public:
   // Total allocation of 4GB will fail in 32 bit programs if allocations are
   // leaked.
   static const int kIterations = 20;
   static const int kSize = 200 * 1024 * 1024 / sizeof(int);  // 200MB
 };
 
@@ skipping 20 matching lines @@
   const int kAccessSize = 3 * 1024 * 1024;
   courgette::PagedArray<int> a;
   a.Allocate(kAccessSize);
   for (int i = 0; i < kAccessSize; ++i) {
     a[i] = i;
   }
   for (int i = 0; i < kAccessSize; ++i) {
     EXPECT_EQ(i, a[i]);
   }
 }
+
+TEST_F(PagedArrayTest, TestIterator) {
+  const int kIterSize = 1024 * 1024;
+  courgette::PagedArray<int> a;
+  EXPECT_TRUE(a.begin() == a.end());
+  EXPECT_FALSE(a.begin() != a.end());
+  EXPECT_FALSE(a.begin() < a.end());
+  EXPECT_FALSE(a.end() < a.begin());
+
+  a.Allocate(kIterSize);
+  EXPECT_FALSE(a.begin() == a.end());
+  EXPECT_TRUE(a.begin() != a.end());
+  EXPECT_TRUE(a.begin() < a.end());
+  EXPECT_FALSE(a.end() < a.begin());
+  EXPECT_EQ(kIterSize, a.end() - a.begin());
+  EXPECT_TRUE(a.begin() + kIterSize == a.end());
+
+  for (int i = 0; i < kIterSize; ++i) {
+    a[i] = i;
+  }
+  std::reverse(a.begin(), a.end());
+  for (auto it = a.begin(); it != a.end(); ++it) {
+    EXPECT_EQ(a.end() - it - 1, *it);
+  }
+}
+
+TEST_F(PagedArrayTest, TestSort) {
+  const int kPrimeSize = 300007;
+  courgette::PagedArray<int> a;
+  a.Allocate(kPrimeSize);
+  EXPECT_EQ(kPrimeSize, a.end() - a.begin());
+  for (int i = 0; i < kPrimeSize; ++i) {
+    a[i] = (i + 11) * 1031 % kPrimeSize;  // Produces distinct elements.
+  }
+  std::sort(a.begin(), a.end());
+  for (int i = 0; i < kPrimeSize; i += 1000) {
+    EXPECT_EQ(i, *(a.begin() + i));
+  }
+}