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 |