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