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// This is a GPU-backend specific test
9#if SK_SUPPORT_GPU
10
11#include "GrRedBlackTree.h"
12#include "SkRandom.h"
13#include "Test.h"
14
15typedef GrRedBlackTree<int> Tree;
16
17DEF_TEST(GrRedBlackTree, reporter) {
18    Tree tree;
19
20    SkRandom r;
21
22    int count[100] = {0};
23    // add 10K ints
24    for (int i = 0; i < 10000; ++i) {
25        int x = r.nextU() % 100;
26        Tree::Iter xi = tree.insert(x);
27        REPORTER_ASSERT(reporter, *xi == x);
28        ++count[x];
29    }
30
31    tree.insert(0);
32    ++count[0];
33    tree.insert(99);
34    ++count[99];
35    REPORTER_ASSERT(reporter, *tree.begin() == 0);
36    REPORTER_ASSERT(reporter, *tree.last() == 99);
37    REPORTER_ASSERT(reporter, --(++tree.begin()) == tree.begin());
38    REPORTER_ASSERT(reporter, --tree.end() == tree.last());
39    REPORTER_ASSERT(reporter, tree.count() == 10002);
40
41    int c = 0;
42    // check that we iterate through the correct number of
43    // elements and they are properly sorted.
44    for (Tree::Iter a = tree.begin(); tree.end() != a; ++a) {
45        Tree::Iter b = a;
46        ++b;
47        ++c;
48        REPORTER_ASSERT(reporter, b == tree.end() || *a <= *b);
49    }
50    REPORTER_ASSERT(reporter, c == tree.count());
51
52    // check that the tree reports the correct number of each int
53    // and that we can iterate through them correctly both forward
54    // and backward.
55    for (int i = 0; i < 100; ++i) {
56        int c;
57        c = tree.countOf(i);
58        REPORTER_ASSERT(reporter, c == count[i]);
59        c = 0;
60        Tree::Iter iter = tree.findFirst(i);
61        while (iter != tree.end() && *iter == i) {
62            ++c;
63            ++iter;
64        }
65        REPORTER_ASSERT(reporter, count[i] == c);
66        c = 0;
67        iter = tree.findLast(i);
68        if (iter != tree.end()) {
69            do {
70                if (*iter == i) {
71                    ++c;
72                } else {
73                    break;
74                }
75                if (iter != tree.begin()) {
76                    --iter;
77                } else {
78                    break;
79                }
80            } while (true);
81        }
82        REPORTER_ASSERT(reporter, c == count[i]);
83    }
84    // remove all the ints between 25 and 74. Randomly chose to remove
85    // the first, last, or any entry for each.
86    for (int i = 25; i < 75; ++i) {
87        while (0 != tree.countOf(i)) {
88            --count[i];
89            int x = r.nextU() % 3;
90            Tree::Iter iter;
91            switch (x) {
92            case 0:
93                iter = tree.findFirst(i);
94                break;
95            case 1:
96                iter = tree.findLast(i);
97                break;
98            case 2:
99            default:
100                iter = tree.find(i);
101                break;
102            }
103            tree.remove(iter);
104        }
105        REPORTER_ASSERT(reporter, 0 == count[i]);
106        REPORTER_ASSERT(reporter, tree.findFirst(i) == tree.end());
107        REPORTER_ASSERT(reporter, tree.findLast(i) == tree.end());
108        REPORTER_ASSERT(reporter, tree.find(i) == tree.end());
109    }
110    // remove all of the 0 entries. (tests removing begin())
111    REPORTER_ASSERT(reporter, *tree.begin() == 0);
112    REPORTER_ASSERT(reporter, *(--tree.end()) == 99);
113    while (0 != tree.countOf(0)) {
114        --count[0];
115        tree.remove(tree.find(0));
116    }
117    REPORTER_ASSERT(reporter, 0 == count[0]);
118    REPORTER_ASSERT(reporter, tree.findFirst(0) == tree.end());
119    REPORTER_ASSERT(reporter, tree.findLast(0) == tree.end());
120    REPORTER_ASSERT(reporter, tree.find(0) == tree.end());
121    REPORTER_ASSERT(reporter, 0 < *tree.begin());
122
123    // remove all the 99 entries (tests removing last()).
124    while (0 != tree.countOf(99)) {
125        --count[99];
126        tree.remove(tree.find(99));
127    }
128    REPORTER_ASSERT(reporter, 0 == count[99]);
129    REPORTER_ASSERT(reporter, tree.findFirst(99) == tree.end());
130    REPORTER_ASSERT(reporter, tree.findLast(99) == tree.end());
131    REPORTER_ASSERT(reporter, tree.find(99) == tree.end());
132    REPORTER_ASSERT(reporter, 99 > *(--tree.end()));
133    REPORTER_ASSERT(reporter, tree.last() == --tree.end());
134
135    // Make sure iteration still goes through correct number of entries
136    // and is still sorted correctly.
137    c = 0;
138    for (Tree::Iter a = tree.begin(); tree.end() != a; ++a) {
139        Tree::Iter b = a;
140        ++b;
141        ++c;
142        REPORTER_ASSERT(reporter, b == tree.end() || *a <= *b);
143    }
144    REPORTER_ASSERT(reporter, c == tree.count());
145
146    // repeat check that correct number of each entry is in the tree
147    // and iterates correctly both forward and backward.
148    for (int i = 0; i < 100; ++i) {
149        REPORTER_ASSERT(reporter, tree.countOf(i) == count[i]);
150        int c = 0;
151        Tree::Iter iter = tree.findFirst(i);
152        while (iter != tree.end() && *iter == i) {
153            ++c;
154            ++iter;
155        }
156        REPORTER_ASSERT(reporter, count[i] == c);
157        c = 0;
158        iter = tree.findLast(i);
159        if (iter != tree.end()) {
160            do {
161                if (*iter == i) {
162                    ++c;
163                } else {
164                    break;
165                }
166                if (iter != tree.begin()) {
167                    --iter;
168                } else {
169                    break;
170                }
171            } while (true);
172        }
173        REPORTER_ASSERT(reporter, count[i] == c);
174    }
175
176    // remove all entries
177    while (!tree.empty()) {
178        tree.remove(tree.begin());
179    }
180
181    // test reset on empty tree.
182    tree.reset();
183}
184
185#endif
186