Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(170)

Side by Side Diff: tests/GrRedBlackTreeTest.cpp

Issue 148653002: Revert of Unwrap GrRedBlackTree unit test and use REPORTER_ASSERT(). (Closed) Base URL: https://skia.googlecode.com/svn/trunk
Patch Set: Created 6 years, 10 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « src/gpu/GrRedBlackTree.h ('k') | tests/GrUnitTests.cpp » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
1 /*
2 * Copyright 2014 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8 #include "GrRedBlackTree.h"
9 #include "SkRandom.h"
10 #include "Test.h"
11
12 typedef GrRedBlackTree<int> Tree;
13
14 DEF_TEST(GrRedBlackTreeTest, reporter) {
15 Tree tree;
16
17 SkRandom r;
18
19 int count[100] = {0};
20 // add 10K ints
21 for (int i = 0; i < 10000; ++i) {
22 int x = r.nextU()%100;
23 SkDEBUGCODE(Tree::Iter xi = ) tree.insert(x);
24 REPORTER_ASSERT(reporter, *xi == x);
25 ++count[x];
26 }
27
28 tree.insert(0);
29 ++count[0];
30 tree.insert(99);
31 ++count[99];
32 REPORTER_ASSERT(reporter, *tree.begin() == 0);
33 REPORTER_ASSERT(reporter, *tree.last() == 99);
34 REPORTER_ASSERT(reporter, --(++tree.begin()) == tree.begin());
35 REPORTER_ASSERT(reporter, --tree.end() == tree.last());
36 REPORTER_ASSERT(reporter, tree.count() == 10002);
37
38 int c = 0;
39 // check that we iterate through the correct number of
40 // elements and they are properly sorted.
41 for (Tree::Iter a = tree.begin(); tree.end() != a; ++a) {
42 Tree::Iter b = a;
43 ++b;
44 ++c;
45 REPORTER_ASSERT(reporter, b == tree.end() || *a <= *b);
46 }
47 REPORTER_ASSERT(reporter, c == tree.count());
48
49 // check that the tree reports the correct number of each int
50 // and that we can iterate through them correctly both forward
51 // and backward.
52 for (int i = 0; i < 100; ++i) {
53 int c;
54 c = tree.countOf(i);
55 REPORTER_ASSERT(reporter, c == count[i]);
56 c = 0;
57 Tree::Iter iter = tree.findFirst(i);
58 while (iter != tree.end() && *iter == i) {
59 ++c;
60 ++iter;
61 }
62 REPORTER_ASSERT(reporter, count[i] == c);
63 c = 0;
64 iter = tree.findLast(i);
65 if (iter != tree.end()) {
66 do {
67 if (*iter == i) {
68 ++c;
69 } else {
70 break;
71 }
72 if (iter != tree.begin()) {
73 --iter;
74 } else {
75 break;
76 }
77 } while (true);
78 }
79 REPORTER_ASSERT(reporter, c == count[i]);
80 }
81 // remove all the ints between 25 and 74. Randomly chose to remove
82 // the first, last, or any entry for each.
83 for (int i = 25; i < 75; ++i) {
84 while (0 != tree.countOf(i)) {
85 --count[i];
86 int x = r.nextU() % 3;
87 Tree::Iter iter;
88 switch (x) {
89 case 0:
90 iter = tree.findFirst(i);
91 break;
92 case 1:
93 iter = tree.findLast(i);
94 break;
95 case 2:
96 default:
97 iter = tree.find(i);
98 break;
99 }
100 tree.remove(iter);
101 }
102 REPORTER_ASSERT(reporter, 0 == count[i]);
103 REPORTER_ASSERT(reporter, tree.findFirst(i) == tree.end());
104 REPORTER_ASSERT(reporter, tree.findLast(i) == tree.end());
105 REPORTER_ASSERT(reporter, tree.find(i) == tree.end());
106 }
107 // remove all of the 0 entries. (tests removing begin())
108 REPORTER_ASSERT(reporter, *tree.begin() == 0);
109 REPORTER_ASSERT(reporter, *(--tree.end()) == 99);
110 while (0 != tree.countOf(0)) {
111 --count[0];
112 tree.remove(tree.find(0));
113 }
114 REPORTER_ASSERT(reporter, 0 == count[0]);
115 REPORTER_ASSERT(reporter, tree.findFirst(0) == tree.end());
116 REPORTER_ASSERT(reporter, tree.findLast(0) == tree.end());
117 REPORTER_ASSERT(reporter, tree.find(0) == tree.end());
118 REPORTER_ASSERT(reporter, 0 < *tree.begin());
119
120 // remove all the 99 entries (tests removing last()).
121 while (0 != tree.countOf(99)) {
122 --count[99];
123 tree.remove(tree.find(99));
124 }
125 REPORTER_ASSERT(reporter, 0 == count[99]);
126 REPORTER_ASSERT(reporter, tree.findFirst(99) == tree.end());
127 REPORTER_ASSERT(reporter, tree.findLast(99) == tree.end());
128 REPORTER_ASSERT(reporter, tree.find(99) == tree.end());
129 REPORTER_ASSERT(reporter, 99 > *(--tree.end()));
130 REPORTER_ASSERT(reporter, tree.last() == --tree.end());
131
132 // Make sure iteration still goes through correct number of entries
133 // and is still sorted correctly.
134 c = 0;
135 for (Tree::Iter a = tree.begin(); tree.end() != a; ++a) {
136 Tree::Iter b = a;
137 ++b;
138 ++c;
139 REPORTER_ASSERT(reporter, b == tree.end() || *a <= *b);
140 }
141 REPORTER_ASSERT(reporter, c == tree.count());
142
143 // repeat check that correct number of each entry is in the tree
144 // and iterates correctly both forward and backward.
145 for (int i = 0; i < 100; ++i) {
146 REPORTER_ASSERT(reporter, tree.countOf(i) == count[i]);
147 int c = 0;
148 Tree::Iter iter = tree.findFirst(i);
149 while (iter != tree.end() && *iter == i) {
150 ++c;
151 ++iter;
152 }
153 REPORTER_ASSERT(reporter, count[i] == c);
154 c = 0;
155 iter = tree.findLast(i);
156 if (iter != tree.end()) {
157 do {
158 if (*iter == i) {
159 ++c;
160 } else {
161 break;
162 }
163 if (iter != tree.begin()) {
164 --iter;
165 } else {
166 break;
167 }
168 } while (true);
169 }
170 REPORTER_ASSERT(reporter, count[i] == c);
171 }
172
173 // remove all entries
174 while (!tree.empty()) {
175 tree.remove(tree.begin());
176 }
177
178 // test reset on empty tree.
179 tree.reset();
180 }
OLDNEW
« no previous file with comments | « src/gpu/GrRedBlackTree.h ('k') | tests/GrUnitTests.cpp » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698