19e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com/* 29e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * Copyright 2012 Google Inc. 39e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * 49e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * Use of this source code is governed by a BSD-style license that can be 59e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com * found in the LICENSE file. 69e49fb63d355446b91d20ff78ad78b297e89a50dcaryclark@google.com */ 7d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#ifndef TSearch_DEFINED 8d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#define TSearch_DEFINED 9d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com 10c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com// FIXME: Move this templated version into SKTSearch.h 11c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 12c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comtemplate <typename T> 1373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comstatic T* QSort_Partition(T* left, T* right, T* pivot) 1473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com{ 1573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com T pivotValue = *pivot; 1673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com SkTSwap(*pivot, *right); 1773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com T* newPivot = left; 1873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com while (left < right) { 1973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (*left < pivotValue) { 2073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com SkTSwap(*left, *newPivot); 2173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com newPivot += 1; 2273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 2373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com left += 1; 2473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 2573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com SkTSwap(*newPivot, *right); 2673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return newPivot; 2773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 2873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 2973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comtemplate <typename T> 3073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comvoid QSort(T* left, T* right) 3173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com{ 3273ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com if (left >= right) { 3373ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com return; 3473ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com } 3573ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com T* pivot = left + (right - left >> 1); 3673ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com pivot = QSort_Partition(left, right, pivot); 3773ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com QSort(left, pivot - 1); 3873ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com QSort(pivot + 1, right); 3973ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com} 4073ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.com 4173ca6243b31e225e9fd5b75a96cbc82d62557de6caryclark@google.comtemplate <typename T> 42cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.comstatic T** QSort_Partition(T** left, T** right, T** pivot) 43c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com{ 44cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com T* pivotValue = *pivot; 45cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com SkTSwap(*pivot, *right); 46cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com T** newPivot = left; 47cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com while (left < right) { 48cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com if (**left < *pivotValue) { 49cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com SkTSwap(*left, *newPivot); 50cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com newPivot += 1; 51c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 52cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com left += 1; 53c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 54cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com SkTSwap(*newPivot, *right); 55cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com return newPivot; 56c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 57c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 58c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.comtemplate <typename T> 59cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.comvoid QSort(T** left, T** right) 60c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com{ 61cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com if (left >= right) { 62c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return; 63c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 64cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com T** pivot = left + (right - left >> 1); 65cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com pivot = QSort_Partition(left, right, pivot); 66cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com QSort(left, pivot - 1); 67cd4421df5012b75c792c6c8bf2c5ee0410921c15caryclark@google.com QSort(pivot + 1, right); 68c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 69c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 70f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comtemplate <typename S, typename T> 71cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.comstatic T* QSort_Partition(S& context, T* left, T* right, T* pivot, 72cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com bool (*lessThan)(S&, const T, const T)) 73c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com{ 74cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com T pivotValue = *pivot; 75cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkTSwap(*pivot, *right); 76cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com T* newPivot = left; 77cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com while (left < right) { 78cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (lessThan(context, *left, pivotValue)) { 79cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkTSwap(*left, *newPivot); 80cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com newPivot += 1; 81c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 82cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com left += 1; 83c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 84cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com SkTSwap(*newPivot, *right); 85cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com return newPivot; 86c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 87c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com 88f8b000d7ae32ac9bb67c8e33cae500cac7407d26caryclark@google.comtemplate <typename S, typename T> 89cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.comvoid QSort(S& context, T* left, T* right, 90cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com bool (*lessThan)(S& , const T, const T)) 91c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com{ 92cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com if (left >= right) { 93c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com return; 94c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com } 95cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com T* pivot = left + (right - left >> 1); 96cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com pivot = QSort_Partition(context, left, right, pivot, lessThan); 97cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com QSort(context, left, pivot - 1, lessThan); 98cef7e3fc4bc6223ab0e42ed754e2a09028479c0bcaryclark@google.com QSort(context, pivot + 1, right, lessThan); 99c682590538a27d73489bc91c098e000fdfb07ccfcaryclark@google.com} 100d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com 101d88e0894d0156f4d427b812fec69bfba3eec7a8dcaryclark@google.com#endif 102