| OLD | NEW |
| (Empty) |
| 1 /* libs/corecg/SkTSort.h | |
| 2 ** | |
| 3 ** Copyright 2006, The Android Open Source Project | |
| 4 ** | |
| 5 ** Licensed under the Apache License, Version 2.0 (the "License"); | |
| 6 ** you may not use this file except in compliance with the License. | |
| 7 ** You may obtain a copy of the License at | |
| 8 ** | |
| 9 ** http://www.apache.org/licenses/LICENSE-2.0 | |
| 10 ** | |
| 11 ** Unless required by applicable law or agreed to in writing, software | |
| 12 ** distributed under the License is distributed on an "AS IS" BASIS, | |
| 13 ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | |
| 14 ** See the License for the specific language governing permissions and | |
| 15 ** limitations under the License. | |
| 16 */ | |
| 17 | |
| 18 #ifndef SkTSort_DEFINED | |
| 19 #define SkTSort_DEFINED | |
| 20 | |
| 21 #include "SkTypes.h" | |
| 22 | |
| 23 template <typename T> | |
| 24 void SkTHeapSort_SiftDown(T array[], int root, int bottom) | |
| 25 { | |
| 26 int root2 = root << 1; | |
| 27 | |
| 28 while (root2 <= bottom) | |
| 29 { | |
| 30 int maxChild; | |
| 31 | |
| 32 if (root2 == bottom) | |
| 33 maxChild = root2; | |
| 34 else if (array[root2] > array[root2 + 1]) | |
| 35 maxChild = root2; | |
| 36 else | |
| 37 maxChild = root2 + 1; | |
| 38 | |
| 39 if (array[root] < array[maxChild]) | |
| 40 { | |
| 41 SkTSwap<T>(array[root], array[maxChild]); | |
| 42 root = maxChild; | |
| 43 root2 = root << 1; | |
| 44 } | |
| 45 else | |
| 46 break; | |
| 47 } | |
| 48 } | |
| 49 | |
| 50 template <typename T> | |
| 51 void SkTHeapSort(T array[], int count) | |
| 52 { | |
| 53 int i; | |
| 54 | |
| 55 for (i = count/2 - 1; i >= 0; --i) | |
| 56 SkTHeapSort_SiftDown<T>(array, i, count); | |
| 57 | |
| 58 for (i = count - 2; i >= 0; --i) | |
| 59 { | |
| 60 SkTSwap<T>(array[0], array[i + 1]); | |
| 61 SkTHeapSort_SiftDown<T>(array, 0, i); | |
| 62 } | |
| 63 } | |
| 64 | |
| 65 #endif | |
| OLD | NEW |