1 | /* |
2 | * Copyright 2011-present Facebook, Inc. |
3 | * |
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
5 | * you may not use this file except in compliance with the License. |
6 | * You may obtain a copy of the License at |
7 | * |
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
9 | * |
10 | * Unless required by applicable law or agreed to in writing, software |
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
13 | * See the License for the specific language governing permissions and |
14 | * limitations under the License. |
15 | */ |
16 | |
17 | #include <folly/sorted_vector_types.h> |
18 | |
19 | #include <iterator> |
20 | #include <list> |
21 | #include <memory> |
22 | #include <string> |
23 | |
24 | #include <folly/Range.h> |
25 | #include <folly/portability/GMock.h> |
26 | #include <folly/portability/GTest.h> |
27 | |
28 | using folly::sorted_vector_map; |
29 | using folly::sorted_vector_set; |
30 | |
31 | namespace { |
32 | |
33 | template <class T> |
34 | struct less_invert { |
35 | bool operator()(const T& a, const T& b) const { |
36 | return b < a; |
37 | } |
38 | }; |
39 | |
40 | template <class Container> |
41 | void check_invariant(Container& c) { |
42 | auto it = c.begin(); |
43 | auto end = c.end(); |
44 | if (it == end) { |
45 | return; |
46 | } |
47 | auto prev = it; |
48 | ++it; |
49 | for (; it != end; ++it, ++prev) { |
50 | EXPECT_TRUE(c.value_comp()(*prev, *it)); |
51 | } |
52 | } |
53 | |
54 | struct OneAtATimePolicy { |
55 | template <class Container> |
56 | void increase_capacity(Container& c) { |
57 | if (c.size() == c.capacity()) { |
58 | c.reserve(c.size() + 1); |
59 | } |
60 | } |
61 | }; |
62 | |
63 | struct CountCopyCtor { |
64 | explicit CountCopyCtor() : val_(0) {} |
65 | |
66 | explicit CountCopyCtor(int val) : val_(val), count_(0) {} |
67 | |
68 | CountCopyCtor(const CountCopyCtor& c) : val_(c.val_), count_(c.count_ + 1) {} |
69 | |
70 | bool operator<(const CountCopyCtor& o) const { |
71 | return val_ < o.val_; |
72 | } |
73 | |
74 | int val_; |
75 | int count_; |
76 | }; |
77 | |
78 | struct Opaque { |
79 | int value; |
80 | friend bool operator==(Opaque a, Opaque b) { |
81 | return a.value == b.value; |
82 | } |
83 | friend bool operator<(Opaque a, Opaque b) { |
84 | return a.value < b.value; |
85 | } |
86 | struct Compare : std::less<int>, std::less<Opaque> { |
87 | using is_transparent = void; |
88 | using std::less<int>::operator(); |
89 | using std::less<Opaque>::operator(); |
90 | bool operator()(int a, Opaque b) const { |
91 | return std::less<int>::operator()(a, b.value); |
92 | } |
93 | bool operator()(Opaque a, int b) const { |
94 | return std::less<int>::operator()(a.value, b); |
95 | } |
96 | }; |
97 | }; |
98 | |
99 | } // namespace |
100 | |
101 | TEST(SortedVectorTypes, SetAssignmentInitListTest) { |
102 | sorted_vector_set<int> s{3, 4, 5}; |
103 | EXPECT_THAT(s, testing::ElementsAreArray({3, 4, 5})); |
104 | s = {}; // empty ilist assignment |
105 | EXPECT_THAT(s, testing::IsEmpty()); |
106 | s = {7, 8, 9}; // non-empty ilist assignment |
107 | EXPECT_THAT(s, testing::ElementsAreArray({7, 8, 9})); |
108 | } |
109 | |
110 | TEST(SortedVectorTypes, MapAssignmentInitListTest) { |
111 | using v = std::pair<int, const char*>; |
112 | v p = {3, "a" }, q = {4, "b" }, r = {5, "c" }; |
113 | sorted_vector_map<int, const char*> m{p, q, r}; |
114 | EXPECT_THAT(m, testing::ElementsAreArray({p, q, r})); |
115 | m = {}; // empty ilist assignment |
116 | EXPECT_THAT(m, testing::IsEmpty()); |
117 | m = {p, q, r}; // non-empty ilist assignment |
118 | EXPECT_THAT(m, testing::ElementsAreArray({p, q, r})); |
119 | } |
120 | |
121 | TEST(SortedVectorTypes, SimpleSetTest) { |
122 | sorted_vector_set<int> s; |
123 | EXPECT_TRUE(s.empty()); |
124 | for (int i = 0; i < 1000; ++i) { |
125 | s.insert(rand() % 100000); |
126 | } |
127 | EXPECT_FALSE(s.empty()); |
128 | check_invariant(s); |
129 | |
130 | sorted_vector_set<int> s2; |
131 | s2.insert(s.begin(), s.end()); |
132 | check_invariant(s2); |
133 | EXPECT_TRUE(s == s2); |
134 | |
135 | auto it = s2.lower_bound(32); |
136 | if (*it == 32) { |
137 | s2.erase(it); |
138 | it = s2.lower_bound(32); |
139 | } |
140 | check_invariant(s2); |
141 | auto oldSz = s2.size(); |
142 | s2.insert(it, 32); |
143 | EXPECT_TRUE(s2.size() == oldSz + 1); |
144 | check_invariant(s2); |
145 | |
146 | const sorted_vector_set<int>& cs2 = s2; |
147 | auto range = cs2.equal_range(32); |
148 | auto lbound = cs2.lower_bound(32); |
149 | auto ubound = cs2.upper_bound(32); |
150 | EXPECT_TRUE(range.first == lbound); |
151 | EXPECT_TRUE(range.second == ubound); |
152 | EXPECT_TRUE(range.first != cs2.end()); |
153 | EXPECT_TRUE(range.second != cs2.end()); |
154 | EXPECT_TRUE(cs2.count(32) == 1); |
155 | EXPECT_FALSE(cs2.find(32) == cs2.end()); |
156 | |
157 | // Bad insert hint. |
158 | s2.insert(s2.begin() + 3, 33); |
159 | EXPECT_TRUE(s2.find(33) != s2.begin()); |
160 | EXPECT_TRUE(s2.find(33) != s2.end()); |
161 | check_invariant(s2); |
162 | s2.erase(33); |
163 | check_invariant(s2); |
164 | |
165 | it = s2.find(32); |
166 | EXPECT_FALSE(it == s2.end()); |
167 | s2.erase(it); |
168 | EXPECT_TRUE(s2.size() == oldSz); |
169 | check_invariant(s2); |
170 | |
171 | sorted_vector_set<int> cpy(s); |
172 | check_invariant(cpy); |
173 | EXPECT_TRUE(cpy == s); |
174 | sorted_vector_set<int> cpy2(s); |
175 | cpy2.insert(100001); |
176 | EXPECT_TRUE(cpy2 != cpy); |
177 | EXPECT_TRUE(cpy2 != s); |
178 | check_invariant(cpy2); |
179 | EXPECT_TRUE(cpy2.count(100001) == 1); |
180 | s.swap(cpy2); |
181 | check_invariant(cpy2); |
182 | check_invariant(s); |
183 | EXPECT_TRUE(s != cpy); |
184 | EXPECT_TRUE(s != cpy2); |
185 | EXPECT_TRUE(cpy2 == cpy); |
186 | |
187 | sorted_vector_set<int> s3 = {}; |
188 | s3.insert({1, 2, 3}); |
189 | s3.emplace(4); |
190 | EXPECT_EQ(s3.size(), 4); |
191 | |
192 | sorted_vector_set<std::string> s4; |
193 | s4.emplace("foobar" , 3); |
194 | EXPECT_EQ(s4.count("foo" ), 1); |
195 | } |
196 | |
197 | TEST(SortedVectorTypes, TransparentSetTest) { |
198 | using namespace folly::string_piece_literals; |
199 | using Compare = folly::transparent<std::less<folly::StringPiece>>; |
200 | |
201 | constexpr auto buddy = "buddy"_sp ; |
202 | constexpr auto hello = "hello"_sp ; |
203 | constexpr auto stake = "stake"_sp ; |
204 | constexpr auto world = "world"_sp ; |
205 | constexpr auto zebra = "zebra"_sp ; |
206 | |
207 | sorted_vector_set<std::string, Compare> const s({hello.str(), world.str()}); |
208 | |
209 | // find |
210 | EXPECT_TRUE(s.end() == s.find(buddy)); |
211 | EXPECT_EQ(hello, *s.find(hello)); |
212 | EXPECT_TRUE(s.end() == s.find(stake)); |
213 | EXPECT_EQ(world, *s.find(world)); |
214 | EXPECT_TRUE(s.end() == s.find(zebra)); |
215 | |
216 | // count |
217 | EXPECT_EQ(0, s.count(buddy)); |
218 | EXPECT_EQ(1, s.count(hello)); |
219 | EXPECT_EQ(0, s.count(stake)); |
220 | EXPECT_EQ(1, s.count(world)); |
221 | EXPECT_EQ(0, s.count(zebra)); |
222 | |
223 | // lower_bound |
224 | EXPECT_TRUE(s.find(hello) == s.lower_bound(buddy)); |
225 | EXPECT_TRUE(s.find(hello) == s.lower_bound(hello)); |
226 | EXPECT_TRUE(s.find(world) == s.lower_bound(stake)); |
227 | EXPECT_TRUE(s.find(world) == s.lower_bound(world)); |
228 | EXPECT_TRUE(s.end() == s.lower_bound(zebra)); |
229 | |
230 | // upper_bound |
231 | EXPECT_TRUE(s.find(hello) == s.upper_bound(buddy)); |
232 | EXPECT_TRUE(s.find(world) == s.upper_bound(hello)); |
233 | EXPECT_TRUE(s.find(world) == s.upper_bound(stake)); |
234 | EXPECT_TRUE(s.end() == s.upper_bound(world)); |
235 | EXPECT_TRUE(s.end() == s.upper_bound(zebra)); |
236 | |
237 | // equal_range |
238 | for (auto value : {buddy, hello, stake, world, zebra}) { |
239 | EXPECT_TRUE( |
240 | std::make_pair(s.lower_bound(value), s.upper_bound(value)) == |
241 | s.equal_range(value)) |
242 | << value; |
243 | } |
244 | } |
245 | |
246 | TEST(SortedVectorTypes, BadHints) { |
247 | for (int toInsert = -1; toInsert <= 7; ++toInsert) { |
248 | for (int hintPos = 0; hintPos <= 4; ++hintPos) { |
249 | sorted_vector_set<int> s; |
250 | for (int i = 0; i <= 3; ++i) { |
251 | s.insert(i * 2); |
252 | } |
253 | s.insert(s.begin() + hintPos, toInsert); |
254 | size_t expectedSize = (toInsert % 2) == 0 ? 4 : 5; |
255 | EXPECT_EQ(s.size(), expectedSize); |
256 | check_invariant(s); |
257 | } |
258 | } |
259 | } |
260 | |
261 | TEST(SortedVectorTypes, SimpleMapTest) { |
262 | sorted_vector_map<int, float> m; |
263 | for (int i = 0; i < 1000; ++i) { |
264 | m[i] = i / 1000.0; |
265 | } |
266 | check_invariant(m); |
267 | |
268 | m[32] = 100.0; |
269 | check_invariant(m); |
270 | EXPECT_TRUE(m.count(32) == 1); |
271 | EXPECT_DOUBLE_EQ(100.0, m.at(32)); |
272 | EXPECT_FALSE(m.find(32) == m.end()); |
273 | m.erase(32); |
274 | EXPECT_TRUE(m.find(32) == m.end()); |
275 | check_invariant(m); |
276 | EXPECT_THROW(m.at(32), std::out_of_range); |
277 | |
278 | sorted_vector_map<int, float> m2 = m; |
279 | EXPECT_TRUE(m2 == m); |
280 | EXPECT_FALSE(m2 != m); |
281 | auto it = m2.lower_bound(1 << 20); |
282 | EXPECT_TRUE(it == m2.end()); |
283 | m2.insert(it, std::make_pair(1 << 20, 10.0f)); |
284 | check_invariant(m2); |
285 | EXPECT_TRUE(m2.count(1 << 20) == 1); |
286 | EXPECT_TRUE(m < m2); |
287 | EXPECT_TRUE(m <= m2); |
288 | |
289 | const sorted_vector_map<int, float>& cm = m; |
290 | auto range = cm.equal_range(42); |
291 | auto lbound = cm.lower_bound(42); |
292 | auto ubound = cm.upper_bound(42); |
293 | EXPECT_TRUE(range.first == lbound); |
294 | EXPECT_TRUE(range.second == ubound); |
295 | EXPECT_FALSE(range.first == cm.end()); |
296 | EXPECT_FALSE(range.second == cm.end()); |
297 | m.erase(m.lower_bound(42)); |
298 | check_invariant(m); |
299 | |
300 | sorted_vector_map<int, float> m3; |
301 | m3.insert(m2.begin(), m2.end()); |
302 | check_invariant(m3); |
303 | EXPECT_TRUE(m3 == m2); |
304 | EXPECT_FALSE(m3 == m); |
305 | |
306 | EXPECT_TRUE(m != m2); |
307 | EXPECT_TRUE(m2 == m3); |
308 | EXPECT_TRUE(m3 != m); |
309 | m.swap(m3); |
310 | check_invariant(m); |
311 | check_invariant(m2); |
312 | check_invariant(m3); |
313 | EXPECT_TRUE(m3 != m2); |
314 | EXPECT_TRUE(m3 != m); |
315 | EXPECT_TRUE(m == m2); |
316 | |
317 | // Bad insert hint. |
318 | m.insert(m.begin() + 3, std::make_pair(1 << 15, 1.0f)); |
319 | check_invariant(m); |
320 | |
321 | sorted_vector_map<int, float> m4 = {}; |
322 | m4.insert({{1, 1.0f}, {2, 2.0f}, {1, 2.0f}}); |
323 | EXPECT_EQ(m4.at(2), 2.0f); |
324 | } |
325 | |
326 | TEST(SortedVectorTypes, TransparentMapTest) { |
327 | using namespace folly::string_piece_literals; |
328 | using Compare = folly::transparent<std::less<folly::StringPiece>>; |
329 | |
330 | constexpr auto buddy = "buddy"_sp ; |
331 | constexpr auto hello = "hello"_sp ; |
332 | constexpr auto stake = "stake"_sp ; |
333 | constexpr auto world = "world"_sp ; |
334 | constexpr auto zebra = "zebra"_sp ; |
335 | |
336 | sorted_vector_map<std::string, float, Compare> const m( |
337 | {{hello.str(), -1.}, {world.str(), +1.}}); |
338 | |
339 | // find |
340 | EXPECT_TRUE(m.end() == m.find(buddy)); |
341 | EXPECT_EQ(hello, m.find(hello)->first); |
342 | EXPECT_TRUE(m.end() == m.find(stake)); |
343 | EXPECT_EQ(world, m.find(world)->first); |
344 | EXPECT_TRUE(m.end() == m.find(zebra)); |
345 | |
346 | // count |
347 | EXPECT_EQ(0, m.count(buddy)); |
348 | EXPECT_EQ(1, m.count(hello)); |
349 | EXPECT_EQ(0, m.count(stake)); |
350 | EXPECT_EQ(1, m.count(world)); |
351 | EXPECT_EQ(0, m.count(zebra)); |
352 | |
353 | // lower_bound |
354 | EXPECT_TRUE(m.find(hello) == m.lower_bound(buddy)); |
355 | EXPECT_TRUE(m.find(hello) == m.lower_bound(hello)); |
356 | EXPECT_TRUE(m.find(world) == m.lower_bound(stake)); |
357 | EXPECT_TRUE(m.find(world) == m.lower_bound(world)); |
358 | EXPECT_TRUE(m.end() == m.lower_bound(zebra)); |
359 | |
360 | // upper_bound |
361 | EXPECT_TRUE(m.find(hello) == m.upper_bound(buddy)); |
362 | EXPECT_TRUE(m.find(world) == m.upper_bound(hello)); |
363 | EXPECT_TRUE(m.find(world) == m.upper_bound(stake)); |
364 | EXPECT_TRUE(m.end() == m.upper_bound(world)); |
365 | EXPECT_TRUE(m.end() == m.upper_bound(zebra)); |
366 | |
367 | // equal_range |
368 | for (auto value : {buddy, hello, stake, world, zebra}) { |
369 | EXPECT_TRUE( |
370 | std::make_pair(m.lower_bound(value), m.upper_bound(value)) == |
371 | m.equal_range(value)) |
372 | << value; |
373 | } |
374 | } |
375 | |
376 | TEST(SortedVectorTypes, Sizes) { |
377 | EXPECT_EQ(sizeof(sorted_vector_set<int>), sizeof(std::vector<int>)); |
378 | EXPECT_EQ( |
379 | sizeof(sorted_vector_map<int, int>), |
380 | sizeof(std::vector<std::pair<int, int>>)); |
381 | |
382 | typedef sorted_vector_set< |
383 | int, |
384 | std::less<int>, |
385 | std::allocator<int>, |
386 | OneAtATimePolicy> |
387 | SetT; |
388 | typedef sorted_vector_map< |
389 | int, |
390 | int, |
391 | std::less<int>, |
392 | std::allocator<std::pair<int, int>>, |
393 | OneAtATimePolicy> |
394 | MapT; |
395 | |
396 | EXPECT_EQ(sizeof(SetT), sizeof(std::vector<int>)); |
397 | EXPECT_EQ(sizeof(MapT), sizeof(std::vector<std::pair<int, int>>)); |
398 | } |
399 | |
400 | TEST(SortedVectorTypes, InitializerLists) { |
401 | sorted_vector_set<int> empty_initialized_set{}; |
402 | EXPECT_TRUE(empty_initialized_set.empty()); |
403 | |
404 | sorted_vector_set<int> singleton_initialized_set{1}; |
405 | EXPECT_EQ(1, singleton_initialized_set.size()); |
406 | EXPECT_EQ(1, *singleton_initialized_set.begin()); |
407 | |
408 | sorted_vector_set<int> forward_initialized_set{1, 2}; |
409 | sorted_vector_set<int> backward_initialized_set{2, 1}; |
410 | EXPECT_EQ(2, forward_initialized_set.size()); |
411 | EXPECT_EQ(1, *forward_initialized_set.begin()); |
412 | EXPECT_EQ(2, *forward_initialized_set.rbegin()); |
413 | EXPECT_TRUE(forward_initialized_set == backward_initialized_set); |
414 | |
415 | sorted_vector_map<int, int> empty_initialized_map{}; |
416 | EXPECT_TRUE(empty_initialized_map.empty()); |
417 | |
418 | sorted_vector_map<int, int> singleton_initialized_map{{1, 10}}; |
419 | EXPECT_EQ(1, singleton_initialized_map.size()); |
420 | EXPECT_EQ(10, singleton_initialized_map[1]); |
421 | |
422 | sorted_vector_map<int, int> forward_initialized_map{{1, 10}, {2, 20}}; |
423 | sorted_vector_map<int, int> backward_initialized_map{{2, 20}, {1, 10}}; |
424 | EXPECT_EQ(2, forward_initialized_map.size()); |
425 | EXPECT_EQ(10, forward_initialized_map[1]); |
426 | EXPECT_EQ(20, forward_initialized_map[2]); |
427 | EXPECT_TRUE(forward_initialized_map == backward_initialized_map); |
428 | } |
429 | |
430 | TEST(SortedVectorTypes, CustomCompare) { |
431 | sorted_vector_set<int, less_invert<int>> s; |
432 | for (int i = 0; i < 200; ++i) { |
433 | s.insert(i); |
434 | } |
435 | check_invariant(s); |
436 | |
437 | sorted_vector_map<int, float, less_invert<int>> m; |
438 | for (int i = 0; i < 200; ++i) { |
439 | m[i] = 12.0; |
440 | } |
441 | check_invariant(m); |
442 | } |
443 | |
444 | TEST(SortedVectorTypes, GrowthPolicy) { |
445 | typedef sorted_vector_set< |
446 | CountCopyCtor, |
447 | std::less<CountCopyCtor>, |
448 | std::allocator<CountCopyCtor>, |
449 | OneAtATimePolicy> |
450 | SetT; |
451 | |
452 | SetT a; |
453 | for (int i = 0; i < 20; ++i) { |
454 | a.insert(CountCopyCtor(i)); |
455 | } |
456 | check_invariant(a); |
457 | SetT::iterator it = a.begin(); |
458 | EXPECT_FALSE(it == a.end()); |
459 | if (it != a.end()) { |
460 | EXPECT_EQ(it->val_, 0); |
461 | // 1 copy for the initial insertion, 19 more for reallocs on the |
462 | // additional insertions. |
463 | EXPECT_EQ(it->count_, 20); |
464 | } |
465 | |
466 | std::list<CountCopyCtor> v; |
467 | for (int i = 0; i < 20; ++i) { |
468 | v.emplace_back(20 + i); |
469 | } |
470 | a.insert(v.begin(), v.end()); |
471 | check_invariant(a); |
472 | |
473 | it = a.begin(); |
474 | EXPECT_FALSE(it == a.end()); |
475 | if (it != a.end()) { |
476 | EXPECT_EQ(it->val_, 0); |
477 | // Should be only 1 more copy for inserting this above range. |
478 | EXPECT_EQ(it->count_, 21); |
479 | } |
480 | } |
481 | |
482 | TEST(SortedVectorTest, EmptyTest) { |
483 | sorted_vector_set<int> emptySet; |
484 | EXPECT_TRUE(emptySet.lower_bound(10) == emptySet.end()); |
485 | EXPECT_TRUE(emptySet.find(10) == emptySet.end()); |
486 | |
487 | sorted_vector_map<int, int> emptyMap; |
488 | EXPECT_TRUE(emptyMap.lower_bound(10) == emptyMap.end()); |
489 | EXPECT_TRUE(emptyMap.find(10) == emptyMap.end()); |
490 | EXPECT_THROW(emptyMap.at(10), std::out_of_range); |
491 | } |
492 | |
493 | TEST(SortedVectorTest, MoveTest) { |
494 | sorted_vector_set<std::unique_ptr<int>> s; |
495 | s.insert(std::make_unique<int>(5)); |
496 | s.insert(s.end(), std::make_unique<int>(10)); |
497 | EXPECT_EQ(s.size(), 2); |
498 | |
499 | for (const auto& p : s) { |
500 | EXPECT_TRUE(*p == 5 || *p == 10); |
501 | } |
502 | |
503 | sorted_vector_map<int, std::unique_ptr<int>> m; |
504 | m.insert(std::make_pair(5, std::make_unique<int>(5))); |
505 | m.insert(m.end(), std::make_pair(10, std::make_unique<int>(10))); |
506 | |
507 | EXPECT_EQ(*m[5], 5); |
508 | EXPECT_EQ(*m[10], 10); |
509 | } |
510 | |
511 | TEST(SortedVectorTest, ShrinkTest) { |
512 | sorted_vector_set<int> s; |
513 | int i = 0; |
514 | // Hopefully your resize policy doubles when capacity is full, or this will |
515 | // hang forever :( |
516 | while (s.capacity() == s.size()) { |
517 | s.insert(i++); |
518 | } |
519 | s.shrink_to_fit(); |
520 | // The standard does not actually enforce that this be true, but assume that |
521 | // vector::shrink_to_fit respects the caller. |
522 | EXPECT_EQ(s.capacity(), s.size()); |
523 | } |
524 | |
525 | TEST(SortedVectorTypes, EraseTest) { |
526 | sorted_vector_set<int> s1; |
527 | s1.insert(1); |
528 | sorted_vector_set<int> s2(s1); |
529 | EXPECT_EQ(0, s1.erase(0)); |
530 | EXPECT_EQ(s2, s1); |
531 | } |
532 | |
533 | TEST(SortedVectorTypes, EraseTest2) { |
534 | sorted_vector_set<int> s; |
535 | for (int i = 0; i < 1000; ++i) { |
536 | s.insert(i); |
537 | } |
538 | |
539 | auto it = s.lower_bound(32); |
540 | EXPECT_EQ(*it, 32); |
541 | it = s.erase(it); |
542 | EXPECT_NE(s.end(), it); |
543 | EXPECT_EQ(*it, 33); |
544 | it = s.erase(it, it + 5); |
545 | EXPECT_EQ(*it, 38); |
546 | |
547 | it = s.begin(); |
548 | while (it != s.end()) { |
549 | if (*it >= 5) { |
550 | it = s.erase(it); |
551 | } else { |
552 | it++; |
553 | } |
554 | } |
555 | EXPECT_EQ(it, s.end()); |
556 | EXPECT_EQ(s.size(), 5); |
557 | |
558 | sorted_vector_map<int, int> m; |
559 | for (int i = 0; i < 1000; ++i) { |
560 | m.insert(std::make_pair(i, i)); |
561 | } |
562 | |
563 | auto it2 = m.lower_bound(32); |
564 | EXPECT_EQ(it2->first, 32); |
565 | it2 = m.erase(it2); |
566 | EXPECT_NE(m.end(), it2); |
567 | EXPECT_EQ(it2->first, 33); |
568 | it2 = m.erase(it2, it2 + 5); |
569 | EXPECT_EQ(it2->first, 38); |
570 | |
571 | it2 = m.begin(); |
572 | while (it2 != m.end()) { |
573 | if (it2->first >= 5) { |
574 | it2 = m.erase(it2); |
575 | } else { |
576 | it2++; |
577 | } |
578 | } |
579 | EXPECT_EQ(it2, m.end()); |
580 | EXPECT_EQ(m.size(), 5); |
581 | } |
582 | |
583 | std::vector<int> (sorted_vector_set<CountCopyCtor> const& in) { |
584 | std::vector<int> ret; |
585 | std::transform( |
586 | in.begin(), |
587 | in.end(), |
588 | std::back_inserter(ret), |
589 | [](const CountCopyCtor& c) { return c.val_; }); |
590 | return ret; |
591 | } |
592 | |
593 | template <typename T, typename S> |
594 | std::vector<T> (std::vector<S> ss) { |
595 | std::vector<T> ts; |
596 | ts.reserve(ss.size()); |
597 | for (auto const& s : ss) { |
598 | ts.emplace_back(s); |
599 | } |
600 | return ts; |
601 | } |
602 | |
603 | TEST(SortedVectorTypes, TestSetBulkInsertionSortMerge) { |
604 | auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2}); |
605 | |
606 | sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end()); |
607 | check_invariant(vset); |
608 | |
609 | // Add an unsorted range that will have to be merged in. |
610 | s = makeVectorOfWrappers<CountCopyCtor, int>({10, 7, 5, 1}); |
611 | |
612 | vset.insert(s.begin(), s.end()); |
613 | check_invariant(vset); |
614 | EXPECT_EQ(vset.rbegin()->count_, 1); |
615 | |
616 | EXPECT_THAT( |
617 | extractValues(vset), |
618 | testing::ElementsAreArray({1, 2, 4, 5, 6, 7, 8, 10})); |
619 | } |
620 | |
621 | TEST(SortedVectorTypes, TestSetBulkInsertionMiddleValuesEqualDuplication) { |
622 | auto s = makeVectorOfWrappers<CountCopyCtor, int>({4, 6, 8}); |
623 | |
624 | sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end()); |
625 | check_invariant(vset); |
626 | |
627 | s = makeVectorOfWrappers<CountCopyCtor, int>({8, 10, 12}); |
628 | |
629 | vset.insert(s.begin(), s.end()); |
630 | check_invariant(vset); |
631 | EXPECT_EQ(vset.rbegin()->count_, 1); |
632 | |
633 | EXPECT_THAT( |
634 | extractValues(vset), testing::ElementsAreArray({4, 6, 8, 10, 12})); |
635 | } |
636 | |
637 | TEST(SortedVectorTypes, TestSetBulkInsertionSortMergeDups) { |
638 | auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2}); |
639 | |
640 | sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end()); |
641 | check_invariant(vset); |
642 | |
643 | // Add an unsorted range that will have to be merged in. |
644 | s = makeVectorOfWrappers<CountCopyCtor, int>({10, 6, 5, 2}); |
645 | |
646 | vset.insert(s.begin(), s.end()); |
647 | check_invariant(vset); |
648 | EXPECT_EQ(vset.rbegin()->count_, 1); |
649 | EXPECT_THAT( |
650 | extractValues(vset), testing::ElementsAreArray({2, 4, 5, 6, 8, 10})); |
651 | } |
652 | |
653 | TEST(SortedVectorTypes, TestSetInsertionDupsOneByOne) { |
654 | auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2}); |
655 | |
656 | sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end()); |
657 | check_invariant(vset); |
658 | |
659 | // Add an unsorted range that will have to be merged in. |
660 | s = makeVectorOfWrappers<CountCopyCtor, int>({10, 6, 5, 2}); |
661 | |
662 | for (const auto& elem : s) { |
663 | vset.insert(elem); |
664 | } |
665 | check_invariant(vset); |
666 | EXPECT_EQ(vset.rbegin()->count_, 2); |
667 | EXPECT_THAT( |
668 | extractValues(vset), testing::ElementsAreArray({2, 4, 5, 6, 8, 10})); |
669 | } |
670 | |
671 | TEST(SortedVectorTypes, TestSetBulkInsertionSortNoMerge) { |
672 | auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2}); |
673 | |
674 | sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end()); |
675 | check_invariant(vset); |
676 | |
677 | // Add an unsorted range that will not have to be merged in. |
678 | s = makeVectorOfWrappers<CountCopyCtor, int>({20, 15, 16, 13}); |
679 | |
680 | vset.insert(s.begin(), s.end()); |
681 | check_invariant(vset); |
682 | EXPECT_EQ(vset.rbegin()->count_, 1); |
683 | EXPECT_THAT( |
684 | extractValues(vset), |
685 | testing::ElementsAreArray({2, 4, 6, 8, 13, 15, 16, 20})); |
686 | } |
687 | |
688 | TEST(SortedVectorTypes, TestSetBulkInsertionNoSortMerge) { |
689 | auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2}); |
690 | |
691 | sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end()); |
692 | check_invariant(vset); |
693 | |
694 | // Add a sorted range that will have to be merged in. |
695 | s = makeVectorOfWrappers<CountCopyCtor, int>({1, 3, 5, 9}); |
696 | |
697 | vset.insert(s.begin(), s.end()); |
698 | check_invariant(vset); |
699 | EXPECT_EQ(vset.rbegin()->count_, 1); |
700 | EXPECT_THAT( |
701 | extractValues(vset), testing::ElementsAreArray({1, 2, 3, 4, 5, 6, 8, 9})); |
702 | } |
703 | |
704 | TEST(SortedVectorTypes, TestSetBulkInsertionNoSortNoMerge) { |
705 | auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2}); |
706 | |
707 | sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end()); |
708 | check_invariant(vset); |
709 | |
710 | // Add a sorted range that will not have to be merged in. |
711 | s = makeVectorOfWrappers<CountCopyCtor, int>({21, 22, 23, 24}); |
712 | |
713 | vset.insert(s.begin(), s.end()); |
714 | check_invariant(vset); |
715 | EXPECT_EQ(vset.rbegin()->count_, 1); |
716 | EXPECT_THAT( |
717 | extractValues(vset), |
718 | testing::ElementsAreArray({2, 4, 6, 8, 21, 22, 23, 24})); |
719 | } |
720 | |
721 | TEST(SortedVectorTypes, TestSetBulkInsertionEmptyRange) { |
722 | std::vector<CountCopyCtor> s; |
723 | EXPECT_TRUE(s.empty()); |
724 | |
725 | // insertion of empty range into empty container. |
726 | sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end()); |
727 | check_invariant(vset); |
728 | |
729 | s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2}); |
730 | |
731 | vset.insert(s.begin(), s.end()); |
732 | |
733 | // insertion of empty range into non-empty container. |
734 | s.clear(); |
735 | vset.insert(s.begin(), s.end()); |
736 | check_invariant(vset); |
737 | |
738 | EXPECT_THAT(extractValues(vset), testing::ElementsAreArray({2, 4, 6, 8})); |
739 | } |
740 | |
741 | // This is a test of compilation - the behavior has already been tested |
742 | // extensively above. |
743 | TEST(SortedVectorTypes, TestBulkInsertionUncopyableTypes) { |
744 | std::vector<std::pair<int, std::unique_ptr<int>>> s; |
745 | s.emplace_back(1, std::make_unique<int>(0)); |
746 | |
747 | sorted_vector_map<int, std::unique_ptr<int>> vmap( |
748 | std::make_move_iterator(s.begin()), std::make_move_iterator(s.end())); |
749 | |
750 | s.clear(); |
751 | s.emplace_back(3, std::make_unique<int>(0)); |
752 | vmap.insert( |
753 | std::make_move_iterator(s.begin()), std::make_move_iterator(s.end())); |
754 | } |
755 | |
756 | // A moveable and copyable struct, which we use to make sure that no copy |
757 | // operations are performed during bulk insertion if moving is an option. |
758 | struct Movable { |
759 | int x_; |
760 | explicit Movable(int x) : x_(x) {} |
761 | Movable(const Movable&) { |
762 | ADD_FAILURE() << "Copy ctor should not be called" ; |
763 | } |
764 | Movable& operator=(const Movable&) { |
765 | ADD_FAILURE() << "Copy assignment should not be called" ; |
766 | return *this; |
767 | } |
768 | |
769 | Movable(Movable&&) = default; |
770 | Movable& operator=(Movable&&) = default; |
771 | }; |
772 | |
773 | TEST(SortedVectorTypes, TestBulkInsertionMovableTypes) { |
774 | std::vector<std::pair<int, Movable>> s; |
775 | s.emplace_back(3, Movable(2)); |
776 | s.emplace_back(1, Movable(0)); |
777 | |
778 | sorted_vector_map<int, Movable> vmap( |
779 | std::make_move_iterator(s.begin()), std::make_move_iterator(s.end())); |
780 | |
781 | s.clear(); |
782 | s.emplace_back(4, Movable(3)); |
783 | s.emplace_back(2, Movable(1)); |
784 | vmap.insert( |
785 | std::make_move_iterator(s.begin()), std::make_move_iterator(s.end())); |
786 | } |
787 | |
788 | TEST(SortedVectorTypes, TestSetCreationFromVector) { |
789 | std::vector<int> vec = {3, 1, -1, 5, 0}; |
790 | sorted_vector_set<int> vset(std::move(vec)); |
791 | check_invariant(vset); |
792 | EXPECT_THAT(vset, testing::ElementsAreArray({-1, 0, 1, 3, 5})); |
793 | } |
794 | |
795 | TEST(SortedVectorTypes, TestMapCreationFromVector) { |
796 | std::vector<std::pair<int, int>> vec = { |
797 | {3, 1}, {1, 5}, {-1, 2}, {5, 3}, {0, 3}}; |
798 | sorted_vector_map<int, int> vmap(std::move(vec)); |
799 | check_invariant(vmap); |
800 | auto contents = std::vector<std::pair<int, int>>(vmap.begin(), vmap.end()); |
801 | auto expected_contents = std::vector<std::pair<int, int>>({ |
802 | {-1, 2}, |
803 | {0, 3}, |
804 | {1, 5}, |
805 | {3, 1}, |
806 | {5, 3}, |
807 | }); |
808 | EXPECT_EQ(contents, expected_contents); |
809 | } |
810 | |
811 | TEST(SortedVectorTypes, TestBulkInsertionWithDuplicatesIntoEmptySet) { |
812 | sorted_vector_set<int> set; |
813 | { |
814 | std::vector<int> const vec = {0, 1, 0, 1}; |
815 | set.insert(vec.begin(), vec.end()); |
816 | } |
817 | EXPECT_THAT(set, testing::ElementsAreArray({0, 1})); |
818 | } |
819 | |
820 | TEST(SortedVectorTypes, TestDataPointsToFirstElement) { |
821 | sorted_vector_set<int> set; |
822 | sorted_vector_map<int, int> map; |
823 | |
824 | set.insert(0); |
825 | map[0] = 0; |
826 | EXPECT_EQ(set.data(), &*set.begin()); |
827 | EXPECT_EQ(map.data(), &*map.begin()); |
828 | |
829 | set.insert(1); |
830 | map[1] = 1; |
831 | EXPECT_EQ(set.data(), &*set.begin()); |
832 | EXPECT_EQ(map.data(), &*map.begin()); |
833 | } |
834 | |