From 0c03c28a3b7609d218a9acdff099fc0bda0f4ae6 Mon Sep 17 00:00:00 2001 From: Gil Date: Fri, 20 Apr 2018 12:11:19 -0700 Subject: Implement find-related methods on C++ immutable maps (#1145) * Standardize method ordering across sorted maps * Add SortedMap::find * Add SortedMap::find_index * Add SortedMap::contains --- .../firestore/immutable/array_sorted_map_test.cc | 40 ------------------ .../firestore/immutable/sorted_map_test.cc | 49 ++++++++++++++++++++-- .../test/firebase/firestore/immutable/testing.h | 13 +++++- 3 files changed, 58 insertions(+), 44 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 9f18f2d..ea8ae6e 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,14 +32,6 @@ namespace impl { using IntMap = ArraySortedMap; constexpr IntMap::size_type kFixedSize = IntMap::kFixedSize; -TEST(ArraySortedMap, SearchForSpecificKey) { - IntMap map{{1, 3}, {2, 4}}; - - ASSERT_TRUE(Found(map, 1, 3)); - ASSERT_TRUE(Found(map, 2, 4)); - ASSERT_TRUE(NotFound(map, 3)); -} - TEST(ArraySortedMap, RemoveKeyValuePair) { IntMap map{{1, 3}, {2, 4}}; @@ -100,13 +92,6 @@ TEST(ArraySortedMap, RemovesMiddle) { ASSERT_TRUE(Found(s1, 3, 3)); } -TEST(ArraySortedMap, Override) { - IntMap map = IntMap{}.insert(10, 10).insert(10, 8); - - ASSERT_TRUE(Found(map, 10, 8)); - ASSERT_FALSE(Found(map, 10, 10)); -} - TEST(ArraySortedMap, ChecksSize) { std::vector to_insert = Sequence(kFixedSize); IntMap map = ToMap(to_insert); @@ -118,11 +103,6 @@ TEST(ArraySortedMap, ChecksSize) { ASSERT_ANY_THROW(map.insert(next, next)); } -TEST(ArraySortedMap, EmptyGet) { - IntMap map; - EXPECT_TRUE(NotFound(map, 10)); -} - TEST(ArraySortedMap, EmptyRemoval) { IntMap map; IntMap new_map = map.erase(1); @@ -158,26 +138,6 @@ TEST(ArraySortedMap, BalanceProblem) { ASSERT_SEQ_EQ(Pairs(Sorted(to_insert)), map); } -// TODO(wilhuff): Iterators - -// TODO(wilhuff): IndexOf - -TEST(ArraySortedMap, AvoidsCopying) { - IntMap map = IntMap{}.insert(10, 20); - auto found = map.find(10); - ASSERT_NE(found, map.end()); - EXPECT_EQ(20, found->second); - - // Verify that inserting something with equal keys and values just returns - // the same underlying array. - IntMap duped = map.insert(10, 20); - auto duped_found = duped.find(10); - - // If everything worked correctly, the backing array should not have been - // copied and the pointer to the entry with 10 as key should be the same. - EXPECT_EQ(found, duped_found); -} - } // 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 f6d00eb..0c5b2b9 100644 --- a/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc +++ b/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc @@ -77,9 +77,8 @@ TYPED_TEST(SortedMapTest, Empty) { EXPECT_TRUE(map.empty()); EXPECT_EQ(0u, map.size()); - // TODO(wilhuff): re-add find - // EXPECT_TRUE(NotFound(map, 1)); - // EXPECT_TRUE(NotFound(map, 10)); + EXPECT_TRUE(NotFound(map, 1)); + EXPECT_TRUE(NotFound(map, 10)); } TYPED_TEST(SortedMapTest, Size) { @@ -116,6 +115,50 @@ TYPED_TEST(SortedMapTest, Increasing) { ASSERT_EQ(Pairs(empty), Collect(map)); } +TYPED_TEST(SortedMapTest, Overwrite) { + TypeParam map = TypeParam().insert(10, 10).insert(10, 8); + + ASSERT_TRUE(Found(map, 10, 8)); + ASSERT_FALSE(Found(map, 10, 10)); +} + +TYPED_TEST(SortedMapTest, BalanceProblem) { + std::vector to_insert{1, 7, 8, 5, 2, 6, 4, 0, 3}; + + TypeParam map = ToMap(to_insert); + ASSERT_SEQ_EQ(Pairs(Sorted(to_insert)), map); +} + +TYPED_TEST(SortedMapTest, FindEmpty) { + TypeParam map; + EXPECT_TRUE(NotFound(map, 10)); +} + +TYPED_TEST(SortedMapTest, FindSpecificKey) { + TypeParam map = TypeParam{}.insert(1, 3).insert(2, 4); + + ASSERT_TRUE(Found(map, 1, 3)); + ASSERT_TRUE(Found(map, 2, 4)); + ASSERT_TRUE(NotFound(map, 3)); +} + +TYPED_TEST(SortedMapTest, FindIndex) { + std::vector to_insert{1, 3, 4, 7, 9, 50}; + TypeParam map = ToMap(to_insert); + + ASSERT_EQ(TypeParam::npos, map.find_index(0)); + ASSERT_EQ(0u, map.find_index(1)); + ASSERT_EQ(TypeParam::npos, map.find_index(2)); + ASSERT_EQ(1u, map.find_index(3)); + ASSERT_EQ(2u, map.find_index(4)); + ASSERT_EQ(TypeParam::npos, map.find_index(5)); + ASSERT_EQ(TypeParam::npos, map.find_index(6)); + ASSERT_EQ(3u, map.find_index(7)); + ASSERT_EQ(TypeParam::npos, map.find_index(8)); + ASSERT_EQ(4u, map.find_index(9)); + ASSERT_EQ(5u, map.find_index(50)); +} + TYPED_TEST(SortedMapTest, IteratorsAreDefaultConstructible) { // If this compiles the test has succeeded typename TypeParam::const_iterator iter; diff --git a/Firestore/core/test/firebase/firestore/immutable/testing.h b/Firestore/core/test/firebase/firestore/immutable/testing.h index 0b25b66..9e839c6 100644 --- a/Firestore/core/test/firebase/firestore/immutable/testing.h +++ b/Firestore/core/test/firebase/firestore/immutable/testing.h @@ -30,6 +30,11 @@ namespace immutable { template testing::AssertionResult NotFound(const Container& map, const K& key) { + if (map.contains(key)) { + return testing::AssertionFailure() + << "Should not have found " << key << " using contains()"; + } + auto found = map.find(key); if (found == map.end()) { return testing::AssertionSuccess(); @@ -44,9 +49,15 @@ template testing::AssertionResult Found(const Container& map, const K& key, const V& expected) { + if (!map.contains(key)) { + return testing::AssertionFailure() + << "Did not find key " << key << " using contains()"; + } + auto found = map.find(key); if (found == map.end()) { - return testing::AssertionFailure() << "Did not find key " << key; + return testing::AssertionFailure() + << "Did not find key " << key << " using find()"; } if (found->second == expected) { return testing::AssertionSuccess(); -- cgit v1.2.3