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 "SkRandom.h"
9#include "Test.h"
10// This is a GPU-backend specific test
11#if SK_SUPPORT_GPU
12#include "GrOrderedSet.h"
13
14typedef GrOrderedSet<int> Set;
15typedef GrOrderedSet<const char*, GrStrLess> Set2;
16
17DEF_TEST(GrOrderedSet, reporter) {
18    Set set;
19
20    REPORTER_ASSERT(reporter, set.empty());
21
22    SkRandom r;
23
24    int count[1000] = {0};
25    // add 10K ints
26    for (int i = 0; i < 10000; ++i) {
27        int x = r.nextU() % 1000;
28        Set::Iter xi = set.insert(x);
29        REPORTER_ASSERT(reporter, *xi == x);
30        REPORTER_ASSERT(reporter, !set.empty());
31        count[x] = 1;
32    }
33    set.insert(0);
34    count[0] = 1;
35    set.insert(999);
36    count[999] = 1;
37    int totalCount = 0;
38    for (int i = 0; i < 1000; ++i) {
39        totalCount += count[i];
40    }
41    REPORTER_ASSERT(reporter, *set.begin() == 0);
42    REPORTER_ASSERT(reporter, *set.last() == 999);
43    REPORTER_ASSERT(reporter, --(++set.begin()) == set.begin());
44    REPORTER_ASSERT(reporter, --set.end() == set.last());
45    REPORTER_ASSERT(reporter, set.count() == totalCount);
46
47    int c = 0;
48    // check that we iterate through the correct number of
49    // elements and they are properly sorted.
50    for (Set::Iter a = set.begin(); set.end() != a; ++a) {
51        Set::Iter b = a;
52        ++b;
53        ++c;
54        REPORTER_ASSERT(reporter, b == set.end() || *a <= *b);
55    }
56    REPORTER_ASSERT(reporter, c == set.count());
57
58    // check that the set finds all ints and only ints added to set
59    for (int i = 0; i < 1000; ++i) {
60        bool existsFind = set.find(i) != set.end();
61        bool existsCount = 0 != count[i];
62        REPORTER_ASSERT(reporter, existsFind == existsCount);
63    }
64    // remove all the ints between 100 and 200.
65    for (int i = 100; i < 200; ++i) {
66        set.remove(set.find(i));
67        if (1 == count[i]) {
68            count[i] = 0;
69            --totalCount;
70        }
71        REPORTER_ASSERT(reporter, set.count() == totalCount);
72        REPORTER_ASSERT(reporter, set.find(i) == set.end());
73    }
74    // remove the 0 entry. (tests removing begin())
75    REPORTER_ASSERT(reporter, *set.begin() == 0);
76    REPORTER_ASSERT(reporter, *(--set.end()) == 999);
77    set.remove(set.find(0));
78    count[0] = 0;
79    --totalCount;
80    REPORTER_ASSERT(reporter, set.count() == totalCount);
81    REPORTER_ASSERT(reporter, set.find(0) == set.end());
82    REPORTER_ASSERT(reporter, 0 < *set.begin());
83
84    // remove all the 999 entries (tests removing last()).
85    set.remove(set.find(999));
86    count[999] = 0;
87    --totalCount;
88    REPORTER_ASSERT(reporter, set.count() == totalCount);
89    REPORTER_ASSERT(reporter, set.find(999) == set.end());
90    REPORTER_ASSERT(reporter, 999 > *(--set.end()));
91    REPORTER_ASSERT(reporter, set.last() == --set.end());
92
93    // Make sure iteration still goes through correct number of entries
94    // and is still sorted correctly.
95    c = 0;
96    for (Set::Iter a = set.begin(); set.end() != a; ++a) {
97        Set::Iter b = a;
98        ++b;
99        ++c;
100        REPORTER_ASSERT(reporter, b == set.end() || *a <= *b);
101    }
102    REPORTER_ASSERT(reporter, c == set.count());
103
104    // repeat check that the set finds all ints and only ints added to set
105    for (int i = 0; i < 1000; ++i) {
106        bool existsFind = set.find(i) != set.end();
107        bool existsCount = 0 != count[i];
108        REPORTER_ASSERT(reporter, existsFind == existsCount);
109    }
110
111    // remove all entries
112    while (!set.empty()) {
113        set.remove(set.begin());
114    }
115
116    // test reset on empty set.
117    set.reset();
118    REPORTER_ASSERT(reporter, set.empty());
119
120
121    // test using c strings
122    const char* char1 = "dog";
123    const char* char2 = "cat";
124    const char* char3 = "dog";
125
126    Set2 set2;
127
128    set2.insert("ape");
129    set2.insert(char1);
130    set2.insert(char2);
131    set2.insert(char3);
132    set2.insert("ant");
133    set2.insert("cat");
134
135    REPORTER_ASSERT(reporter, set2.count() == 4);
136    REPORTER_ASSERT(reporter, set2.find("dog") == set2.last());
137    REPORTER_ASSERT(reporter, set2.find("cat") != set2.end());
138    REPORTER_ASSERT(reporter, set2.find("ant") == set2.begin());
139    REPORTER_ASSERT(reporter, set2.find("bug") == set2.end());
140
141    set2.remove(set2.find("ant"));
142    REPORTER_ASSERT(reporter, set2.find("ant") == set2.end());
143    REPORTER_ASSERT(reporter, set2.count() == 3);
144
145    set2.reset();
146    REPORTER_ASSERT(reporter, set2.empty());
147}
148
149#endif
150