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'. */ 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 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 */ 42 template <typename T, typename C> 43 void 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 */ 76 template <typename T, typename C> 77 void 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 */ 102 template <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. */ 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; 130 } 131 } 132 133 /////////////////////////////////////////////////////////////////////////////// 134 135 template <typename T, typename C> 136 static 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 */ 163 template <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 */ 191 template <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. */ 201 template <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. */ 206 template <typename T> void SkTQSort(T** left, T** right) { 207 SkTQSort(left, right, SkTPointerCompareLT<T>()); 208 } 209 210 #endif 211
