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

courgette/third_party/paged_array.h

Index: courgette/third_party/paged_array.h
diff --git a/courgette/third_party/paged_array.h b/courgette/third_party/paged_array.h
index 48a92f171fb1a804d9947ba419c1b7a60027d7ab..ba66408680dce5408dabecb763372e20d5afaebb 100644
--- a/courgette/third_party/paged_array.h
+++ b/courgette/third_party/paged_array.h
@@ -12,12 +12,88 @@
 #define COURGETTE_BSDIFF_PAGED_ARRAY_H_
 
 #include <stddef.h>
+#include <iterator>
 
 #include "base/macros.h"
 #include "base/process/memory.h"
 
 namespace courgette {
 
+template<typename T>
+class PagedArray;
+
+// RandomAccessIterator for PagedArray<T> to enable std::sort().
+template<typename T>
+class PagedArray_iterator {
+ public:
+  PagedArray_iterator() : array_(nullptr), index_(0U) { }
+
+  PagedArray_iterator(PagedArray<T>* array, size_t index)
+      : array_(array), index_(index) { }
+
+  ~PagedArray_iterator() { }
+
+  const T& operator*() const { return (*array_)[index_]; }
+
+  T& operator*() { return (*array_)[index_]; }
+
+  PagedArray_iterator<T>& operator++() {
+    ++index_;
+    return *this;
+  }
+
+  PagedArray_iterator<T> operator++(int) {
+    return PagedArray_iterator<T>(array_, index_++);
+  }
+
+  PagedArray_iterator<T> operator+=(size_t inc) {
+    return PagedArray_iterator<T>(array_, index_ += inc);
+  }
+
+  PagedArray_iterator<T>& operator--() {
+    --index_;
+    return *this;
+  }
+
+  PagedArray_iterator<T> operator+(size_t offset) {
+    return PagedArray_iterator<T>(array_, index_ + offset);
+  }
+
+  PagedArray_iterator<T> operator-(size_t offset) {
+    return PagedArray_iterator<T>(array_, index_ - offset);
+  }
+
+  bool operator==(const PagedArray_iterator<T>& it) const {
+    return index_ == it.index_ && array_ == it.array_;
+  }
+
+  bool operator!=(const PagedArray_iterator<T>& it) const {
+    return index_ != it.index_ || array_ != it.array_;
+  }
+
+  bool operator<(const PagedArray_iterator<T>& it) const {
+    // Not bothering to check array_, for performance.
+    return index_ < it.index_;
+  }
+
+  ptrdiff_t operator-(const PagedArray_iterator<T>& it) const {
+    return index_ - it.index_;
+  }
+
+ private:
+  PagedArray<T>* array_;
+  size_t index_;
+};
+
+template<typename T>
+struct std::iterator_traits<class PagedArray_iterator<T> > {
+  typedef ptrdiff_t difference_type;
+  typedef T value_type;
+  typedef T& reference;
+  typedef T* pointer;
+  typedef std::random_access_iterator_tag iterator_category;
+};
+
 // PagedArray implements an array stored using many fixed-size pages.
 template<typename T>
 class PagedArray {
@@ -28,10 +104,16 @@ class PagedArray {
   };
 
  public:
-  PagedArray() : pages_(NULL), page_count_(0) {}
+  typedef PagedArray_iterator<T> iterator;
+
+  PagedArray() { }
 
   ~PagedArray() { clear(); }
 
+  iterator begin() { return iterator(this, 0); }
+
+  iterator end() { return iterator(this, size_); }
+
   T& operator[](size_t i) {
     size_t page = i >> kLogPageSize;
     size_t offset = i & (kPageSize - 1);
@@ -44,7 +126,8 @@ class PagedArray {
   // allocation fails.
   bool Allocate(size_t size) {
     clear();
-    size_t pages_needed = (size + kPageSize - 1) >> kLogPageSize;
+    size_ = size;
+    size_t pages_needed = (size_ + kPageSize - 1) >> kLogPageSize;
     if (!base::UncheckedMalloc(sizeof(T*) * pages_needed,
                                reinterpret_cast<void**>(&pages_))) {
       return false;
@@ -64,21 +147,25 @@ class PagedArray {
 
   // Releases all storage.  May be called more than once.
   void clear() {
-    if (pages_ != NULL) {
+    if (pages_ != nullptr) {
       while (page_count_ != 0) {
         --page_count_;
         free(pages_[page_count_]);
       }
       free(pages_);
-      pages_ = NULL;
+      pages_ = nullptr;
     }
+    size_ = 0;
   }
 
  private:
-  T** pages_;
-  size_t page_count_;
+  T** pages_ = nullptr;
+  size_t size_ = 0U;
+  size_t page_count_ = 0U;
 
   DISALLOW_COPY_AND_ASSIGN(PagedArray);
 };
-}  // namespace
+
+}  // namespace courgette
+
 #endif  // COURGETTE_BSDIFF_PAGED_ARRAY_H_