From 8327390ccc27853c5bee794029a9ab2cc54df335 Mon Sep 17 00:00:00 2001 From: Gil Date: Tue, 24 Apr 2018 08:59:38 -0700 Subject: Implement erase in C++ immutable maps (#1158) * Add SortedMap::min * Add SortedMap::erase --- .../firestore/immutable/array_sorted_map_test.cc | 95 -------------- .../firestore/immutable/sorted_map_test.cc | 139 ++++++++++++++++++++- 2 files changed, 138 insertions(+), 96 deletions(-) (limited to 'Firestore/core/test') diff --git a/Firestore/core/test/firebase/firestore/immutable/array_sorted_map_test.cc b/Firestore/core/test/firebase/firestore/immutable/array_sorted_map_test.cc index ea8ae6e..9a23df5 100644 --- a/Firestore/core/test/firebase/firestore/immutable/array_sorted_map_test.cc +++ b/Firestore/core/test/firebase/firestore/immutable/array_sorted_map_test.cc @@ -32,66 +32,6 @@ namespace impl { using IntMap = ArraySortedMap; constexpr IntMap::size_type kFixedSize = IntMap::kFixedSize; -TEST(ArraySortedMap, RemoveKeyValuePair) { - IntMap map{{1, 3}, {2, 4}}; - - IntMap new_map = map.erase(1); - ASSERT_TRUE(Found(new_map, 2, 4)); - ASSERT_TRUE(NotFound(new_map, 1)); - - // Make sure the original one is not mutated - ASSERT_TRUE(Found(map, 1, 3)); - ASSERT_TRUE(Found(map, 2, 4)); -} - -TEST(ArraySortedMap, MoreRemovals) { - IntMap map = IntMap{} - .insert(1, 1) - .insert(50, 50) - .insert(3, 3) - .insert(4, 4) - .insert(7, 7) - .insert(9, 9) - .insert(1, 20) - .insert(18, 18) - .insert(3, 2) - .insert(4, 71) - .insert(7, 42) - .insert(9, 88); - - ASSERT_TRUE(Found(map, 7, 42)); - ASSERT_TRUE(Found(map, 3, 2)); - ASSERT_TRUE(Found(map, 1, 20)); - - IntMap s1 = map.erase(7); - IntMap s2 = map.erase(3); - IntMap s3 = map.erase(1); - - ASSERT_TRUE(NotFound(s1, 7)); - ASSERT_TRUE(Found(s1, 3, 2)); - ASSERT_TRUE(Found(s1, 1, 20)); - - ASSERT_TRUE(Found(s2, 7, 42)); - ASSERT_TRUE(NotFound(s2, 3)); - ASSERT_TRUE(Found(s2, 1, 20)); - - ASSERT_TRUE(Found(s3, 7, 42)); - ASSERT_TRUE(Found(s3, 3, 2)); - ASSERT_TRUE(NotFound(s3, 1)); -} - -TEST(ArraySortedMap, RemovesMiddle) { - IntMap map{{1, 1}, {2, 2}, {3, 3}}; - ASSERT_TRUE(Found(map, 1, 1)); - ASSERT_TRUE(Found(map, 2, 2)); - ASSERT_TRUE(Found(map, 3, 3)); - - IntMap s1 = map.erase(2); - ASSERT_TRUE(Found(s1, 1, 1)); - ASSERT_TRUE(NotFound(s1, 2)); - ASSERT_TRUE(Found(s1, 3, 3)); -} - TEST(ArraySortedMap, ChecksSize) { std::vector to_insert = Sequence(kFixedSize); IntMap map = ToMap(to_insert); @@ -103,41 +43,6 @@ TEST(ArraySortedMap, ChecksSize) { ASSERT_ANY_THROW(map.insert(next, next)); } -TEST(ArraySortedMap, EmptyRemoval) { - IntMap map; - IntMap new_map = map.erase(1); - EXPECT_TRUE(new_map.empty()); - EXPECT_EQ(0u, new_map.size()); - EXPECT_TRUE(NotFound(new_map, 1)); -} - -TEST(ArraySortedMap, InsertionAndRemovalOfMaxItems) { - auto expected_size = kFixedSize; - auto n = static_cast(expected_size); - std::vector to_insert = Shuffled(Sequence(n)); - std::vector to_remove = Shuffled(to_insert); - - // Add them to the map - IntMap map = ToMap(to_insert); - ASSERT_EQ(expected_size, map.size()) - << "Check if all N objects are in the map"; - - // check the order is correct - ASSERT_SEQ_EQ(Pairs(Sorted(to_insert)), map); - - for (int i : to_remove) { - map = map.erase(i); - } - ASSERT_EQ(0u, map.size()) << "Check we removed all of the items"; -} - -TEST(ArraySortedMap, BalanceProblem) { - std::vector to_insert{1, 7, 8, 5, 2, 6, 4, 0, 3}; - - IntMap map = ToMap(to_insert); - ASSERT_SEQ_EQ(Pairs(Sorted(to_insert)), map); -} - } // namespace impl } // namespace immutable } // namespace firestore diff --git a/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc b/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc index 0c5b2b9..25332c2 100644 --- a/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc +++ b/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc @@ -102,12 +102,14 @@ TYPED_TEST(SortedMapTest, Size) { } TYPED_TEST(SortedMapTest, Increasing) { - std::vector to_insert = Sequence(this->large_number()); + int n = this->large_number(); + std::vector to_insert = Sequence(n); TypeParam map = ToMap(to_insert); ASSERT_EQ(this->large_size(), map.size()); for (int i : to_insert) { map = map.erase(i); + ASSERT_EQ(static_cast(n - i - 1), map.size()); } ASSERT_EQ(0u, map.size()); @@ -129,6 +131,107 @@ TYPED_TEST(SortedMapTest, BalanceProblem) { ASSERT_SEQ_EQ(Pairs(Sorted(to_insert)), map); } +TYPED_TEST(SortedMapTest, EmptyRemoval) { + TypeParam map; + TypeParam new_map = map.erase(1); + EXPECT_TRUE(new_map.empty()); + EXPECT_EQ(0u, new_map.size()); + EXPECT_TRUE(NotFound(new_map, 1)); +} + +TYPED_TEST(SortedMapTest, RemoveKeyValuePair) { + TypeParam map = TypeParam{}.insert(1, 3).insert(2, 4); + + TypeParam new_map = map.erase(1); + ASSERT_TRUE(Found(new_map, 2, 4)); + ASSERT_TRUE(NotFound(new_map, 1)); + + // Make sure the original one is not mutated + ASSERT_TRUE(Found(map, 1, 3)); + ASSERT_TRUE(Found(map, 2, 4)); +} + +TYPED_TEST(SortedMapTest, MoreRemovals) { + TypeParam map = TypeParam() + .insert(1, 1) + .insert(50, 50) + .insert(3, 3) + .insert(4, 4) + .insert(7, 7) + .insert(9, 9) + .insert(1, 20) + .insert(18, 18) + .insert(3, 2) + .insert(4, 71) + .insert(7, 42) + .insert(9, 88); + + ASSERT_TRUE(Found(map, 7, 42)); + ASSERT_TRUE(Found(map, 3, 2)); + ASSERT_TRUE(Found(map, 1, 20)); + + TypeParam s1 = map.erase(7); + TypeParam s2 = map.erase(3); + TypeParam s3 = map.erase(1); + + ASSERT_TRUE(NotFound(s1, 7)); + ASSERT_TRUE(Found(s1, 3, 2)); + ASSERT_TRUE(Found(s1, 1, 20)); + + ASSERT_TRUE(Found(s2, 7, 42)); + ASSERT_TRUE(NotFound(s2, 3)); + ASSERT_TRUE(Found(s2, 1, 20)); + + ASSERT_TRUE(Found(s3, 7, 42)); + ASSERT_TRUE(Found(s3, 3, 2)); + ASSERT_TRUE(NotFound(s3, 1)); +} + +TYPED_TEST(SortedMapTest, RemovesMiddle) { + TypeParam map = TypeParam{}.insert(1, 1).insert(2, 2).insert(3, 3); + ASSERT_TRUE(Found(map, 1, 1)); + ASSERT_TRUE(Found(map, 2, 2)); + ASSERT_TRUE(Found(map, 3, 3)); + + TypeParam s1 = map.erase(2); + ASSERT_TRUE(Found(s1, 1, 1)); + ASSERT_TRUE(NotFound(s1, 2)); + ASSERT_TRUE(Found(s1, 3, 3)); +} + +TYPED_TEST(SortedMapTest, InsertionAndRemovalOfMaxItems) { + auto expected_size = this->large_size(); + int n = this->large_number(); + std::vector to_insert = Shuffled(Sequence(n)); + std::vector to_remove = Shuffled(to_insert); + + // Add them to the map + TypeParam map = ToMap(to_insert); + ASSERT_EQ(expected_size, map.size()) + << "Check if all N objects are in the map"; + + // check the order is correct + ASSERT_SEQ_EQ(Pairs(Sorted(to_insert)), map); + + for (int i : to_remove) { + map = map.erase(i); + } + ASSERT_EQ(0u, map.size()) << "Check we removed all of the items"; +} + +TYPED_TEST(SortedMapTest, EraseDoesNotInvalidateIterators) { + std::vector keys = Sequence(1, 4); + TypeParam original = ToMap(keys); + + auto begin = original.begin(); + auto end = original.end(); + ASSERT_EQ(Collect(original), (std::vector>{begin, end})); + + TypeParam erased = original.erase(2); + ASSERT_EQ(erased.size(), original.size() - 1); + ASSERT_EQ(Collect(original), (std::vector>{begin, end})); +} + TYPED_TEST(SortedMapTest, FindEmpty) { TypeParam map; EXPECT_TRUE(NotFound(map, 10)); @@ -159,6 +262,40 @@ TYPED_TEST(SortedMapTest, FindIndex) { ASSERT_EQ(5u, map.find_index(50)); } +TYPED_TEST(SortedMapTest, MinMax) { + TypeParam empty; + auto min = empty.min(); + auto max = empty.max(); + ASSERT_EQ(empty.end(), min); + ASSERT_EQ(empty.end(), max); + ASSERT_EQ(min, max); + + TypeParam one = empty.insert(1, 1); + min = one.min(); + max = one.max(); + ASSERT_NE(one.end(), min); + ASSERT_NE(one.end(), max); + ASSERT_EQ(1, min->first); + ASSERT_EQ(1, max->first); + + // Just a regular iterator + ++min; + ASSERT_EQ(one.end(), min); + + TypeParam two = one.insert(2, 2); + min = two.min(); + max = two.max(); + ASSERT_EQ(1, min->first); + ASSERT_EQ(2, max->first); + + std::vector to_insert = Sequence(this->large_number()); + TypeParam lots = ToMap(to_insert); + min = lots.min(); + max = lots.max(); + ASSERT_EQ(to_insert.front(), min->first); + ASSERT_EQ(to_insert.back(), max->first); +} + TYPED_TEST(SortedMapTest, IteratorsAreDefaultConstructible) { // If this compiles the test has succeeded typename TypeParam::const_iterator iter; -- cgit v1.2.3