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