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