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

courgette/third_party/paged_array_unittest.cc

Index: courgette/third_party/paged_array_unittest.cc
diff --git a/courgette/third_party/paged_array_unittest.cc b/courgette/third_party/paged_array_unittest.cc
index faa5548fb8f13d870b7ce8666a57b6a0e6817477..1c3ce1b0db74b2eb44b0b61728b8f24aacffab5c 100644
--- a/courgette/third_party/paged_array_unittest.cc
+++ b/courgette/third_party/paged_array_unittest.cc
@@ -4,6 +4,8 @@
 
 #include "courgette/third_party/paged_array.h"
 
+#include <algorithm>
+
 #include "testing/gtest/include/gtest/gtest.h"
 
 class PagedArrayTest : public testing::Test {
@@ -44,3 +46,42 @@ TEST_F(PagedArrayTest, TestAccess) {
     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));
+  }
+}