Add range insertion for base::flat_tree

base/containers/flat_tree_unittest.cc

 // Copyright 2017 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "base/containers/flat_tree.h"
 
 // Following tests are ported and extended tests from libcpp for std::set.
 // They can be found here:
 // https://github.com/llvm-mirror/libcxx/tree/master/test/std/containers/associative/set
 //
@@ skipping 13 matching lines @@
 // * No tests with DefaultOnly.
 //   Standard containers allocate each element in the separate node on the heap
 //   and then manipulate these nodes. Flat containers store their elements in
 //   contiguous memory and move them around, type is required to be movable.
 // * No tests for N3644.
 //   This proposal suggests that all default constructed iterators compare
 //   equal. Currently we use std::vector iterators and they don't implement
 //   this.
 // * No tests with min_allocator and no tests counting allocations.
 //   Flat sets currently don't support allocators.
-// * No tests for range insertion. Flat sets currently do not support this
-//   functionality.
 
+#include <forward_list>
+#include <iterator>
+#include <list>
 #include <string>
 #include <vector>
 
 #include "base/containers/container_test_utils.h"
 #include "base/macros.h"
 #include "testing/gmock/include/gmock/gmock.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace base {
 namespace internal {
@@ skipping 116 matching lines @@
 
 using TreeWithStrangeCompare = flat_tree<int,
                                          int,
                                          GetKeyFromValueIdentity<int>,
                                          NonDefaultConstructibleCompare>;
 
 using ::testing::ElementsAre;
 
 }  // namespace
 
+TEST(FlatTree, IsMultipass) {
+  static_assert(!is_multipass<std::istream_iterator<int>>(),
+                "InputIterator is not multipass");
+  static_assert(!is_multipass<std::ostream_iterator<int>>(),
+                "OutputIterator is not multipass");
+
+  static_assert(is_multipass<std::forward_list<int>::iterator>(),
+                "ForwardIterator is multipass");
+  static_assert(is_multipass<std::list<int>::iterator>(),
+                "BidirectionalIterator is multipass");
+  static_assert(is_multipass<std::vector<int>::iterator>(),
+                "RandomAccessIterator is multipass");
+}
+
 TEST(FlatTree, LastUnique) {
   using Pair = std::pair<int, int>;
   using Vect = std::vector<Pair>;
 
   auto cmp = [](const Pair& lhs, const Pair& rhs) {
     return lhs.first == rhs.first;
   };
 
   // Empty case.
   Vect empty;
@@ skipping 548 matching lines @@
   EXPECT_EQ(std::prev(cont.end()), result);
   EXPECT_EQ(3U, cont.size());
   EXPECT_EQ(3, result->data());
 
   result = cont.insert(cont.cend(), MoveOnlyInt(3));
   EXPECT_EQ(std::prev(cont.end()), result);
   EXPECT_EQ(3U, cont.size());
   EXPECT_EQ(3, result->data());
 }
 
+// template <class InputIterator>
+//   void insert(InputIterator first, InputIterator last);
+
+TEST(FlatTree, InsertIterIter) {
+  struct GetKeyFromIntIntPair {
+    int operator()(const std::pair<int, int>& p) const { return p.first; }
+  };
+
+  using IntIntMap =
+      flat_tree<int, IntPair, GetKeyFromIntIntPair, std::less<int>>;
+
+  {
+    IntIntMap cont;
+    IntPair int_pairs[] = {{3, 1}, {1, 1}, {4, 1}, {2, 1}};
+    cont.insert(std::begin(int_pairs), std::end(int_pairs),
+                KEEP_FIRST_OF_DUPES);
+    EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
+                                  IntPair(4, 1)));
+  }
+
+  {
+    IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}}, KEEP_FIRST_OF_DUPES);
+    std::vector<IntPair> int_pairs;
+    cont.insert(std::begin(int_pairs), std::end(int_pairs),
+                KEEP_FIRST_OF_DUPES);
+    EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
+                                  IntPair(4, 1)));
+  }
+
+  {
+    IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}}, KEEP_FIRST_OF_DUPES);
+    IntPair int_pairs[] = {{1, 1}};
+    cont.insert(std::begin(int_pairs), std::end(int_pairs),
+                KEEP_FIRST_OF_DUPES);
+    EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
+                                  IntPair(4, 1)));
+  }
+
+  {
+    IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}}, KEEP_FIRST_OF_DUPES);
+    IntPair int_pairs[] = {{1, 2}};
+    cont.insert(std::begin(int_pairs), std::end(int_pairs), KEEP_LAST_OF_DUPES);
+    EXPECT_THAT(cont, ElementsAre(IntPair(1, 2), IntPair(2, 1), IntPair(3, 1),
+                                  IntPair(4, 1)));
+  }
+
+  {
+    IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}}, KEEP_FIRST_OF_DUPES);
+    IntPair int_pairs[] = {{5, 1}};
+    cont.insert(std::begin(int_pairs), std::end(int_pairs),
+                KEEP_FIRST_OF_DUPES);
+    EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
+                                  IntPair(4, 1), IntPair(5, 1)));
+  }
+
+  {
+    IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}}, KEEP_FIRST_OF_DUPES);
+    IntPair int_pairs[] = {{5, 1}};
+    cont.insert(std::begin(int_pairs), std::end(int_pairs), KEEP_LAST_OF_DUPES);
+    EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
+                                  IntPair(4, 1), IntPair(5, 1)));
+  }
+
+  {
+    IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}}, KEEP_FIRST_OF_DUPES);
+    IntPair int_pairs[] = {{3, 2}, {1, 2}, {4, 2}, {2, 2}};
+    cont.insert(std::begin(int_pairs), std::end(int_pairs),
+                KEEP_FIRST_OF_DUPES);
+    EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
+                                  IntPair(4, 1)));
+  }
+
+  {
+    IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}}, KEEP_FIRST_OF_DUPES);
+    IntPair int_pairs[] = {{3, 2}, {1, 2}, {4, 2}, {2, 2}};
+    cont.insert(std::begin(int_pairs), std::end(int_pairs), KEEP_LAST_OF_DUPES);
+    EXPECT_THAT(cont, ElementsAre(IntPair(1, 2), IntPair(2, 2), IntPair(3, 2),
+                                  IntPair(4, 2)));
+  }
+
+  {
+    IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}}, KEEP_FIRST_OF_DUPES);
+    IntPair int_pairs[] = {{3, 2}, {1, 2}, {4, 2}, {2, 2}, {7, 2}, {6, 2},
+                           {8, 2}, {5, 2}, {5, 3}, {6, 3}, {7, 3}, {8, 3}};
+    cont.insert(std::begin(int_pairs), std::end(int_pairs),
+                KEEP_FIRST_OF_DUPES);
+    EXPECT_THAT(cont, ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1),
+                                  IntPair(4, 1), IntPair(5, 2), IntPair(6, 2),
+                                  IntPair(7, 2), IntPair(8, 2)));
+  }
+
+  {
+    IntIntMap cont({{1, 1}, {2, 1}, {3, 1}, {4, 1}}, KEEP_FIRST_OF_DUPES);
+    IntPair int_pairs[] = {{3, 2}, {1, 2}, {4, 2}, {2, 2}, {7, 2}, {6, 2},
+                           {8, 2}, {5, 2}, {5, 3}, {6, 3}, {7, 3}, {8, 3}};
+    cont.insert(std::begin(int_pairs), std::end(int_pairs), KEEP_LAST_OF_DUPES);
+    EXPECT_THAT(cont, ElementsAre(IntPair(1, 2), IntPair(2, 2), IntPair(3, 2),
+                                  IntPair(4, 2), IntPair(5, 3), IntPair(6, 3),
+                                  IntPair(7, 3), IntPair(8, 3)));
+  }
+}
+
 // template <class... Args>
 // pair<iterator, bool> emplace(Args&&... args)
 
 TEST(FlatTree, Emplace) {
   {
     EmplaceableTree cont;
 
     std::pair<EmplaceableTree::iterator, bool> result = cont.emplace();
     EXPECT_TRUE(result.second);
     EXPECT_EQ(cont.begin(), result.first);
@@ skipping 625 matching lines @@
   EraseIf(x, [](int elem) { return !(elem & 1); });
   EXPECT_THAT(x, ElementsAre(1, 3));
 
   x = {1, 2, 3, 4};
   EraseIf(x, [](int elem) { return elem & 1; });
   EXPECT_THAT(x, ElementsAre(2, 4));
 }
 
 }  // namespace internal
 }  // namespace base