epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 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 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 9 | |
| 10 | #ifndef SkTSort_DEFINED |
| 11 | #define SkTSort_DEFINED |
| 12 | |
| 13 | #include "SkTypes.h" |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 14 | #include "SkMath.h" |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 15 | |
| 16 | /* A comparison functor which performs the comparison 'a < b'. */ |
| 17 | template <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'. */ |
| 22 | template <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 |
bungeman@google.com | 59ed910 | 2013-01-24 22:18:56 +0000 | [diff] [blame] | 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 | */ |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 42 | template <typename T, typename C> |
| 43 | void SkTHeapSort_SiftUp(T array[], size_t root, size_t bottom, C lessThan) { |
bungeman@google.com | 59ed910 | 2013-01-24 22:18:56 +0000 | [diff] [blame] | 44 | T x = array[root-1]; |
| 45 | size_t start = root; |
| 46 | size_t j = root << 1; |
| 47 | while (j <= bottom) { |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 48 | if (j < bottom && lessThan(array[j-1], array[j])) { |
bungeman@google.com | 59ed910 | 2013-01-24 22:18:56 +0000 | [diff] [blame] | 49 | ++j; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 50 | } |
bungeman@google.com | 59ed910 | 2013-01-24 22:18:56 +0000 | [diff] [blame] | 51 | array[root-1] = array[j-1]; |
| 52 | root = j; |
| 53 | j = root << 1; |
| 54 | } |
| 55 | j = root >> 1; |
| 56 | while (j >= start) { |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 57 | if (lessThan(array[j-1], x)) { |
bungeman@google.com | 59ed910 | 2013-01-24 22:18:56 +0000 | [diff] [blame] | 58 | array[root-1] = array[j-1]; |
| 59 | root = j; |
| 60 | j = root >> 1; |
reed@android.com | eff416b | 2009-03-18 03:08:15 +0000 | [diff] [blame] | 61 | } else { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 62 | break; |
reed@android.com | eff416b | 2009-03-18 03:08:15 +0000 | [diff] [blame] | 63 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 64 | } |
bungeman@google.com | 59ed910 | 2013-01-24 22:18:56 +0000 | [diff] [blame] | 65 | array[root-1] = x; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 66 | } |
| 67 | |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 68 | /* Sifts a broken heap. The input array is a heap from root to bottom |
bungeman@google.com | 59ed910 | 2013-01-24 22:18:56 +0000 | [diff] [blame] | 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 | */ |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 76 | template <typename T, typename C> |
| 77 | void SkTHeapSort_SiftDown(T array[], size_t root, size_t bottom, C lessThan) { |
bungeman@google.com | 59ed910 | 2013-01-24 22:18:56 +0000 | [diff] [blame] | 78 | T x = array[root-1]; |
| 79 | size_t child = root << 1; |
| 80 | while (child <= bottom) { |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 81 | if (child < bottom && lessThan(array[child-1], array[child])) { |
bungeman@google.com | 59ed910 | 2013-01-24 22:18:56 +0000 | [diff] [blame] | 82 | ++child; |
| 83 | } |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 84 | if (lessThan(x, array[child-1])) { |
bungeman@google.com | 59ed910 | 2013-01-24 22:18:56 +0000 | [diff] [blame] | 85 | array[root-1] = array[child-1]; |
| 86 | root = child; |
| 87 | child = root << 1; |
| 88 | } else { |
| 89 | break; |
| 90 | } |
reed@android.com | eff416b | 2009-03-18 03:08:15 +0000 | [diff] [blame] | 91 | } |
bungeman@google.com | 59ed910 | 2013-01-24 22:18:56 +0000 | [diff] [blame] | 92 | array[root-1] = x; |
| 93 | } |
| 94 | |
bsalomon@google.com | ff43661 | 2013-02-27 19:07:32 +0000 | [diff] [blame] | 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. |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 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 | */ |
| 102 | template <typename T, typename C> void SkTHeapSort(T array[], size_t count, C lessThan) { |
bungeman@google.com | 59ed910 | 2013-01-24 22:18:56 +0000 | [diff] [blame] | 103 | for (size_t i = count >> 1; i > 0; --i) { |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 104 | SkTHeapSort_SiftDown(array, i, count, lessThan); |
bungeman@google.com | 59ed910 | 2013-01-24 22:18:56 +0000 | [diff] [blame] | 105 | } |
| 106 | |
| 107 | for (size_t i = count - 1; i > 0; --i) { |
reed@android.com | eff416b | 2009-03-18 03:08:15 +0000 | [diff] [blame] | 108 | SkTSwap<T>(array[0], array[i]); |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 109 | SkTHeapSort_SiftUp(array, 1, i, lessThan); |
| 110 | } |
| 111 | } |
| 112 | |
| 113 | /** Sorts the array of size count using comparator '<' using a Heap Sort algorithm. */ |
| 114 | template <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. */ |
| 121 | template <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; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 130 | } |
| 131 | } |
| 132 | |
reed@google.com | 92fde90 | 2012-05-07 18:10:15 +0000 | [diff] [blame] | 133 | /////////////////////////////////////////////////////////////////////////////// |
| 134 | |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 135 | template <typename T, typename C> |
| 136 | static T* SkTQSort_Partition(T* left, T* right, T* pivot, C lessThan) { |
| 137 | T pivotValue = *pivot; |
reed@google.com | 92fde90 | 2012-05-07 18:10:15 +0000 | [diff] [blame] | 138 | SkTSwap(*pivot, *right); |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 139 | T* newPivot = left; |
reed@google.com | 92fde90 | 2012-05-07 18:10:15 +0000 | [diff] [blame] | 140 | while (left < right) { |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 141 | if (lessThan(*left, pivotValue)) { |
reed@google.com | 92fde90 | 2012-05-07 18:10:15 +0000 | [diff] [blame] | 142 | SkTSwap(*left, *newPivot); |
| 143 | newPivot += 1; |
| 144 | } |
| 145 | left += 1; |
| 146 | } |
| 147 | SkTSwap(*newPivot, *right); |
| 148 | return newPivot; |
| 149 | } |
| 150 | |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 151 | /* Intro Sort is a modified Quick Sort. |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 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. |
bungeman@google.com | 4e5a895 | 2013-02-04 19:54:15 +0000 | [diff] [blame] | 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. |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 162 | */ |
| 163 | template <typename T, typename C> void SkTIntroSort(int depth, T* left, T* right, C lessThan) { |
bungeman@google.com | 4e5a895 | 2013-02-04 19:54:15 +0000 | [diff] [blame] | 164 | while (true) { |
| 165 | if (right - left < 32) { |
| 166 | SkTInsertionSort(left, right, lessThan); |
| 167 | return; |
| 168 | } |
| 169 | |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 170 | if (depth == 0) { |
| 171 | SkTHeapSort<T>(left, right - left + 1, lessThan); |
| 172 | return; |
| 173 | } |
| 174 | --depth; |
bungeman@google.com | bbec4e6 | 2013-01-25 18:25:17 +0000 | [diff] [blame] | 175 | |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 176 | T* pivot = left + ((right - left) >> 1); |
| 177 | pivot = SkTQSort_Partition(left, right, pivot, lessThan); |
| 178 | |
bungeman@google.com | 4e5a895 | 2013-02-04 19:54:15 +0000 | [diff] [blame] | 179 | SkTIntroSort(depth, left, pivot - 1, lessThan); |
| 180 | left = pivot + 1; |
reed@google.com | 92fde90 | 2012-05-07 18:10:15 +0000 | [diff] [blame] | 181 | } |
rileya@google.com | 5ee3f67 | 2012-08-28 14:40:49 +0000 | [diff] [blame] | 182 | } |
| 183 | |
bsalomon@google.com | ff43661 | 2013-02-27 19:07:32 +0000 | [diff] [blame] | 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. |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 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 | */ |
| 191 | template <typename T, typename C> void SkTQSort(T* left, T* right, C lessThan) { |
bungeman@google.com | 118c1a7 | 2013-01-30 21:23:13 +0000 | [diff] [blame] | 192 | if (left >= right) { |
| 193 | return; |
| 194 | } |
bungeman@google.com | 4e5a895 | 2013-02-04 19:54:15 +0000 | [diff] [blame] | 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); |
rileya@google.com | 5ee3f67 | 2012-08-28 14:40:49 +0000 | [diff] [blame] | 198 | } |
| 199 | |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 200 | /** Sorts the region from left to right using comparator '<' using a Quick Sort algorithm. */ |
rileya@google.com | 5ee3f67 | 2012-08-28 14:40:49 +0000 | [diff] [blame] | 201 | template <typename T> void SkTQSort(T* left, T* right) { |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 202 | SkTQSort(left, right, SkTCompareLT<T>()); |
reed@google.com | 92fde90 | 2012-05-07 18:10:15 +0000 | [diff] [blame] | 203 | } |
| 204 | |
bungeman@google.com | e83e994 | 2013-01-30 21:01:26 +0000 | [diff] [blame] | 205 | /** Sorts the region from left to right using comparator '* < *' using a Quick Sort algorithm. */ |
| 206 | template <typename T> void SkTQSort(T** left, T** right) { |
| 207 | SkTQSort(left, right, SkTPointerCompareLT<T>()); |
reed@google.com | 92fde90 | 2012-05-07 18:10:15 +0000 | [diff] [blame] | 208 | } |
| 209 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 210 | #endif |