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
|
#include "SkTypes.h"
// FIXME: Move this templated version into SKTSearch.h
template <typename T>
static void QSort_Partition(T** first, T** last)
{
T** left = first;
T** rite = last;
T** pivot = left;
while (left <= rite) {
while (left < last && **left < **pivot)
left += 1;
while (first < rite && **pivot < **rite)
rite -= 1;
if (left <= rite) {
if (left < rite) {
SkTSwap(*left, *rite);
}
left += 1;
rite -= 1;
}
}
if (first < rite)
QSort_Partition(first, rite);
if (left < last)
QSort_Partition(left, last);
}
template <typename T>
void QSort(T** base, size_t count)
{
SkASSERT(base);
if (count <= 1) {
return;
}
QSort_Partition(base, base + (count - 1));
}
template <typename S, typename T>
static void QSort_Partition(S& context, T* first, T* last,
bool (*lessThan)(S&, const T*, const T*))
{
T* left = first;
T* rite = last;
T* pivot = left;
while (left <= rite) {
while (left < last && lessThan(context, left, pivot))
left += 1;
while (first < rite && lessThan(context, pivot, rite))
rite -= 1;
if (left <= rite) {
if (left < rite) {
SkTSwap(*left, *rite);
}
left += 1;
rite -= 1;
}
}
if (first < rite)
QSort_Partition(context, first, rite, lessThan);
if (left < last)
QSort_Partition(context, left, last, lessThan);
}
template <typename S, typename T>
void QSort(S& context, T* base, size_t count,
bool (*lessThan)(S& , const T*, const T*))
{
SkASSERT(base);
SkASSERT(lessThan);
if (count <= 1) {
return;
}
QSort_Partition(context, base, base + (count - 1), lessThan);
}
|
