Line data Source code
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 {
17 0 : 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 {
22 2963 : 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>
42 0 : void SkTHeapSort_SiftUp(T array[], size_t root, size_t bottom, C lessThan) {
43 0 : T x = array[root-1];
44 0 : size_t start = root;
45 0 : size_t j = root << 1;
46 0 : while (j <= bottom) {
47 0 : if (j < bottom && lessThan(array[j-1], array[j])) {
48 0 : ++j;
49 : }
50 0 : array[root-1] = array[j-1];
51 0 : root = j;
52 0 : j = root << 1;
53 : }
54 0 : j = root >> 1;
55 0 : while (j >= start) {
56 0 : if (lessThan(array[j-1], x)) {
57 0 : array[root-1] = array[j-1];
58 0 : root = j;
59 0 : j = root >> 1;
60 : } else {
61 0 : break;
62 : }
63 : }
64 0 : array[root-1] = x;
65 0 : }
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>
76 0 : void SkTHeapSort_SiftDown(T array[], size_t root, size_t bottom, C lessThan) {
77 0 : T x = array[root-1];
78 0 : size_t child = root << 1;
79 0 : while (child <= bottom) {
80 0 : if (child < bottom && lessThan(array[child-1], array[child])) {
81 0 : ++child;
82 : }
83 0 : if (lessThan(x, array[child-1])) {
84 0 : array[root-1] = array[child-1];
85 0 : root = child;
86 0 : child = root << 1;
87 : } else {
88 0 : break;
89 : }
90 : }
91 0 : array[root-1] = x;
92 0 : }
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 : */
101 0 : template <typename T, typename C> void SkTHeapSort(T array[], size_t count, C lessThan) {
102 0 : for (size_t i = count >> 1; i > 0; --i) {
103 0 : SkTHeapSort_SiftDown(array, i, count, lessThan);
104 : }
105 :
106 0 : for (size_t i = count - 1; i > 0; --i) {
107 0 : SkTSwap<T>(array[0], array[i]);
108 0 : SkTHeapSort_SiftUp(array, 1, i, lessThan);
109 : }
110 0 : }
111 :
112 : /** Sorts the array of size count using comparator '<' using a Heap Sort algorithm. */
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. */
120 217 : template <typename T, typename C> static void SkTInsertionSort(T* left, T* right, C lessThan) {
121 1104 : for (T* next = left + 1; next <= right; ++next) {
122 887 : if (!lessThan(*next, *(next - 1))) {
123 250 : continue;
124 : }
125 637 : T insert = std::move(*next);
126 637 : T* hole = next;
127 2164 : do {
128 2164 : *hole = std::move(*(hole - 1));
129 2164 : --hole;
130 2164 : } while (left < hole && lessThan(insert, *(hole - 1)));
131 637 : *hole = std::move(insert);
132 : }
133 217 : }
134 :
135 : ///////////////////////////////////////////////////////////////////////////////
136 :
137 : template <typename T, typename C>
138 3 : static T* SkTQSort_Partition(T* left, T* right, T* pivot, C lessThan) {
139 3 : T pivotValue = *pivot;
140 3 : SkTSwap(*pivot, *right);
141 3 : T* newPivot = left;
142 257 : while (left < right) {
143 127 : if (lessThan(*left, pivotValue)) {
144 39 : SkTSwap(*left, *newPivot);
145 39 : newPivot += 1;
146 : }
147 127 : left += 1;
148 : }
149 3 : SkTSwap(*newPivot, *right);
150 3 : 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 : */
165 220 : template <typename T, typename C> void SkTIntroSort(int depth, T* left, T* right, C lessThan) {
166 3 : while (true) {
167 220 : if (right - left < 32) {
168 217 : SkTInsertionSort(left, right, lessThan);
169 217 : return;
170 : }
171 :
172 3 : if (depth == 0) {
173 0 : SkTHeapSort<T>(left, right - left + 1, lessThan);
174 0 : return;
175 : }
176 3 : --depth;
177 :
178 3 : T* pivot = left + ((right - left) >> 1);
179 3 : pivot = SkTQSort_Partition(left, right, pivot, lessThan);
180 :
181 3 : SkTIntroSort(depth, left, pivot - 1, lessThan);
182 3 : 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 : */
193 219 : template <typename T, typename C> void SkTQSort(T* left, T* right, C lessThan) {
194 219 : if (left >= right) {
195 5 : return;
196 : }
197 : // Limit Intro Sort recursion depth to no more than 2 * ceil(log2(n)).
198 214 : int depth = 2 * SkNextLog2(SkToU32(right - left));
199 214 : SkTIntroSort(depth, left, right, lessThan);
200 : }
201 :
202 : /** Sorts the region from left to right using comparator '<' using a Quick Sort algorithm. */
203 0 : template <typename T> void SkTQSort(T* left, T* right) {
204 0 : SkTQSort(left, right, SkTCompareLT<T>());
205 0 : }
206 :
207 : /** Sorts the region from left to right using comparator '* < *' using a Quick Sort algorithm. */
208 219 : template <typename T> void SkTQSort(T** left, T** right) {
209 219 : SkTQSort(left, right, SkTPointerCompareLT<T>());
210 219 : }
211 :
212 : #endif
|
