1 /*
2 * Copyright 2006 The Android Open Source Project
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
8
9 #ifndef SkTSort_DEFINED
10 #define SkTSort_DEFINED
11
12 #include "SkTypes.h"
13 #include "SkMathPriv.h"
14
15 /* A comparison functor which performs the comparison 'a < b'. */
16 template <typename T> struct SkTCompareLT {
operatorSkTCompareLT17 bool operator()(const T a, const T b) const { return a < b; }
18 };
19
20 /* A comparison functor which performs the comparison '*a < *b'. */
21 template <typename T> struct SkTPointerCompareLT {
operatorSkTPointerCompareLT22 bool operator()(const T* a, const T* b) const { return *a < *b; }
23 };
24
25 ///////////////////////////////////////////////////////////////////////////////
26
27 /* Sifts a broken heap. The input array is a heap from root to bottom
28 * except that the root entry may be out of place.
29 *
30 * Sinks a hole from array[root] to leaf and then sifts the original array[root] element
31 * from the leaf level up.
32 *
33 * This version does extra work, in that it copies child to parent on the way down,
34 * then copies parent to child on the way back up. When copies are inexpensive,
35 * this is an optimization as this sift variant should only be used when
36 * the potentially out of place root entry value is expected to be small.
37 *
38 * @param root the one based index into array of the out-of-place root of the heap.
39 * @param bottom the one based index in the array of the last entry in the heap.
40 */
41 template <typename T, typename C>
SkTHeapSort_SiftUp(T array[],size_t root,size_t bottom,C lessThan)42 void SkTHeapSort_SiftUp(T array[], size_t root, size_t bottom, C lessThan) {
43 T x = array[root-1];
44 size_t start = root;
45 size_t j = root << 1;
46 while (j <= bottom) {
47 if (j < bottom && lessThan(array[j-1], array[j])) {
48 ++j;
49 }
50 array[root-1] = array[j-1];
51 root = j;
52 j = root << 1;
53 }
54 j = root >> 1;
55 while (j >= start) {
56 if (lessThan(array[j-1], x)) {
57 array[root-1] = array[j-1];
58 root = j;
59 j = root >> 1;
60 } else {
61 break;
62 }
63 }
64 array[root-1] = x;
65 }
66
67 /* Sifts a broken heap. The input array is a heap from root to bottom
68 * except that the root entry may be out of place.
69 *
70 * Sifts the array[root] element from the root down.
71 *
72 * @param root the one based index into array of the out-of-place root of the heap.
73 * @param bottom the one based index in the array of the last entry in the heap.
74 */
75 template <typename T, typename C>
SkTHeapSort_SiftDown(T array[],size_t root,size_t bottom,C lessThan)76 void SkTHeapSort_SiftDown(T array[], size_t root, size_t bottom, C lessThan) {
77 T x = array[root-1];
78 size_t child = root << 1;
79 while (child <= bottom) {
80 if (child < bottom && lessThan(array[child-1], array[child])) {
81 ++child;
82 }
83 if (lessThan(x, array[child-1])) {
84 array[root-1] = array[child-1];
85 root = child;
86 child = root << 1;
87 } else {
88 break;
89 }
90 }
91 array[root-1] = x;
92 }
93
94 /** Sorts the array of size count using comparator lessThan using a Heap Sort algorithm. Be sure to
95 * specialize SkTSwap if T has an efficient swap operation.
96 *
97 * @param array the array to be sorted.
98 * @param count the number of elements in the array.
99 * @param lessThan a functor with bool operator()(T a, T b) which returns true if a comes before b.
100 */
SkTHeapSort(T array[],size_t count,C lessThan)101 template <typename T, typename C> void SkTHeapSort(T array[], size_t count, C lessThan) {
102 for (size_t i = count >> 1; i > 0; --i) {
103 SkTHeapSort_SiftDown(array, i, count, lessThan);
104 }
105
106 for (size_t i = count - 1; i > 0; --i) {
107 SkTSwap<T>(array[0], array[i]);
108 SkTHeapSort_SiftUp(array, 1, i, lessThan);
109 }
110 }
111
112 /** Sorts the array of size count using comparator '<' using a Heap Sort algorithm. */
SkTHeapSort(T array[],size_t count)113 template <typename T> void SkTHeapSort(T array[], size_t count) {
114 SkTHeapSort(array, count, SkTCompareLT<T>());
115 }
116
117 ///////////////////////////////////////////////////////////////////////////////
118
119 /** Sorts the array of size count using comparator lessThan using an Insertion Sort algorithm. */
SkTInsertionSort(T * left,T * right,C lessThan)120 template <typename T, typename C> static void SkTInsertionSort(T* left, T* right, C lessThan) {
121 for (T* next = left + 1; next <= right; ++next) {
122 if (!lessThan(*next, *(next - 1))) {
123 continue;
124 }
125 T insert = std::move(*next);
126 T* hole = next;
127 do {
128 *hole = std::move(*(hole - 1));
129 --hole;
130 } while (left < hole && lessThan(insert, *(hole - 1)));
131 *hole = std::move(insert);
132 }
133 }
134
135 ///////////////////////////////////////////////////////////////////////////////
136
137 template <typename T, typename C>
SkTQSort_Partition(T * left,T * right,T * pivot,C lessThan)138 static T* SkTQSort_Partition(T* left, T* right, T* pivot, C lessThan) {
139 T pivotValue = *pivot;
140 SkTSwap(*pivot, *right);
141 T* newPivot = left;
142 while (left < right) {
143 if (lessThan(*left, pivotValue)) {
144 SkTSwap(*left, *newPivot);
145 newPivot += 1;
146 }
147 left += 1;
148 }
149 SkTSwap(*newPivot, *right);
150 return newPivot;
151 }
152
153 /* Intro Sort is a modified Quick Sort.
154 * When the region to be sorted is a small constant size it uses Insertion Sort.
155 * When depth becomes zero, it switches over to Heap Sort.
156 * This implementation recurses on the left region after pivoting and loops on the right,
157 * we already limit the stack depth by switching to heap sort,
158 * and cache locality on the data appears more important than saving a few stack frames.
159 *
160 * @param depth at this recursion depth, switch to Heap Sort.
161 * @param left the beginning of the region to be sorted.
162 * @param right the end of the region to be sorted (inclusive).
163 * @param lessThan a functor with bool operator()(T a, T b) which returns true if a comes before b.
164 */
SkTIntroSort(int depth,T * left,T * right,C lessThan)165 template <typename T, typename C> void SkTIntroSort(int depth, T* left, T* right, C lessThan) {
166 while (true) {
167 if (right - left < 32) {
168 SkTInsertionSort(left, right, lessThan);
169 return;
170 }
171
172 if (depth == 0) {
173 SkTHeapSort<T>(left, right - left + 1, lessThan);
174 return;
175 }
176 --depth;
177
178 T* pivot = left + ((right - left) >> 1);
179 pivot = SkTQSort_Partition(left, right, pivot, lessThan);
180
181 SkTIntroSort(depth, left, pivot - 1, lessThan);
182 left = pivot + 1;
183 }
184 }
185
186 /** Sorts the region from left to right using comparator lessThan using a Quick Sort algorithm. Be
187 * sure to specialize SkTSwap if T has an efficient swap operation.
188 *
189 * @param left the beginning of the region to be sorted.
190 * @param right the end of the region to be sorted (inclusive).
191 * @param lessThan a functor with bool operator()(T a, T b) which returns true if a comes before b.
192 */
SkTQSort(T * left,T * right,C lessThan)193 template <typename T, typename C> void SkTQSort(T* left, T* right, C lessThan) {
194 if (left >= right) {
195 return;
196 }
197 // Limit Intro Sort recursion depth to no more than 2 * ceil(log2(n)).
198 int depth = 2 * SkNextLog2(SkToU32(right - left));
199 SkTIntroSort(depth, left, right, lessThan);
200 }
201
202 /** Sorts the region from left to right using comparator '<' using a Quick Sort algorithm. */
SkTQSort(T * left,T * right)203 template <typename T> void SkTQSort(T* left, T* right) {
204 SkTQSort(left, right, SkTCompareLT<T>());
205 }
206
207 /** Sorts the region from left to right using comparator '* < *' using a Quick Sort algorithm. */
SkTQSort(T ** left,T ** right)208 template <typename T> void SkTQSort(T** left, T** right) {
209 SkTQSort(left, right, SkTPointerCompareLT<T>());
210 }
211
212 #endif
213