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 8 9 #ifndef SkTSort_DEFINED 10 #define SkTSort_DEFINED 11 12 #include "SkTypes.h" 13 #include "SkMathPriv.h" 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 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 */ 41 template <typename T, typename C> 42 void SkTHeapSort_SiftUp(T array[], size_t root, size_t bottom, C lessThan) { 43 T x = array[root-1]; 44 size_t start = root; 45 size_t j = root << 1; 46 while (j <= bottom) { 47 if (j < bottom && lessThan(array[j-1], array[j])) { 48 ++j; 49 } 50 array[root-1] = array[j-1]; 51 root = j; 52 j = root << 1; 53 } 54 j = root >> 1; 55 while (j >= start) { 56 if (lessThan(array[j-1], x)) { 57 array[root-1] = array[j-1]; 58 root = j; 59 j = root >> 1; 60 } else { 61 break; 62 } 63 } 64 array[root-1] = x; 65 } 66 67 /* Sifts a broken heap. The input array is a heap from root to bottom 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 */ 75 template <typename T, typename C> 76 void SkTHeapSort_SiftDown(T array[], size_t root, size_t bottom, C lessThan) { 77 T x = array[root-1]; 78 size_t child = root << 1; 79 while (child <= bottom) { 80 if (child < bottom && lessThan(array[child-1], array[child])) { 81 ++child; 82 } 83 if (lessThan(x, array[child-1])) { 84 array[root-1] = array[child-1]; 85 root = child; 86 child = root << 1; 87 } else { 88 break; 89 } 90 } 91 array[root-1] = x; 92 } 93 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. 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) { 102 for (size_t i = count >> 1; i > 0; --i) { 103 SkTHeapSort_SiftDown(array, i, count, lessThan); 104 } 105 106 for (size_t i = count - 1; i > 0; --i) { 107 SkTSwap<T>(array[0], array[i]); 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) { 122 if (!lessThan(*next, *(next - 1))) { 123 continue; 124 } 125 T insert = std::move(*next); 126 T* hole = next; 127 do { 128 *hole = std::move(*(hole - 1)); 129 --hole; 130 } while (left < hole && lessThan(insert, *(hole - 1))); 131 *hole = std::move(insert); 132 } 133 } 134 135 /////////////////////////////////////////////////////////////////////////////// 136 137 template <typename T, typename C> 138 static T* SkTQSort_Partition(T* left, T* right, T* pivot, C lessThan) { 139 T pivotValue = *pivot; 140 SkTSwap(*pivot, *right); 141 T* newPivot = left; 142 while (left < right) { 143 if (lessThan(*left, pivotValue)) { 144 SkTSwap(*left, *newPivot); 145 newPivot += 1; 146 } 147 left += 1; 148 } 149 SkTSwap(*newPivot, *right); 150 return newPivot; 151 } 152 153 /* Intro Sort is a modified Quick Sort. 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. 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. 164 */ 165 template <typename T, typename C> void SkTIntroSort(int depth, T* left, T* right, C lessThan) { 166 while (true) { 167 if (right - left < 32) { 168 SkTInsertionSort(left, right, lessThan); 169 return; 170 } 171 172 if (depth == 0) { 173 SkTHeapSort<T>(left, right - left + 1, lessThan); 174 return; 175 } 176 --depth; 177 178 T* pivot = left + ((right - left) >> 1); 179 pivot = SkTQSort_Partition(left, right, pivot, lessThan); 180 181 SkTIntroSort(depth, left, pivot - 1, lessThan); 182 left = pivot + 1; 183 } 184 } 185 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. 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) { 194 if (left >= right) { 195 return; 196 } 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); 200 } 201 202 /** Sorts the region from left to right using comparator '<' using a Quick Sort algorithm. */ 203 template <typename T> void SkTQSort(T* left, T* right) { 204 SkTQSort(left, right, SkTCompareLT<T>()); 205 } 206 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>()); 210 } 211 212 #endif 213