src/third_party/skia/tests/GrOrderedSetTest.cpp

   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
  14 typedef GrOrderedSet<int> Set;
  15 typedef GrOrderedSet<const char*, GrStrLess> Set2;
  16
  17 DEF_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