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
28using folly::sorted_vector_map;
29using folly::sorted_vector_set;
30
31namespace {
32
33template <class T>
34struct less_invert {
35 bool operator()(const T& a, const T& b) const {
36 return b < a;
37 }
38};
39
40template <class Container>
41void 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
54struct 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
63struct 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
78struct 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
101TEST(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
110TEST(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
121TEST(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
197TEST(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
246TEST(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
261TEST(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
326TEST(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
376TEST(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
400TEST(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
430TEST(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
444TEST(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
482TEST(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
493TEST(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
511TEST(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
525TEST(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
533TEST(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
583std::vector<int> extractValues(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
593template <typename T, typename S>
594std::vector<T> makeVectorOfWrappers(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
603TEST(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
621TEST(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
637TEST(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
653TEST(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
671TEST(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
688TEST(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
704TEST(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
721TEST(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.
743TEST(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.
758struct 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
773TEST(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
788TEST(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
795TEST(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
811TEST(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
820TEST(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