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/sorted_map_test.cc | 139 ++++++++++++++++++++- 1 file changed, 138 insertions(+), 1 deletion(-) (limited to 'Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc') 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