12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541 |
- // 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/llvm-project/tree/main/libcxx/test/std/containers/associative/set
- //
- // Not ported tests:
- // * No tests with PrivateConstructor and std::less<> changed to std::less<T>
- // These tests have to do with C++14 std::less<>
- // http://en.cppreference.com/w/cpp/utility/functional/less_void
- // and add support for templated versions of lookup functions.
- // Because we use same implementation, we figured that it's OK just to check
- // compilation and this is what we do in flat_set_unittest/flat_map_unittest.
- // * No tests for max_size()
- // Has to do with allocator support.
- // * 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.
- #include <deque>
- #include <forward_list>
- #include <functional>
- #include <iterator>
- #include <list>
- #include <string>
- #include <vector>
- #include "base/functional/identity.h"
- #include "base/ranges/algorithm.h"
- #include "base/template_util.h"
- #include "base/test/gtest_util.h"
- #include "base/test/move_only_int.h"
- #include "testing/gmock/include/gmock/gmock.h"
- #include "testing/gtest/include/gtest/gtest.h"
- namespace base {
- namespace internal {
- namespace {
- template <class It>
- class InputIterator {
- public:
- using iterator_category = std::input_iterator_tag;
- using value_type = typename std::iterator_traits<It>::value_type;
- using difference_type = typename std::iterator_traits<It>::difference_type;
- using pointer = It;
- using reference = typename std::iterator_traits<It>::reference;
- InputIterator() : it_() {}
- explicit InputIterator(It it) : it_(it) {}
- reference operator*() const { return *it_; }
- pointer operator->() const { return it_; }
- InputIterator& operator++() {
- ++it_;
- return *this;
- }
- InputIterator operator++(int) {
- InputIterator tmp(*this);
- ++(*this);
- return tmp;
- }
- friend bool operator==(const InputIterator& lhs, const InputIterator& rhs) {
- return lhs.it_ == rhs.it_;
- }
- friend bool operator!=(const InputIterator& lhs, const InputIterator& rhs) {
- return !(lhs == rhs);
- }
- private:
- It it_;
- };
- template <typename It>
- InputIterator<It> MakeInputIterator(It it) {
- return InputIterator<It>(it);
- }
- class Emplaceable {
- public:
- Emplaceable() : Emplaceable(0, 0.0) {}
- Emplaceable(int i, double d) : int_(i), double_(d) {}
- Emplaceable(Emplaceable&& other) : int_(other.int_), double_(other.double_) {
- other.int_ = 0;
- other.double_ = 0.0;
- }
- Emplaceable(const Emplaceable&) = delete;
- Emplaceable& operator=(const Emplaceable&) = delete;
- Emplaceable& operator=(Emplaceable&& other) {
- int_ = other.int_;
- other.int_ = 0;
- double_ = other.double_;
- other.double_ = 0.0;
- return *this;
- }
- friend bool operator==(const Emplaceable& lhs, const Emplaceable& rhs) {
- return std::tie(lhs.int_, lhs.double_) == std::tie(rhs.int_, rhs.double_);
- }
- friend bool operator<(const Emplaceable& lhs, const Emplaceable& rhs) {
- return std::tie(lhs.int_, lhs.double_) < std::tie(rhs.int_, rhs.double_);
- }
- private:
- int int_;
- double double_;
- };
- struct TemplateConstructor {
- template <typename T>
- TemplateConstructor(const T&) {}
- friend bool operator<(const TemplateConstructor&,
- const TemplateConstructor&) {
- return false;
- }
- };
- class NonDefaultConstructibleCompare {
- public:
- explicit NonDefaultConstructibleCompare(int) {}
- template <typename T>
- bool operator()(const T& lhs, const T& rhs) const {
- return std::less<T>()(lhs, rhs);
- }
- };
- template <class PairType>
- struct LessByFirst {
- bool operator()(const PairType& lhs, const PairType& rhs) const {
- return lhs.first < rhs.first;
- }
- };
- // Common test trees.
- template <typename ContainerT>
- using TypedTree = flat_tree<typename ContainerT::value_type,
- base::identity,
- std::less<>,
- ContainerT>;
- using IntTree = TypedTree<std::vector<int>>;
- using IntPair = std::pair<int, int>;
- using IntPairTree = flat_tree<IntPair,
- base::identity,
- LessByFirst<IntPair>,
- std::vector<IntPair>>;
- using MoveOnlyTree = flat_tree<MoveOnlyInt,
- base::identity,
- std::less<>,
- std::vector<MoveOnlyInt>>;
- using EmplaceableTree = flat_tree<Emplaceable,
- base::identity,
- std::less<>,
- std::vector<Emplaceable>>;
- using ReversedTree =
- flat_tree<int, base::identity, std::greater<int>, std::vector<int>>;
- using TreeWithStrangeCompare = flat_tree<int,
- base::identity,
- NonDefaultConstructibleCompare,
- std::vector<int>>;
- using ::testing::ElementsAre;
- using ::testing::IsEmpty;
- } // namespace
- template <typename T>
- class FlatTreeTest : public testing::Test {};
- TYPED_TEST_SUITE_P(FlatTreeTest);
- 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");
- }
- // Tests that the compiler generated move operators propagrate noexcept
- // specifiers.
- TEST(FlatTree, NoExcept) {
- struct MoveThrows {
- MoveThrows(MoveThrows&&) noexcept(false) {}
- MoveThrows& operator=(MoveThrows&&) noexcept(false) { return *this; }
- };
- using MoveThrowsTree = flat_tree<MoveThrows, base::identity, std::less<>,
- std::array<MoveThrows, 1>>;
- static_assert(std::is_nothrow_move_constructible<IntTree>::value,
- "Error: IntTree is not nothrow move constructible");
- static_assert(std::is_nothrow_move_assignable<IntTree>::value,
- "Error: IntTree is not nothrow move assignable");
- static_assert(!std::is_nothrow_move_constructible<MoveThrowsTree>::value,
- "Error: MoveThrowsTree is nothrow move constructible");
- static_assert(!std::is_nothrow_move_assignable<MoveThrowsTree>::value,
- "Error: MoveThrowsTree is nothrow move assignable");
- }
- // ----------------------------------------------------------------------------
- // Class.
- // Check that flat_tree and its iterators can be instantiated with an
- // incomplete type.
- TEST(FlatTree, IncompleteType) {
- struct A {
- using Tree = flat_tree<A, base::identity, std::less<A>, std::vector<A>>;
- int data;
- Tree set_with_incomplete_type;
- Tree::iterator it;
- Tree::const_iterator cit;
- // We do not declare operator< because clang complains that it's unused.
- };
- A a;
- }
- TEST(FlatTree, Stability) {
- using Pair = std::pair<int, int>;
- using Tree =
- flat_tree<Pair, base::identity, LessByFirst<Pair>, std::vector<Pair>>;
- // Constructors are stable.
- Tree cont({{0, 0}, {1, 0}, {0, 1}, {2, 0}, {0, 2}, {1, 1}});
- auto AllOfSecondsAreZero = [&cont] {
- return ranges::all_of(cont,
- [](const Pair& elem) { return elem.second == 0; });
- };
- EXPECT_TRUE(AllOfSecondsAreZero()) << "constructor should be stable";
- // Should not replace existing.
- cont.insert(Pair(0, 2));
- cont.insert(Pair(1, 2));
- cont.insert(Pair(2, 2));
- EXPECT_TRUE(AllOfSecondsAreZero()) << "insert should be stable";
- cont.insert(Pair(3, 0));
- cont.insert(Pair(3, 2));
- EXPECT_TRUE(AllOfSecondsAreZero()) << "insert should be stable";
- }
- // ----------------------------------------------------------------------------
- // Types.
- // key_type
- // key_compare
- // value_type
- // value_compare
- // pointer
- // const_pointer
- // reference
- // const_reference
- // size_type
- // difference_type
- // iterator
- // const_iterator
- // reverse_iterator
- // const_reverse_iterator
- TEST(FlatTree, Types) {
- // These are guaranteed to be portable.
- 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<>, 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*, IntTree::pointer>::value), "");
- static_assert((std::is_same<const int*, IntTree::const_pointer>::value), "");
- }
- // ----------------------------------------------------------------------------
- // Lifetime.
- // flat_tree()
- // flat_tree(const Compare& comp)
- TYPED_TEST_P(FlatTreeTest, DefaultConstructor) {
- {
- TypedTree<TypeParam> cont;
- EXPECT_THAT(cont, ElementsAre());
- }
- {
- TreeWithStrangeCompare cont(NonDefaultConstructibleCompare(0));
- EXPECT_THAT(cont, ElementsAre());
- }
- }
- // flat_tree(const flat_tree& x)
- TYPED_TEST_P(FlatTreeTest, CopyConstructor) {
- TypedTree<TypeParam> original({1, 2, 3, 4});
- TypedTree<TypeParam> copied(original);
- EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4));
- EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4));
- EXPECT_THAT(original, ElementsAre(1, 2, 3, 4));
- EXPECT_EQ(original, copied);
- }
- // flat_tree(flat_tree&& x)
- TEST(FlatTree, MoveConstructor) {
- int input_range[] = {1, 2, 3, 4};
- MoveOnlyTree original(std::begin(input_range), std::end(input_range));
- MoveOnlyTree moved(std::move(original));
- 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_tree(InputIterator first,
- // InputIterator last,
- // const Compare& comp = Compare())
- TEST(FlatTree, RangeConstructor) {
- {
- IntPair input_vals[] = {{1, 1}, {1, 2}, {2, 1}, {2, 2}, {1, 3},
- {2, 3}, {3, 1}, {3, 2}, {3, 3}};
- IntPairTree first_of(MakeInputIterator(std::begin(input_vals)),
- MakeInputIterator(std::end(input_vals)));
- EXPECT_THAT(first_of,
- ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1)));
- }
- {
- TreeWithStrangeCompare::value_type input_vals[] = {1, 1, 1, 2, 2,
- 2, 3, 3, 3};
- TreeWithStrangeCompare cont(MakeInputIterator(std::begin(input_vals)),
- MakeInputIterator(std::end(input_vals)),
- NonDefaultConstructibleCompare(0));
- EXPECT_THAT(cont, ElementsAre(1, 2, 3));
- }
- }
- // flat_tree(const container_type&)
- TYPED_TEST_P(FlatTreeTest, ContainerCopyConstructor) {
- TypeParam items = {1, 2, 3, 4};
- TypedTree<TypeParam> tree(items);
- EXPECT_THAT(tree, ElementsAre(1, 2, 3, 4));
- EXPECT_THAT(items, ElementsAre(1, 2, 3, 4));
- }
- // flat_tree(container_type&&)
- TEST(FlatTree, ContainerMoveConstructor) {
- using Pair = std::pair<int, MoveOnlyInt>;
- // Construct an unsorted vector with a duplicate item in it. Sorted by the
- // first item, the second allows us to test for stability. Using a move
- // only type to ensure the vector is not copied.
- std::vector<Pair> storage;
- storage.push_back(Pair(2, MoveOnlyInt(0)));
- storage.push_back(Pair(1, MoveOnlyInt(0)));
- storage.push_back(Pair(2, MoveOnlyInt(1)));
- using Tree =
- flat_tree<Pair, base::identity, LessByFirst<Pair>, std::vector<Pair>>;
- Tree tree(std::move(storage));
- // The list should be two items long, with only the first "2" saved.
- ASSERT_EQ(2u, tree.size());
- const Pair& zeroth = *tree.begin();
- ASSERT_EQ(1, zeroth.first);
- ASSERT_EQ(0, zeroth.second.data());
- const Pair& first = *(tree.begin() + 1);
- ASSERT_EQ(2, first.first);
- ASSERT_EQ(0, first.second.data());
- }
- // flat_tree(std::initializer_list<value_type> ilist,
- // const Compare& comp = Compare())
- TYPED_TEST_P(FlatTreeTest, InitializerListConstructor) {
- {
- TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 10, 8});
- EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
- }
- {
- TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 10, 8});
- EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
- }
- {
- TreeWithStrangeCompare cont({1, 2, 3, 4, 5, 6, 10, 8},
- NonDefaultConstructibleCompare(0));
- EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
- }
- {
- IntPairTree first_of({{1, 1}, {2, 1}, {1, 2}});
- EXPECT_THAT(first_of, ElementsAre(IntPair(1, 1), IntPair(2, 1)));
- }
- }
- // flat_tree(sorted_unique_t,
- // InputIterator first,
- // InputIterator last,
- // const Compare& comp = Compare())
- TEST(FlatTree, SortedUniqueRangeConstructor) {
- {
- IntPair input_vals[] = {{1, 1}, {2, 1}, {3, 1}};
- IntPairTree first_of(sorted_unique,
- MakeInputIterator(std::begin(input_vals)),
- MakeInputIterator(std::end(input_vals)));
- EXPECT_THAT(first_of,
- ElementsAre(IntPair(1, 1), IntPair(2, 1), IntPair(3, 1)));
- }
- {
- TreeWithStrangeCompare::value_type input_vals[] = {1, 2, 3};
- TreeWithStrangeCompare cont(sorted_unique,
- MakeInputIterator(std::begin(input_vals)),
- MakeInputIterator(std::end(input_vals)),
- NonDefaultConstructibleCompare(0));
- EXPECT_THAT(cont, ElementsAre(1, 2, 3));
- }
- }
- // flat_tree(sorted_unique_t, const container_type&)
- TYPED_TEST_P(FlatTreeTest, SortedUniqueContainerCopyConstructor) {
- TypeParam items = {1, 2, 3, 4};
- TypedTree<TypeParam> tree(sorted_unique, items);
- EXPECT_THAT(tree, ElementsAre(1, 2, 3, 4));
- EXPECT_THAT(items, ElementsAre(1, 2, 3, 4));
- }
- // flat_tree(sorted_unique_t, std::vector<value_type>&&)
- TEST(FlatTree, SortedUniqueVectorMoveConstructor) {
- using Pair = std::pair<int, MoveOnlyInt>;
- std::vector<Pair> storage;
- storage.push_back(Pair(1, MoveOnlyInt(0)));
- storage.push_back(Pair(2, MoveOnlyInt(0)));
- using Tree =
- flat_tree<Pair, base::identity, LessByFirst<Pair>, std::vector<Pair>>;
- Tree tree(sorted_unique, std::move(storage));
- ASSERT_EQ(2u, tree.size());
- const Pair& zeroth = *tree.begin();
- ASSERT_EQ(1, zeroth.first);
- ASSERT_EQ(0, zeroth.second.data());
- const Pair& first = *(tree.begin() + 1);
- ASSERT_EQ(2, first.first);
- ASSERT_EQ(0, first.second.data());
- }
- // flat_tree(sorted_unique_t,
- // std::initializer_list<value_type> ilist,
- // const Compare& comp = Compare())
- TYPED_TEST_P(FlatTreeTest, SortedUniqueInitializerListConstructor) {
- {
- TypedTree<TypeParam> cont(sorted_unique, {1, 2, 3, 4, 5, 6, 8, 10});
- EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
- }
- {
- TypedTree<TypeParam> cont(sorted_unique, {1, 2, 3, 4, 5, 6, 8, 10});
- EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
- }
- {
- TreeWithStrangeCompare cont(sorted_unique, {1, 2, 3, 4, 5, 6, 8, 10},
- NonDefaultConstructibleCompare(0));
- EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
- }
- {
- IntPairTree first_of(sorted_unique, {{1, 1}, {2, 1}});
- EXPECT_THAT(first_of, ElementsAre(IntPair(1, 1), IntPair(2, 1)));
- }
- }
- // ----------------------------------------------------------------------------
- // Assignments.
- // flat_tree& operator=(const flat_tree&)
- TYPED_TEST_P(FlatTreeTest, CopyAssignable) {
- TypedTree<TypeParam> original({1, 2, 3, 4});
- TypedTree<TypeParam> copied;
- copied = original;
- EXPECT_THAT(copied, ElementsAre(1, 2, 3, 4));
- EXPECT_THAT(original, ElementsAre(1, 2, 3, 4));
- EXPECT_EQ(original, copied);
- }
- // flat_tree& operator=(flat_tree&&)
- TEST(FlatTree, MoveAssignable) {
- int input_range[] = {1, 2, 3, 4};
- MoveOnlyTree original(std::begin(input_range), std::end(input_range));
- MoveOnlyTree moved;
- moved = std::move(original);
- 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_tree& operator=(std::initializer_list<value_type> ilist)
- TYPED_TEST_P(FlatTreeTest, InitializerListAssignable) {
- TypedTree<TypeParam> cont({0});
- cont = {1, 2, 3, 4, 5, 6, 10, 8};
- EXPECT_EQ(0U, cont.count(0));
- EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4, 5, 6, 8, 10));
- }
- // --------------------------------------------------------------------------
- // Memory management.
- // void reserve(size_type new_capacity)
- TEST(FlatTreeTest, Reserve) {
- IntTree cont({1, 2, 3});
- cont.reserve(5);
- EXPECT_LE(5U, cont.capacity());
- }
- // size_type capacity() const
- TEST(FlatTreeTest, Capacity) {
- IntTree cont({1, 2, 3});
- EXPECT_LE(cont.size(), cont.capacity());
- cont.reserve(5);
- EXPECT_LE(cont.size(), cont.capacity());
- }
- // void shrink_to_fit()
- TEST(FlatTreeTest, ShrinkToFit) {
- IntTree cont({1, 2, 3});
- IntTree::size_type capacity_before = cont.capacity();
- cont.shrink_to_fit();
- EXPECT_GE(capacity_before, cont.capacity());
- }
- // ----------------------------------------------------------------------------
- // Size management.
- // void clear()
- TYPED_TEST_P(FlatTreeTest, Clear) {
- TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8});
- cont.clear();
- EXPECT_THAT(cont, ElementsAre());
- }
- // size_type size() const
- TYPED_TEST_P(FlatTreeTest, Size) {
- TypedTree<TypeParam> cont;
- EXPECT_EQ(0U, cont.size());
- cont.insert(2);
- EXPECT_EQ(1U, cont.size());
- cont.insert(1);
- EXPECT_EQ(2U, cont.size());
- cont.insert(3);
- EXPECT_EQ(3U, cont.size());
- cont.erase(cont.begin());
- EXPECT_EQ(2U, cont.size());
- cont.erase(cont.begin());
- EXPECT_EQ(1U, cont.size());
- cont.erase(cont.begin());
- EXPECT_EQ(0U, cont.size());
- }
- // bool empty() const
- TYPED_TEST_P(FlatTreeTest, Empty) {
- TypedTree<TypeParam> cont;
- EXPECT_TRUE(cont.empty());
- cont.insert(1);
- EXPECT_FALSE(cont.empty());
- cont.clear();
- EXPECT_TRUE(cont.empty());
- }
- // ----------------------------------------------------------------------------
- // Iterators.
- // iterator begin()
- // const_iterator begin() const
- // iterator end()
- // const_iterator end() const
- //
- // reverse_iterator rbegin()
- // const_reverse_iterator rbegin() const
- // reverse_iterator rend()
- // const_reverse_iterator rend() const
- //
- // const_iterator cbegin() const
- // const_iterator cend() const
- // const_reverse_iterator crbegin() const
- // const_reverse_iterator crend() const
- TYPED_TEST_P(FlatTreeTest, Iterators) {
- TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8});
- auto size =
- static_cast<typename TypedTree<TypeParam>::difference_type>(cont.size());
- EXPECT_EQ(size, std::distance(cont.begin(), cont.end()));
- EXPECT_EQ(size, std::distance(cont.cbegin(), cont.cend()));
- EXPECT_EQ(size, std::distance(cont.rbegin(), cont.rend()));
- EXPECT_EQ(size, std::distance(cont.crbegin(), cont.crend()));
- {
- auto it = cont.begin();
- auto c_it = cont.cbegin();
- EXPECT_EQ(it, c_it);
- for (int j = 1; it != cont.end(); ++it, ++c_it, ++j) {
- EXPECT_EQ(j, *it);
- EXPECT_EQ(j, *c_it);
- }
- }
- {
- auto rit = cont.rbegin();
- auto c_rit = cont.crbegin();
- EXPECT_EQ(rit, c_rit);
- for (int j = static_cast<int>(size); rit != cont.rend();
- ++rit, ++c_rit, --j) {
- EXPECT_EQ(j, *rit);
- EXPECT_EQ(j, *c_rit);
- }
- }
- }
- // ----------------------------------------------------------------------------
- // Insert operations.
- // pair<iterator, bool> insert(const value_type& val)
- TYPED_TEST_P(FlatTreeTest, InsertLValue) {
- TypedTree<TypeParam> cont;
- int value = 2;
- std::pair<typename TypedTree<TypeParam>::iterator, bool> result =
- cont.insert(value);
- EXPECT_TRUE(result.second);
- EXPECT_EQ(cont.begin(), result.first);
- EXPECT_EQ(1U, cont.size());
- EXPECT_EQ(2, *result.first);
- value = 1;
- result = cont.insert(value);
- EXPECT_TRUE(result.second);
- EXPECT_EQ(cont.begin(), result.first);
- EXPECT_EQ(2U, cont.size());
- EXPECT_EQ(1, *result.first);
- value = 3;
- result = cont.insert(value);
- EXPECT_TRUE(result.second);
- EXPECT_EQ(std::prev(cont.end()), result.first);
- EXPECT_EQ(3U, cont.size());
- EXPECT_EQ(3, *result.first);
- value = 3;
- result = cont.insert(value);
- EXPECT_FALSE(result.second);
- EXPECT_EQ(std::prev(cont.end()), result.first);
- EXPECT_EQ(3U, cont.size());
- EXPECT_EQ(3, *result.first);
- }
- // pair<iterator, bool> insert(value_type&& val)
- TEST(FlatTree, InsertRValue) {
- MoveOnlyTree cont;
- 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(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(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(MoveOnlyInt(3));
- EXPECT_FALSE(result.second);
- EXPECT_EQ(std::prev(cont.end()), result.first);
- EXPECT_EQ(3U, cont.size());
- EXPECT_EQ(3, result.first->data());
- }
- // iterator insert(const_iterator position_hint, const value_type& val)
- TYPED_TEST_P(FlatTreeTest, InsertPositionLValue) {
- TypedTree<TypeParam> cont;
- auto result = cont.insert(cont.cend(), 2);
- EXPECT_EQ(cont.begin(), result);
- EXPECT_EQ(1U, cont.size());
- EXPECT_EQ(2, *result);
- result = cont.insert(cont.cend(), 1);
- EXPECT_EQ(cont.begin(), result);
- EXPECT_EQ(2U, cont.size());
- EXPECT_EQ(1, *result);
- result = cont.insert(cont.cend(), 3);
- EXPECT_EQ(std::prev(cont.end()), result);
- EXPECT_EQ(3U, cont.size());
- EXPECT_EQ(3, *result);
- result = cont.insert(cont.cend(), 3);
- EXPECT_EQ(std::prev(cont.end()), result);
- EXPECT_EQ(3U, cont.size());
- EXPECT_EQ(3, *result);
- }
- // iterator insert(const_iterator position_hint, value_type&& val)
- TEST(FlatTree, InsertPositionRValue) {
- MoveOnlyTree cont;
- auto 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(), MoveOnlyInt(1));
- EXPECT_EQ(cont.begin(), result);
- EXPECT_EQ(2U, cont.size());
- EXPECT_EQ(1, 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());
- 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 {
- const int& operator()(const std::pair<int, int>& p) const {
- return p.first;
- }
- };
- using IntIntMap = flat_tree<int, GetKeyFromIntIntPair, std::less<int>,
- std::vector<IntPair>>;
- {
- IntIntMap cont;
- IntPair int_pairs[] = {{3, 1}, {1, 1}, {4, 1}, {2, 1}};
- cont.insert(std::begin(int_pairs), std::end(int_pairs));
- 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}});
- std::vector<IntPair> int_pairs;
- cont.insert(std::begin(int_pairs), std::end(int_pairs));
- 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}});
- IntPair int_pairs[] = {{1, 1}};
- cont.insert(std::begin(int_pairs), std::end(int_pairs));
- 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}});
- IntPair int_pairs[] = {{5, 1}};
- cont.insert(std::begin(int_pairs), std::end(int_pairs));
- 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}});
- IntPair int_pairs[] = {{3, 2}, {1, 2}, {4, 2}, {2, 2}};
- cont.insert(std::begin(int_pairs), std::end(int_pairs));
- 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}});
- 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));
- 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)));
- }
- }
- // template <class... Args>
- // pair<iterator, bool> emplace(Args&&... args)
- TYPED_TEST_P(FlatTreeTest, Emplace) {
- {
- EmplaceableTree cont;
- std::pair<EmplaceableTree::iterator, bool> result = cont.emplace();
- EXPECT_TRUE(result.second);
- EXPECT_EQ(cont.begin(), result.first);
- EXPECT_EQ(1U, cont.size());
- EXPECT_EQ(Emplaceable(), *cont.begin());
- result = cont.emplace(2, 3.5);
- EXPECT_TRUE(result.second);
- EXPECT_EQ(std::next(cont.begin()), result.first);
- EXPECT_EQ(2U, cont.size());
- EXPECT_EQ(Emplaceable(2, 3.5), *result.first);
- result = cont.emplace(2, 3.5);
- EXPECT_FALSE(result.second);
- EXPECT_EQ(std::next(cont.begin()), result.first);
- EXPECT_EQ(2U, cont.size());
- EXPECT_EQ(Emplaceable(2, 3.5), *result.first);
- }
- {
- TypedTree<TypeParam> cont;
- std::pair<typename TypedTree<TypeParam>::iterator, bool> result =
- cont.emplace(2);
- EXPECT_TRUE(result.second);
- EXPECT_EQ(cont.begin(), result.first);
- EXPECT_EQ(1U, cont.size());
- EXPECT_EQ(2, *result.first);
- }
- }
- // template <class... Args>
- // iterator emplace_hint(const_iterator position_hint, Args&&... args)
- TYPED_TEST_P(FlatTreeTest, EmplacePosition) {
- {
- EmplaceableTree cont;
- auto result = cont.emplace_hint(cont.cend());
- EXPECT_EQ(cont.begin(), result);
- EXPECT_EQ(1U, cont.size());
- EXPECT_EQ(Emplaceable(), *cont.begin());
- result = cont.emplace_hint(cont.cend(), 2, 3.5);
- EXPECT_EQ(std::next(cont.begin()), result);
- EXPECT_EQ(2U, cont.size());
- EXPECT_EQ(Emplaceable(2, 3.5), *result);
- result = cont.emplace_hint(cont.cbegin(), 2, 3.5);
- EXPECT_EQ(std::next(cont.begin()), result);
- EXPECT_EQ(2U, cont.size());
- EXPECT_EQ(Emplaceable(2, 3.5), *result);
- }
- {
- TypedTree<TypeParam> cont;
- auto result = cont.emplace_hint(cont.cend(), 2);
- EXPECT_EQ(cont.begin(), result);
- EXPECT_EQ(1U, cont.size());
- EXPECT_EQ(2, *result);
- }
- }
- // ----------------------------------------------------------------------------
- // Underlying type operations.
- // underlying_type extract() &&
- TYPED_TEST_P(FlatTreeTest, Extract) {
- TypedTree<TypeParam> cont;
- cont.emplace(3);
- cont.emplace(1);
- cont.emplace(2);
- cont.emplace(4);
- TypeParam body = std::move(cont).extract();
- EXPECT_THAT(cont, IsEmpty());
- EXPECT_THAT(body, ElementsAre(1, 2, 3, 4));
- }
- // replace(underlying_type&&)
- TYPED_TEST_P(FlatTreeTest, Replace) {
- TypeParam body = {1, 2, 3, 4};
- TypedTree<TypeParam> cont;
- cont.replace(std::move(body));
- EXPECT_THAT(cont, ElementsAre(1, 2, 3, 4));
- }
- // ----------------------------------------------------------------------------
- // Erase operations.
- // iterator erase(const_iterator position_hint)
- TYPED_TEST_P(FlatTreeTest, ErasePosition) {
- {
- TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8});
- auto 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));
- it = cont.erase(std::next(cont.cbegin(), 0));
- EXPECT_EQ(cont.begin(), it);
- EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8));
- it = cont.erase(std::next(cont.cbegin(), 5));
- EXPECT_EQ(cont.end(), it);
- EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7));
- it = cont.erase(std::next(cont.cbegin(), 1));
- EXPECT_EQ(std::next(cont.begin()), it);
- EXPECT_THAT(cont, ElementsAre(2, 5, 6, 7));
- it = cont.erase(std::next(cont.cbegin(), 2));
- EXPECT_EQ(std::next(cont.begin(), 2), it);
- EXPECT_THAT(cont, ElementsAre(2, 5, 7));
- it = cont.erase(std::next(cont.cbegin(), 2));
- EXPECT_EQ(std::next(cont.begin(), 2), it);
- EXPECT_THAT(cont, ElementsAre(2, 5));
- it = cont.erase(std::next(cont.cbegin(), 0));
- EXPECT_EQ(std::next(cont.begin(), 0), it);
- EXPECT_THAT(cont, ElementsAre(5));
- it = cont.erase(cont.cbegin());
- EXPECT_EQ(cont.begin(), it);
- EXPECT_EQ(cont.end(), it);
- }
- // This is LWG #2059.
- // There is a potential ambiguity between erase with an iterator and erase
- // with a key, if key has a templated constructor.
- {
- using T = TemplateConstructor;
- flat_tree<T, base::identity, std::less<>, std::vector<T>> cont;
- T v(0);
- auto it = cont.find(v);
- if (it != cont.end())
- cont.erase(it);
- }
- }
- // iterator erase(const_iterator first, const_iterator last)
- TYPED_TEST_P(FlatTreeTest, EraseRange) {
- TypedTree<TypeParam> cont({1, 2, 3, 4, 5, 6, 7, 8});
- auto 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));
- it = cont.erase(std::next(cont.cbegin(), 3), std::next(cont.cbegin(), 4));
- EXPECT_EQ(std::next(cont.begin(), 3), it);
- EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8));
- it = cont.erase(std::next(cont.cbegin(), 2), std::next(cont.cbegin(), 5));
- EXPECT_EQ(std::next(cont.begin(), 2), it);
- EXPECT_THAT(cont, ElementsAre(1, 2, 7, 8));
- it = cont.erase(std::next(cont.cbegin(), 0), std::next(cont.cbegin(), 2));
- EXPECT_EQ(std::next(cont.begin(), 0), it);
- EXPECT_THAT(cont, ElementsAre(7, 8));
- it = cont.erase(cont.cbegin(), cont.cend());
- EXPECT_EQ(cont.begin(), it);
- EXPECT_EQ(cont.end(), it);
- }
- // size_type erase(const key_type& key)
- TYPED_TEST_P(FlatTreeTest, EraseKey) {
- TypedTree<TypeParam> 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));
- EXPECT_EQ(1U, cont.erase(4));
- EXPECT_THAT(cont, ElementsAre(1, 2, 3, 5, 6, 7, 8));
- EXPECT_EQ(1U, cont.erase(1));
- EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7, 8));
- EXPECT_EQ(1U, cont.erase(8));
- EXPECT_THAT(cont, ElementsAre(2, 3, 5, 6, 7));
- EXPECT_EQ(1U, cont.erase(3));
- EXPECT_THAT(cont, ElementsAre(2, 5, 6, 7));
- EXPECT_EQ(1U, cont.erase(6));
- EXPECT_THAT(cont, ElementsAre(2, 5, 7));
- EXPECT_EQ(1U, cont.erase(7));
- EXPECT_THAT(cont, ElementsAre(2, 5));
- EXPECT_EQ(1U, cont.erase(2));
- EXPECT_THAT(cont, ElementsAre(5));
- EXPECT_EQ(1U, cont.erase(5));
- EXPECT_THAT(cont, ElementsAre());
- }
- TYPED_TEST_P(FlatTreeTest, EraseEndDeath) {
- {
- TypedTree<TypeParam> tree;
- ASSERT_DEATH_IF_SUPPORTED(tree.erase(tree.cend()), "");
- }
- {
- TypedTree<TypeParam> tree = {1, 2, 3, 4};
- ASSERT_DEATH_IF_SUPPORTED(tree.erase(tree.find(5)), "");
- }
- }
- // ----------------------------------------------------------------------------
- // Comparators.
- // key_compare key_comp() const
- TEST(FlatTree, KeyComp) {
- ReversedTree cont({1, 2, 3, 4, 5});
- EXPECT_TRUE(ranges::is_sorted(cont, cont.key_comp()));
- int new_elements[] = {6, 7, 8, 9, 10};
- std::copy(std::begin(new_elements), std::end(new_elements),
- std::inserter(cont, cont.end()));
- EXPECT_TRUE(ranges::is_sorted(cont, cont.key_comp()));
- }
- // value_compare value_comp() const
- TEST(FlatTree, ValueComp) {
- ReversedTree cont({1, 2, 3, 4, 5});
- EXPECT_TRUE(ranges::is_sorted(cont, cont.value_comp()));
- int new_elements[] = {6, 7, 8, 9, 10};
- std::copy(std::begin(new_elements), std::end(new_elements),
- std::inserter(cont, cont.end()));
- EXPECT_TRUE(ranges::is_sorted(cont, cont.value_comp()));
- }
- // ----------------------------------------------------------------------------
- // Search operations.
- // size_type count(const key_type& key) const
- TYPED_TEST_P(FlatTreeTest, Count) {
- const TypedTree<TypeParam> cont({5, 6, 7, 8, 9, 10, 11, 12});
- EXPECT_EQ(1U, cont.count(5));
- EXPECT_EQ(1U, cont.count(6));
- EXPECT_EQ(1U, cont.count(7));
- EXPECT_EQ(1U, cont.count(8));
- EXPECT_EQ(1U, cont.count(9));
- EXPECT_EQ(1U, cont.count(10));
- EXPECT_EQ(1U, cont.count(11));
- EXPECT_EQ(1U, cont.count(12));
- EXPECT_EQ(0U, cont.count(4));
- }
- // iterator find(const key_type& key)
- // const_iterator find(const key_type& key) const
- TYPED_TEST_P(FlatTreeTest, Find) {
- {
- TypedTree<TypeParam> 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));
- EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7));
- EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8));
- EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9));
- EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10));
- EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11));
- EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12));
- EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4));
- }
- {
- const TypedTree<TypeParam> 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));
- EXPECT_EQ(std::next(cont.begin(), 2), cont.find(7));
- EXPECT_EQ(std::next(cont.begin(), 3), cont.find(8));
- EXPECT_EQ(std::next(cont.begin(), 4), cont.find(9));
- EXPECT_EQ(std::next(cont.begin(), 5), cont.find(10));
- EXPECT_EQ(std::next(cont.begin(), 6), cont.find(11));
- EXPECT_EQ(std::next(cont.begin(), 7), cont.find(12));
- EXPECT_EQ(std::next(cont.begin(), 8), cont.find(4));
- }
- }
- // bool contains(const key_type& key) const
- TYPED_TEST_P(FlatTreeTest, Contains) {
- const TypedTree<TypeParam> cont({5, 6, 7, 8, 9, 10, 11, 12});
- EXPECT_TRUE(cont.contains(5));
- EXPECT_TRUE(cont.contains(6));
- EXPECT_TRUE(cont.contains(7));
- EXPECT_TRUE(cont.contains(8));
- EXPECT_TRUE(cont.contains(9));
- EXPECT_TRUE(cont.contains(10));
- EXPECT_TRUE(cont.contains(11));
- EXPECT_TRUE(cont.contains(12));
- EXPECT_FALSE(cont.contains(4));
- }
- // pair<iterator, iterator> equal_range(const key_type& key)
- // pair<const_iterator, const_iterator> equal_range(const key_type& key) const
- TYPED_TEST_P(FlatTreeTest, EqualRange) {
- {
- TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19});
- std::pair<typename TypedTree<TypeParam>::iterator,
- typename TypedTree<TypeParam>::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);
- EXPECT_EQ(std::next(cont.begin(), 1), result.first);
- EXPECT_EQ(std::next(cont.begin(), 2), result.second);
- result = cont.equal_range(9);
- EXPECT_EQ(std::next(cont.begin(), 2), result.first);
- EXPECT_EQ(std::next(cont.begin(), 3), result.second);
- result = cont.equal_range(11);
- EXPECT_EQ(std::next(cont.begin(), 3), result.first);
- EXPECT_EQ(std::next(cont.begin(), 4), result.second);
- result = cont.equal_range(13);
- EXPECT_EQ(std::next(cont.begin(), 4), result.first);
- EXPECT_EQ(std::next(cont.begin(), 5), result.second);
- result = cont.equal_range(15);
- EXPECT_EQ(std::next(cont.begin(), 5), result.first);
- EXPECT_EQ(std::next(cont.begin(), 6), result.second);
- result = cont.equal_range(17);
- EXPECT_EQ(std::next(cont.begin(), 6), result.first);
- EXPECT_EQ(std::next(cont.begin(), 7), result.second);
- result = cont.equal_range(19);
- EXPECT_EQ(std::next(cont.begin(), 7), result.first);
- EXPECT_EQ(std::next(cont.begin(), 8), result.second);
- result = cont.equal_range(4);
- EXPECT_EQ(std::next(cont.begin(), 0), result.first);
- EXPECT_EQ(std::next(cont.begin(), 0), result.second);
- result = cont.equal_range(6);
- EXPECT_EQ(std::next(cont.begin(), 1), result.first);
- EXPECT_EQ(std::next(cont.begin(), 1), result.second);
- result = cont.equal_range(8);
- EXPECT_EQ(std::next(cont.begin(), 2), result.first);
- EXPECT_EQ(std::next(cont.begin(), 2), result.second);
- result = cont.equal_range(10);
- EXPECT_EQ(std::next(cont.begin(), 3), result.first);
- EXPECT_EQ(std::next(cont.begin(), 3), result.second);
- result = cont.equal_range(12);
- EXPECT_EQ(std::next(cont.begin(), 4), result.first);
- EXPECT_EQ(std::next(cont.begin(), 4), result.second);
- result = cont.equal_range(14);
- EXPECT_EQ(std::next(cont.begin(), 5), result.first);
- EXPECT_EQ(std::next(cont.begin(), 5), result.second);
- result = cont.equal_range(16);
- EXPECT_EQ(std::next(cont.begin(), 6), result.first);
- EXPECT_EQ(std::next(cont.begin(), 6), result.second);
- result = cont.equal_range(18);
- EXPECT_EQ(std::next(cont.begin(), 7), result.first);
- EXPECT_EQ(std::next(cont.begin(), 7), result.second);
- result = cont.equal_range(20);
- EXPECT_EQ(std::next(cont.begin(), 8), result.first);
- EXPECT_EQ(std::next(cont.begin(), 8), result.second);
- }
- {
- const TypedTree<TypeParam> cont({5, 7, 9, 11, 13, 15, 17, 19});
- std::pair<typename TypedTree<TypeParam>::const_iterator,
- typename TypedTree<TypeParam>::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);
- result = cont.equal_range(7);
- EXPECT_EQ(std::next(cont.begin(), 1), result.first);
- EXPECT_EQ(std::next(cont.begin(), 2), result.second);
- result = cont.equal_range(9);
- EXPECT_EQ(std::next(cont.begin(), 2), result.first);
- EXPECT_EQ(std::next(cont.begin(), 3), result.second);
- result = cont.equal_range(11);
- EXPECT_EQ(std::next(cont.begin(), 3), result.first);
- EXPECT_EQ(std::next(cont.begin(), 4), result.second);
- result = cont.equal_range(13);
- EXPECT_EQ(std::next(cont.begin(), 4), result.first);
- EXPECT_EQ(std::next(cont.begin(), 5), result.second);
- result = cont.equal_range(15);
- EXPECT_EQ(std::next(cont.begin(), 5), result.first);
- EXPECT_EQ(std::next(cont.begin(), 6), result.second);
- result = cont.equal_range(17);
- EXPECT_EQ(std::next(cont.begin(), 6), result.first);
- EXPECT_EQ(std::next(cont.begin(), 7), result.second);
- result = cont.equal_range(19);
- EXPECT_EQ(std::next(cont.begin(), 7), result.first);
- EXPECT_EQ(std::next(cont.begin(), 8), result.second);
- result = cont.equal_range(4);
- EXPECT_EQ(std::next(cont.begin(), 0), result.first);
- EXPECT_EQ(std::next(cont.begin(), 0), result.second);
- result = cont.equal_range(6);
- EXPECT_EQ(std::next(cont.begin(), 1), result.first);
- EXPECT_EQ(std::next(cont.begin(), 1), result.second);
- result = cont.equal_range(8);
- EXPECT_EQ(std::next(cont.begin(), 2), result.first);
- EXPECT_EQ(std::next(cont.begin(), 2), result.second);
- result = cont.equal_range(10);
- EXPECT_EQ(std::next(cont.begin(), 3), result.first);
- EXPECT_EQ(std::next(cont.begin(), 3), result.second);
- result = cont.equal_range(12);
- EXPECT_EQ(std::next(cont.begin(), 4), result.first);
- EXPECT_EQ(std::next(cont.begin(), 4), result.second);
- result = cont.equal_range(14);
- EXPECT_EQ(std::next(cont.begin(), 5), result.first);
- EXPECT_EQ(std::next(cont.begin(), 5), result.second);
- result = cont.equal_range(16);
- EXPECT_EQ(std::next(cont.begin(), 6), result.first);
- EXPECT_EQ(std::next(cont.begin(), 6), result.second);
- result = cont.equal_range(18);
- EXPECT_EQ(std::next(cont.begin(), 7), result.first);
- EXPECT_EQ(std::next(cont.begin(), 7), result.second);
- result = cont.equal_range(20);
- EXPECT_EQ(std::next(cont.begin(), 8), result.first);
- EXPECT_EQ(std::next(cont.begin(), 8), result.second);
- }
- }
- // iterator lower_bound(const key_type& key);
- // const_iterator lower_bound(const key_type& key) const;
- TYPED_TEST_P(FlatTreeTest, LowerBound) {
- {
- TypedTree<TypeParam> 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));
- EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9));
- EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11));
- EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13));
- EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15));
- EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17));
- EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19));
- EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4));
- EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6));
- EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8));
- EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10));
- EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12));
- EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14));
- EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16));
- EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18));
- EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20));
- }
- {
- const TypedTree<TypeParam> 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));
- EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(9));
- EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(11));
- EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(13));
- EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(15));
- EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(17));
- EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(19));
- EXPECT_EQ(std::next(cont.begin(), 0), cont.lower_bound(4));
- EXPECT_EQ(std::next(cont.begin(), 1), cont.lower_bound(6));
- EXPECT_EQ(std::next(cont.begin(), 2), cont.lower_bound(8));
- EXPECT_EQ(std::next(cont.begin(), 3), cont.lower_bound(10));
- EXPECT_EQ(std::next(cont.begin(), 4), cont.lower_bound(12));
- EXPECT_EQ(std::next(cont.begin(), 5), cont.lower_bound(14));
- EXPECT_EQ(std::next(cont.begin(), 6), cont.lower_bound(16));
- EXPECT_EQ(std::next(cont.begin(), 7), cont.lower_bound(18));
- EXPECT_EQ(std::next(cont.begin(), 8), cont.lower_bound(20));
- }
- }
- // iterator upper_bound(const key_type& key)
- // const_iterator upper_bound(const key_type& key) const
- TYPED_TEST_P(FlatTreeTest, UpperBound) {
- {
- TypedTree<TypeParam> 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));
- EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9));
- EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11));
- EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13));
- EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15));
- EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17));
- EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19));
- EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4));
- EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6));
- EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8));
- EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10));
- EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12));
- EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14));
- EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16));
- EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18));
- EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20));
- }
- {
- const TypedTree<TypeParam> 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));
- EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(9));
- EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(11));
- EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(13));
- EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(15));
- EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(17));
- EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(19));
- EXPECT_EQ(std::next(cont.begin(), 0), cont.upper_bound(4));
- EXPECT_EQ(std::next(cont.begin(), 1), cont.upper_bound(6));
- EXPECT_EQ(std::next(cont.begin(), 2), cont.upper_bound(8));
- EXPECT_EQ(std::next(cont.begin(), 3), cont.upper_bound(10));
- EXPECT_EQ(std::next(cont.begin(), 4), cont.upper_bound(12));
- EXPECT_EQ(std::next(cont.begin(), 5), cont.upper_bound(14));
- EXPECT_EQ(std::next(cont.begin(), 6), cont.upper_bound(16));
- EXPECT_EQ(std::next(cont.begin(), 7), cont.upper_bound(18));
- EXPECT_EQ(std::next(cont.begin(), 8), cont.upper_bound(20));
- }
- }
- // ----------------------------------------------------------------------------
- // General operations.
- // void swap(flat_tree& other)
- // void swap(flat_tree& lhs, flat_tree& rhs)
- TYPED_TEST_P(FlatTreeTest, Swap) {
- TypedTree<TypeParam> x({1, 2, 3});
- TypedTree<TypeParam> y({4});
- swap(x, y);
- EXPECT_THAT(x, ElementsAre(4));
- EXPECT_THAT(y, ElementsAre(1, 2, 3));
- y.swap(x);
- EXPECT_THAT(x, ElementsAre(1, 2, 3));
- EXPECT_THAT(y, ElementsAre(4));
- }
- // 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(FlatTree, Comparison) {
- // Provided comparator does not participate in comparison.
- ReversedTree biggest({3});
- ReversedTree smallest({1});
- ReversedTree middle({1, 2});
- EXPECT_EQ(biggest, biggest);
- EXPECT_NE(biggest, smallest);
- EXPECT_LT(smallest, middle);
- EXPECT_LE(smallest, middle);
- EXPECT_LE(middle, middle);
- EXPECT_GT(biggest, middle);
- EXPECT_GE(biggest, middle);
- EXPECT_GE(biggest, biggest);
- }
- TYPED_TEST_P(FlatTreeTest, EraseIf) {
- TypedTree<TypeParam> x;
- EXPECT_EQ(0u, base::EraseIf(x, [](int) { return false; }));
- EXPECT_THAT(x, ElementsAre());
- x = {1, 2, 3};
- EXPECT_EQ(1u, base::EraseIf(x, [](int elem) { return !(elem & 1); }));
- EXPECT_THAT(x, ElementsAre(1, 3));
- x = {1, 2, 3, 4};
- EXPECT_EQ(2u, base::EraseIf(x, [](int elem) { return elem & 1; }));
- EXPECT_THAT(x, ElementsAre(2, 4));
- }
- // Test unsorted containers or containers with repeated elements cause a DCHECK
- // if used with the sorted_unique tag.
- TYPED_TEST_P(FlatTreeTest, SortedUniqueRangeConstructorDCHECKs) {
- int unsorted[] = {2, 1};
- EXPECT_DCHECK_DEATH(TypedTree<TypeParam>(sorted_unique, std::begin(unsorted),
- std::end(unsorted)));
- int repeated[] = {1, 2, 2};
- EXPECT_DCHECK_DEATH(TypedTree<TypeParam>(sorted_unique, std::begin(repeated),
- std::end(repeated)));
- }
- TYPED_TEST_P(FlatTreeTest, SortedUniqueVectorCopyConstructorDCHECKs) {
- TypeParam unsorted = {2, 1};
- EXPECT_DCHECK_DEATH(TypedTree<TypeParam>(sorted_unique, unsorted));
- TypeParam repeated = {1, 2, 2};
- EXPECT_DCHECK_DEATH(TypedTree<TypeParam>(sorted_unique, repeated));
- }
- TYPED_TEST_P(FlatTreeTest, SortedUniqueVectorMoveConstructorDCHECKs) {
- TypeParam unsorted = {2, 1};
- EXPECT_DCHECK_DEATH(TypedTree<TypeParam>(sorted_unique, std::move(unsorted)));
- TypeParam repeated = {1, 2, 2};
- EXPECT_DCHECK_DEATH(TypedTree<TypeParam>(sorted_unique, std::move(repeated)));
- }
- TYPED_TEST_P(FlatTreeTest, SortedUniqueInitializerListConstructorDCHECKs) {
- std::initializer_list<int> unsorted = {2, 1};
- EXPECT_DCHECK_DEATH(TypedTree<TypeParam>(sorted_unique, unsorted));
- std::initializer_list<int> repeated = {1, 2, 2};
- EXPECT_DCHECK_DEATH(TypedTree<TypeParam>(sorted_unique, repeated));
- }
- TYPED_TEST_P(FlatTreeTest, ReplaceDCHECKs) {
- TypedTree<TypeParam> tree;
- TypeParam unsorted = {2, 1};
- EXPECT_DCHECK_DEATH(tree.replace(std::move(unsorted)));
- TypeParam repeated = {1, 2, 2};
- EXPECT_DCHECK_DEATH(tree.replace(std::move(repeated)));
- }
- REGISTER_TYPED_TEST_SUITE_P(FlatTreeTest,
- DefaultConstructor,
- CopyConstructor,
- ContainerCopyConstructor,
- InitializerListConstructor,
- SortedUniqueContainerCopyConstructor,
- SortedUniqueInitializerListConstructor,
- CopyAssignable,
- InitializerListAssignable,
- Clear,
- Size,
- Empty,
- Iterators,
- InsertLValue,
- InsertPositionLValue,
- Emplace,
- EmplacePosition,
- Extract,
- Replace,
- ErasePosition,
- EraseRange,
- EraseKey,
- EraseEndDeath,
- Count,
- Find,
- Contains,
- EqualRange,
- LowerBound,
- UpperBound,
- Swap,
- EraseIf,
- SortedUniqueRangeConstructorDCHECKs,
- SortedUniqueVectorCopyConstructorDCHECKs,
- SortedUniqueVectorMoveConstructorDCHECKs,
- SortedUniqueInitializerListConstructorDCHECKs,
- ReplaceDCHECKs);
- using IntSequenceContainers =
- ::testing::Types<std::deque<int>, std::vector<int>>;
- INSTANTIATE_TYPED_TEST_SUITE_P(My, FlatTreeTest, IntSequenceContainers);
- } // namespace internal
- } // namespace base
|