epoger@google.com | ec3ed6a | 2011-07-28 14:26:00 +0000 | [diff] [blame] | 1 | |
| 2 | /* |
| 3 | * Copyright 2006 The Android Open Source Project |
| 4 | * |
| 5 | * Use of this source code is governed by a BSD-style license that can be |
| 6 | * found in the LICENSE file. |
| 7 | */ |
| 8 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 9 | |
| 10 | #ifndef SkTSort_DEFINED |
| 11 | #define SkTSort_DEFINED |
| 12 | |
| 13 | #include "SkTypes.h" |
| 14 | |
| 15 | template <typename T> |
reed@android.com | eff416b | 2009-03-18 03:08:15 +0000 | [diff] [blame] | 16 | void SkTHeapSort_SiftDown(T array[], int root, int bottom) { |
| 17 | while (root*2 + 1 <= bottom) { |
| 18 | int child = root * 2 + 1; |
| 19 | if (child+1 <= bottom && array[child] < array[child+1]) { |
| 20 | child += 1; |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 21 | } |
reed@android.com | eff416b | 2009-03-18 03:08:15 +0000 | [diff] [blame] | 22 | if (array[root] < array[child]) { |
| 23 | SkTSwap<T>(array[root], array[child]); |
| 24 | root = child; |
| 25 | } else { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 26 | break; |
reed@android.com | eff416b | 2009-03-18 03:08:15 +0000 | [diff] [blame] | 27 | } |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 28 | } |
| 29 | } |
| 30 | |
reed@android.com | eff416b | 2009-03-18 03:08:15 +0000 | [diff] [blame] | 31 | template <typename T> void SkTHeapSort(T array[], int count) { |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 32 | int i; |
reed@android.com | eff416b | 2009-03-18 03:08:15 +0000 | [diff] [blame] | 33 | for (i = count/2 - 1; i >= 0; --i) { |
| 34 | SkTHeapSort_SiftDown<T>(array, i, count-1); |
| 35 | } |
| 36 | for (i = count - 1; i > 0; --i) { |
| 37 | SkTSwap<T>(array[0], array[i]); |
| 38 | SkTHeapSort_SiftDown<T>(array, 0, i-1); |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 39 | } |
| 40 | } |
| 41 | |
reed@google.com | 92fde90 | 2012-05-07 18:10:15 +0000 | [diff] [blame] | 42 | /////////////////////////////////////////////////////////////////////////////// |
| 43 | |
| 44 | template <typename T> |
| 45 | static T** SkTQSort_Partition(T** left, T** right, T** pivot) { |
| 46 | T* pivotValue = *pivot; |
| 47 | SkTSwap(*pivot, *right); |
| 48 | T** newPivot = left; |
| 49 | while (left < right) { |
| 50 | if (**left < *pivotValue) { |
| 51 | SkTSwap(*left, *newPivot); |
| 52 | newPivot += 1; |
| 53 | } |
| 54 | left += 1; |
| 55 | } |
| 56 | SkTSwap(*newPivot, *right); |
| 57 | return newPivot; |
| 58 | } |
| 59 | |
| 60 | template <typename T> void SkTQSort(T** left, T** right) { |
| 61 | if (left >= right) { |
| 62 | return; |
| 63 | } |
| 64 | T** pivot = left + (right - left >> 1); |
| 65 | pivot = SkTQSort_Partition(left, right, pivot); |
| 66 | SkTQSort(left, pivot - 1); |
| 67 | SkTQSort(pivot + 1, right); |
| 68 | } |
| 69 | |
| 70 | template <typename S, typename T> |
| 71 | static T* SkTQSort_Partition(S& context, T* left, T* right, T* pivot, |
| 72 | bool (*lessThan)(S&, const T, const T)) { |
| 73 | T pivotValue = *pivot; |
| 74 | SkTSwap(*pivot, *right); |
| 75 | T* newPivot = left; |
| 76 | while (left < right) { |
| 77 | if (lessThan(context, *left, pivotValue)) { |
| 78 | SkTSwap(*left, *newPivot); |
| 79 | newPivot += 1; |
| 80 | } |
| 81 | left += 1; |
| 82 | } |
| 83 | SkTSwap(*newPivot, *right); |
| 84 | return newPivot; |
| 85 | } |
| 86 | |
| 87 | template <typename S, typename T> |
| 88 | void SkQSort(S& context, T* left, T* right, |
| 89 | bool (*lessThan)(S& , const T, const T)) { |
| 90 | if (left >= right) { |
| 91 | return; |
| 92 | } |
| 93 | T* pivot = left + (right - left >> 1); |
| 94 | pivot = SkTQSort_Partition(context, left, right, pivot, lessThan); |
| 95 | SkQSort(context, left, pivot - 1, lessThan); |
| 96 | SkQSort(context, pivot + 1, right, lessThan); |
| 97 | } |
| 98 | |
reed@android.com | 8a1c16f | 2008-12-17 15:59:43 +0000 | [diff] [blame] | 99 | #endif |