Revert of Unwrap GrRedBlackTree unit test and use REPORTER_ASSERT(). (https://codereview.chromium.org/147713002/)

Reason for revert:
broke http://108.170.217.252:10115/builders/Build-Mac10.8-Clang-x86_64-Release/builds/2908/steps/Retry_BuildTests/logs/stdio and other builders:

GrRedBlackTreeTest.cpp:24:36: error: use of undeclared identifier 'xi'


Original issue's description:
> Unwrap GrRedBlackTree unit test and use REPORTER_ASSERT().
>
> This fixes the mtklein's TODO in GrUnitTests.cpp.
>
> BUG=None
> TEST=out/Debug/tests
> R=mtklein@google.com, robertphillips@google.com
>
> Committed: https://code.google.com/p/skia/source/detail?r=13208

R=mtklein@google.com, robertphillips@google.com, reed@google.com, tfarina@chromium.org
TBR=mtklein@google.com, reed@google.com, robertphillips@google.com, tfarina@chromium.org
NOTREECHECKS=true
NOTRY=true
BUG=None

Author: epoger@google.com

Review URL: https://codereview.chromium.org/148653002

git-svn-id: http://skia.googlecode.com/svn/trunk@13209 2bbb7eff-a529-9590-31e7-b0007b416f81

1 files changed, 171 insertions, 1 deletions

diff --git a/src/gpu/GrRedBlackTree.h b/src/gpu/GrRedBlackTree.h
index 41a3dfb61e..1b2195c4f7 100644
--- a/src/gpu/GrRedBlackTree.h
+++ b/src/gpu/GrRedBlackTree.h
@@ -8,7 +8,6 @@
 #ifndef GrRedBlackTree_DEFINED
 #define GrRedBlackTree_DEFINED
 
-#include "GrConfig.h"
 #include "SkTypes.h"
 
 template <typename T>
@@ -942,4 +941,175 @@ bool GrRedBlackTree<T,C>::validateChildRelations(const Node* n,
 }
 #endif
 
+#include "SkRandom.h"
+
+template <typename T, typename C>
+void GrRedBlackTree<T,C>::UnitTest() {
+    GrRedBlackTree<int> tree;
+
+    SkRandom r;
+
+    int count[100] = {0};
+    // add 10K ints
+    for (int i = 0; i < 10000; ++i) {
+        int x = r.nextU()%100;
+        SkDEBUGCODE(Iter xi = ) tree.insert(x);
+        SkASSERT(*xi == x);
+        ++count[x];
+    }
+
+    tree.insert(0);
+    ++count[0];
+    tree.insert(99);
+    ++count[99];
+    SkASSERT(*tree.begin() == 0);
+    SkASSERT(*tree.last() == 99);
+    SkASSERT(--(++tree.begin()) == tree.begin());
+    SkASSERT(--tree.end() == tree.last());
+    SkASSERT(tree.count() == 10002);
+
+    int c = 0;
+    // check that we iterate through the correct number of
+    // elements and they are properly sorted.
+    for (Iter a = tree.begin(); tree.end() != a; ++a) {
+        Iter b = a;
+        ++b;
+        ++c;
+        SkASSERT(b == tree.end() || *a <= *b);
+    }
+    SkASSERT(c == tree.count());
+
+    // check that the tree reports the correct number of each int
+    // and that we can iterate through them correctly both forward
+    // and backward.
+    for (int i = 0; i < 100; ++i) {
+        int c;
+        c = tree.countOf(i);
+        SkASSERT(c == count[i]);
+        c = 0;
+        Iter iter = tree.findFirst(i);
+        while (iter != tree.end() && *iter == i) {
+            ++c;
+            ++iter;
+        }
+        SkASSERT(count[i] == c);
+        c = 0;
+        iter = tree.findLast(i);
+        if (iter != tree.end()) {
+            do {
+                if (*iter == i) {
+                    ++c;
+                } else {
+                    break;
+                }
+                if (iter != tree.begin()) {
+                    --iter;
+                } else {
+                    break;
+                }
+            } while (true);
+        }
+        SkASSERT(c == count[i]);
+    }
+    // remove all the ints between 25 and 74. Randomly chose to remove
+    // the first, last, or any entry for each.
+    for (int i = 25; i < 75; ++i) {
+        while (0 != tree.countOf(i)) {
+            --count[i];
+            int x = r.nextU() % 3;
+            Iter iter;
+            switch (x) {
+            case 0:
+                iter = tree.findFirst(i);
+                break;
+            case 1:
+                iter = tree.findLast(i);
+                break;
+            case 2:
+            default:
+                iter = tree.find(i);
+                break;
+            }
+            tree.remove(iter);
+        }
+        SkASSERT(0 == count[i]);
+        SkASSERT(tree.findFirst(i) == tree.end());
+        SkASSERT(tree.findLast(i) == tree.end());
+        SkASSERT(tree.find(i) == tree.end());
+    }
+    // remove all of the 0 entries. (tests removing begin())
+    SkASSERT(*tree.begin() == 0);
+    SkASSERT(*(--tree.end()) == 99);
+    while (0 != tree.countOf(0)) {
+        --count[0];
+        tree.remove(tree.find(0));
+    }
+    SkASSERT(0 == count[0]);
+    SkASSERT(tree.findFirst(0) == tree.end());
+    SkASSERT(tree.findLast(0) == tree.end());
+    SkASSERT(tree.find(0) == tree.end());
+    SkASSERT(0 < *tree.begin());
+
+    // remove all the 99 entries (tests removing last()).
+    while (0 != tree.countOf(99)) {
+        --count[99];
+        tree.remove(tree.find(99));
+    }
+    SkASSERT(0 == count[99]);
+    SkASSERT(tree.findFirst(99) == tree.end());
+    SkASSERT(tree.findLast(99) == tree.end());
+    SkASSERT(tree.find(99) == tree.end());
+    SkASSERT(99 > *(--tree.end()));
+    SkASSERT(tree.last() == --tree.end());
+
+    // Make sure iteration still goes through correct number of entries
+    // and is still sorted correctly.
+    c = 0;
+    for (Iter a = tree.begin(); tree.end() != a; ++a) {
+        Iter b = a;
+        ++b;
+        ++c;
+        SkASSERT(b == tree.end() || *a <= *b);
+    }
+    SkASSERT(c == tree.count());
+
+    // repeat check that correct number of each entry is in the tree
+    // and iterates correctly both forward and backward.
+    for (int i = 0; i < 100; ++i) {
+        SkASSERT(tree.countOf(i) == count[i]);
+        int c = 0;
+        Iter iter = tree.findFirst(i);
+        while (iter != tree.end() && *iter == i) {
+            ++c;
+            ++iter;
+        }
+        SkASSERT(count[i] == c);
+        c = 0;
+        iter = tree.findLast(i);
+        if (iter != tree.end()) {
+            do {
+                if (*iter == i) {
+                    ++c;
+                } else {
+                    break;
+                }
+                if (iter != tree.begin()) {
+                    --iter;
+                } else {
+                    break;
+                }
+            } while (true);
+        }
+        SkASSERT(count[i] == c);
+    }
+
+    // remove all entries
+    while (!tree.empty()) {
+        tree.remove(tree.begin());
+    }
+
+    // test reset on empty tree.
+    tree.reset();
+}
+
 #endif