From eff416bec1bc08685af1dc4265b9d860e43b8240 Mon Sep 17 00:00:00 2001
From: "reed@android.com"
 <reed@android.com@2bbb7eff-a529-9590-31e7-b0007b416f81>
Date: Wed, 18 Mar 2009 03:08:15 +0000
Subject: fix heapsort

git-svn-id: http://skia.googlecode.com/svn/trunk@126 2bbb7eff-a529-9590-31e7-b0007b416f81
---
 tests/SortTest.cpp | 38 +++++++++++++++++++++++++++++---------
 1 file changed, 29 insertions(+), 9 deletions(-)

(limited to 'tests/SortTest.cpp')

diff --git a/tests/SortTest.cpp b/tests/SortTest.cpp
index 6d287c5004..2ca5553c2e 100644
--- a/tests/SortTest.cpp
+++ b/tests/SortTest.cpp
@@ -1,6 +1,7 @@
 #include "Test.h"
 #include "SkRandom.h"
 #include "SkTSearch.h"
+#include "SkTSort.h"
 
 extern "C" {
     int compare_int(const void* a, const void* b) {
@@ -8,19 +9,38 @@ extern "C" {
     }
 }
 
+static void rand_array(SkRandom& rand, int array[], int n) {
+    for (int j = 0; j < n; j++) {
+        array[j] = rand.nextS() & 0xFF;
+    }
+}
+
+static void check_sort(skiatest::Reporter* reporter, const char label[],
+                       const int array[], int n) {
+    for (int j = 1; j < n; j++) {
+        if (array[j-1] > array[j]) {
+            SkString str;
+           str.printf("%sSort [%d] failed %d %d", label, n,
+                      array[j-1], array[j]);
+            reporter->reportFailed(str);
+        }
+    }
+}
+
 static void TestSort(skiatest::Reporter* reporter) {
-    int         array[100];
+    int         array[500];
     SkRandom    rand;
 
-    for (int i = 0; i < 1000; i++) {
-        int j, count = rand.nextRangeU(1, SK_ARRAY_COUNT(array));
-        for (j = 0; j < count; j++) {
-            array[j] = rand.nextS() & 0xFF;
-        }
+    for (int i = 0; i < 10000; i++) {
+        int count = rand.nextRangeU(1, SK_ARRAY_COUNT(array));
+
+        rand_array(rand, array, count);
         SkQSort(array, count, sizeof(int), compare_int);
-        for (j = 1; j < count; j++) {
-            REPORTER_ASSERT(reporter, array[j-1] <= array[j]);
-        }
+        check_sort(reporter, "Quick", array, count);
+
+        rand_array(rand, array, count);
+        SkTHeapSort<int>(array, count);
+        check_sort(reporter, "Heap", array, count);
     }
 }
 
-- 
cgit v1.2.3