1 /*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7 #ifndef TSearch_DEFINED
8 #define TSearch_DEFINED
9
10 // FIXME: Move this templated version into SKTSearch.h
11
12 template <typename T>
QSort_Partition(T * left,T * right,T * pivot)13 static T* QSort_Partition(T* left, T* right, T* pivot)
14 {
15 T pivotValue = *pivot;
16 SkTSwap(*pivot, *right);
17 T* newPivot = left;
18 while (left < right) {
19 if (*left < pivotValue) {
20 SkTSwap(*left, *newPivot);
21 newPivot += 1;
22 }
23 left += 1;
24 }
25 SkTSwap(*newPivot, *right);
26 return newPivot;
27 }
28
29 template <typename T>
QSort(T * left,T * right)30 void QSort(T* left, T* right)
31 {
32 if (left >= right) {
33 return;
34 }
35 T* pivot = left + (right - left >> 1);
36 pivot = QSort_Partition(left, right, pivot);
37 QSort(left, pivot - 1);
38 QSort(pivot + 1, right);
39 }
40
41 template <typename T>
QSort_Partition(T ** left,T ** right,T ** pivot)42 static T** QSort_Partition(T** left, T** right, T** pivot)
43 {
44 T* pivotValue = *pivot;
45 SkTSwap(*pivot, *right);
46 T** newPivot = left;
47 while (left < right) {
48 if (**left < *pivotValue) {
49 SkTSwap(*left, *newPivot);
50 newPivot += 1;
51 }
52 left += 1;
53 }
54 SkTSwap(*newPivot, *right);
55 return newPivot;
56 }
57
58 template <typename T>
QSort(T ** left,T ** right)59 void QSort(T** left, T** right)
60 {
61 if (left >= right) {
62 return;
63 }
64 T** pivot = left + (right - left >> 1);
65 pivot = QSort_Partition(left, right, pivot);
66 QSort(left, pivot - 1);
67 QSort(pivot + 1, right);
68 }
69
70 template <typename S, typename T>
QSort_Partition(S & context,T * left,T * right,T * pivot,bool (* lessThan)(S &,const T,const T))71 static T* QSort_Partition(S& context, T* left, T* right, T* pivot,
72 bool (*lessThan)(S&, const T, const T))
73 {
74 T pivotValue = *pivot;
75 SkTSwap(*pivot, *right);
76 T* newPivot = left;
77 while (left < right) {
78 if (lessThan(context, *left, pivotValue)) {
79 SkTSwap(*left, *newPivot);
80 newPivot += 1;
81 }
82 left += 1;
83 }
84 SkTSwap(*newPivot, *right);
85 return newPivot;
86 }
87
88 template <typename S, typename T>
QSort(S & context,T * left,T * right,bool (* lessThan)(S &,const T,const T))89 void QSort(S& context, T* left, T* right,
90 bool (*lessThan)(S& , const T, const T))
91 {
92 if (left >= right) {
93 return;
94 }
95 T* pivot = left + (right - left >> 1);
96 pivot = QSort_Partition(context, left, right, pivot, lessThan);
97 QSort(context, left, pivot - 1, lessThan);
98 QSort(context, pivot + 1, right, lessThan);
99 }
100
101 #endif
102