Index: base/containers/flat_tree_unittest.cc |
diff --git a/base/containers/flat_set_unittest.cc b/base/containers/flat_tree_unittest.cc |
similarity index 79% |
copy from base/containers/flat_set_unittest.cc |
copy to base/containers/flat_tree_unittest.cc |
index 34190ee01efa7cd8f6a632e59667035912abb100..91a853c736ca6df5547383ca25826cff2d28a1a0 100644 |
--- a/base/containers/flat_set_unittest.cc |
+++ b/base/containers/flat_tree_unittest.cc |
@@ -2,7 +2,7 @@ |
// Use of this source code is governed by a BSD-style license that can be |
// found in the LICENSE file. |
-#include "base/containers/flat_set.h" |
+#include "base/containers/flat_tree.h" |
// Following tests are ported and extended tests from libcpp for std::set. |
// They can be found here: |
@@ -37,33 +37,15 @@ |
#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 { |
- |
-class MoveOnly { |
- public: |
- explicit MoveOnly(int data = 1) : data_(data) {} |
- MoveOnly(MoveOnly&& other) : data_(other.data_) { other.data_ = 0; } |
- MoveOnly& operator=(MoveOnly&& other) { |
- data_ = other.data_; |
- other.data_ = 0; |
- return *this; |
- } |
- |
- friend bool operator<(const MoveOnly& lhs, const MoveOnly& rhs) { |
- return lhs.data_ < rhs.data_; |
- } |
- |
- int data() const { return data_; } |
+namespace base { |
+namespace internal { |
- private: |
- int data_; |
- |
- DISALLOW_COPY_AND_ASSIGN(MoveOnly); |
-}; |
+namespace { |
template <class It> |
class InputIterator { |
@@ -143,23 +125,34 @@ class NonDefaultConstructibleCompare { |
explicit NonDefaultConstructibleCompare(int) {} |
template <typename T> |
- bool operator()(const T& lhs, const T& rhs) { |
+ bool operator()(const T& lhs, const T& rhs) const { |
return std::less<T>()(lhs, rhs); |
} |
}; |
-// Common test sets. |
-using IntSet = base::flat_set<int>; |
-using MoveOnlySet = base::flat_set<MoveOnly>; |
-using EmplaceableSet = base::flat_set<Emplaceable>; |
-using ReversedSet = base::flat_set<int, std::greater<int>>; |
+// Common test trees. |
// TODO(dyaroshev): replace less<int> with less<>, once we have it |
-// crbug.com/682254. |
-using SetWithLess = base::flat_set<int, std::less<int>>; |
- |
-using SetWithStrangeCompare = |
- base::flat_set<int, NonDefaultConstructibleCompare>; |
+// crbug.com/682254. This will make it different than IntTree. |
+using IntTreeWithLess = |
+ flat_tree<int, int, GetKeyFromValueIdentity<int>, std::less<int>>; |
+using IntTree = |
+ flat_tree<int, int, GetKeyFromValueIdentity<int>, std::less<int>>; |
+using MoveOnlyTree = flat_tree<MoveOnlyInt, |
+ MoveOnlyInt, |
+ GetKeyFromValueIdentity<MoveOnlyInt>, |
+ std::less<MoveOnlyInt>>; |
+using EmplaceableTree = flat_tree<Emplaceable, |
+ Emplaceable, |
+ GetKeyFromValueIdentity<Emplaceable>, |
+ std::less<Emplaceable>>; |
+using ReversedTree = |
+ flat_tree<int, int, GetKeyFromValueIdentity<int>, std::greater<int>>; |
+ |
+using TreeWithStrangeCompare = flat_tree<int, |
+ int, |
+ GetKeyFromValueIdentity<int>, |
+ NonDefaultConstructibleCompare>; |
using ::testing::ElementsAre; |
@@ -168,16 +161,16 @@ using ::testing::ElementsAre; |
// ---------------------------------------------------------------------------- |
// Class. |
-// Check that base::flat_set and its iterators can be instantiated with an |
+// Check that flat_tree and its iterators can be instantiated with an |
// incomplete type. |
-TEST(FlatSet, IncompleteType) { |
+TEST(FlatTree, IncompleteType) { |
struct A { |
- using Set = base::flat_set<A>; |
+ using Tree = flat_tree<A, A, GetKeyFromValueIdentity<A>, std::less<A>>; |
int data; |
- Set set_with_incomplete_type; |
- Set::iterator it; |
- Set::const_iterator cit; |
+ Tree set_with_incomplete_type; |
+ Tree::iterator it; |
+ Tree::const_iterator cit; |
// We do not declare operator< because clang complains that it's unused. |
}; |
@@ -185,19 +178,20 @@ TEST(FlatSet, IncompleteType) { |
A a; |
} |
-TEST(FlatSet, Stability) { |
+TEST(FlatTree, Stability) { |
using Pair = std::pair<int, int>; |
struct LessByFirst { |
- bool operator()(const Pair& lhs, const Pair& rhs) { |
+ bool operator()(const Pair& lhs, const Pair& rhs) const { |
return lhs.first < rhs.first; |
} |
}; |
- using Set = base::flat_set<Pair, LessByFirst>; |
+ using Tree = |
+ flat_tree<Pair, Pair, GetKeyFromValueIdentity<Pair>, LessByFirst>; |
// Constructors are not stable. |
- Set cont{{0, 0}, {1, 0}, {0, 1}, {2, 0}, {0, 2}, {1, 1}}; |
+ Tree cont{{0, 0}, {1, 0}, {0, 1}, {2, 0}, {0, 2}, {1, 1}}; |
auto NoneOfSecondsAreTwo = [&cont] { |
return std::none_of(cont.begin(), cont.end(), |
@@ -237,65 +231,65 @@ TEST(FlatSet, Stability) { |
// reverse_iterator |
// const_reverse_iterator |
-TEST(FlatSet, Types) { |
+TEST(FlatTree, Types) { |
// These are guaranteed to be portable. |
- static_assert((std::is_same<int, IntSet::key_type>::value), ""); |
- static_assert((std::is_same<int, IntSet::value_type>::value), ""); |
- static_assert((std::is_same<std::less<int>, IntSet::key_compare>::value), ""); |
- static_assert((std::is_same<std::less<int>, IntSet::value_compare>::value), |
+ static_assert((std::is_same<int, IntTree::key_type>::value), ""); |
+ static_assert((std::is_same<int, IntTree::value_type>::value), ""); |
+ static_assert((std::is_same<std::less<int>, IntTree::key_compare>::value), |
+ ""); |
+ static_assert((std::is_same<int&, IntTree::reference>::value), ""); |
+ static_assert((std::is_same<const int&, IntTree::const_reference>::value), |
""); |
- static_assert((std::is_same<int&, IntSet::reference>::value), ""); |
- static_assert((std::is_same<const int&, IntSet::const_reference>::value), ""); |
- static_assert((std::is_same<int*, IntSet::pointer>::value), ""); |
- static_assert((std::is_same<const int*, IntSet::const_pointer>::value), ""); |
+ static_assert((std::is_same<int*, IntTree::pointer>::value), ""); |
+ static_assert((std::is_same<const int*, IntTree::const_pointer>::value), ""); |
} |
// ---------------------------------------------------------------------------- |
// Lifetime. |
-// flat_set() |
-// flat_set(const Compare& comp) |
+// flat_tree() |
+// flat_tree(const Compare& comp) |
-TEST(FlatSet, DefaultConstructor) { |
+TEST(FlatTree, DefaultConstructor) { |
{ |
- IntSet cont; |
+ IntTree cont; |
EXPECT_THAT(cont, ElementsAre()); |
} |
{ |
- SetWithStrangeCompare cont(NonDefaultConstructibleCompare(0)); |
+ TreeWithStrangeCompare cont(NonDefaultConstructibleCompare(0)); |
EXPECT_THAT(cont, ElementsAre()); |
} |
} |
-// flat_set(InputIterator first, |
+// flat_tree(InputIterator first, |
// InputIterator last, |
// const Compare& comp = Compare()) |
-TEST(FlatSet, RangeConstructor) { |
+TEST(FlatTree, RangeConstructor) { |
{ |
- IntSet::value_type input_vals[] = {1, 1, 1, 2, 2, 2, 3, 3, 3}; |
+ IntTree::value_type input_vals[] = {1, 1, 1, 2, 2, 2, 3, 3, 3}; |
- IntSet cont(MakeInputIterator(std::begin(input_vals)), |
- MakeInputIterator(std::end(input_vals))); |
+ IntTree cont(MakeInputIterator(std::begin(input_vals)), |
+ MakeInputIterator(std::end(input_vals))); |
EXPECT_THAT(cont, ElementsAre(1, 2, 3)); |
} |
{ |
- SetWithStrangeCompare::value_type input_vals[] = {1, 1, 1, 2, 2, |
- 2, 3, 3, 3}; |
+ TreeWithStrangeCompare::value_type input_vals[] = {1, 1, 1, 2, 2, |
+ 2, 3, 3, 3}; |
- SetWithStrangeCompare cont(MakeInputIterator(std::begin(input_vals)), |
- MakeInputIterator(std::end(input_vals)), |
- NonDefaultConstructibleCompare(0)); |
+ TreeWithStrangeCompare cont(MakeInputIterator(std::begin(input_vals)), |
+ MakeInputIterator(std::end(input_vals)), |
+ NonDefaultConstructibleCompare(0)); |
EXPECT_THAT(cont, ElementsAre(1, 2, 3)); |
} |
} |
-// flat_set(const flat_set& x) |
+// flat_tree(const flat_tree& x) |
-TEST(FlatSet, CopyConstructor) { |
- IntSet original{1, 2, 3, 4}; |
- IntSet copied(original); |
+TEST(FlatTree, CopyConstructor) { |
+ IntTree original{1, 2, 3, 4}; |
+ IntTree copied(original); |
EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4)); |
@@ -304,31 +298,31 @@ TEST(FlatSet, CopyConstructor) { |
EXPECT_EQ(original, copied); |
} |
-// flat_set(flat_set&& x) |
+// flat_tree(flat_tree&& x) |
-TEST(FlatSet, MoveConstructor) { |
+TEST(FlatTree, MoveConstructor) { |
int input_range[] = {1, 2, 3, 4}; |
- MoveOnlySet original(std::begin(input_range), std::end(input_range)); |
- MoveOnlySet moved(std::move(original)); |
+ MoveOnlyTree original(std::begin(input_range), std::end(input_range)); |
+ MoveOnlyTree moved(std::move(original)); |
- EXPECT_EQ(1U, moved.count(MoveOnly(1))); |
- EXPECT_EQ(1U, moved.count(MoveOnly(2))); |
- EXPECT_EQ(1U, moved.count(MoveOnly(3))); |
- EXPECT_EQ(1U, moved.count(MoveOnly(4))); |
+ EXPECT_EQ(1U, moved.count(MoveOnlyInt(1))); |
+ EXPECT_EQ(1U, moved.count(MoveOnlyInt(2))); |
+ EXPECT_EQ(1U, moved.count(MoveOnlyInt(3))); |
+ EXPECT_EQ(1U, moved.count(MoveOnlyInt(4))); |
} |
-// flat_set(std::initializer_list<value_type> ilist, |
+// flat_tree(std::initializer_list<value_type> ilist, |
// const Compare& comp = Compare()) |
-TEST(FlatSet, InitializerListConstructor) { |
+TEST(FlatTree, InitializerListConstructor) { |
{ |
- IntSet cont{1, 2, 3, 4, 5, 6, 10, 8}; |
+ IntTree cont{1, 2, 3, 4, 5, 6, 10, 8}; |
EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); |
} |
{ |
- SetWithStrangeCompare cont({1, 2, 3, 4, 5, 6, 10, 8}, |
- NonDefaultConstructibleCompare(0)); |
+ TreeWithStrangeCompare cont({1, 2, 3, 4, 5, 6, 10, 8}, |
+ NonDefaultConstructibleCompare(0)); |
EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10)); |
} |
} |
@@ -336,11 +330,11 @@ TEST(FlatSet, InitializerListConstructor) { |
// ---------------------------------------------------------------------------- |
// Assignments. |
-// flat_set& operator=(const flat_set&) |
+// flat_tree& operator=(const flat_tree&) |
-TEST(FlatSet, CopyAssignable) { |
- IntSet original{1, 2, 3, 4}; |
- IntSet copied; |
+TEST(FlatTree, CopyAssignable) { |
+ IntTree original{1, 2, 3, 4}; |
+ IntTree copied; |
copied = original; |
EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4)); |
@@ -348,25 +342,25 @@ TEST(FlatSet, CopyAssignable) { |
EXPECT_EQ(original, copied); |
} |
-// flat_set& operator=(flat_set&&) |
+// flat_tree& operator=(flat_tree&&) |
-TEST(FlatSet, MoveAssignable) { |
+TEST(FlatTree, MoveAssignable) { |
int input_range[] = {1, 2, 3, 4}; |
- MoveOnlySet original(std::begin(input_range), std::end(input_range)); |
- MoveOnlySet moved; |
+ MoveOnlyTree original(std::begin(input_range), std::end(input_range)); |
+ MoveOnlyTree moved; |
moved = std::move(original); |
- EXPECT_EQ(1U, moved.count(MoveOnly(1))); |
- EXPECT_EQ(1U, moved.count(MoveOnly(2))); |
- EXPECT_EQ(1U, moved.count(MoveOnly(3))); |
- EXPECT_EQ(1U, moved.count(MoveOnly(4))); |
+ EXPECT_EQ(1U, moved.count(MoveOnlyInt(1))); |
+ EXPECT_EQ(1U, moved.count(MoveOnlyInt(2))); |
+ EXPECT_EQ(1U, moved.count(MoveOnlyInt(3))); |
+ EXPECT_EQ(1U, moved.count(MoveOnlyInt(4))); |
} |
-// flat_set& operator=(std::initializer_list<value_type> ilist) |
+// flat_tree& operator=(std::initializer_list<value_type> ilist) |
-TEST(FlatSet, InitializerListAssignable) { |
- IntSet cont{0}; |
+TEST(FlatTree, InitializerListAssignable) { |
+ IntTree cont{0}; |
cont = {1, 2, 3, 4, 5, 6, 10, 8}; |
EXPECT_EQ(0U, cont.count(0)); |
@@ -378,8 +372,8 @@ TEST(FlatSet, InitializerListAssignable) { |
// void reserve(size_type new_capacity) |
-TEST(FlatSet, Reserve) { |
- IntSet cont{1, 2, 3}; |
+TEST(FlatTree, Reserve) { |
+ IntTree cont{1, 2, 3}; |
cont.reserve(5); |
EXPECT_LE(5U, cont.capacity()); |
@@ -387,8 +381,8 @@ TEST(FlatSet, Reserve) { |
// size_type capacity() const |
-TEST(FlatSet, Capacity) { |
- IntSet cont{1, 2, 3}; |
+TEST(FlatTree, Capacity) { |
+ IntTree cont{1, 2, 3}; |
EXPECT_LE(cont.size(), cont.capacity()); |
cont.reserve(5); |
@@ -397,10 +391,10 @@ TEST(FlatSet, Capacity) { |
// void shrink_to_fit() |
-TEST(FlatSet, ShrinkToFit) { |
- IntSet cont{1, 2, 3}; |
+TEST(FlatTree, ShrinkToFit) { |
+ IntTree cont{1, 2, 3}; |
- IntSet::size_type capacity_before = cont.capacity(); |
+ IntTree::size_type capacity_before = cont.capacity(); |
cont.shrink_to_fit(); |
EXPECT_GE(capacity_before, cont.capacity()); |
} |
@@ -410,16 +404,16 @@ TEST(FlatSet, ShrinkToFit) { |
// void clear() |
-TEST(FlatSet, Clear) { |
- IntSet cont{1, 2, 3, 4, 5, 6, 7, 8}; |
+TEST(FlatTree, Clear) { |
+ IntTree cont{1, 2, 3, 4, 5, 6, 7, 8}; |
cont.clear(); |
EXPECT_THAT(cont, ElementsAre()); |
} |
// size_type size() const |
-TEST(FlatSet, Size) { |
- IntSet cont; |
+TEST(FlatTree, Size) { |
+ IntTree cont; |
EXPECT_EQ(0U, cont.size()); |
cont.insert(2); |
@@ -438,8 +432,8 @@ TEST(FlatSet, Size) { |
// bool empty() const |
-TEST(FlatSet, Empty) { |
- IntSet cont; |
+TEST(FlatTree, Empty) { |
+ IntTree cont; |
EXPECT_TRUE(cont.empty()); |
cont.insert(1); |
@@ -466,10 +460,10 @@ TEST(FlatSet, Empty) { |
// const_reverse_iterator crbegin() const |
// const_reverse_iterator crend() const |
-TEST(FlatSet, Iterators) { |
- IntSet cont{1, 2, 3, 4, 5, 6, 7, 8}; |
+TEST(FlatTree, Iterators) { |
+ IntTree cont{1, 2, 3, 4, 5, 6, 7, 8}; |
- auto size = static_cast<IntSet::difference_type>(cont.size()); |
+ auto size = static_cast<IntTree::difference_type>(cont.size()); |
EXPECT_EQ(size, std::distance(cont.begin(), cont.end())); |
EXPECT_EQ(size, std::distance(cont.cbegin(), cont.cend())); |
@@ -477,8 +471,8 @@ TEST(FlatSet, Iterators) { |
EXPECT_EQ(size, std::distance(cont.crbegin(), cont.crend())); |
{ |
- IntSet::iterator it = cont.begin(); |
- IntSet::const_iterator c_it = cont.cbegin(); |
+ IntTree::iterator it = cont.begin(); |
+ IntTree::const_iterator c_it = cont.cbegin(); |
EXPECT_EQ(it, c_it); |
for (int j = 1; it != cont.end(); ++it, ++c_it, ++j) { |
EXPECT_EQ(j, *it); |
@@ -486,8 +480,8 @@ TEST(FlatSet, Iterators) { |
} |
} |
{ |
- IntSet::reverse_iterator rit = cont.rbegin(); |
- IntSet::const_reverse_iterator c_rit = cont.crbegin(); |
+ IntTree::reverse_iterator rit = cont.rbegin(); |
+ IntTree::const_reverse_iterator c_rit = cont.crbegin(); |
EXPECT_EQ(rit, c_rit); |
for (int j = static_cast<int>(size); rit != cont.rend(); |
++rit, ++c_rit, --j) { |
@@ -502,11 +496,11 @@ TEST(FlatSet, Iterators) { |
// pair<iterator, bool> insert(const value_type& val) |
-TEST(FlatSet, InsertLValue) { |
- IntSet cont; |
+TEST(FlatTree, InsertLValue) { |
+ IntTree cont; |
int value = 2; |
- std::pair<IntSet::iterator, bool> result = cont.insert(value); |
+ std::pair<IntTree::iterator, bool> result = cont.insert(value); |
EXPECT_TRUE(result.second); |
EXPECT_EQ(cont.begin(), result.first); |
EXPECT_EQ(1U, cont.size()); |
@@ -536,28 +530,28 @@ TEST(FlatSet, InsertLValue) { |
// pair<iterator, bool> insert(value_type&& val) |
-TEST(FlatSet, InsertRValue) { |
- MoveOnlySet cont; |
+TEST(FlatTree, InsertRValue) { |
+ MoveOnlyTree cont; |
- std::pair<MoveOnlySet::iterator, bool> result = cont.insert(MoveOnly(2)); |
+ std::pair<MoveOnlyTree::iterator, bool> result = cont.insert(MoveOnlyInt(2)); |
EXPECT_TRUE(result.second); |
EXPECT_EQ(cont.begin(), result.first); |
EXPECT_EQ(1U, cont.size()); |
EXPECT_EQ(2, result.first->data()); |
- result = cont.insert(MoveOnly(1)); |
+ result = cont.insert(MoveOnlyInt(1)); |
EXPECT_TRUE(result.second); |
EXPECT_EQ(cont.begin(), result.first); |
EXPECT_EQ(2U, cont.size()); |
EXPECT_EQ(1, result.first->data()); |
- result = cont.insert(MoveOnly(3)); |
+ result = cont.insert(MoveOnlyInt(3)); |
EXPECT_TRUE(result.second); |
EXPECT_EQ(std::prev(cont.end()), result.first); |
EXPECT_EQ(3U, cont.size()); |
EXPECT_EQ(3, result.first->data()); |
- result = cont.insert(MoveOnly(3)); |
+ result = cont.insert(MoveOnlyInt(3)); |
EXPECT_FALSE(result.second); |
EXPECT_EQ(std::prev(cont.end()), result.first); |
EXPECT_EQ(3U, cont.size()); |
@@ -566,10 +560,10 @@ TEST(FlatSet, InsertRValue) { |
// iterator insert(const_iterator position_hint, const value_type& val) |
-TEST(FlatSet, InsertPositionLValue) { |
- IntSet cont; |
+TEST(FlatTree, InsertPositionLValue) { |
+ IntTree cont; |
- IntSet::iterator result = cont.insert(cont.cend(), 2); |
+ IntTree::iterator result = cont.insert(cont.cend(), 2); |
EXPECT_EQ(cont.begin(), result); |
EXPECT_EQ(1U, cont.size()); |
EXPECT_EQ(2, *result); |
@@ -592,25 +586,25 @@ TEST(FlatSet, InsertPositionLValue) { |
// iterator insert(const_iterator position_hint, value_type&& val) |
-TEST(FlatSet, InsertPositionRValue) { |
- MoveOnlySet cont; |
+TEST(FlatTree, InsertPositionRValue) { |
+ MoveOnlyTree cont; |
- MoveOnlySet::iterator result = cont.insert(cont.cend(), MoveOnly(2)); |
+ MoveOnlyTree::iterator result = cont.insert(cont.cend(), MoveOnlyInt(2)); |
EXPECT_EQ(cont.begin(), result); |
EXPECT_EQ(1U, cont.size()); |
EXPECT_EQ(2, result->data()); |
- result = cont.insert(cont.cend(), MoveOnly(1)); |
+ result = cont.insert(cont.cend(), MoveOnlyInt(1)); |
EXPECT_EQ(cont.begin(), result); |
EXPECT_EQ(2U, cont.size()); |
EXPECT_EQ(1, result->data()); |
- result = cont.insert(cont.cend(), MoveOnly(3)); |
+ result = cont.insert(cont.cend(), MoveOnlyInt(3)); |
EXPECT_EQ(std::prev(cont.end()), result); |
EXPECT_EQ(3U, cont.size()); |
EXPECT_EQ(3, result->data()); |
- result = cont.insert(cont.cend(), MoveOnly(3)); |
+ result = cont.insert(cont.cend(), MoveOnlyInt(3)); |
EXPECT_EQ(std::prev(cont.end()), result); |
EXPECT_EQ(3U, cont.size()); |
EXPECT_EQ(3, result->data()); |
@@ -619,11 +613,11 @@ TEST(FlatSet, InsertPositionRValue) { |
// template <class... Args> |
// pair<iterator, bool> emplace(Args&&... args) |
-TEST(FlatSet, Emplace) { |
+TEST(FlatTree, Emplace) { |
{ |
- EmplaceableSet cont; |
+ EmplaceableTree cont; |
- std::pair<EmplaceableSet::iterator, bool> result = cont.emplace(); |
+ std::pair<EmplaceableTree::iterator, bool> result = cont.emplace(); |
EXPECT_TRUE(result.second); |
EXPECT_EQ(cont.begin(), result.first); |
EXPECT_EQ(1U, cont.size()); |
@@ -642,9 +636,9 @@ TEST(FlatSet, Emplace) { |
EXPECT_EQ(Emplaceable(2, 3.5), *result.first); |
} |
{ |
- IntSet cont; |
+ IntTree cont; |
- std::pair<IntSet::iterator, bool> result = cont.emplace(2); |
+ std::pair<IntTree::iterator, bool> result = cont.emplace(2); |
EXPECT_TRUE(result.second); |
EXPECT_EQ(cont.begin(), result.first); |
EXPECT_EQ(1U, cont.size()); |
@@ -655,11 +649,11 @@ TEST(FlatSet, Emplace) { |
// template <class... Args> |
// iterator emplace_hint(const_iterator position_hint, Args&&... args) |
-TEST(FlatSet, EmplacePosition) { |
+TEST(FlatTree, EmplacePosition) { |
{ |
- EmplaceableSet cont; |
+ EmplaceableTree cont; |
- EmplaceableSet::iterator result = cont.emplace_hint(cont.cend()); |
+ EmplaceableTree::iterator result = cont.emplace_hint(cont.cend()); |
EXPECT_EQ(cont.begin(), result); |
EXPECT_EQ(1U, cont.size()); |
EXPECT_EQ(Emplaceable(), *cont.begin()); |
@@ -675,9 +669,9 @@ TEST(FlatSet, EmplacePosition) { |
EXPECT_EQ(Emplaceable(2, 3.5), *result); |
} |
{ |
- IntSet cont; |
+ IntTree cont; |
- IntSet::iterator result = cont.emplace_hint(cont.cend(), 2); |
+ IntTree::iterator result = cont.emplace_hint(cont.cend(), 2); |
EXPECT_EQ(cont.begin(), result); |
EXPECT_EQ(1U, cont.size()); |
EXPECT_EQ(2, *result); |
@@ -689,10 +683,10 @@ TEST(FlatSet, EmplacePosition) { |
// iterator erase(const_iterator position_hint) |
-TEST(FlatSet, ErasePosition) { |
- IntSet cont{1, 2, 3, 4, 5, 6, 7, 8}; |
+TEST(FlatTree, ErasePosition) { |
+ IntTree cont{1, 2, 3, 4, 5, 6, 7, 8}; |
- IntSet::iterator it = cont.erase(std::next(cont.cbegin(), 3)); |
+ IntTree::iterator it = cont.erase(std::next(cont.cbegin(), 3)); |
EXPECT_EQ(std::next(cont.begin(), 3), it); |
EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8)); |
@@ -727,10 +721,10 @@ TEST(FlatSet, ErasePosition) { |
// iterator erase(const_iterator first, const_iterator last) |
-TEST(FlatSet, EraseRange) { |
- IntSet cont{1, 2, 3, 4, 5, 6, 7, 8}; |
+TEST(FlatTree, EraseRange) { |
+ IntTree cont{1, 2, 3, 4, 5, 6, 7, 8}; |
- IntSet::iterator it = |
+ IntTree::iterator it = |
cont.erase(std::next(cont.cbegin(), 5), std::next(cont.cbegin(), 5)); |
EXPECT_EQ(std::next(cont.begin(), 5), it); |
EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8)); |
@@ -754,8 +748,8 @@ TEST(FlatSet, EraseRange) { |
// size_type erase(const key_type& key) |
-TEST(FlatSet, EraseKey) { |
- IntSet cont{1, 2, 3, 4, 5, 6, 7, 8}; |
+TEST(FlatTree, EraseKey) { |
+ IntTree cont{1, 2, 3, 4, 5, 6, 7, 8}; |
EXPECT_EQ(0U, cont.erase(9)); |
EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 7, 8)); |
@@ -790,8 +784,8 @@ TEST(FlatSet, EraseKey) { |
// key_compare key_comp() const |
-TEST(FlatSet, KeyComp) { |
- ReversedSet cont{1, 2, 3, 4, 5}; |
+TEST(FlatTree, KeyComp) { |
+ ReversedTree cont{1, 2, 3, 4, 5}; |
EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.key_comp())); |
int new_elements[] = {6, 7, 8, 9, 10}; |
@@ -802,8 +796,8 @@ TEST(FlatSet, KeyComp) { |
// value_compare value_comp() const |
-TEST(FlatSet, ValueComp) { |
- ReversedSet cont{1, 2, 3, 4, 5}; |
+TEST(FlatTree, ValueComp) { |
+ ReversedTree cont{1, 2, 3, 4, 5}; |
EXPECT_TRUE(std::is_sorted(cont.begin(), cont.end(), cont.value_comp())); |
int new_elements[] = {6, 7, 8, 9, 10}; |
@@ -817,9 +811,9 @@ TEST(FlatSet, ValueComp) { |
// size_type count(const key_type& key) const |
-TEST(FlatSet, Count) { |
+TEST(FlatTree, Count) { |
{ |
- const IntSet cont{5, 6, 7, 8, 9, 10, 11, 12}; |
+ const IntTree cont{5, 6, 7, 8, 9, 10, 11, 12}; |
EXPECT_EQ(1U, cont.count(5)); |
EXPECT_EQ(1U, cont.count(6)); |
@@ -832,7 +826,7 @@ TEST(FlatSet, Count) { |
EXPECT_EQ(0U, cont.count(4)); |
} |
{ |
- const SetWithLess cont{5, 6, 7, 8, 9, 10, 11, 12}; |
+ const IntTreeWithLess cont{5, 6, 7, 8, 9, 10, 11, 12}; |
EXPECT_EQ(1U, cont.count(5)); |
EXPECT_EQ(1U, cont.count(6)); |
@@ -849,9 +843,9 @@ TEST(FlatSet, Count) { |
// iterator find(const key_type& key) |
// const_iterator find(const key_type& key) const |
-TEST(FlatSet, Find) { |
+TEST(FlatTree, Find) { |
{ |
- IntSet cont{5, 6, 7, 8, 9, 10, 11, 12}; |
+ IntTree cont{5, 6, 7, 8, 9, 10, 11, 12}; |
EXPECT_EQ(cont.begin(), cont.find(5)); |
EXPECT_EQ(std::next(cont.begin()), cont.find(6)); |
@@ -864,7 +858,7 @@ TEST(FlatSet, Find) { |
EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); |
} |
{ |
- const IntSet cont{5, 6, 7, 8, 9, 10, 11, 12}; |
+ const IntTree cont{5, 6, 7, 8, 9, 10, 11, 12}; |
EXPECT_EQ(cont.begin(), cont.find(5)); |
EXPECT_EQ(std::next(cont.begin()), cont.find(6)); |
@@ -877,7 +871,7 @@ TEST(FlatSet, Find) { |
EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4)); |
} |
{ |
- SetWithLess cont{5, 6, 7, 8, 9, 10, 11, 12}; |
+ IntTreeWithLess cont{5, 6, 7, 8, 9, 10, 11, 12}; |
EXPECT_EQ(cont.begin(), cont.find(5)); |
EXPECT_EQ(std::next(cont.begin()), cont.find(6)); |
@@ -894,11 +888,12 @@ TEST(FlatSet, Find) { |
// pair<iterator, iterator> equal_range(const key_type& key) |
// pair<const_iterator, const_iterator> equal_range(const key_type& key) const |
-TEST(FlatSet, EqualRange) { |
+TEST(FlatTree, EqualRange) { |
{ |
- IntSet cont{5, 7, 9, 11, 13, 15, 17, 19}; |
+ IntTree cont{5, 7, 9, 11, 13, 15, 17, 19}; |
- std::pair<IntSet::iterator, IntSet::iterator> result = cont.equal_range(5); |
+ std::pair<IntTree::iterator, IntTree::iterator> result = |
+ cont.equal_range(5); |
EXPECT_EQ(std::next(cont.begin(), 0), result.first); |
EXPECT_EQ(std::next(cont.begin(), 1), result.second); |
result = cont.equal_range(7); |
@@ -951,9 +946,9 @@ TEST(FlatSet, EqualRange) { |
EXPECT_EQ(std::next(cont.begin(), 8), result.second); |
} |
{ |
- const IntSet cont{5, 7, 9, 11, 13, 15, 17, 19}; |
+ const IntTree cont{5, 7, 9, 11, 13, 15, 17, 19}; |
- std::pair<IntSet::const_iterator, IntSet::const_iterator> result = |
+ std::pair<IntTree::const_iterator, IntTree::const_iterator> result = |
cont.equal_range(5); |
EXPECT_EQ(std::next(cont.begin(), 0), result.first); |
EXPECT_EQ(std::next(cont.begin(), 1), result.second); |
@@ -1007,9 +1002,9 @@ TEST(FlatSet, EqualRange) { |
EXPECT_EQ(std::next(cont.begin(), 8), result.second); |
} |
{ |
- SetWithLess cont{5, 7, 9, 11, 13, 15, 17, 19}; |
+ IntTreeWithLess cont{5, 7, 9, 11, 13, 15, 17, 19}; |
- std::pair<SetWithLess::iterator, SetWithLess::iterator> result = |
+ std::pair<IntTree::iterator, IntTree::iterator> result = |
cont.equal_range(5); |
EXPECT_EQ(std::next(cont.begin(), 0), result.first); |
EXPECT_EQ(std::next(cont.begin(), 1), result.second); |
@@ -1067,9 +1062,9 @@ TEST(FlatSet, EqualRange) { |
// iterator lower_bound(const key_type& key); |
// const_iterator lower_bound(const key_type& key) const; |
-TEST(FlatSet, LowerBound) { |
+TEST(FlatTree, LowerBound) { |
{ |
- IntSet cont{5, 7, 9, 11, 13, 15, 17, 19}; |
+ IntTree cont{5, 7, 9, 11, 13, 15, 17, 19}; |
EXPECT_EQ(cont.begin(), cont.lower_bound(5)); |
EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7)); |
@@ -1090,7 +1085,7 @@ TEST(FlatSet, LowerBound) { |
EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); |
} |
{ |
- const IntSet cont{5, 7, 9, 11, 13, 15, 17, 19}; |
+ const IntTree cont{5, 7, 9, 11, 13, 15, 17, 19}; |
EXPECT_EQ(cont.begin(), cont.lower_bound(5)); |
EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7)); |
@@ -1111,7 +1106,7 @@ TEST(FlatSet, LowerBound) { |
EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20)); |
} |
{ |
- SetWithLess cont{5, 7, 9, 11, 13, 15, 17, 19}; |
+ IntTreeWithLess cont{5, 7, 9, 11, 13, 15, 17, 19}; |
EXPECT_EQ(cont.begin(), cont.lower_bound(5)); |
EXPECT_EQ(std::next(cont.begin()), cont.lower_bound(7)); |
@@ -1136,9 +1131,9 @@ TEST(FlatSet, LowerBound) { |
// iterator upper_bound(const key_type& key) |
// const_iterator upper_bound(const key_type& key) const |
-TEST(FlatSet, UpperBound) { |
+TEST(FlatTree, UpperBound) { |
{ |
- IntSet cont{5, 7, 9, 11, 13, 15, 17, 19}; |
+ IntTree cont{5, 7, 9, 11, 13, 15, 17, 19}; |
EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); |
EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7)); |
@@ -1159,7 +1154,7 @@ TEST(FlatSet, UpperBound) { |
EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); |
} |
{ |
- const IntSet cont{5, 7, 9, 11, 13, 15, 17, 19}; |
+ const IntTree cont{5, 7, 9, 11, 13, 15, 17, 19}; |
EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); |
EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7)); |
@@ -1180,7 +1175,7 @@ TEST(FlatSet, UpperBound) { |
EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20)); |
} |
{ |
- SetWithLess cont{5, 7, 9, 11, 13, 15, 17, 19}; |
+ IntTreeWithLess cont{5, 7, 9, 11, 13, 15, 17, 19}; |
EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(5)); |
EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(7)); |
@@ -1205,12 +1200,12 @@ TEST(FlatSet, UpperBound) { |
// ---------------------------------------------------------------------------- |
// General operations. |
-// void swap(flat_set& other) |
-// void swap(flat_set& lhs, flat_set& rhs) |
+// void swap(flat_tree& other) |
+// void swap(flat_tree& lhs, flat_tree& rhs) |
-TEST(FlatSetOurs, Swap) { |
- IntSet x{1, 2, 3}; |
- IntSet y{4}; |
+TEST(FlatTreeOurs, Swap) { |
+ IntTree x{1, 2, 3}; |
+ IntTree y{4}; |
swap(x, y); |
EXPECT_THAT(x, ElementsAre(4)); |
EXPECT_THAT(y, ElementsAre(1, 2, 3)); |
@@ -1220,18 +1215,18 @@ TEST(FlatSetOurs, Swap) { |
EXPECT_THAT(y, ElementsAre(4)); |
} |
-// bool operator==(const flat_set& lhs, const flat_set& rhs) |
-// bool operator!=(const flat_set& lhs, const flat_set& rhs) |
-// bool operator<(const flat_set& lhs, const flat_set& rhs) |
-// bool operator>(const flat_set& lhs, const flat_set& rhs) |
-// bool operator<=(const flat_set& lhs, const flat_set& rhs) |
-// bool operator>=(const flat_set& lhs, const flat_set& rhs) |
+// bool operator==(const flat_tree& lhs, const flat_tree& rhs) |
+// bool operator!=(const flat_tree& lhs, const flat_tree& rhs) |
+// bool operator<(const flat_tree& lhs, const flat_tree& rhs) |
+// bool operator>(const flat_tree& lhs, const flat_tree& rhs) |
+// bool operator<=(const flat_tree& lhs, const flat_tree& rhs) |
+// bool operator>=(const flat_tree& lhs, const flat_tree& rhs) |
-TEST(FlatSet, Comparison) { |
+TEST(FlatTree, Comparison) { |
// Provided comparator does not participate in comparison. |
- ReversedSet biggest{3}; |
- ReversedSet smallest{1}; |
- ReversedSet middle{1, 2}; |
+ ReversedTree biggest{3}; |
+ ReversedTree smallest{1}; |
+ ReversedTree middle{1, 2}; |
EXPECT_EQ(biggest, biggest); |
EXPECT_NE(biggest, smallest); |
@@ -1244,15 +1239,18 @@ TEST(FlatSet, Comparison) { |
} |
TEST(FlatSet, EraseIf) { |
- IntSet x; |
- base::EraseIf(x, [](int) { return false; }); |
+ IntTree x; |
+ EraseIf(x, [](int) { return false; }); |
EXPECT_THAT(x, ElementsAre()); |
x = {1, 2, 3}; |
- base::EraseIf(x, [](int elem) { return !(elem & 1); }); |
+ EraseIf(x, [](int elem) { return !(elem & 1); }); |
EXPECT_THAT(x, ElementsAre(1, 3)); |
x = {1, 2, 3, 4}; |
- base::EraseIf(x, [](int elem) { return elem & 1; }); |
+ EraseIf(x, [](int elem) { return elem & 1; }); |
EXPECT_THAT(x, ElementsAre(2, 4)); |
} |
+ |
+} // namespace internal |
+} // namespace base |