Index: tests/GrRedBlackTreeTest.cpp |
diff --git a/tests/GrRedBlackTreeTest.cpp b/tests/GrRedBlackTreeTest.cpp |
deleted file mode 100644 |
index 44effd4de8645490ecd1fee97775bd61580cad0d..0000000000000000000000000000000000000000 |
--- a/tests/GrRedBlackTreeTest.cpp |
+++ /dev/null |
@@ -1,180 +0,0 @@ |
-/* |
- * Copyright 2014 Google Inc. |
- * |
- * Use of this source code is governed by a BSD-style license that can be |
- * found in the LICENSE file. |
- */ |
- |
-#include "GrRedBlackTree.h" |
-#include "SkRandom.h" |
-#include "Test.h" |
- |
-typedef GrRedBlackTree<int> Tree; |
- |
-DEF_TEST(GrRedBlackTreeTest, reporter) { |
- Tree tree; |
- |
- SkRandom r; |
- |
- int count[100] = {0}; |
- // add 10K ints |
- for (int i = 0; i < 10000; ++i) { |
- int x = r.nextU()%100; |
- SkDEBUGCODE(Tree::Iter xi = ) tree.insert(x); |
- REPORTER_ASSERT(reporter, *xi == x); |
- ++count[x]; |
- } |
- |
- tree.insert(0); |
- ++count[0]; |
- tree.insert(99); |
- ++count[99]; |
- REPORTER_ASSERT(reporter, *tree.begin() == 0); |
- REPORTER_ASSERT(reporter, *tree.last() == 99); |
- REPORTER_ASSERT(reporter, --(++tree.begin()) == tree.begin()); |
- REPORTER_ASSERT(reporter, --tree.end() == tree.last()); |
- REPORTER_ASSERT(reporter, tree.count() == 10002); |
- |
- int c = 0; |
- // check that we iterate through the correct number of |
- // elements and they are properly sorted. |
- for (Tree::Iter a = tree.begin(); tree.end() != a; ++a) { |
- Tree::Iter b = a; |
- ++b; |
- ++c; |
- REPORTER_ASSERT(reporter, b == tree.end() || *a <= *b); |
- } |
- REPORTER_ASSERT(reporter, 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); |
- REPORTER_ASSERT(reporter, c == count[i]); |
- c = 0; |
- Tree::Iter iter = tree.findFirst(i); |
- while (iter != tree.end() && *iter == i) { |
- ++c; |
- ++iter; |
- } |
- REPORTER_ASSERT(reporter, 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); |
- } |
- REPORTER_ASSERT(reporter, 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; |
- Tree::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); |
- } |
- REPORTER_ASSERT(reporter, 0 == count[i]); |
- REPORTER_ASSERT(reporter, tree.findFirst(i) == tree.end()); |
- REPORTER_ASSERT(reporter, tree.findLast(i) == tree.end()); |
- REPORTER_ASSERT(reporter, tree.find(i) == tree.end()); |
- } |
- // remove all of the 0 entries. (tests removing begin()) |
- REPORTER_ASSERT(reporter, *tree.begin() == 0); |
- REPORTER_ASSERT(reporter, *(--tree.end()) == 99); |
- while (0 != tree.countOf(0)) { |
- --count[0]; |
- tree.remove(tree.find(0)); |
- } |
- REPORTER_ASSERT(reporter, 0 == count[0]); |
- REPORTER_ASSERT(reporter, tree.findFirst(0) == tree.end()); |
- REPORTER_ASSERT(reporter, tree.findLast(0) == tree.end()); |
- REPORTER_ASSERT(reporter, tree.find(0) == tree.end()); |
- REPORTER_ASSERT(reporter, 0 < *tree.begin()); |
- |
- // remove all the 99 entries (tests removing last()). |
- while (0 != tree.countOf(99)) { |
- --count[99]; |
- tree.remove(tree.find(99)); |
- } |
- REPORTER_ASSERT(reporter, 0 == count[99]); |
- REPORTER_ASSERT(reporter, tree.findFirst(99) == tree.end()); |
- REPORTER_ASSERT(reporter, tree.findLast(99) == tree.end()); |
- REPORTER_ASSERT(reporter, tree.find(99) == tree.end()); |
- REPORTER_ASSERT(reporter, 99 > *(--tree.end())); |
- REPORTER_ASSERT(reporter, tree.last() == --tree.end()); |
- |
- // Make sure iteration still goes through correct number of entries |
- // and is still sorted correctly. |
- c = 0; |
- for (Tree::Iter a = tree.begin(); tree.end() != a; ++a) { |
- Tree::Iter b = a; |
- ++b; |
- ++c; |
- REPORTER_ASSERT(reporter, b == tree.end() || *a <= *b); |
- } |
- REPORTER_ASSERT(reporter, 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) { |
- REPORTER_ASSERT(reporter, tree.countOf(i) == count[i]); |
- int c = 0; |
- Tree::Iter iter = tree.findFirst(i); |
- while (iter != tree.end() && *iter == i) { |
- ++c; |
- ++iter; |
- } |
- REPORTER_ASSERT(reporter, 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); |
- } |
- REPORTER_ASSERT(reporter, count[i] == c); |
- } |
- |
- // remove all entries |
- while (!tree.empty()) { |
- tree.remove(tree.begin()); |
- } |
- |
- // test reset on empty tree. |
- tree.reset(); |
-} |