SkTSort.h 7.4 KB

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