shape ops work in progress

mostly working on cubic/cubic intersect

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

1 files changed, 29 insertions, 0 deletions

diff --git a/experimental/Intersection/TSearch.h b/experimental/Intersection/TSearch.h
index 010e69f5e7..6952425585 100644
--- a/experimental/Intersection/TSearch.h
+++ b/experimental/Intersection/TSearch.h
@@ -12,6 +12,35 @@
 // FIXME: Move this templated version into SKTSearch.h
 
 template <typename T>
+static T* QSort_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 QSort(T* left, T* right)
+{
+    if (left >= right) {
+        return;
+    }
+    T* pivot = left + (right - left >> 1);
+    pivot = QSort_Partition(left, right, pivot);
+    QSort(left, pivot - 1);
+    QSort(pivot + 1, right);
+}
+
+template <typename T>
 static T** QSort_Partition(T** left, T** right, T** pivot)
 {
     T* pivotValue = *pivot;