1 files changed, 65 insertions, 0 deletions
diff --git a/src/core/SkTSort.h b/src/core/SkTSort.h
new file mode 100644
index 0000000..fba49e2
--- /dev/null
+++ b/src/core/SkTSort.h
@@ -0,0 +1,65 @@
+/* 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