180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/* 380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Copyright 2006 The Android Open Source Project 480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * 580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * Use of this source code is governed by a BSD-style license that can be 680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru * found in the LICENSE file. 780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru */ 880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#ifndef SkTSort_DEFINED 1180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#define SkTSort_DEFINED 1280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 1380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#include "SkTypes.h" 14d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger#include "SkMath.h" 1580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 16d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger/* A comparison functor which performs the comparison 'a < b'. */ 17d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenbergertemplate <typename T> struct SkTCompareLT { 18d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger bool operator()(const T a, const T b) const { return a < b; } 19d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger}; 20d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger 21d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger/* A comparison functor which performs the comparison '*a < *b'. */ 22d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenbergertemplate <typename T> struct SkTPointerCompareLT { 23d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger bool operator()(const T* a, const T* b) const { return *a < *b; } 24d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger}; 25d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger 26d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger/////////////////////////////////////////////////////////////////////////////// 27d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger 28d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger/* Sifts a broken heap. The input array is a heap from root to bottom 29d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * except that the root entry may be out of place. 30d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * 31d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * Sinks a hole from array[root] to leaf and then sifts the original array[root] element 32d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * from the leaf level up. 33d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * 34d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * This version does extra work, in that it copies child to parent on the way down, 35d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * then copies parent to child on the way back up. When copies are inexpensive, 36d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * this is an optimization as this sift variant should only be used when 37d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * the potentially out of place root entry value is expected to be small. 38d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * 39d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * @param root the one based index into array of the out-of-place root of the heap. 40d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * @param bottom the one based index in the array of the last entry in the heap. 41d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger */ 42d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenbergertemplate <typename T, typename C> 43d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenbergervoid SkTHeapSort_SiftUp(T array[], size_t root, size_t bottom, C lessThan) { 44d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger T x = array[root-1]; 45d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger size_t start = root; 46d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger size_t j = root << 1; 47d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger while (j <= bottom) { 48d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger if (j < bottom && lessThan(array[j-1], array[j])) { 49d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger ++j; 50d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger } 51d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger array[root-1] = array[j-1]; 52d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger root = j; 53d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger j = root << 1; 54d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger } 55d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger j = root >> 1; 56d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger while (j >= start) { 57d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger if (lessThan(array[j-1], x)) { 58d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger array[root-1] = array[j-1]; 59d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger root = j; 60d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger j = root >> 1; 61d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger } else { 62d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger break; 63d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger } 64d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger } 65d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger array[root-1] = x; 66d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger} 67d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger 68d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger/* Sifts a broken heap. The input array is a heap from root to bottom 69d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * except that the root entry may be out of place. 70d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * 71d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * Sifts the array[root] element from the root down. 72d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * 73d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * @param root the one based index into array of the out-of-place root of the heap. 74d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * @param bottom the one based index in the array of the last entry in the heap. 75d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger */ 76d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenbergertemplate <typename T, typename C> 77d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenbergervoid SkTHeapSort_SiftDown(T array[], size_t root, size_t bottom, C lessThan) { 78d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger T x = array[root-1]; 79d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger size_t child = root << 1; 80d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger while (child <= bottom) { 81d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger if (child < bottom && lessThan(array[child-1], array[child])) { 82d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger ++child; 8380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 84d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger if (lessThan(x, array[child-1])) { 85d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger array[root-1] = array[child-1]; 8680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru root = child; 87d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger child = root << 1; 8880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } else { 8980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru break; 9080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 9180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 92d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger array[root-1] = x; 9380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 9480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 95096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger/** Sorts the array of size count using comparator lessThan using a Heap Sort algorithm. Be sure to 96096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger * specialize SkTSwap if T has an efficient swap operation. 97d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * 98d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * @param array the array to be sorted. 99d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * @param count the number of elements in the array. 100d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * @param lessThan a functor with bool operator()(T a, T b) which returns true if a comes before b. 101d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger */ 102d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenbergertemplate <typename T, typename C> void SkTHeapSort(T array[], size_t count, C lessThan) { 103d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger for (size_t i = count >> 1; i > 0; --i) { 104d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger SkTHeapSort_SiftDown(array, i, count, lessThan); 10580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 106d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger 107d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger for (size_t i = count - 1; i > 0; --i) { 10880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkTSwap<T>(array[0], array[i]); 109d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger SkTHeapSort_SiftUp(array, 1, i, lessThan); 11080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 11180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 11280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 113d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger/** Sorts the array of size count using comparator '<' using a Heap Sort algorithm. */ 114d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenbergertemplate <typename T> void SkTHeapSort(T array[], size_t count) { 115d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger SkTHeapSort(array, count, SkTCompareLT<T>()); 116d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger} 117d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger 11880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru/////////////////////////////////////////////////////////////////////////////// 11980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 120d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger/** Sorts the array of size count using comparator lessThan using an Insertion Sort algorithm. */ 121d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenbergertemplate <typename T, typename C> static void SkTInsertionSort(T* left, T* right, C lessThan) { 122d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger for (T* next = left + 1; next <= right; ++next) { 123d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger T insert = *next; 124d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger T* hole = next; 125d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger while (left < hole && lessThan(insert, *(hole - 1))) { 126d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger *hole = *(hole - 1); 127d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger --hole; 12880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 129d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger *hole = insert; 13080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 13180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 13280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 133d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger/////////////////////////////////////////////////////////////////////////////// 13480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 135d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenbergertemplate <typename T, typename C> 136d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenbergerstatic T* SkTQSort_Partition(T* left, T* right, T* pivot, C lessThan) { 13780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru T pivotValue = *pivot; 13880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkTSwap(*pivot, *right); 13980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru T* newPivot = left; 14080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru while (left < right) { 141d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger if (lessThan(*left, pivotValue)) { 14280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkTSwap(*left, *newPivot); 14380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru newPivot += 1; 14480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 14580bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru left += 1; 14680bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 14780bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru SkTSwap(*newPivot, *right); 14880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return newPivot; 14980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 15080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 151d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger/* Intro Sort is a modified Quick Sort. 152d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * When the region to be sorted is a small constant size it uses Insertion Sort. 153d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * When depth becomes zero, it switches over to Heap Sort. 154096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger * This implementation recurses on the left region after pivoting and loops on the right, 155096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger * we already limit the stack depth by switching to heap sort, 156096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger * and cache locality on the data appears more important than saving a few stack frames. 157096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger * 158096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger * @param depth at this recursion depth, switch to Heap Sort. 159096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger * @param left the beginning of the region to be sorted. 160096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger * @param right the end of the region to be sorted (inclusive). 161096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger * @param lessThan a functor with bool operator()(T a, T b) which returns true if a comes before b. 162d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger */ 163d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenbergertemplate <typename T, typename C> void SkTIntroSort(int depth, T* left, T* right, C lessThan) { 164096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger while (true) { 165096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger if (right - left < 32) { 166096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger SkTInsertionSort(left, right, lessThan); 167096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger return; 168096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger } 169096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger 170d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger if (depth == 0) { 171d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger SkTHeapSort<T>(left, right - left + 1, lessThan); 172d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger return; 173d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger } 174d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger --depth; 175d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger 176d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger T* pivot = left + ((right - left) >> 1); 177d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger pivot = SkTQSort_Partition(left, right, pivot, lessThan); 178d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger 179096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger SkTIntroSort(depth, left, pivot - 1, lessThan); 180096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger left = pivot + 1; 18180bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 18280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 18380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 184096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger/** Sorts the region from left to right using comparator lessThan using a Quick Sort algorithm. Be 185096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger * sure to specialize SkTSwap if T has an efficient swap operation. 186d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * 187d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * @param left the beginning of the region to be sorted. 188d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * @param right the end of the region to be sorted (inclusive). 189d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger * @param lessThan a functor with bool operator()(T a, T b) which returns true if a comes before b. 190d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger */ 191d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenbergertemplate <typename T, typename C> void SkTQSort(T* left, T* right, C lessThan) { 19280bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru if (left >= right) { 19380bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru return; 19480bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru } 195096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger // Limit Intro Sort recursion depth to no more than 2 * ceil(log2(n)). 196096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger int depth = 2 * SkNextLog2(SkToU32(right - left)); 197096defe64d408e54474fe19f418c95bf1a554fc7Derek Sollenberger SkTIntroSort(depth, left, right, lessThan); 198d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger} 199d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger 200d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger/** Sorts the region from left to right using comparator '<' using a Quick Sort algorithm. */ 201d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenbergertemplate <typename T> void SkTQSort(T* left, T* right) { 202d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger SkTQSort(left, right, SkTCompareLT<T>()); 203d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger} 204d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger 205d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger/** Sorts the region from left to right using comparator '* < *' using a Quick Sort algorithm. */ 206d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenbergertemplate <typename T> void SkTQSort(T** left, T** right) { 207d686ac77c2c485c4a3302eda9c1de597a6f8c568Derek Sollenberger SkTQSort(left, right, SkTPointerCompareLT<T>()); 20880bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru} 20980bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru 21080bacfeb4bda06541e8695bd502229727bccfeaJean-Baptiste Queru#endif 211