From 92fde90d9b5bfa07ba22be816f558434e7b07a93 Mon Sep 17 00:00:00 2001
From: "reed@google.com" <reed@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>
Date: Mon, 7 May 2012 18:10:15 +0000
Subject: add SkTQSort (stolen from cary's experimental work)

git-svn-id: http://skia.googlecode.com/svn/trunk@3854 2bbb7eff-a529-9590-31e7-b0007b416f81
---
 src/core/SkTSort.h | 57 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 57 insertions(+)

(limited to 'src/core')

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
-- 
cgit v1.2.3