1 /* libs/graphics/sgl/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>
SkTHeapSort_SiftDown(T array[],int root,int bottom)24 void SkTHeapSort_SiftDown(T array[], int root, int bottom) {
25 while (root*2 + 1 <= bottom) {
26 int child = root * 2 + 1;
27 if (child+1 <= bottom && array[child] < array[child+1]) {
28 child += 1;
29 }
30 if (array[root] < array[child]) {
31 SkTSwap<T>(array[root], array[child]);
32 root = child;
33 } else {
34 break;
35 }
36 }
37 }
38
SkTHeapSort(T array[],int count)39 template <typename T> void SkTHeapSort(T array[], int count) {
40 int i;
41 for (i = count/2 - 1; i >= 0; --i) {
42 SkTHeapSort_SiftDown<T>(array, i, count-1);
43 }
44 for (i = count - 1; i > 0; --i) {
45 SkTSwap<T>(array[0], array[i]);
46 SkTHeapSort_SiftDown<T>(array, 0, i-1);
47 }
48 }
49
50 #endif
51