| /* libs/graphics/sgl/SkTSort.h |
| ** |
| ** Copyright 2006, The Android Open Source Project |
| ** |
| ** Licensed under the Apache License, Version 2.0 (the "License"); |
| ** you may not use this file except in compliance with the License. |
| ** You may obtain a copy of the License at |
| ** |
| ** http://www.apache.org/licenses/LICENSE-2.0 |
| ** |
| ** Unless required by applicable law or agreed to in writing, software |
| ** distributed under the License is distributed on an "AS IS" BASIS, |
| ** WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| ** See the License for the specific language governing permissions and |
| ** limitations under the License. |
| */ |
| |
| #ifndef SkTSort_DEFINED |
| #define SkTSort_DEFINED |
| |
| #include "SkTypes.h" |
| |
| template <typename T> |
| void SkTHeapSort_SiftDown(T array[], int root, int bottom) |
| { |
| int root2 = root << 1; |
| |
| while (root2 <= bottom) |
| { |
| int maxChild; |
| |
| if (root2 == bottom) |
| maxChild = root2; |
| else if (array[root2] > array[root2 + 1]) |
| maxChild = root2; |
| else |
| maxChild = root2 + 1; |
| |
| if (array[root] < array[maxChild]) |
| { |
| SkTSwap<T>(array[root], array[maxChild]); |
| root = maxChild; |
| root2 = root << 1; |
| } |
| else |
| break; |
| } |
| } |
| |
| template <typename T> |
| void SkTHeapSort(T array[], int count) |
| { |
| int i; |
| |
| for (i = count/2 - 1; i >= 0; --i) |
| SkTHeapSort_SiftDown<T>(array, i, count); |
| |
| for (i = count - 2; i >= 0; --i) |
| { |
| SkTSwap<T>(array[0], array[i + 1]); |
| SkTHeapSort_SiftDown<T>(array, 0, i); |
| } |
| } |
| |
| #endif |