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