add SkTQSort (stolen from cary's experimental work)

git-svn-id: http://skia.googlecode.com/svn/trunk@3854 2bbb7eff-a529-9590-31e7-b0007b416f81

1 files changed, 57 insertions, 0 deletions

diff --git a/src/core/SkTSort.h b/src/core/SkTSort.h
index 38f8f22526..86cc23a82e 100644
--- a/src/core/SkTSort.h
+++ b/src/core/SkTSort.h
@@ -39,4 +39,61 @@ template <typename T> void SkTHeapSort(T array[], int count) {
     }
 }
 
+///////////////////////////////////////////////////////////////////////////////
+
+template <typename T>
+static T** SkTQSort_Partition(T** left, T** right, T** pivot) {
+    T* pivotValue = *pivot;
+    SkTSwap(*pivot, *right);
+    T** newPivot = left;
+    while (left < right) {
+        if (**left < *pivotValue) {
+            SkTSwap(*left, *newPivot);
+            newPivot += 1;
+        }
+        left += 1;
+    }
+    SkTSwap(*newPivot, *right);
+    return newPivot;
+}
+
+template <typename T> void SkTQSort(T** left, T** right) {
+    if (left >= right) {
+        return;
+    }
+    T** pivot = left + (right - left >> 1);
+    pivot = SkTQSort_Partition(left, right, pivot);
+    SkTQSort(left, pivot - 1);
+    SkTQSort(pivot + 1, right);
+}
+
+template <typename S, typename T>
+static T* SkTQSort_Partition(S& context, T* left, T* right, T* pivot,
+                             bool (*lessThan)(S&, const T, const T)) {
+    T pivotValue = *pivot;
+    SkTSwap(*pivot, *right);
+    T* newPivot = left;
+    while (left < right) {
+        if (lessThan(context, *left, pivotValue)) {
+            SkTSwap(*left, *newPivot);
+            newPivot += 1;
+        }
+        left += 1;
+    }
+    SkTSwap(*newPivot, *right);
+    return newPivot;
+}
+
+template <typename S, typename T>
+void SkQSort(S& context, T* left, T* right,
+             bool (*lessThan)(S& , const T, const T)) {
+    if (left >= right) {
+        return;
+    }
+    T* pivot = left + (right - left >> 1);
+    pivot = SkTQSort_Partition(context, left, right, pivot, lessThan);
+    SkQSort(context, left, pivot - 1, lessThan);
+    SkQSort(context, pivot + 1, right, lessThan);
+}
+
 #endif