1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
|
#include "StarFlatHashSet.hpp"
#include "StarFlatHashMap.hpp"
#include "StarRandom.hpp"
#include "StarVector.hpp"
#include "StarIterator.hpp"
#include "gtest/gtest.h"
using namespace Star;
TEST(FlatHashSet, Preset) {
FlatHashSet<int> testSet = {42, 63};
ASSERT_EQ(testSet.find(41), testSet.end());
ASSERT_EQ(*testSet.find(42), 42);
ASSERT_EQ(*testSet.find(63), 63);
ASSERT_EQ(testSet.find(64), testSet.end());
ASSERT_EQ(testSet.size(), 2u);
testSet.erase(testSet.find(42));
ASSERT_EQ(testSet.find(42), testSet.end());
ASSERT_EQ(*testSet.find(63), 63);
ASSERT_EQ(testSet.size(), 1u);
testSet.erase(testSet.find(63));
ASSERT_EQ(testSet.find(42), testSet.end());
ASSERT_EQ(testSet.find(63), testSet.end());
ASSERT_EQ(testSet.size(), 0u);
testSet.insert(12);
testSet.insert(24);
ASSERT_EQ(*testSet.find(12), 12);
ASSERT_EQ(testSet.size(), 2u);
testSet.clear();
ASSERT_EQ(testSet.find(12), testSet.end());
ASSERT_EQ(testSet.size(), 0u);
EXPECT_TRUE(testSet.insert(7).second);
EXPECT_TRUE(testSet.insert(11).second);
EXPECT_FALSE(testSet.insert(7).second);
ASSERT_EQ(testSet.size(), 2u);
FlatHashSet<int> testSet2(testSet.begin(), testSet.end());
ASSERT_EQ(testSet, testSet2);
ASSERT_EQ(testSet.erase(testSet.begin(), testSet.end()), testSet.end());
ASSERT_EQ(testSet.size(), 0u);
ASSERT_NE(testSet, testSet2);
FlatHashSet<int> testSet3(testSet.begin(), testSet.end());
ASSERT_EQ(testSet3.size(), 0u);
testSet2 = testSet;
ASSERT_EQ(testSet, testSet2);
}
TEST(FlatHashSet, Random) {
List<Vec2I> keys;
for (unsigned i = 0; i < 100000; ++i)
keys.append(Vec2I(i * 743202097, i * 205495087));
Random::shuffle(keys);
FlatHashSet<Vec2I> testSet;
for (size_t i = 0; i < keys.size(); ++i)
testSet.insert(keys[i]);
Random::shuffle(keys);
for (size_t i = 0; i < keys.size() / 2; ++i)
testSet.erase(keys[i]);
Random::shuffle(keys);
for (size_t i = 0; i < keys.size() / 3; ++i)
testSet.insert(keys[i]);
Random::shuffle(keys);
for (size_t i = 0; i < keys.size() / 2; ++i)
testSet.erase(keys[i]);
Random::shuffle(keys);
for (auto k : keys) {
auto i = testSet.find(k);
if (i != testSet.end()) {
ASSERT_TRUE(*i == k);
}
}
Random::shuffle(keys);
for (auto k : keys) {
testSet.insert(k);
ASSERT_TRUE(testSet.find(k) != testSet.end());
}
List<Vec2I> cmp;
for (auto const& k : testSet)
cmp.append(k);
cmp.sort();
keys.sort();
ASSERT_TRUE(cmp == keys);
Random::shuffle(keys);
for (auto k : keys) {
testSet.erase(k);
ASSERT_TRUE(testSet.find(k) == testSet.end());
}
ASSERT_TRUE(testSet.empty());
}
TEST(FlatHashMap, Preset) {
FlatHashMap<int, int> testMap = {{42, 42}, {63, 63}};
ASSERT_EQ(testMap.find(41), testMap.end());
ASSERT_EQ(testMap.find(42)->second, 42);
ASSERT_EQ(testMap.find(63)->second, 63);
ASSERT_EQ(testMap.find(64), testMap.end());
ASSERT_EQ(testMap.size(), 2u);
testMap.erase(testMap.find(42));
ASSERT_EQ(testMap.find(42), testMap.end());
ASSERT_EQ(testMap.find(63)->second, 63);
ASSERT_EQ(testMap.size(), 1u);
testMap.erase(testMap.find(63));
ASSERT_EQ(testMap.find(42), testMap.end());
ASSERT_EQ(testMap.find(63), testMap.end());
ASSERT_EQ(testMap.size(), 0u);
testMap.insert({12, 12});
testMap.insert({24, 24});
ASSERT_EQ(testMap.find(12)->second, 12);
ASSERT_EQ(testMap.size(), 2u);
testMap.clear();
ASSERT_EQ(testMap.find(12), testMap.end());
ASSERT_EQ(testMap.size(), 0u);
EXPECT_TRUE(testMap.insert({7, 7}).second);
EXPECT_TRUE(testMap.insert({11, 11}).second);
EXPECT_FALSE(testMap.insert({7, 7}).second);
ASSERT_EQ(testMap.size(), 2u);
FlatHashMap<int, int> testMap2(testMap.begin(), testMap.end());
ASSERT_EQ(testMap, testMap2);
ASSERT_EQ(testMap.erase(testMap.begin(), testMap.end()), testMap.end());
ASSERT_EQ(testMap.size(), 0u);
ASSERT_NE(testMap, testMap2);
FlatHashMap<int, int> testMap3(testMap.begin(), testMap.end());
ASSERT_EQ(testMap3.size(), 0u);
testMap2 = testMap;
ASSERT_EQ(testMap, testMap2);
}
TEST(FlatHashMap, Random) {
List<pair<Vec2I, int>> values;
for (unsigned i = 0; i < 100000; ++i)
values.append({Vec2I(i * 743202097, i * 205495087), i});
Random::shuffle(values);
FlatHashMap<Vec2I, int> testMap;
for (auto v : values)
testMap.insert(v);
Random::shuffle(values);
for (size_t i = 0; i < values.size() / 2; ++i)
testMap.erase(values[i].first);
Random::shuffle(values);
for (size_t i = 0; i < values.size() / 3; ++i)
testMap.insert(values[i]);
Random::shuffle(values);
for (size_t i = 0; i < values.size() / 2; ++i)
testMap.erase(values[i].first);
Random::shuffle(values);
for (auto v : values) {
auto i = testMap.find(v.first);
if (i != testMap.end()) {
ASSERT_TRUE(i->second == v.second);
}
}
Random::shuffle(values);
for (auto v : values) {
ASSERT_TRUE(testMap.insert(v).first->second == v.second);
ASSERT_TRUE(testMap.at(v.first) == v.second);
}
Random::shuffle(values);
for (auto v : values) {
ASSERT_EQ(testMap.erase(v.first), 1u);
ASSERT_TRUE(testMap.find(v.first) == testMap.end());
}
ASSERT_TRUE(testMap.empty());
}
TEST(FlatHashMap, Iterator) {
List<pair<Vec2I, int>> values;
for (unsigned i = 0; i < 100000; ++i)
values.append({Vec2I(i * 743202097, i * 205495087), i});
FlatHashMap<Vec2I, int> testMap;
for (auto v : values)
testMap.insert(v);
auto it = makeSMutableMapIterator(testMap);
while (it.hasNext()) {
if (it.next().second % 3 == 0)
it.remove();
}
auto i = values.begin();
std::advance(i, values.size());
ASSERT_EQ(i, values.end());
}
|