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

3 files changed, 58 insertions, 44 deletions

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<int, int>;
 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<int> to_insert = Sequence(kFixedSize);
   IntMap map = ToMap<IntMap>(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<int> to_insert{1, 7, 8, 5, 2, 6, 4, 0, 3};
+
+  TypeParam map = ToMap<TypeParam>(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<int> to_insert{1, 3, 4, 7, 9, 50};
+  TypeParam map = ToMap<TypeParam>(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 <typename Container, typename K>
 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 <typename Container, typename K, typename V>
 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();