AK: Add a basic QuickSort template implementation.

It was depressing not being able to capture anything when passing a lambda
to qsort_r() so let's just have our own QuickSort. I was gonna have to do
this eventually anyway. :^)

3 files changed, 61 insertions, 16 deletions

diff --git a/AK/QuickSort.h b/AK/QuickSort.h
new file mode 100644
index 0000000000..88ecd80623
--- /dev/null
+++ b/AK/QuickSort.h
@@ -0,0 +1,47 @@
+#pragma once
+
+namespace AK {
+
+template<typename IteratorType, typename LessThan>
+IteratorType partition(IteratorType first, IteratorType last, LessThan less_than)
+{
+    auto pivot = last;
+    auto smallest = first - 1;
+    auto it = first;
+    for (; it < last; ++it) {
+        if (less_than(*it, *pivot)) {
+            ++smallest;
+            swap(*it, *smallest);
+        }
+    }
+    swap(*(smallest + 1), *last);
+    return smallest + 1;
+}
+
+template<typename IteratorType, typename LessThan>
+void quick_sort_impl(IteratorType begin, IteratorType first, IteratorType last, LessThan less_than)
+{
+    if (first < last) {
+        auto pivot = partition(first, last, less_than);
+        quick_sort_impl(begin, first, pivot - 1, less_than);
+        quick_sort_impl(begin, pivot + 1, last, less_than);
+    }
+}
+
+template<typename T>
+bool is_less_than(const T& a, const T& b)
+{
+    return a < b;
+}
+
+template<typename IteratorType, typename LessThan>
+void quick_sort(IteratorType begin, IteratorType end, LessThan less_than = is_less_than)
+{
+    if (begin == end)
+        return;
+    quick_sort_impl(begin, begin, end - 1, less_than);
+}
+
+}
+
+using AK::quick_sort;
diff --git a/AK/Vector.h b/AK/Vector.h
index 02f3997fd5..76e957c05d 100644
--- a/AK/Vector.h
+++ b/AK/Vector.h
@@ -274,7 +274,11 @@ public:
     class Iterator {
     public:
         bool operator!=(const Iterator& other) { return m_index != other.m_index; }
+        bool operator==(const Iterator& other) { return m_index == other.m_index; }
+        bool operator<(const Iterator& other) { return m_index < other.m_index; }
         Iterator& operator++() { ++m_index; return *this; }
+        Iterator operator-(int value) { return { m_vector, m_index - value }; }
+        Iterator operator+(int value) { return { m_vector, m_index + value }; }
         T& operator*() { return m_vector[m_index]; }
     private:
         friend class Vector;
@@ -289,7 +293,11 @@ public:
     class ConstIterator {
     public:
         bool operator!=(const ConstIterator& other) { return m_index != other.m_index; }
+        bool operator==(const ConstIterator& other) { return m_index == other.m_index; }
+        bool operator<(const ConstIterator& other) { return m_index < other.m_index; }
         ConstIterator& operator++() { ++m_index; return *this; }
+        ConstIterator operator-(int value) { return { m_vector, m_index - value }; }
+        ConstIterator operator+(int value) { return { m_vector, m_index + value }; }
         const T& operator*() const { return m_vector[m_index]; }
     private:
         friend class Vector;
diff --git a/LibGUI/GSortingProxyTableModel.cpp b/LibGUI/GSortingProxyTableModel.cpp
index 364b5f3638..bdb7dfba82 100644
--- a/LibGUI/GSortingProxyTableModel.cpp
+++ b/LibGUI/GSortingProxyTableModel.cpp
@@ -1,4 +1,5 @@
 #include <LibGUI/GSortingProxyTableModel.h>
+#include <AK/QuickSort.h>
 #include <stdlib.h>
 #include <stdio.h>
 
@@ -84,25 +85,14 @@ void GSortingProxyTableModel::resort()
         m_row_mappings[i] = i;
     if (m_key_column == -1)
         return;
-    struct Context {
-        GTableModel* target;
-        int key_column;
-        GSortOrder sort_order;
-    };
-    Context context { m_target.ptr(), m_key_column, m_sort_order };
-    qsort_r(m_row_mappings.data(), m_row_mappings.size(), sizeof(int), [] (const void* a, const void* b, void* ctx) -> int {
-        auto& context = *(Context*)(ctx);
-        GModelIndex index1 { *(const int*)(a), context.key_column };
-        GModelIndex index2 { *(const int*)(b), context.key_column };
-        auto data1 = context.target->data(index1, GTableModel::Role::Sort);
-        auto data2 = context.target->data(index2, GTableModel::Role::Sort);
+    quick_sort(m_row_mappings.begin(), m_row_mappings.end(), [&] (auto row1, auto row2) -> bool {
+        auto data1 = target().data({ row1, m_key_column }, GTableModel::Role::Sort);
+        auto data2 = target().data({ row2, m_key_column }, GTableModel::Role::Sort);
         if (data1 == data2)
             return 0;
         bool is_less_than = data1 < data2;
-        if (context.sort_order == GSortOrder::Ascending)
-            return is_less_than ? -1 : 1;
-        return is_less_than ? 1 : -1;
-    }, &context);
+        return m_sort_order == GSortOrder::Ascending ? is_less_than : !is_less_than;
+    });
 
     did_update();
 }