OLD | NEW |
| (Empty) |
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> | |
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> | |
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> | |
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> | |
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> | |
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> | |
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 | |
OLD | NEW |