From 5ee3f67ce35f19f6e5ef44b67db62e964f77d69d Mon Sep 17 00:00:00 2001
From: "rileya@google.com"
 <rileya@google.com@2bbb7eff-a529-9590-31e7-b0007b416f81>
Date: Tue, 28 Aug 2012 14:40:49 +0000
Subject: [PATCH] Added an overload of SkTQSort that sorts an array of values,
 rather than an array of pointers.

Also added some parentheses to all the QSort variants to get rid of a gcc warning.
Review URL: https://codereview.appspot.com/6492044

git-svn-id: http://skia.googlecode.com/svn/trunk@5311 2bbb7eff-a529-9590-31e7-b0007b416f81
---
 src/core/SkTSort.h | 30 ++++++++++++++++++++++++++++--
 tests/SortTest.cpp |  4 ++++
 2 files changed, 32 insertions(+), 2 deletions(-)

diff --git a/src/core/SkTSort.h b/src/core/SkTSort.h
index 86cc23a..db961d0 100644
--- a/src/core/SkTSort.h
+++ b/src/core/SkTSort.h
@@ -61,7 +61,33 @@ template <typename T> void SkTQSort(T** left, T** right) {
     if (left >= right) {
         return;
     }
-    T** pivot = left + (right - left >> 1);
+    T** pivot = left + ((right - left) >> 1);
+    pivot = SkTQSort_Partition(left, right, pivot);
+    SkTQSort(left, pivot - 1);
+    SkTQSort(pivot + 1, right);
+}
+
+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);
@@ -90,7 +116,7 @@ void SkQSort(S& context, T* left, T* right,
     if (left >= right) {
         return;
     }
-    T* pivot = left + (right - left >> 1);
+    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);
diff --git a/tests/SortTest.cpp b/tests/SortTest.cpp
index d1a61d4..65c4863 100644
--- a/tests/SortTest.cpp
+++ b/tests/SortTest.cpp
@@ -69,6 +69,10 @@ static void TestSort(skiatest::Reporter* reporter) {
         rand_array(rand, array, count);
         SkTHeapSort<int>(array, count);
         check_sort(reporter, "Heap", array, count);
+
+        rand_array(rand, array, count);
+        SkTQSort<int>(array, array + count - 1);
+        check_sort(reporter, "Quick", array, count);
     }
     if (false) { // avoid bit rot, suppress warning
         compare_int(array, array);
-- 
2.7.4