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