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 "include/core/SkTypes.h"
12#include "include/private/SkTo.h"
13#include "src/core/SkMathPriv.h"
14
15#include <utility>
16
17/* A comparison functor which performs the comparison 'a < b'. */
18template <typename T> struct SkTCompareLT {
19 bool operator()(const T a, const T b) const { return a < b; }
20};
21
22/* A comparison functor which performs the comparison '*a < *b'. */
23template <typename T> struct SkTPointerCompareLT {
24 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 */
43template <typename T, typename C>
44void 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 */
77template <typename T, typename C>
78void 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 */
103template <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. */
116template <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. */
123template <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
140template <typename T, typename C>
141static 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 */
169template <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 */
197template <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. */
207template <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. */
212template <typename T> void SkTQSort(T** left, T** right) {
213 SkTQSort(left, right, SkTPointerCompareLT<T>());
214}
215
216#endif
217