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