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 12template <typename T> 13static 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 29template <typename T> 30void 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 41template <typename T> 42static 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 58template <typename T> 59void 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 70template <typename S, typename T> 71static 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 88template <typename S, typename T> 89void 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