Remove explicit copy ctor in favor of the default so as not to disable/deprecate...
[oota-llvm.git] / unittests / ADT / SparseSetTest.cpp
1 //===------ ADT/SparseSetTest.cpp - SparseSet unit tests -  -----*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #include "llvm/ADT/SparseSet.h"
11 #include "gtest/gtest.h"
12
13 using namespace llvm;
14
15 namespace {
16
17 typedef SparseSet<unsigned> USet;
18
19 // Empty set tests.
20 TEST(SparseSetTest, EmptySet) {
21   USet Set;
22   EXPECT_TRUE(Set.empty());
23   EXPECT_TRUE(Set.begin() == Set.end());
24   EXPECT_EQ(0u, Set.size());
25
26   Set.setUniverse(10);
27
28   // Lookups on empty set.
29   EXPECT_TRUE(Set.find(0) == Set.end());
30   EXPECT_TRUE(Set.find(9) == Set.end());
31
32   // Same thing on a const reference.
33   const USet &CSet = Set;
34   EXPECT_TRUE(CSet.empty());
35   EXPECT_TRUE(CSet.begin() == CSet.end());
36   EXPECT_EQ(0u, CSet.size());
37   EXPECT_TRUE(CSet.find(0) == CSet.end());
38   USet::const_iterator I = CSet.find(5);
39   EXPECT_TRUE(I == CSet.end());
40 }
41
42 // Single entry set tests.
43 TEST(SparseSetTest, SingleEntrySet) {
44   USet Set;
45   Set.setUniverse(10);
46   std::pair<USet::iterator, bool> IP = Set.insert(5);
47   EXPECT_TRUE(IP.second);
48   EXPECT_TRUE(IP.first == Set.begin());
49
50   EXPECT_FALSE(Set.empty());
51   EXPECT_FALSE(Set.begin() == Set.end());
52   EXPECT_TRUE(Set.begin() + 1 == Set.end());
53   EXPECT_EQ(1u, Set.size());
54
55   EXPECT_TRUE(Set.find(0) == Set.end());
56   EXPECT_TRUE(Set.find(9) == Set.end());
57
58   EXPECT_FALSE(Set.count(0));
59   EXPECT_TRUE(Set.count(5));
60
61   // Redundant insert.
62   IP = Set.insert(5);
63   EXPECT_FALSE(IP.second);
64   EXPECT_TRUE(IP.first == Set.begin());
65
66   // Erase non-existent element.
67   EXPECT_FALSE(Set.erase(1));
68   EXPECT_EQ(1u, Set.size());
69   EXPECT_EQ(5u, *Set.begin());
70
71   // Erase iterator.
72   USet::iterator I = Set.find(5);
73   EXPECT_TRUE(I == Set.begin());
74   I = Set.erase(I);
75   EXPECT_TRUE(I == Set.end());
76   EXPECT_TRUE(Set.empty());
77 }
78
79 // Multiple entry set tests.
80 TEST(SparseSetTest, MultipleEntrySet) {
81   USet Set;
82   Set.setUniverse(10);
83
84   Set.insert(5);
85   Set.insert(3);
86   Set.insert(2);
87   Set.insert(1);
88   Set.insert(4);
89   EXPECT_EQ(5u, Set.size());
90
91   // Without deletions, iteration order == insertion order.
92   USet::const_iterator I = Set.begin();
93   EXPECT_EQ(5u, *I);
94   ++I;
95   EXPECT_EQ(3u, *I);
96   ++I;
97   EXPECT_EQ(2u, *I);
98   ++I;
99   EXPECT_EQ(1u, *I);
100   ++I;
101   EXPECT_EQ(4u, *I);
102   ++I;
103   EXPECT_TRUE(I == Set.end());
104
105   // Redundant insert.
106   std::pair<USet::iterator, bool> IP = Set.insert(3);
107   EXPECT_FALSE(IP.second);
108   EXPECT_TRUE(IP.first == Set.begin() + 1);
109
110   // Erase last element by key.
111   EXPECT_TRUE(Set.erase(4));
112   EXPECT_EQ(4u, Set.size());
113   EXPECT_FALSE(Set.count(4));
114   EXPECT_FALSE(Set.erase(4));
115   EXPECT_EQ(4u, Set.size());
116   EXPECT_FALSE(Set.count(4));
117
118   // Erase first element by key.
119   EXPECT_TRUE(Set.count(5));
120   EXPECT_TRUE(Set.find(5) == Set.begin());
121   EXPECT_TRUE(Set.erase(5));
122   EXPECT_EQ(3u, Set.size());
123   EXPECT_FALSE(Set.count(5));
124   EXPECT_FALSE(Set.erase(5));
125   EXPECT_EQ(3u, Set.size());
126   EXPECT_FALSE(Set.count(5));
127
128   Set.insert(6);
129   Set.insert(7);
130   EXPECT_EQ(5u, Set.size());
131
132   // Erase last element by iterator.
133   I = Set.erase(Set.end() - 1);
134   EXPECT_TRUE(I == Set.end());
135   EXPECT_EQ(4u, Set.size());
136
137   // Erase second element by iterator.
138   I = Set.erase(Set.begin() + 1);
139   EXPECT_TRUE(I == Set.begin() + 1);
140
141   // Clear and resize the universe.
142   Set.clear();
143   EXPECT_FALSE(Set.count(5));
144   Set.setUniverse(1000);
145
146   // Add more than 256 elements.
147   for (unsigned i = 100; i != 800; ++i)
148     Set.insert(i);
149
150   for (unsigned i = 0; i != 10; ++i)
151     Set.erase(i);
152
153   for (unsigned i = 100; i != 800; ++i)
154     EXPECT_TRUE(Set.count(i));
155
156   EXPECT_FALSE(Set.count(99));
157   EXPECT_FALSE(Set.count(800));
158   EXPECT_EQ(700u, Set.size());
159 }
160
161 struct Alt {
162   unsigned Value;
163   explicit Alt(unsigned x) : Value(x) {}
164   unsigned getSparseSetIndex() const { return Value - 1000; }
165 };
166
167 TEST(SparseSetTest, AltStructSet) {
168   typedef SparseSet<Alt> ASet;
169   ASet Set;
170   Set.setUniverse(10);
171   Set.insert(Alt(1005));
172
173   ASet::iterator I = Set.find(5);
174   ASSERT_TRUE(I == Set.begin());
175   EXPECT_EQ(1005u, I->Value);
176
177   Set.insert(Alt(1006));
178   Set.insert(Alt(1006));
179   I = Set.erase(Set.begin());
180   ASSERT_TRUE(I == Set.begin());
181   EXPECT_EQ(1006u, I->Value);
182
183   EXPECT_FALSE(Set.erase(5));
184   EXPECT_TRUE(Set.erase(6));
185 }
186 } // namespace