1 // Copyright 2017 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4 
5 #include "base/containers/flat_tree.h"
6 
7 // Following tests are ported and extended tests from libcpp for std::set.
8 // They can be found here:
9 // https://github.com/llvm-mirror/libcxx/tree/master/test/std/containers/associative/set
10 //
11 // Not ported tests:
12 // * No tests with PrivateConstructor and std::less<> changed to std::less<T>
13 //   These tests have to do with C++14 std::less<>
14 //   http://en.cppreference.com/w/cpp/utility/functional/less_void
15 //   and add support for templated versions of lookup functions.
16 //   Because we use same implementation, we figured that it's OK just to check
17 //   compilation and this is what we do in flat_set_unittest/flat_map_unittest.
18 // * No tests for max_size()
19 //   Has to do with allocator support.
20 // * No tests with DefaultOnly.
21 //   Standard containers allocate each element in the separate node on the heap
22 //   and then manipulate these nodes. Flat containers store their elements in
23 //   contiguous memory and move them around, type is required to be movable.
24 // * No tests for N3644.
25 //   This proposal suggests that all default constructed iterators compare
26 //   equal. Currently we use std::vector iterators and they don't implement
27 //   this.
28 // * No tests with min_allocator and no tests counting allocations.
29 //   Flat sets currently don't support allocators.
30 
31 #include <forward_list>
32 #include <functional>
33 #include <iterator>
34 #include <list>
35 #include <string>
36 #include <vector>
37 
38 #include "base/macros.h"
39 #include "base/template_util.h"
40 #include "base/test/move_only_int.h"
41 #include "testing/gmock/include/gmock/gmock.h"
42 #include "testing/gtest/include/gtest/gtest.h"
43 
44 namespace base {
45 namespace internal {
46 
47 namespace {
48 
49 template <class It>
50 class InputIterator {
51  public:
52   using iterator_category = std::input_iterator_tag;
53   using value_type = typename std::iterator_traits<It>::value_type;
54   using difference_type = typename std::iterator_traits<It>::difference_type;
55   using pointer = It;
56   using reference = typename std::iterator_traits<It>::reference;
57 
InputIterator()58   InputIterator() : it_() {}
InputIterator(It it)59   explicit InputIterator(It it) : it_(it) {}
60 
operator *() const61   reference operator*() const { return *it_; }
operator ->() const62   pointer operator->() const { return it_; }
63 
operator ++()64   InputIterator& operator++() {
65     ++it_;
66     return *this;
67   }
operator ++(int)68   InputIterator operator++(int) {
69     InputIterator tmp(*this);
70     ++(*this);
71     return tmp;
72   }
73 
operator ==(const InputIterator & lhs,const InputIterator & rhs)74   friend bool operator==(const InputIterator& lhs, const InputIterator& rhs) {
75     return lhs.it_ == rhs.it_;
76   }
operator !=(const InputIterator & lhs,const InputIterator & rhs)77   friend bool operator!=(const InputIterator& lhs, const InputIterator& rhs) {
78     return !(lhs == rhs);
79   }
80 
81  private:
82   It it_;
83 };
84 
85 template <typename It>
MakeInputIterator(It it)86 InputIterator<It> MakeInputIterator(It it) {
87   return InputIterator<It>(it);
88 }
89 
90 class Emplaceable {
91  public:
Emplaceable()92   Emplaceable() : Emplaceable(0, 0.0) {}
Emplaceable(int i,double d)93   Emplaceable(int i, double d) : int_(i), double_(d) {}
Emplaceable(Emplaceable && other)94   Emplaceable(Emplaceable&& other) : int_(other.int_), double_(other.double_) {
95     other.int_ = 0;
96     other.double_ = 0.0;
97   }
98 
operator =(Emplaceable && other)99   Emplaceable& operator=(Emplaceable&& other) {
100     int_ = other.int_;
101     other.int_ = 0;
102     double_ = other.double_;
103     other.double_ = 0.0;
104     return *this;
105   }
106 
operator ==(const Emplaceable & lhs,const Emplaceable & rhs)107   friend bool operator==(const Emplaceable& lhs, const Emplaceable& rhs) {
108     return std::tie(lhs.int_, lhs.double_) == std::tie(rhs.int_, rhs.double_);
109   }
110 
operator <(const Emplaceable & lhs,const Emplaceable & rhs)111   friend bool operator<(const Emplaceable& lhs, const Emplaceable& rhs) {
112     return std::tie(lhs.int_, lhs.double_) < std::tie(rhs.int_, rhs.double_);
113   }
114 
115  private:
116   int int_;
117   double double_;
118 
119   DISALLOW_COPY_AND_ASSIGN(Emplaceable);
120 };
121 
122 struct TemplateConstructor {
123   template <typename T>
TemplateConstructorbase::internal::__anon5cec0eed0111::TemplateConstructor124   TemplateConstructor(const T&) {}
125 
operator <(const TemplateConstructor &,const TemplateConstructor &)126   friend bool operator<(const TemplateConstructor&,
127                         const TemplateConstructor&) {
128     return false;
129   }
130 };
131 
132 class NonDefaultConstructibleCompare {
133  public:
NonDefaultConstructibleCompare(int)134   explicit NonDefaultConstructibleCompare(int) {}
135 
136   template <typename T>
operator ()(const T & lhs,const T & rhs) const137   bool operator()(const T& lhs, const T& rhs) const {
138     return std::less<T>()(lhs, rhs);
139   }
140 };
141 
142 template <class PairType>
143 struct LessByFirst {
operator ()base::internal::__anon5cec0eed0111::LessByFirst144   bool operator()(const PairType& lhs, const PairType& rhs) const {
145     return lhs.first < rhs.first;
146   }
147 };
148 
149 // Common test trees.
150 using IntTree =
151     flat_tree<int, int, GetKeyFromValueIdentity<int>, std::less<int>>;
152 using IntPair = std::pair<int, int>;
153 using IntPairTree = flat_tree<IntPair,
154                               IntPair,
155                               GetKeyFromValueIdentity<IntPair>,
156                               LessByFirst<IntPair>>;
157 using MoveOnlyTree = flat_tree<MoveOnlyInt,
158                                MoveOnlyInt,
159                                GetKeyFromValueIdentity<MoveOnlyInt>,
160                                std::less<MoveOnlyInt>>;
161 using EmplaceableTree = flat_tree<Emplaceable,
162                                   Emplaceable,
163                                   GetKeyFromValueIdentity<Emplaceable>,
164                                   std::less<Emplaceable>>;
165 using ReversedTree =
166     flat_tree<int, int, GetKeyFromValueIdentity<int>, std::greater<int>>;
167 
168 using TreeWithStrangeCompare = flat_tree<int,
169                                          int,
170                                          GetKeyFromValueIdentity<int>,
171                                          NonDefaultConstructibleCompare>;
172 
173 using ::testing::ElementsAre;
174 
175 }  // namespace
176 
TEST(FlatTree,IsMultipass)177 TEST(FlatTree, IsMultipass) {
178   static_assert(!is_multipass<std::istream_iterator<int>>(),
179                 "InputIterator is not multipass");
180   static_assert(!is_multipass<std::ostream_iterator<int>>(),
181                 "OutputIterator is not multipass");
182 
183   static_assert(is_multipass<std::forward_list<int>::iterator>(),
184                 "ForwardIterator is multipass");
185   static_assert(is_multipass<std::list<int>::iterator>(),
186                 "BidirectionalIterator is multipass");
187   static_assert(is_multipass<std::vector<int>::iterator>(),
188                 "RandomAccessIterator is multipass");
189 }
190 
TEST(FlatTree,LastUnique)191 TEST(FlatTree, LastUnique) {
192   using Pair = std::pair<int, int>;
193   using Vect = std::vector<Pair>;
194 
195   auto cmp = [](const Pair& lhs, const Pair& rhs) {
196     return lhs.first == rhs.first;
197   };
198 
199   // Empty case.
200   Vect empty;
201   EXPECT_EQ(empty.end(), LastUnique(empty.begin(), empty.end(), cmp));
202 
203   // Single element.
204   Vect one;
205   one.push_back(Pair(1, 1));
206   EXPECT_EQ(one.end(), LastUnique(one.begin(), one.end(), cmp));
207   ASSERT_EQ(1u, one.size());
208   EXPECT_THAT(one, ElementsAre(Pair(1, 1)));
209 
210   // Two elements, already unique.
211   Vect two_u;
212   two_u.push_back(Pair(1, 1));
213   two_u.push_back(Pair(2, 2));
214   EXPECT_EQ(two_u.end(), LastUnique(two_u.begin(), two_u.end(), cmp));
215   EXPECT_THAT(two_u, ElementsAre(Pair(1, 1), Pair(2, 2)));
216 
217   // Two elements, dupes.
218   Vect two_d;
219   two_d.push_back(Pair(1, 1));
220   two_d.push_back(Pair(1, 2));
221   auto last = LastUnique(two_d.begin(), two_d.end(), cmp);
222   EXPECT_EQ(two_d.begin() + 1, last);
223   two_d.erase(last, two_d.end());
224   EXPECT_THAT(two_d, ElementsAre(Pair(1, 2)));
225 
226   // Non-dupes, dupes, non-dupes.
227   Vect ndn;
228   ndn.push_back(Pair(1, 1));
229   ndn.push_back(Pair(2, 1));
230   ndn.push_back(Pair(2, 2));
231   ndn.push_back(Pair(2, 3));
232   ndn.push_back(Pair(3, 1));
233   last = LastUnique(ndn.begin(), ndn.end(), cmp);
234   EXPECT_EQ(ndn.begin() + 3, last);
235   ndn.erase(last, ndn.end());
236   EXPECT_THAT(ndn, ElementsAre(Pair(1, 1), Pair(2, 3), Pair(3, 1)));
237 
238   // Dupes, non-dupes, dupes.
239   Vect dnd;
240   dnd.push_back(Pair(1, 1));
241   dnd.push_back(Pair(1, 2));
242   dnd.push_back(Pair(1, 3));
243   dnd.push_back(Pair(2, 1));
244   dnd.push_back(Pair(3, 1));
245   dnd.push_back(Pair(3, 2));
246   dnd.push_back(Pair(3, 3));
247   last = LastUnique(dnd.begin(), dnd.end(), cmp);
248   EXPECT_EQ(dnd.begin() + 3, last);
249   dnd.erase(last, dnd.end());
250   EXPECT_THAT(dnd, ElementsAre(Pair(1, 3), Pair(2, 1), Pair(3, 3)));
251 }
252 
253 // ----------------------------------------------------------------------------
254 // Class.
255 
256 // Check that flat_tree and its iterators can be instantiated with an
257 // incomplete type.
258 
TEST(FlatTree,IncompleteType)259 TEST(FlatTree, IncompleteType) {
260   struct A {
261     using Tree = flat_tree<A, A, GetKeyFromValueIdentity<A>, std::less<A>>;
262     int data;
263     Tree set_with_incomplete_type;
264     Tree::iterator it;
265     Tree::const_iterator cit;
266 
267     // We do not declare operator< because clang complains that it's unused.
268   };
269 
270   A a;
271 }
272 
TEST(FlatTree,Stability)273 TEST(FlatTree, Stability) {
274   using Pair = std::pair<int, int>;
275 
276   using Tree =
277       flat_tree<Pair, Pair, GetKeyFromValueIdentity<Pair>, LessByFirst<Pair>>;
278 
279   // Constructors are stable.
280   Tree cont({{0, 0}, {1, 0}, {0, 1}, {2, 0}, {0, 2}, {1, 1}});
281 
282   auto AllOfSecondsAreZero = [&cont] {
283     return std::all_of(cont.begin(), cont.end(),
284                        [](const Pair& elem) { return elem.second == 0; });
285   };
286 
287   EXPECT_TRUE(AllOfSecondsAreZero()) << "constructor should be stable";
288 
289   // Should not replace existing.
290   cont.insert(Pair(0, 2));
291   cont.insert(Pair(1, 2));
292   cont.insert(Pair(2, 2));
293 
294   EXPECT_TRUE(AllOfSecondsAreZero()) << "insert should be stable";
295 
296   cont.insert(Pair(3, 0));
297   cont.insert(Pair(3, 2));
298 
299   EXPECT_TRUE(AllOfSecondsAreZero()) << "insert should be stable";
300 }
301 
302 // ----------------------------------------------------------------------------
303 // Types.
304 
305 // key_type
306 // key_compare
307 // value_type
308 // value_compare
309 // pointer
310 // const_pointer
311 // reference
312 // const_reference
313 // size_type
314 // difference_type
315 // iterator
316 // const_iterator
317 // reverse_iterator
318 // const_reverse_iterator
319 
TEST(FlatTree,Types)320 TEST(FlatTree, Types) {
321   // These are guaranteed to be portable.
322   static_assert((std::is_same<int, IntTree::key_type>::value), "");
323   static_assert((std::is_same<int, IntTree::value_type>::value), "");
324   static_assert((std::is_same<std::less<int>, IntTree::key_compare>::value),
325                 "");
326   static_assert((std::is_same<int&, IntTree::reference>::value), "");
327   static_assert((std::is_same<const int&, IntTree::const_reference>::value),
328                 "");
329   static_assert((std::is_same<int*, IntTree::pointer>::value), "");
330   static_assert((std::is_same<const int*, IntTree::const_pointer>::value), "");
331 }
332 
333 // ----------------------------------------------------------------------------
334 // Lifetime.
335 
336 // flat_tree()
337 // flat_tree(const Compare& comp)
338 
TEST(FlatTree,DefaultConstructor)339 TEST(FlatTree, DefaultConstructor) {
340   {
341     IntTree cont;
342     EXPECT_THAT(cont, ElementsAre());
343   }
344 
345   {
346     TreeWithStrangeCompare cont(NonDefaultConstructibleCompare(0));
347     EXPECT_THAT(cont, ElementsAre());
348   }
349 }
350 
351 // flat_tree(InputIterator first,
352 //           InputIterator last,
353 //           FlatContainerDupes dupe_handling,
354 //           const Compare& comp = Compare())
355 
TEST(FlatTree,RangeConstructor)356 TEST(FlatTree, RangeConstructor) {
357   {
358     IntPair input_vals[] = {{1, 1}, {1, 2}, {2, 1}, {2, 2}, {1, 3},
359                             {2, 3}, {3, 1}, {3, 2}, {3, 3}};
360 
361     IntPairTree first_of(MakeInputIterator(std::begin(input_vals)),
362                          MakeInputIterator(std::end(input_vals)));
363     EXPECT_THAT(first_of,
364                 ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1)));
365 
366     IntPairTree last_of(MakeInputIterator(std::begin(input_vals)),
367                         MakeInputIterator(std::end(input_vals)),
368                         KEEP_LAST_OF_DUPES);
369     EXPECT_THAT(last_of,
370                 ElementsAre(IntPair(1, 3), IntPair(2, 3), IntPair(3, 3)));
371   }
372   {
373     TreeWithStrangeCompare::value_type input_vals[] = {1, 1, 1, 2, 2,
374                                                        2, 3, 3, 3};
375 
376     TreeWithStrangeCompare cont(MakeInputIterator(std::begin(input_vals)),
377                                 MakeInputIterator(std::end(input_vals)),
378                                 KEEP_FIRST_OF_DUPES,
379                                 NonDefaultConstructibleCompare(0));
380     EXPECT_THAT(cont, ElementsAre(1, 2, 3));
381   }
382 }
383 
384 // flat_tree(const flat_tree& x)
385 
TEST(FlatTree,CopyConstructor)386 TEST(FlatTree, CopyConstructor) {
387   IntTree original({1, 2, 3, 4});
388   IntTree copied(original);
389 
390   EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4));
391 
392   EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4));
393   EXPECT_THAT(original, ElementsAre(1, 2, 3, 4));
394   EXPECT_EQ(original, copied);
395 }
396 
397 // flat_tree(flat_tree&& x)
398 
TEST(FlatTree,MoveConstructor)399 TEST(FlatTree, MoveConstructor) {
400   int input_range[] = {1, 2, 3, 4};
401 
402   MoveOnlyTree original(std::begin(input_range), std::end(input_range));
403   MoveOnlyTree moved(std::move(original));
404 
405   EXPECT_EQ(1U, moved.count(MoveOnlyInt(1)));
406   EXPECT_EQ(1U, moved.count(MoveOnlyInt(2)));
407   EXPECT_EQ(1U, moved.count(MoveOnlyInt(3)));
408   EXPECT_EQ(1U, moved.count(MoveOnlyInt(4)));
409 }
410 
411 // flat_tree(std::vector<value_type>, FlatContainerDupes dupe_handling)
412 
TEST(FlatTree,VectorConstructor)413 TEST(FlatTree, VectorConstructor) {
414   using Pair = std::pair<int, MoveOnlyInt>;
415 
416   // Construct an unsorted vector with a duplicate item in it. Sorted by the
417   // first item, the second allows us to test for stability. Using a move
418   // only type to ensure the vector is not copied.
419   std::vector<Pair> storage;
420   storage.push_back(Pair(2, MoveOnlyInt(0)));
421   storage.push_back(Pair(1, MoveOnlyInt(0)));
422   storage.push_back(Pair(2, MoveOnlyInt(1)));
423 
424   using Tree =
425       flat_tree<Pair, Pair, GetKeyFromValueIdentity<Pair>, LessByFirst<Pair>>;
426   Tree tree(std::move(storage));
427 
428   // The list should be two items long, with only the first "2" saved.
429   ASSERT_EQ(2u, tree.size());
430   const Pair& zeroth = *tree.begin();
431   ASSERT_EQ(1, zeroth.first);
432   ASSERT_EQ(0, zeroth.second.data());
433 
434   const Pair& first = *(tree.begin() + 1);
435   ASSERT_EQ(2, first.first);
436   ASSERT_EQ(0, first.second.data());
437 
438   // Test KEEP_LAST_OF_DUPES with a simple vector constructor.
439   std::vector<IntPair> int_storage{{1, 1}, {1, 2}, {2, 1}};
440   IntPairTree int_tree(std::move(int_storage), KEEP_LAST_OF_DUPES);
441   EXPECT_THAT(int_tree, ElementsAre(IntPair(1, 2), IntPair(2, 1)));
442 }
443 
444 // flat_tree(std::initializer_list<value_type> ilist,
445 //           FlatContainerDupes dupe_handling,
446 //           const Compare& comp = Compare())
447 
TEST(FlatTree,InitializerListConstructor)448 TEST(FlatTree, InitializerListConstructor) {
449   {
450     IntTree cont({1, 2, 3, 4, 5, 6, 10, 8});
451     EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
452   }
453   {
454     IntTree cont({1, 2, 3, 4, 5, 6, 10, 8});
455     EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
456   }
457   {
458     TreeWithStrangeCompare cont({1, 2, 3, 4, 5, 6, 10, 8}, KEEP_FIRST_OF_DUPES,
459                                 NonDefaultConstructibleCompare(0));
460     EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
461   }
462   {
463     IntPairTree first_of({{1, 1}, {2, 1}, {1, 2}});
464     EXPECT_THAT(first_of, ElementsAre(IntPair(1, 1), IntPair(2, 1)));
465   }
466   {
467     IntPairTree last_of({{1, 1}, {2, 1}, {1, 2}}, KEEP_LAST_OF_DUPES);
468     EXPECT_THAT(last_of, ElementsAre(IntPair(1, 2), IntPair(2, 1)));
469   }
470 }
471 
472 // ----------------------------------------------------------------------------
473 // Assignments.
474 
475 // flat_tree& operator=(const flat_tree&)
476 
TEST(FlatTree,CopyAssignable)477 TEST(FlatTree, CopyAssignable) {
478   IntTree original({1, 2, 3, 4});
479   IntTree copied;
480   copied = original;
481 
482   EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4));
483   EXPECT_THAT(original, ElementsAre(1, 2, 3, 4));
484   EXPECT_EQ(original, copied);
485 }
486 
487 // flat_tree& operator=(flat_tree&&)
488 
TEST(FlatTree,MoveAssignable)489 TEST(FlatTree, MoveAssignable) {
490   int input_range[] = {1, 2, 3, 4};
491 
492   MoveOnlyTree original(std::begin(input_range), std::end(input_range));
493   MoveOnlyTree moved;
494   moved = std::move(original);
495 
496   EXPECT_EQ(1U, moved.count(MoveOnlyInt(1)));
497   EXPECT_EQ(1U, moved.count(MoveOnlyInt(2)));
498   EXPECT_EQ(1U, moved.count(MoveOnlyInt(3)));
499   EXPECT_EQ(1U, moved.count(MoveOnlyInt(4)));
500 }
501 
502 // flat_tree& operator=(std::initializer_list<value_type> ilist)
503 
TEST(FlatTree,InitializerListAssignable)504 TEST(FlatTree, InitializerListAssignable) {
505   IntTree cont({0});
506   cont = {1, 2, 3, 4, 5, 6, 10, 8};
507 
508   EXPECT_EQ(0U, cont.count(0));
509   EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
510 }
511 
512 // --------------------------------------------------------------------------
513 // Memory management.
514 
515 // void reserve(size_type new_capacity)
516 
TEST(FlatTree,Reserve)517 TEST(FlatTree, Reserve) {
518   IntTree cont({1, 2, 3});
519 
520   cont.reserve(5);
521   EXPECT_LE(5U, cont.capacity());
522 }
523 
524 // size_type capacity() const
525 
TEST(FlatTree,Capacity)526 TEST(FlatTree, Capacity) {
527   IntTree cont({1, 2, 3});
528 
529   EXPECT_LE(cont.size(), cont.capacity());
530   cont.reserve(5);
531   EXPECT_LE(cont.size(), cont.capacity());
532 }
533 
534 // void shrink_to_fit()
535 
TEST(FlatTree,ShrinkToFit)536 TEST(FlatTree, ShrinkToFit) {
537   IntTree cont({1, 2, 3});
538 
539   IntTree::size_type capacity_before = cont.capacity();
540   cont.shrink_to_fit();
541   EXPECT_GE(capacity_before, cont.capacity());
542 }
543 
544 // ----------------------------------------------------------------------------
545 // Size management.
546 
547 // void clear()
548 
TEST(FlatTree,Clear)549 TEST(FlatTree, Clear) {
550   IntTree cont({1, 2, 3, 4, 5, 6, 7, 8});
551   cont.clear();
552   EXPECT_THAT(cont, ElementsAre());
553 }
554 
555 // size_type size() const
556 
TEST(FlatTree,Size)557 TEST(FlatTree, Size) {
558   IntTree cont;
559 
560   EXPECT_EQ(0U, cont.size());
561   cont.insert(2);
562   EXPECT_EQ(1U, cont.size());
563   cont.insert(1);
564   EXPECT_EQ(2U, cont.size());
565   cont.insert(3);
566   EXPECT_EQ(3U, cont.size());
567   cont.erase(cont.begin());
568   EXPECT_EQ(2U, cont.size());
569   cont.erase(cont.begin());
570   EXPECT_EQ(1U, cont.size());
571   cont.erase(cont.begin());
572   EXPECT_EQ(0U, cont.size());
573 }
574 
575 // bool empty() const
576 
TEST(FlatTree,Empty)577 TEST(FlatTree, Empty) {
578   IntTree cont;
579 
580   EXPECT_TRUE(cont.empty());
581   cont.insert(1);
582   EXPECT_FALSE(cont.empty());
583   cont.clear();
584   EXPECT_TRUE(cont.empty());
585 }
586 
587 // ----------------------------------------------------------------------------
588 // Iterators.
589 
590 // iterator begin()
591 // const_iterator begin() const
592 // iterator end()
593 // const_iterator end() const
594 //
595 // reverse_iterator rbegin()
596 // const_reverse_iterator rbegin() const
597 // reverse_iterator rend()
598 // const_reverse_iterator rend() const
599 //
600 // const_iterator cbegin() const
601 // const_iterator cend() const
602 // const_reverse_iterator crbegin() const
603 // const_reverse_iterator crend() const
604 
TEST(FlatTree,Iterators)605 TEST(FlatTree, Iterators) {
606   IntTree cont({1, 2, 3, 4, 5, 6, 7, 8});
607 
608   auto size = static_cast<IntTree::difference_type>(cont.size());
609 
610   EXPECT_EQ(size, std::distance(cont.begin(), cont.end()));
611   EXPECT_EQ(size, std::distance(cont.cbegin(), cont.cend()));
612   EXPECT_EQ(size, std::distance(cont.rbegin(), cont.rend()));
613   EXPECT_EQ(size, std::distance(cont.crbegin(), cont.crend()));
614 
615   {
616     IntTree::iterator it = cont.begin();
617     IntTree::const_iterator c_it = cont.cbegin();
618     EXPECT_EQ(it, c_it);
619     for (int j = 1; it != cont.end(); ++it, ++c_it, ++j) {
620       EXPECT_EQ(j, *it);
621       EXPECT_EQ(j, *c_it);
622     }
623   }
624   {
625     IntTree::reverse_iterator rit = cont.rbegin();
626     IntTree::const_reverse_iterator c_rit = cont.crbegin();
627     EXPECT_EQ(rit, c_rit);
628     for (int j = static_cast<int>(size); rit != cont.rend();
629          ++rit, ++c_rit, --j) {
630       EXPECT_EQ(j, *rit);
631       EXPECT_EQ(j, *c_rit);
632     }
633   }
634 }
635 
636 // ----------------------------------------------------------------------------
637 // Insert operations.
638 
639 // pair<iterator, bool> insert(const value_type& val)
640 
TEST(FlatTree,InsertLValue)641 TEST(FlatTree, InsertLValue) {
642   IntTree cont;
643 
644   int value = 2;
645   std::pair<IntTree::iterator, bool> result = cont.insert(value);
646   EXPECT_TRUE(result.second);
647   EXPECT_EQ(cont.begin(), result.first);
648   EXPECT_EQ(1U, cont.size());
649   EXPECT_EQ(2, *result.first);
650 
651   value = 1;
652   result = cont.insert(value);
653   EXPECT_TRUE(result.second);
654   EXPECT_EQ(cont.begin(), result.first);
655   EXPECT_EQ(2U, cont.size());
656   EXPECT_EQ(1, *result.first);
657 
658   value = 3;
659   result = cont.insert(value);
660   EXPECT_TRUE(result.second);
661   EXPECT_EQ(std::prev(cont.end()), result.first);
662   EXPECT_EQ(3U, cont.size());
663   EXPECT_EQ(3, *result.first);
664 
665   value = 3;
666   result = cont.insert(value);
667   EXPECT_FALSE(result.second);
668   EXPECT_EQ(std::prev(cont.end()), result.first);
669   EXPECT_EQ(3U, cont.size());
670   EXPECT_EQ(3, *result.first);
671 }
672 
673 // pair<iterator, bool> insert(value_type&& val)
674 
TEST(FlatTree,InsertRValue)675 TEST(FlatTree, InsertRValue) {
676   MoveOnlyTree cont;
677 
678   std::pair<MoveOnlyTree::iterator, bool> result = cont.insert(MoveOnlyInt(2));
679   EXPECT_TRUE(result.second);
680   EXPECT_EQ(cont.begin(), result.first);
681   EXPECT_EQ(1U, cont.size());
682   EXPECT_EQ(2, result.first->data());
683 
684   result = cont.insert(MoveOnlyInt(1));
685   EXPECT_TRUE(result.second);
686   EXPECT_EQ(cont.begin(), result.first);
687   EXPECT_EQ(2U, cont.size());
688   EXPECT_EQ(1, result.first->data());
689 
690   result = cont.insert(MoveOnlyInt(3));
691   EXPECT_TRUE(result.second);
692   EXPECT_EQ(std::prev(cont.end()), result.first);
693   EXPECT_EQ(3U, cont.size());
694   EXPECT_EQ(3, result.first->data());
695 
696   result = cont.insert(MoveOnlyInt(3));
697   EXPECT_FALSE(result.second);
698   EXPECT_EQ(std::prev(cont.end()), result.first);
699   EXPECT_EQ(3U, cont.size());
700   EXPECT_EQ(3, result.first->data());
701 }
702 
703 // iterator insert(const_iterator position_hint, const value_type& val)
704 
TEST(FlatTree,InsertPositionLValue)705 TEST(FlatTree, InsertPositionLValue) {
706   IntTree cont;
707 
708   IntTree::iterator result = cont.insert(cont.cend(), 2);
709   EXPECT_EQ(cont.begin(), result);
710   EXPECT_EQ(1U, cont.size());
711   EXPECT_EQ(2, *result);
712 
713   result = cont.insert(cont.cend(), 1);
714   EXPECT_EQ(cont.begin(), result);
715   EXPECT_EQ(2U, cont.size());
716   EXPECT_EQ(1, *result);
717 
718   result = cont.insert(cont.cend(), 3);
719   EXPECT_EQ(std::prev(cont.end()), result);
720   EXPECT_EQ(3U, cont.size());
721   EXPECT_EQ(3, *result);
722 
723   result = cont.insert(cont.cend(), 3);
724   EXPECT_EQ(std::prev(cont.end()), result);
725   EXPECT_EQ(3U, cont.size());
726   EXPECT_EQ(3, *result);
727 }
728 
729 // iterator insert(const_iterator position_hint, value_type&& val)
730 
TEST(FlatTree,InsertPositionRValue)731 TEST(FlatTree, InsertPositionRValue) {
732   MoveOnlyTree cont;
733 
734   MoveOnlyTree::iterator result = cont.insert(cont.cend(), MoveOnlyInt(2));
735   EXPECT_EQ(cont.begin(), result);
736   EXPECT_EQ(1U, cont.size());
737   EXPECT_EQ(2, result->data());
738 
739   result = cont.insert(cont.cend(), MoveOnlyInt(1));
740   EXPECT_EQ(cont.begin(), result);
741   EXPECT_EQ(2U, cont.size());
742   EXPECT_EQ(1, result->data());
743 
744   result = cont.insert(cont.cend(), MoveOnlyInt(3));
745   EXPECT_EQ(std::prev(cont.end()), result);
746   EXPECT_EQ(3U, cont.size());
747   EXPECT_EQ(3, result->data());
748 
749   result = cont.insert(cont.cend(), MoveOnlyInt(3));
750   EXPECT_EQ(std::prev(cont.end()), result);
751   EXPECT_EQ(3U, cont.size());
752   EXPECT_EQ(3, result->data());
753 }
754 
755 // template <class InputIterator>
756 //   void insert(InputIterator first, InputIterator last);
757 
TEST(FlatTree,InsertIterIter)758 TEST(FlatTree, InsertIterIter) {
759   struct GetKeyFromIntIntPair {
760     const int& operator()(const std::pair<int, int>& p) const {
761       return p.first;
762     }
763   };
764 
765   using IntIntMap =
766       flat_tree<int, IntPair, GetKeyFromIntIntPair, std::less<int>>;
767 
768   {
769     IntIntMap cont;
770     IntPair int_pairs[] = {{3, 1}, {1, 1}, {4, 1}, {2, 1}};
771     cont.insert(std::begin(int_pairs), std::end(int_pairs));
772     EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
773                                   IntPair(4, 1)));
774   }
775 
776   {
777     IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}});
778     std::vector<IntPair> int_pairs;
779     cont.insert(std::begin(int_pairs), std::end(int_pairs));
780     EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
781                                   IntPair(4, 1)));
782   }
783 
784   {
785     IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}});
786     IntPair int_pairs[] = {{1, 1}};
787     cont.insert(std::begin(int_pairs), std::end(int_pairs));
788     EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
789                                   IntPair(4, 1)));
790   }
791 
792   {
793     IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}});
794     IntPair int_pairs[] = {{1, 2}};
795     cont.insert(std::begin(int_pairs), std::end(int_pairs), KEEP_LAST_OF_DUPES);
796     EXPECT_THAT(cont, ElementsAre(IntPair(1, 2), IntPair(2, 1), IntPair(3, 1),
797                                   IntPair(4, 1)));
798   }
799 
800   {
801     IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}});
802     IntPair int_pairs[] = {{5, 1}};
803     cont.insert(std::begin(int_pairs), std::end(int_pairs));
804     EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
805                                   IntPair(4, 1), IntPair(5, 1)));
806   }
807 
808   {
809     IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}});
810     IntPair int_pairs[] = {{5, 1}};
811     cont.insert(std::begin(int_pairs), std::end(int_pairs), KEEP_LAST_OF_DUPES);
812     EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
813                                   IntPair(4, 1), IntPair(5, 1)));
814   }
815 
816   {
817     IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}});
818     IntPair int_pairs[] = {{3, 2}, {1, 2}, {4, 2}, {2, 2}};
819     cont.insert(std::begin(int_pairs), std::end(int_pairs));
820     EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
821                                   IntPair(4, 1)));
822   }
823 
824   {
825     IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}});
826     IntPair int_pairs[] = {{3, 2}, {1, 2}, {4, 2}, {2, 2}};
827     cont.insert(std::begin(int_pairs), std::end(int_pairs), KEEP_LAST_OF_DUPES);
828     EXPECT_THAT(cont, ElementsAre(IntPair(1, 2), IntPair(2, 2), IntPair(3, 2),
829                                   IntPair(4, 2)));
830   }
831 
832   {
833     IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}});
834     IntPair int_pairs[] = {{3, 2}, {1, 2}, {4, 2}, {2, 2}, {7, 2}, {6, 2},
835                            {8, 2}, {5, 2}, {5, 3}, {6, 3}, {7, 3}, {8, 3}};
836     cont.insert(std::begin(int_pairs), std::end(int_pairs));
837     EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
838                                   IntPair(4, 1), IntPair(5, 2), IntPair(6, 2),
839                                   IntPair(7, 2), IntPair(8, 2)));
840   }
841 
842   {
843     IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}});
844     IntPair int_pairs[] = {{3, 2}, {1, 2}, {4, 2}, {2, 2}, {7, 2}, {6, 2},
845                            {8, 2}, {5, 2}, {5, 3}, {6, 3}, {7, 3}, {8, 3}};
846     cont.insert(std::begin(int_pairs), std::end(int_pairs), KEEP_LAST_OF_DUPES);
847     EXPECT_THAT(cont, ElementsAre(IntPair(1, 2), IntPair(2, 2), IntPair(3, 2),
848                                   IntPair(4, 2), IntPair(5, 3), IntPair(6, 3),
849                                   IntPair(7, 3), IntPair(8, 3)));
850   }
851 }
852 
853 // template <class... Args>
854 // pair<iterator, bool> emplace(Args&&... args)
855 
TEST(FlatTree,Emplace)856 TEST(FlatTree, Emplace) {
857   {
858     EmplaceableTree cont;
859 
860     std::pair<EmplaceableTree::iterator, bool> result = cont.emplace();
861     EXPECT_TRUE(result.second);
862     EXPECT_EQ(cont.begin(), result.first);
863     EXPECT_EQ(1U, cont.size());
864     EXPECT_EQ(Emplaceable(), *cont.begin());
865 
866     result = cont.emplace(2, 3.5);
867     EXPECT_TRUE(result.second);
868     EXPECT_EQ(std::next(cont.begin()), result.first);
869     EXPECT_EQ(2U, cont.size());
870     EXPECT_EQ(Emplaceable(2, 3.5), *result.first);
871 
872     result = cont.emplace(2, 3.5);
873     EXPECT_FALSE(result.second);
874     EXPECT_EQ(std::next(cont.begin()), result.first);
875     EXPECT_EQ(2U, cont.size());
876     EXPECT_EQ(Emplaceable(2, 3.5), *result.first);
877   }
878   {
879     IntTree cont;
880 
881     std::pair<IntTree::iterator, bool> result = cont.emplace(2);
882     EXPECT_TRUE(result.second);
883     EXPECT_EQ(cont.begin(), result.first);
884     EXPECT_EQ(1U, cont.size());
885     EXPECT_EQ(2, *result.first);
886   }
887 }
888 
889 // template <class... Args>
890 // iterator emplace_hint(const_iterator position_hint, Args&&... args)
891 
TEST(FlatTree,EmplacePosition)892 TEST(FlatTree, EmplacePosition) {
893   {
894     EmplaceableTree cont;
895 
896     EmplaceableTree::iterator result = cont.emplace_hint(cont.cend());
897     EXPECT_EQ(cont.begin(), result);
898     EXPECT_EQ(1U, cont.size());
899     EXPECT_EQ(Emplaceable(), *cont.begin());
900 
901     result = cont.emplace_hint(cont.cend(), 2, 3.5);
902     EXPECT_EQ(std::next(cont.begin()), result);
903     EXPECT_EQ(2U, cont.size());
904     EXPECT_EQ(Emplaceable(2, 3.5), *result);
905 
906     result = cont.emplace_hint(cont.cbegin(), 2, 3.5);
907     EXPECT_EQ(std::next(cont.begin()), result);
908     EXPECT_EQ(2U, cont.size());
909     EXPECT_EQ(Emplaceable(2, 3.5), *result);
910   }
911   {
912     IntTree cont;
913 
914     IntTree::iterator result = cont.emplace_hint(cont.cend(), 2);
915     EXPECT_EQ(cont.begin(), result);
916     EXPECT_EQ(1U, cont.size());
917     EXPECT_EQ(2, *result);
918   }
919 }
920 
921 // ----------------------------------------------------------------------------
922 // Erase operations.
923 
924 // iterator erase(const_iterator position_hint)
925 
TEST(FlatTree,ErasePosition)926 TEST(FlatTree, ErasePosition) {
927   {
928     IntTree cont({1, 2, 3, 4, 5, 6, 7, 8});
929 
930     IntTree::iterator it = cont.erase(std::next(cont.cbegin(), 3));
931     EXPECT_EQ(std::next(cont.begin(), 3), it);
932     EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8));
933 
934     it = cont.erase(std::next(cont.cbegin(), 0));
935     EXPECT_EQ(cont.begin(), it);
936     EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8));
937 
938     it = cont.erase(std::next(cont.cbegin(), 5));
939     EXPECT_EQ(cont.end(), it);
940     EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7));
941 
942     it = cont.erase(std::next(cont.cbegin(), 1));
943     EXPECT_EQ(std::next(cont.begin()), it);
944     EXPECT_THAT(cont, ElementsAre(2, 5, 6, 7));
945 
946     it = cont.erase(std::next(cont.cbegin(), 2));
947     EXPECT_EQ(std::next(cont.begin(), 2), it);
948     EXPECT_THAT(cont, ElementsAre(2, 5, 7));
949 
950     it = cont.erase(std::next(cont.cbegin(), 2));
951     EXPECT_EQ(std::next(cont.begin(), 2), it);
952     EXPECT_THAT(cont, ElementsAre(2, 5));
953 
954     it = cont.erase(std::next(cont.cbegin(), 0));
955     EXPECT_EQ(std::next(cont.begin(), 0), it);
956     EXPECT_THAT(cont, ElementsAre(5));
957 
958     it = cont.erase(cont.cbegin());
959     EXPECT_EQ(cont.begin(), it);
960     EXPECT_EQ(cont.end(), it);
961   }
962   //  This is LWG #2059.
963   //  There is a potential ambiguity between erase with an iterator and erase
964   //  with a key, if key has a templated constructor.
965   {
966     using T = TemplateConstructor;
967 
968     flat_tree<T, T, GetKeyFromValueIdentity<T>, std::less<>> cont;
969     T v(0);
970 
971     auto it = cont.find(v);
972     if (it != cont.end())
973       cont.erase(it);
974   }
975 }
976 
977 // iterator erase(const_iterator first, const_iterator last)
978 
TEST(FlatTree,EraseRange)979 TEST(FlatTree, EraseRange) {
980   IntTree cont({1, 2, 3, 4, 5, 6, 7, 8});
981 
982   IntTree::iterator it =
983       cont.erase(std::next(cont.cbegin(), 5), std::next(cont.cbegin(), 5));
984   EXPECT_EQ(std::next(cont.begin(), 5), it);
985   EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8));
986 
987   it = cont.erase(std::next(cont.cbegin(), 3), std::next(cont.cbegin(), 4));
988   EXPECT_EQ(std::next(cont.begin(), 3), it);
989   EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8));
990 
991   it = cont.erase(std::next(cont.cbegin(), 2), std::next(cont.cbegin(), 5));
992   EXPECT_EQ(std::next(cont.begin(), 2), it);
993   EXPECT_THAT(cont, ElementsAre(1, 2, 7, 8));
994 
995   it = cont.erase(std::next(cont.cbegin(), 0), std::next(cont.cbegin(), 2));
996   EXPECT_EQ(std::next(cont.begin(), 0), it);
997   EXPECT_THAT(cont, ElementsAre(7, 8));
998 
999   it = cont.erase(cont.cbegin(), cont.cend());
1000   EXPECT_EQ(cont.begin(), it);
1001   EXPECT_EQ(cont.end(), it);
1002 }
1003 
1004 // size_type erase(const key_type& key)
1005 
TEST(FlatTree,EraseKey)1006 TEST(FlatTree, EraseKey) {
1007   IntTree cont({1, 2, 3, 4, 5, 6, 7, 8});
1008 
1009   EXPECT_EQ(0U, cont.erase(9));
1010   EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8));
1011 
1012   EXPECT_EQ(1U, cont.erase(4));
1013   EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8));
1014 
1015   EXPECT_EQ(1U, cont.erase(1));
1016   EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8));
1017 
1018   EXPECT_EQ(1U, cont.erase(8));
1019   EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7));
1020 
1021   EXPECT_EQ(1U, cont.erase(3));
1022   EXPECT_THAT(cont, ElementsAre(2, 5, 6, 7));
1023 
1024   EXPECT_EQ(1U, cont.erase(6));
1025   EXPECT_THAT(cont, ElementsAre(2, 5, 7));
1026 
1027   EXPECT_EQ(1U, cont.erase(7));
1028   EXPECT_THAT(cont, ElementsAre(2, 5));
1029 
1030   EXPECT_EQ(1U, cont.erase(2));
1031   EXPECT_THAT(cont, ElementsAre(5));
1032 
1033   EXPECT_EQ(1U, cont.erase(5));
1034   EXPECT_THAT(cont, ElementsAre());
1035 }
1036 
1037 // ----------------------------------------------------------------------------
1038 // Comparators.
1039 
1040 // key_compare key_comp() const
1041 
TEST(FlatTree,KeyComp)1042 TEST(FlatTree, KeyComp) {
1043   ReversedTree cont({1, 2, 3, 4, 5});
1044 
1045   EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.key_comp()));
1046   int new_elements[] = {6, 7, 8, 9, 10};
1047   std::copy(std::begin(new_elements), std::end(new_elements),
1048             std::inserter(cont, cont.end()));
1049   EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.key_comp()));
1050 }
1051 
1052 // value_compare value_comp() const
1053 
TEST(FlatTree,ValueComp)1054 TEST(FlatTree, ValueComp) {
1055   ReversedTree cont({1, 2, 3, 4, 5});
1056 
1057   EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp()));
1058   int new_elements[] = {6, 7, 8, 9, 10};
1059   std::copy(std::begin(new_elements), std::end(new_elements),
1060             std::inserter(cont, cont.end()));
1061   EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp()));
1062 }
1063 
1064 // ----------------------------------------------------------------------------
1065 // Search operations.
1066 
1067 // size_type count(const key_type& key) const
1068 
TEST(FlatTree,Count)1069 TEST(FlatTree, Count) {
1070   const IntTree cont({5, 6, 7, 8, 9, 10, 11, 12});
1071 
1072   EXPECT_EQ(1U, cont.count(5));
1073   EXPECT_EQ(1U, cont.count(6));
1074   EXPECT_EQ(1U, cont.count(7));
1075   EXPECT_EQ(1U, cont.count(8));
1076   EXPECT_EQ(1U, cont.count(9));
1077   EXPECT_EQ(1U, cont.count(10));
1078   EXPECT_EQ(1U, cont.count(11));
1079   EXPECT_EQ(1U, cont.count(12));
1080   EXPECT_EQ(0U, cont.count(4));
1081 }
1082 
1083 // iterator find(const key_type& key)
1084 // const_iterator find(const key_type& key) const
1085 
TEST(FlatTree,Find)1086 TEST(FlatTree, Find) {
1087   {
1088     IntTree cont({5, 6, 7, 8, 9, 10, 11, 12});
1089 
1090     EXPECT_EQ(cont.begin(), cont.find(5));
1091     EXPECT_EQ(std::next(cont.begin()), cont.find(6));
1092     EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7));
1093     EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8));
1094     EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9));
1095     EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10));
1096     EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11));
1097     EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12));
1098     EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4));
1099   }
1100   {
1101     const IntTree cont({5, 6, 7, 8, 9, 10, 11, 12});
1102 
1103     EXPECT_EQ(cont.begin(), cont.find(5));
1104     EXPECT_EQ(std::next(cont.begin()), cont.find(6));
1105     EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7));
1106     EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8));
1107     EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9));
1108     EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10));
1109     EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11));
1110     EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12));
1111     EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4));
1112   }
1113 }
1114 
1115 // pair<iterator, iterator> equal_range(const key_type& key)
1116 // pair<const_iterator, const_iterator> equal_range(const key_type& key) const
1117 
TEST(FlatTree,EqualRange)1118 TEST(FlatTree, EqualRange) {
1119   {
1120     IntTree cont({5, 7, 9, 11, 13, 15, 17, 19});
1121 
1122     std::pair<IntTree::iterator, IntTree::iterator> result =
1123         cont.equal_range(5);
1124     EXPECT_EQ(std::next(cont.begin(), 0), result.first);
1125     EXPECT_EQ(std::next(cont.begin(), 1), result.second);
1126     result = cont.equal_range(7);
1127     EXPECT_EQ(std::next(cont.begin(), 1), result.first);
1128     EXPECT_EQ(std::next(cont.begin(), 2), result.second);
1129     result = cont.equal_range(9);
1130     EXPECT_EQ(std::next(cont.begin(), 2), result.first);
1131     EXPECT_EQ(std::next(cont.begin(), 3), result.second);
1132     result = cont.equal_range(11);
1133     EXPECT_EQ(std::next(cont.begin(), 3), result.first);
1134     EXPECT_EQ(std::next(cont.begin(), 4), result.second);
1135     result = cont.equal_range(13);
1136     EXPECT_EQ(std::next(cont.begin(), 4), result.first);
1137     EXPECT_EQ(std::next(cont.begin(), 5), result.second);
1138     result = cont.equal_range(15);
1139     EXPECT_EQ(std::next(cont.begin(), 5), result.first);
1140     EXPECT_EQ(std::next(cont.begin(), 6), result.second);
1141     result = cont.equal_range(17);
1142     EXPECT_EQ(std::next(cont.begin(), 6), result.first);
1143     EXPECT_EQ(std::next(cont.begin(), 7), result.second);
1144     result = cont.equal_range(19);
1145     EXPECT_EQ(std::next(cont.begin(), 7), result.first);
1146     EXPECT_EQ(std::next(cont.begin(), 8), result.second);
1147     result = cont.equal_range(4);
1148     EXPECT_EQ(std::next(cont.begin(), 0), result.first);
1149     EXPECT_EQ(std::next(cont.begin(), 0), result.second);
1150     result = cont.equal_range(6);
1151     EXPECT_EQ(std::next(cont.begin(), 1), result.first);
1152     EXPECT_EQ(std::next(cont.begin(), 1), result.second);
1153     result = cont.equal_range(8);
1154     EXPECT_EQ(std::next(cont.begin(), 2), result.first);
1155     EXPECT_EQ(std::next(cont.begin(), 2), result.second);
1156     result = cont.equal_range(10);
1157     EXPECT_EQ(std::next(cont.begin(), 3), result.first);
1158     EXPECT_EQ(std::next(cont.begin(), 3), result.second);
1159     result = cont.equal_range(12);
1160     EXPECT_EQ(std::next(cont.begin(), 4), result.first);
1161     EXPECT_EQ(std::next(cont.begin(), 4), result.second);
1162     result = cont.equal_range(14);
1163     EXPECT_EQ(std::next(cont.begin(), 5), result.first);
1164     EXPECT_EQ(std::next(cont.begin(), 5), result.second);
1165     result = cont.equal_range(16);
1166     EXPECT_EQ(std::next(cont.begin(), 6), result.first);
1167     EXPECT_EQ(std::next(cont.begin(), 6), result.second);
1168     result = cont.equal_range(18);
1169     EXPECT_EQ(std::next(cont.begin(), 7), result.first);
1170     EXPECT_EQ(std::next(cont.begin(), 7), result.second);
1171     result = cont.equal_range(20);
1172     EXPECT_EQ(std::next(cont.begin(), 8), result.first);
1173     EXPECT_EQ(std::next(cont.begin(), 8), result.second);
1174   }
1175   {
1176     const IntTree cont({5, 7, 9, 11, 13, 15, 17, 19});
1177 
1178     std::pair<IntTree::const_iterator, IntTree::const_iterator> result =
1179         cont.equal_range(5);
1180     EXPECT_EQ(std::next(cont.begin(), 0), result.first);
1181     EXPECT_EQ(std::next(cont.begin(), 1), result.second);
1182     result = cont.equal_range(7);
1183     EXPECT_EQ(std::next(cont.begin(), 1), result.first);
1184     EXPECT_EQ(std::next(cont.begin(), 2), result.second);
1185     result = cont.equal_range(9);
1186     EXPECT_EQ(std::next(cont.begin(), 2), result.first);
1187     EXPECT_EQ(std::next(cont.begin(), 3), result.second);
1188     result = cont.equal_range(11);
1189     EXPECT_EQ(std::next(cont.begin(), 3), result.first);
1190     EXPECT_EQ(std::next(cont.begin(), 4), result.second);
1191     result = cont.equal_range(13);
1192     EXPECT_EQ(std::next(cont.begin(), 4), result.first);
1193     EXPECT_EQ(std::next(cont.begin(), 5), result.second);
1194     result = cont.equal_range(15);
1195     EXPECT_EQ(std::next(cont.begin(), 5), result.first);
1196     EXPECT_EQ(std::next(cont.begin(), 6), result.second);
1197     result = cont.equal_range(17);
1198     EXPECT_EQ(std::next(cont.begin(), 6), result.first);
1199     EXPECT_EQ(std::next(cont.begin(), 7), result.second);
1200     result = cont.equal_range(19);
1201     EXPECT_EQ(std::next(cont.begin(), 7), result.first);
1202     EXPECT_EQ(std::next(cont.begin(), 8), result.second);
1203     result = cont.equal_range(4);
1204     EXPECT_EQ(std::next(cont.begin(), 0), result.first);
1205     EXPECT_EQ(std::next(cont.begin(), 0), result.second);
1206     result = cont.equal_range(6);
1207     EXPECT_EQ(std::next(cont.begin(), 1), result.first);
1208     EXPECT_EQ(std::next(cont.begin(), 1), result.second);
1209     result = cont.equal_range(8);
1210     EXPECT_EQ(std::next(cont.begin(), 2), result.first);
1211     EXPECT_EQ(std::next(cont.begin(), 2), result.second);
1212     result = cont.equal_range(10);
1213     EXPECT_EQ(std::next(cont.begin(), 3), result.first);
1214     EXPECT_EQ(std::next(cont.begin(), 3), result.second);
1215     result = cont.equal_range(12);
1216     EXPECT_EQ(std::next(cont.begin(), 4), result.first);
1217     EXPECT_EQ(std::next(cont.begin(), 4), result.second);
1218     result = cont.equal_range(14);
1219     EXPECT_EQ(std::next(cont.begin(), 5), result.first);
1220     EXPECT_EQ(std::next(cont.begin(), 5), result.second);
1221     result = cont.equal_range(16);
1222     EXPECT_EQ(std::next(cont.begin(), 6), result.first);
1223     EXPECT_EQ(std::next(cont.begin(), 6), result.second);
1224     result = cont.equal_range(18);
1225     EXPECT_EQ(std::next(cont.begin(), 7), result.first);
1226     EXPECT_EQ(std::next(cont.begin(), 7), result.second);
1227     result = cont.equal_range(20);
1228     EXPECT_EQ(std::next(cont.begin(), 8), result.first);
1229     EXPECT_EQ(std::next(cont.begin(), 8), result.second);
1230   }
1231 }
1232 
1233 //       iterator lower_bound(const key_type& key);
1234 // const_iterator lower_bound(const key_type& key) const;
1235 
TEST(FlatTree,LowerBound)1236 TEST(FlatTree, LowerBound) {
1237   {
1238     IntTree cont({5, 7, 9, 11, 13, 15, 17, 19});
1239 
1240     EXPECT_EQ(cont.begin(), cont.lower_bound(5));
1241     EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7));
1242     EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9));
1243     EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11));
1244     EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13));
1245     EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15));
1246     EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17));
1247     EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19));
1248     EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4));
1249     EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6));
1250     EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8));
1251     EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10));
1252     EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12));
1253     EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14));
1254     EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16));
1255     EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18));
1256     EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20));
1257   }
1258   {
1259     const IntTree cont({5, 7, 9, 11, 13, 15, 17, 19});
1260 
1261     EXPECT_EQ(cont.begin(), cont.lower_bound(5));
1262     EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7));
1263     EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9));
1264     EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11));
1265     EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13));
1266     EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15));
1267     EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17));
1268     EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19));
1269     EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4));
1270     EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6));
1271     EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8));
1272     EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10));
1273     EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12));
1274     EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14));
1275     EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16));
1276     EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18));
1277     EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20));
1278   }
1279 }
1280 
1281 // iterator upper_bound(const key_type& key)
1282 // const_iterator upper_bound(const key_type& key) const
1283 
TEST(FlatTree,UpperBound)1284 TEST(FlatTree, UpperBound) {
1285   {
1286     IntTree cont({5, 7, 9, 11, 13, 15, 17, 19});
1287 
1288     EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5));
1289     EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7));
1290     EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9));
1291     EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11));
1292     EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13));
1293     EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15));
1294     EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17));
1295     EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19));
1296     EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4));
1297     EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6));
1298     EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8));
1299     EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10));
1300     EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12));
1301     EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14));
1302     EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16));
1303     EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18));
1304     EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20));
1305   }
1306   {
1307     const IntTree cont({5, 7, 9, 11, 13, 15, 17, 19});
1308 
1309     EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5));
1310     EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7));
1311     EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9));
1312     EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11));
1313     EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13));
1314     EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15));
1315     EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17));
1316     EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19));
1317     EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4));
1318     EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6));
1319     EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8));
1320     EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10));
1321     EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12));
1322     EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14));
1323     EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16));
1324     EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18));
1325     EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20));
1326   }
1327 }
1328 
1329 // ----------------------------------------------------------------------------
1330 // General operations.
1331 
1332 // void swap(flat_tree& other)
1333 // void swap(flat_tree& lhs, flat_tree& rhs)
1334 
TEST(FlatTreeOurs,Swap)1335 TEST(FlatTreeOurs, Swap) {
1336   IntTree x({1, 2, 3});
1337   IntTree y({4});
1338   swap(x, y);
1339   EXPECT_THAT(x, ElementsAre(4));
1340   EXPECT_THAT(y, ElementsAre(1, 2, 3));
1341 
1342   y.swap(x);
1343   EXPECT_THAT(x, ElementsAre(1, 2, 3));
1344   EXPECT_THAT(y, ElementsAre(4));
1345 }
1346 
1347 // bool operator==(const flat_tree& lhs, const flat_tree& rhs)
1348 // bool operator!=(const flat_tree& lhs, const flat_tree& rhs)
1349 // bool operator<(const flat_tree& lhs, const flat_tree& rhs)
1350 // bool operator>(const flat_tree& lhs, const flat_tree& rhs)
1351 // bool operator<=(const flat_tree& lhs, const flat_tree& rhs)
1352 // bool operator>=(const flat_tree& lhs, const flat_tree& rhs)
1353 
TEST(FlatTree,Comparison)1354 TEST(FlatTree, Comparison) {
1355   // Provided comparator does not participate in comparison.
1356   ReversedTree biggest({3});
1357   ReversedTree smallest({1});
1358   ReversedTree middle({1, 2});
1359 
1360   EXPECT_EQ(biggest, biggest);
1361   EXPECT_NE(biggest, smallest);
1362   EXPECT_LT(smallest, middle);
1363   EXPECT_LE(smallest, middle);
1364   EXPECT_LE(middle, middle);
1365   EXPECT_GT(biggest, middle);
1366   EXPECT_GE(biggest, middle);
1367   EXPECT_GE(biggest, biggest);
1368 }
1369 
TEST(FlatSet,EraseIf)1370 TEST(FlatSet, EraseIf) {
1371   IntTree x;
1372   EraseIf(x, [](int) { return false; });
1373   EXPECT_THAT(x, ElementsAre());
1374 
1375   x = {1, 2, 3};
1376   EraseIf(x, [](int elem) { return !(elem & 1); });
1377   EXPECT_THAT(x, ElementsAre(1, 3));
1378 
1379   x = {1, 2, 3, 4};
1380   EraseIf(x, [](int elem) { return elem & 1; });
1381   EXPECT_THAT(x, ElementsAre(2, 4));
1382 }
1383 
1384 }  // namespace internal
1385 }  // namespace base
1386