folly/test/sorted_vector_test.cpp

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