1 /* 2 * Copyright 2012 Google Inc. 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 TSearch_DEFINED 8 #define TSearch_DEFINED 9 10 // FIXME: Move this templated version into SKTSearch.h 11 12 template <typename T> 13 static T* QSort_Partition(T* left, T* right, T* pivot) 14 { 15 T pivotValue = *pivot; 16 SkTSwap(*pivot, *right); 17 T* newPivot = left; 18 while (left < right) { 19 if (*left < pivotValue) { 20 SkTSwap(*left, *newPivot); 21 newPivot += 1; 22 } 23 left += 1; 24 } 25 SkTSwap(*newPivot, *right); 26 return newPivot; 27 } 28 29 template <typename T> 30 void QSort(T* left, T* right) 31 { 32 if (left >= right) { 33 return; 34 } 35 T* pivot = left + (right - left >> 1); 36 pivot = QSort_Partition(left, right, pivot); 37 QSort(left, pivot - 1); 38 QSort(pivot + 1, right); 39 } 40 41 template <typename T> 42 static T** QSort_Partition(T** left, T** right, T** pivot) 43 { 44 T* pivotValue = *pivot; 45 SkTSwap(*pivot, *right); 46 T** newPivot = left; 47 while (left < right) { 48 if (**left < *pivotValue) { 49 SkTSwap(*left, *newPivot); 50 newPivot += 1; 51 } 52 left += 1; 53 } 54 SkTSwap(*newPivot, *right); 55 return newPivot; 56 } 57 58 template <typename T> 59 void QSort(T** left, T** right) 60 { 61 if (left >= right) { 62 return; 63 } 64 T** pivot = left + (right - left >> 1); 65 pivot = QSort_Partition(left, right, pivot); 66 QSort(left, pivot - 1); 67 QSort(pivot + 1, right); 68 } 69 70 template <typename S, typename T> 71 static T* QSort_Partition(S& context, T* left, T* right, T* pivot, 72 bool (*lessThan)(S&, const T, const T)) 73 { 74 T pivotValue = *pivot; 75 SkTSwap(*pivot, *right); 76 T* newPivot = left; 77 while (left < right) { 78 if (lessThan(context, *left, pivotValue)) { 79 SkTSwap(*left, *newPivot); 80 newPivot += 1; 81 } 82 left += 1; 83 } 84 SkTSwap(*newPivot, *right); 85 return newPivot; 86 } 87 88 template <typename S, typename T> 89 void QSort(S& context, T* left, T* right, 90 bool (*lessThan)(S& , const T, const T)) 91 { 92 if (left >= right) { 93 return; 94 } 95 T* pivot = left + (right - left >> 1); 96 pivot = QSort_Partition(context, left, right, pivot, lessThan); 97 QSort(context, left, pivot - 1, lessThan); 98 QSort(context, pivot + 1, right, lessThan); 99 } 100 101 #endif 102