2 * Copyright 2017 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 #include <folly/sorted_vector_types.h>
23 #include <folly/portability/GMock.h>
24 #include <folly/portability/GTest.h>
26 using folly::sorted_vector_set;
27 using folly::sorted_vector_map;
33 bool operator()(const T& a, const T& b) const {
38 template <class Container>
39 void check_invariant(Container& c) {
46 for (; it != end; ++it, ++prev) {
47 EXPECT_TRUE(c.value_comp()(*prev, *it));
51 struct OneAtATimePolicy {
52 template <class Container>
53 void increase_capacity(Container& c) {
54 if (c.size() == c.capacity()) {
55 c.reserve(c.size() + 1);
60 struct CountCopyCtor {
61 explicit CountCopyCtor() : val_(0) {}
63 explicit CountCopyCtor(int val) : val_(val), count_(0) {}
65 CountCopyCtor(const CountCopyCtor& c)
67 , count_(c.count_ + 1)
70 bool operator<(const CountCopyCtor& o) const {
80 TEST(SortedVectorTypes, SimpleSetTest) {
81 sorted_vector_set<int> s;
82 EXPECT_TRUE(s.empty());
83 for (int i = 0; i < 1000; ++i) {
84 s.insert(rand() % 100000);
86 EXPECT_FALSE(s.empty());
89 sorted_vector_set<int> s2;
90 s2.insert(s.begin(), s.end());
94 auto it = s2.lower_bound(32);
97 it = s2.lower_bound(32);
100 auto oldSz = s2.size();
102 EXPECT_TRUE(s2.size() == oldSz + 1);
105 const sorted_vector_set<int>& cs2 = s2;
106 auto range = cs2.equal_range(32);
107 auto lbound = cs2.lower_bound(32);
108 auto ubound = cs2.upper_bound(32);
109 EXPECT_TRUE(range.first == lbound);
110 EXPECT_TRUE(range.second == ubound);
111 EXPECT_TRUE(range.first != cs2.end());
112 EXPECT_TRUE(range.second != cs2.end());
113 EXPECT_TRUE(cs2.count(32) == 1);
114 EXPECT_FALSE(cs2.find(32) == cs2.end());
117 s2.insert(s2.begin() + 3, 33);
118 EXPECT_TRUE(s2.find(33) != s2.begin());
119 EXPECT_TRUE(s2.find(33) != s2.end());
125 EXPECT_FALSE(it == s2.end());
127 EXPECT_TRUE(s2.size() == oldSz);
130 sorted_vector_set<int> cpy(s);
131 check_invariant(cpy);
132 EXPECT_TRUE(cpy == s);
133 sorted_vector_set<int> cpy2(s);
135 EXPECT_TRUE(cpy2 != cpy);
136 EXPECT_TRUE(cpy2 != s);
137 check_invariant(cpy2);
138 EXPECT_TRUE(cpy2.count(100001) == 1);
140 check_invariant(cpy2);
142 EXPECT_TRUE(s != cpy);
143 EXPECT_TRUE(s != cpy2);
144 EXPECT_TRUE(cpy2 == cpy);
147 TEST(SortedVectorTypes, BadHints) {
148 for (int toInsert = -1; toInsert <= 7; ++toInsert) {
149 for (int hintPos = 0; hintPos <= 4; ++hintPos) {
150 sorted_vector_set<int> s;
151 for (int i = 0; i <= 3; ++i) {
154 s.insert(s.begin() + hintPos, toInsert);
155 size_t expectedSize = (toInsert % 2) == 0 ? 4 : 5;
156 EXPECT_EQ(s.size(), expectedSize);
162 TEST(SortedVectorTypes, SimpleMapTest) {
163 sorted_vector_map<int,float> m;
164 for (int i = 0; i < 1000; ++i) {
171 EXPECT_TRUE(m.count(32) == 1);
172 EXPECT_DOUBLE_EQ(100.0, m.at(32));
173 EXPECT_FALSE(m.find(32) == m.end());
175 EXPECT_TRUE(m.find(32) == m.end());
177 EXPECT_THROW(m.at(32), std::out_of_range);
179 sorted_vector_map<int,float> m2 = m;
180 EXPECT_TRUE(m2 == m);
181 EXPECT_FALSE(m2 != m);
182 auto it = m2.lower_bound(1 << 20);
183 EXPECT_TRUE(it == m2.end());
184 m2.insert(it, std::make_pair(1 << 20, 10.0f));
186 EXPECT_TRUE(m2.count(1 << 20) == 1);
188 EXPECT_TRUE(m <= m2);
190 const sorted_vector_map<int,float>& cm = m;
191 auto range = cm.equal_range(42);
192 auto lbound = cm.lower_bound(42);
193 auto ubound = cm.upper_bound(42);
194 EXPECT_TRUE(range.first == lbound);
195 EXPECT_TRUE(range.second == ubound);
196 EXPECT_FALSE(range.first == cm.end());
197 EXPECT_FALSE(range.second == cm.end());
198 m.erase(m.lower_bound(42));
201 sorted_vector_map<int,float> m3;
202 m3.insert(m2.begin(), m2.end());
204 EXPECT_TRUE(m3 == m2);
205 EXPECT_FALSE(m3 == m);
207 EXPECT_TRUE(m != m2);
208 EXPECT_TRUE(m2 == m3);
209 EXPECT_TRUE(m3 != m);
214 EXPECT_TRUE(m3 != m2);
215 EXPECT_TRUE(m3 != m);
216 EXPECT_TRUE(m == m2);
219 m.insert(m.begin() + 3, std::make_pair(1 << 15, 1.0f));
223 TEST(SortedVectorTypes, Sizes) {
224 EXPECT_EQ(sizeof(sorted_vector_set<int>),
225 sizeof(std::vector<int>));
226 EXPECT_EQ(sizeof(sorted_vector_map<int,int>),
227 sizeof(std::vector<std::pair<int,int> >));
229 typedef sorted_vector_set<int,std::less<int>,
230 std::allocator<int>,OneAtATimePolicy> SetT;
231 typedef sorted_vector_map<int,int,std::less<int>,
232 std::allocator<std::pair<int,int>>,OneAtATimePolicy> MapT;
234 EXPECT_EQ(sizeof(SetT), sizeof(std::vector<int>));
235 EXPECT_EQ(sizeof(MapT), sizeof(std::vector<std::pair<int,int> >));
238 TEST(SortedVectorTypes, InitializerLists) {
239 sorted_vector_set<int> empty_initialized_set{};
240 EXPECT_TRUE(empty_initialized_set.empty());
242 sorted_vector_set<int> singleton_initialized_set{1};
243 EXPECT_EQ(1, singleton_initialized_set.size());
244 EXPECT_EQ(1, *singleton_initialized_set.begin());
246 sorted_vector_set<int> forward_initialized_set{1, 2};
247 sorted_vector_set<int> backward_initialized_set{2, 1};
248 EXPECT_EQ(2, forward_initialized_set.size());
249 EXPECT_EQ(1, *forward_initialized_set.begin());
250 EXPECT_EQ(2, *forward_initialized_set.rbegin());
251 EXPECT_TRUE(forward_initialized_set == backward_initialized_set);
253 sorted_vector_map<int,int> empty_initialized_map{};
254 EXPECT_TRUE(empty_initialized_map.empty());
256 sorted_vector_map<int,int> singleton_initialized_map{{1,10}};
257 EXPECT_EQ(1, singleton_initialized_map.size());
258 EXPECT_EQ(10, singleton_initialized_map[1]);
260 sorted_vector_map<int,int> forward_initialized_map{{1,10}, {2,20}};
261 sorted_vector_map<int,int> backward_initialized_map{{2,20}, {1,10}};
262 EXPECT_EQ(2, forward_initialized_map.size());
263 EXPECT_EQ(10, forward_initialized_map[1]);
264 EXPECT_EQ(20, forward_initialized_map[2]);
265 EXPECT_TRUE(forward_initialized_map == backward_initialized_map);
268 TEST(SortedVectorTypes, CustomCompare) {
269 sorted_vector_set<int,less_invert<int> > s;
270 for (int i = 0; i < 200; ++i)
274 sorted_vector_map<int,float,less_invert<int> > m;
275 for (int i = 0; i < 200; ++i)
280 TEST(SortedVectorTypes, GrowthPolicy) {
281 typedef sorted_vector_set<CountCopyCtor,
282 std::less<CountCopyCtor>,
283 std::allocator<CountCopyCtor>,
288 for (int i = 0; i < 20; ++i) {
289 a.insert(CountCopyCtor(i));
292 SetT::iterator it = a.begin();
293 EXPECT_FALSE(it == a.end());
295 EXPECT_EQ(it->val_, 0);
296 // 1 copy for the initial insertion, 19 more for reallocs on the
297 // additional insertions.
298 EXPECT_EQ(it->count_, 20);
301 std::list<CountCopyCtor> v;
302 for (int i = 0; i < 20; ++i) {
303 v.emplace_back(20 + i);
305 a.insert(v.begin(), v.end());
309 EXPECT_FALSE(it == a.end());
311 EXPECT_EQ(it->val_, 0);
312 // Should be only 1 more copy for inserting this above range.
313 EXPECT_EQ(it->count_, 21);
317 TEST(SortedVectorTest, EmptyTest) {
318 sorted_vector_set<int> emptySet;
319 EXPECT_TRUE(emptySet.lower_bound(10) == emptySet.end());
320 EXPECT_TRUE(emptySet.find(10) == emptySet.end());
322 sorted_vector_map<int,int> emptyMap;
323 EXPECT_TRUE(emptyMap.lower_bound(10) == emptyMap.end());
324 EXPECT_TRUE(emptyMap.find(10) == emptyMap.end());
325 EXPECT_THROW(emptyMap.at(10), std::out_of_range);
328 TEST(SortedVectorTest, MoveTest) {
329 sorted_vector_set<std::unique_ptr<int>> s;
330 s.insert(std::unique_ptr<int>(new int(5)));
331 s.insert(s.end(), std::unique_ptr<int>(new int(10)));
332 EXPECT_EQ(s.size(), 2);
334 for (const auto& p : s) {
335 EXPECT_TRUE(*p == 5 || *p == 10);
338 sorted_vector_map<int, std::unique_ptr<int>> m;
339 m.insert(std::make_pair(5, std::unique_ptr<int>(new int(5))));
340 m.insert(m.end(), std::make_pair(10, std::unique_ptr<int>(new int(10))));
343 EXPECT_EQ(*m[10], 10);
346 TEST(SortedVectorTest, ShrinkTest) {
347 sorted_vector_set<int> s;
349 // Hopefully your resize policy doubles when capacity is full, or this will
351 while (s.capacity() == s.size()) {
355 // The standard does not actually enforce that this be true, but assume that
356 // vector::shrink_to_fit respects the caller.
357 EXPECT_EQ(s.capacity(), s.size());
360 TEST(SortedVectorTypes, EraseTest) {
361 sorted_vector_set<int> s1;
363 sorted_vector_set<int> s2(s1);
364 EXPECT_EQ(0, s1.erase(0));
368 std::vector<int> extractValues(sorted_vector_set<CountCopyCtor> const& in) {
369 std::vector<int> ret;
373 std::back_inserter(ret),
374 [](const CountCopyCtor& c) { return c.val_; });
378 template <typename T, typename S>
379 std::vector<T> makeVectorOfWrappers(std::vector<S> ss) {
381 ts.reserve(ss.size());
382 for (auto const& s : ss) {
388 TEST(SortedVectorTypes, TestSetBulkInsertionSortMerge) {
389 auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
391 sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
392 check_invariant(vset);
394 // Add an unsorted range that will have to be merged in.
395 s = makeVectorOfWrappers<CountCopyCtor, int>({10, 7, 5, 1});
397 vset.insert(s.begin(), s.end());
398 check_invariant(vset);
399 EXPECT_EQ(vset.rbegin()->count_, 1);
403 testing::ElementsAreArray({1, 2, 4, 5, 6, 7, 8, 10}));
406 TEST(SortedVectorTypes, TestSetBulkInsertionMiddleValuesEqualDuplication) {
407 auto s = makeVectorOfWrappers<CountCopyCtor, int>({4, 6, 8});
409 sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
410 check_invariant(vset);
412 s = makeVectorOfWrappers<CountCopyCtor, int>({8, 10, 12});
414 vset.insert(s.begin(), s.end());
415 check_invariant(vset);
416 EXPECT_EQ(vset.rbegin()->count_, 1);
420 testing::ElementsAreArray({4, 6, 8, 10, 12}));
423 TEST(SortedVectorTypes, TestSetBulkInsertionSortMergeDups) {
424 auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
426 sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
427 check_invariant(vset);
429 // Add an unsorted range that will have to be merged in.
430 s = makeVectorOfWrappers<CountCopyCtor, int>({10, 6, 5, 2});
432 vset.insert(s.begin(), s.end());
433 check_invariant(vset);
434 EXPECT_EQ(vset.rbegin()->count_, 1);
436 extractValues(vset), testing::ElementsAreArray({2, 4, 5, 6, 8, 10}));
439 TEST(SortedVectorTypes, TestSetInsertionDupsOneByOne) {
440 auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
442 sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
443 check_invariant(vset);
445 // Add an unsorted range that will have to be merged in.
446 s = makeVectorOfWrappers<CountCopyCtor, int>({10, 6, 5, 2});
448 for (const auto& elem : s) {
451 check_invariant(vset);
452 EXPECT_EQ(vset.rbegin()->count_, 3);
454 extractValues(vset), testing::ElementsAreArray({2, 4, 5, 6, 8, 10}));
457 TEST(SortedVectorTypes, TestSetBulkInsertionSortNoMerge) {
458 auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
460 sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
461 check_invariant(vset);
463 // Add an unsorted range that will not have to be merged in.
464 s = makeVectorOfWrappers<CountCopyCtor, int>({20, 15, 16, 13});
466 vset.insert(s.begin(), s.end());
467 check_invariant(vset);
468 EXPECT_EQ(vset.rbegin()->count_, 1);
471 testing::ElementsAreArray({2, 4, 6, 8, 13, 15, 16, 20}));
474 TEST(SortedVectorTypes, TestSetBulkInsertionNoSortMerge) {
475 auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
477 sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
478 check_invariant(vset);
480 // Add a sorted range that will have to be merged in.
481 s = makeVectorOfWrappers<CountCopyCtor, int>({1, 3, 5, 9});
483 vset.insert(s.begin(), s.end());
484 check_invariant(vset);
485 EXPECT_EQ(vset.rbegin()->count_, 1);
487 extractValues(vset), testing::ElementsAreArray({1, 2, 3, 4, 5, 6, 8, 9}));
490 TEST(SortedVectorTypes, TestSetBulkInsertionNoSortNoMerge) {
491 auto s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
493 sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
494 check_invariant(vset);
496 // Add a sorted range that will not have to be merged in.
497 s = makeVectorOfWrappers<CountCopyCtor, int>({21, 22, 23, 24});
499 vset.insert(s.begin(), s.end());
500 check_invariant(vset);
501 EXPECT_EQ(vset.rbegin()->count_, 1);
504 testing::ElementsAreArray({2, 4, 6, 8, 21, 22, 23, 24}));
507 TEST(SortedVectorTypes, TestSetBulkInsertionEmptyRange) {
508 std::vector<CountCopyCtor> s;
509 EXPECT_TRUE(s.empty());
511 // insertion of empty range into empty container.
512 sorted_vector_set<CountCopyCtor> vset(s.begin(), s.end());
513 check_invariant(vset);
515 s = makeVectorOfWrappers<CountCopyCtor, int>({6, 4, 8, 2});
517 vset.insert(s.begin(), s.end());
519 // insertion of empty range into non-empty container.
521 vset.insert(s.begin(), s.end());
522 check_invariant(vset);
524 EXPECT_THAT(extractValues(vset), testing::ElementsAreArray({2, 4, 6, 8}));
527 // This is a test of compilation - the behavior has already been tested
528 // extensively above.
529 TEST(SortedVectorTypes, TestBulkInsertionUncopyableTypes) {
530 std::vector<std::pair<int, std::unique_ptr<int>>> s;
531 s.emplace_back(1, std::make_unique<int>(0));
533 sorted_vector_map<int, std::unique_ptr<int>> vmap(
534 std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
537 s.emplace_back(3, std::make_unique<int>(0));
539 std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
542 // A moveable and copyable struct, which we use to make sure that no copy
543 // operations are performed during bulk insertion if moving is an option.
546 explicit Movable(int x) : x_(x) {}
547 Movable(const Movable&) {
548 ADD_FAILURE() << "Copy ctor should not be called";
550 Movable& operator=(const Movable&) {
551 ADD_FAILURE() << "Copy assignment should not be called";
555 Movable(Movable&&) = default;
556 Movable& operator=(Movable&&) = default;
559 TEST(SortedVectorTypes, TestBulkInsertionMovableTypes) {
560 std::vector<std::pair<int, Movable>> s;
561 s.emplace_back(3, Movable(2));
562 s.emplace_back(1, Movable(0));
564 sorted_vector_map<int, Movable> vmap(
565 std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
568 s.emplace_back(4, Movable(3));
569 s.emplace_back(2, Movable(1));
571 std::make_move_iterator(s.begin()), std::make_move_iterator(s.end()));
574 TEST(SortedVectorTypes, TestSetCreationFromVector) {
575 std::vector<int> vec = {3, 1, -1, 5, 0};
576 sorted_vector_set<int> vset(std::move(vec));
577 check_invariant(vset);
578 EXPECT_THAT(vset, testing::ElementsAreArray({-1, 0, 1, 3, 5}));
581 TEST(SortedVectorTypes, TestMapCreationFromVector) {
582 std::vector<std::pair<int, int>> vec = {
583 {3, 1}, {1, 5}, {-1, 2}, {5, 3}, {0, 3}};
584 sorted_vector_map<int, int> vmap(std::move(vec));
585 check_invariant(vmap);
586 auto contents = std::vector<std::pair<int, int>>(vmap.begin(), vmap.end());
587 auto expected_contents = std::vector<std::pair<int, int>>({
588 {-1, 2}, {0, 3}, {1, 5}, {3, 1}, {5, 3},
590 EXPECT_EQ(contents, expected_contents);