1/*
2 * Copyright 2012 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 "SkTSet.h"
9#include "Test.h"
10
11// Tests the SkTSet<T> class template.
12// Functions that just call SkTDArray are not tested.
13
14static void TestTSet_basic(skiatest::Reporter* reporter) {
15    SkTSet<int> set0;
16    REPORTER_ASSERT(reporter,  set0.isEmpty());
17    REPORTER_ASSERT(reporter, !set0.contains(-1));
18    REPORTER_ASSERT(reporter, !set0.contains(0));
19    REPORTER_ASSERT(reporter, !set0.contains(1));
20    REPORTER_ASSERT(reporter,  set0.count() == 0);
21
22    REPORTER_ASSERT(reporter,  set0.add(0));
23    REPORTER_ASSERT(reporter, !set0.isEmpty());
24    REPORTER_ASSERT(reporter, !set0.contains(-1));
25    REPORTER_ASSERT(reporter,  set0.contains(0));
26    REPORTER_ASSERT(reporter, !set0.contains(1));
27    REPORTER_ASSERT(reporter,  set0.count() == 1);
28    REPORTER_ASSERT(reporter, !set0.add(0));
29    REPORTER_ASSERT(reporter,  set0.count() == 1);
30
31#ifdef SK_DEBUG
32    set0.validate();
33#endif
34}
35
36#define COUNT 1732
37#define PRIME1 10007
38#define PRIME2 1733
39
40// Generates a series of positive unique pseudo-random numbers.
41static int f(int i) {
42    return (long(i) * PRIME1) % PRIME2;
43}
44
45// Will expose contains() too.
46static void TestTSet_advanced(skiatest::Reporter* reporter) {
47    SkTSet<int> set0;
48
49    for (int i = 0; i < COUNT; i++) {
50        REPORTER_ASSERT(reporter, !set0.contains(f(i)));
51        if (i > 0) {
52            REPORTER_ASSERT(reporter,  set0.contains(f(0)));
53            REPORTER_ASSERT(reporter,  set0.contains(f(i / 2)));
54            REPORTER_ASSERT(reporter,  set0.contains(f(i - 1)));
55        }
56        REPORTER_ASSERT(reporter, !set0.contains(f(i)));
57        REPORTER_ASSERT(reporter,  set0.count() == i);
58        REPORTER_ASSERT(reporter,  set0.add(f(i)));
59        REPORTER_ASSERT(reporter,  set0.contains(f(i)));
60        REPORTER_ASSERT(reporter,  set0.count() == i + 1);
61        REPORTER_ASSERT(reporter, !set0.add(f(i)));
62    }
63
64    // Test deterministic output
65    for (int i = 0; i < COUNT; i++) {
66        REPORTER_ASSERT(reporter, set0[i] == f(i));
67    }
68
69    // Test copy constructor too.
70    SkTSet<int> set1 = set0;
71
72    REPORTER_ASSERT(reporter, set0.count() == set1.count());
73    REPORTER_ASSERT(reporter, !set1.contains(-1000));
74
75    for (int i = 0; i < COUNT; i++) {
76        REPORTER_ASSERT(reporter, set1.contains(f(i)));
77        REPORTER_ASSERT(reporter, set1[i] == f(i));
78    }
79
80    // Test operator= too.
81    SkTSet<int> set2;
82    set2 = set0;
83
84    REPORTER_ASSERT(reporter, set0.count() == set2.count());
85    REPORTER_ASSERT(reporter, !set2.contains(-1000));
86
87    for (int i = 0; i < COUNT; i++) {
88        REPORTER_ASSERT(reporter, set2.contains(f(i)));
89        REPORTER_ASSERT(reporter, set2[i] == f(i));
90    }
91
92#ifdef SK_DEBUG
93    set0.validate();
94    set1.validate();
95    set2.validate();
96#endif
97}
98
99static void TestTSet_merge(skiatest::Reporter* reporter) {
100    SkTSet<int> set;
101    SkTSet<int> setOdd;
102
103    for (int i = 0; i < COUNT; i++) {
104        REPORTER_ASSERT(reporter, set.add(2 * i));
105        REPORTER_ASSERT(reporter, setOdd.add(2 * i + 1));
106    }
107    // mergeInto returns the number of duplicates. Expected 0.
108    REPORTER_ASSERT(reporter, set.mergeInto(setOdd) == 0);
109    REPORTER_ASSERT(reporter, set.count() == 2 * COUNT);
110
111    // mergeInto should now find all new numbers duplicate.
112    REPORTER_ASSERT(reporter, set.mergeInto(setOdd) == setOdd.count());
113    REPORTER_ASSERT(reporter, set.count() == 2 * COUNT);
114
115    for (int i = 0; i < 2 * COUNT; i++) {
116        REPORTER_ASSERT(reporter, set.contains(i));
117    }
118
119    // check deterministic output
120    for (int i = 0; i < COUNT; i++) {
121        REPORTER_ASSERT(reporter, set[i] == 2 * i);
122        REPORTER_ASSERT(reporter, set[COUNT + i] == 2 * i + 1);
123    }
124
125#ifdef SK_DEBUG
126    set.validate();
127    setOdd.validate();
128#endif
129}
130
131DEF_TEST(TSet, reporter) {
132    TestTSet_basic(reporter);
133    TestTSet_advanced(reporter);
134    TestTSet_merge(reporter);
135}
136