Add key-only projections to immutable C++ maps (#1166)

* Add a simple range adapter.
* Add SortedMap::keys
* Add SortedMap::keys_from
* Add SortedMap::keys_in

9 files changed, 380 insertions, 21 deletions

diff --git a/Firestore/core/src/firebase/firestore/immutable/CMakeLists.txt b/Firestore/core/src/firebase/firestore/immutable/CMakeLists.txt
index accf5c5..90ce204 100644
--- a/Firestore/core/src/firebase/firestore/immutable/CMakeLists.txt
+++ b/Firestore/core/src/firebase/firestore/immutable/CMakeLists.txt
@@ -16,6 +16,7 @@ cc_library(
   firebase_firestore_immutable
   SOURCES
     array_sorted_map.h
+    keys_view.h
     llrb_node.h
     llrb_node_iterator.h
     map_entry.h
diff --git a/Firestore/core/src/firebase/firestore/immutable/array_sorted_map.h b/Firestore/core/src/firebase/firestore/immutable/array_sorted_map.h
index 487a25a..db53969 100644
--- a/Firestore/core/src/firebase/firestore/immutable/array_sorted_map.h
+++ b/Firestore/core/src/firebase/firestore/immutable/array_sorted_map.h
@@ -24,10 +24,12 @@
 #include <memory>
 #include <utility>
 
+#include "Firestore/core/src/firebase/firestore/immutable/keys_view.h"
 #include "Firestore/core/src/firebase/firestore/immutable/map_entry.h"
 #include "Firestore/core/src/firebase/firestore/immutable/sorted_map_base.h"
 #include "Firestore/core/src/firebase/firestore/util/comparison.h"
 #include "Firestore/core/src/firebase/firestore/util/firebase_assert.h"
+#include "Firestore/core/src/firebase/firestore/util/range.h"
 
 namespace firebase {
 namespace firestore {
@@ -133,6 +135,7 @@ class ArraySortedMap : public SortedMapBase {
    */
   using array_type = FixedArray<value_type>;
   using const_iterator = typename array_type::const_iterator;
+  using const_key_iterator = util::iterator_first<const_iterator>;
 
   using array_pointer = std::shared_ptr<const array_type>;
 
@@ -162,8 +165,8 @@ class ArraySortedMap : public SortedMapBase {
     return array_->size();
   }
 
-  const key_comparator_type& comparator() const {
-    return key_comparator_;
+  const C& comparator() const {
+    return key_comparator_.comparator();
   }
 
   /**
@@ -176,12 +179,12 @@ class ArraySortedMap : public SortedMapBase {
    */
   ArraySortedMap insert(const K& key, const V& value) const {
     const_iterator current_end = end();
-    const_iterator pos = LowerBound(key);
+    const_iterator pos = lower_bound(key);
     bool replacing_entry = false;
 
     if (pos != current_end) {
-      // LowerBound found an entry where pos->first >= pair.first. Reversing the
-      // argument order here tests pair.first < pos->first.
+      // lower_bound found an entry where pos->first >= pair.first. Reversing
+      // the argument order here tests pair.first < pos->first.
       replacing_entry = !key_comparator_(key, *pos);
       if (replacing_entry && value == pos->second) {
         return *this;
@@ -239,9 +242,9 @@ class ArraySortedMap : public SortedMapBase {
    */
   const_iterator find(const K& key) const {
     const_iterator not_found = end();
-    const_iterator lower_bound = LowerBound(key);
-    if (lower_bound != not_found && !key_comparator_(key, *lower_bound)) {
-      return lower_bound;
+    const_iterator bound = lower_bound(key);
+    if (bound != not_found && !key_comparator_(key, *bound)) {
+      return bound;
     } else {
       return not_found;
     }
@@ -258,6 +261,19 @@ class ArraySortedMap : public SortedMapBase {
     return found == end() ? npos : static_cast<size_type>(found - begin());
   }
 
+  /**
+   * Finds the first entry in the map containing a key greater than or equal
+   * to the given key.
+   *
+   * @param key The key to look up.
+   * @return An iterator pointing to the entry containing the key or the next
+   *     largest key. Can return end() if all keys in the map are less than the
+   *     requested key.
+   */
+  const_iterator lower_bound(const K& key) const {
+    return std::lower_bound(begin(), end(), key, key_comparator_);
+  }
+
   const_iterator min() const {
     return begin();
   }
@@ -285,6 +301,32 @@ class ArraySortedMap : public SortedMapBase {
     return array_->end();
   }
 
+  /**
+   * Returns a view of this SortedMap containing just the keys that have been
+   * inserted.
+   */
+  const util::range<const_key_iterator> keys() const {
+    return KeysView(*this);
+  }
+
+  /**
+   * Returns a view of this SortedMap containing just the keys that have been
+   * inserted that are greater than or equal to the given key.
+   */
+  const util::range<const_key_iterator> keys_from(const K& key) const {
+    return KeysViewFrom(*this, key);
+  }
+
+  /**
+   * Returns a view of this SortedMap containing just the keys that have been
+   * inserted that are greater than or equal to the given start_key and less
+   * than the given end_key.
+   */
+  const util::range<const_key_iterator> keys_in(const K& start_key,
+                                                const K& end_key) const {
+    return impl::KeysViewIn(*this, start_key, end_key, comparator());
+  }
+
  private:
   static array_pointer EmptyArray() {
     static const array_pointer kEmptyArray =
@@ -301,10 +343,6 @@ class ArraySortedMap : public SortedMapBase {
     return ArraySortedMap{array, key_comparator_};
   }
 
-  const_iterator LowerBound(const K& key) const {
-    return std::lower_bound(begin(), end(), key, key_comparator_);
-  }
-
   array_pointer array_;
   key_comparator_type key_comparator_;
 };
diff --git a/Firestore/core/src/firebase/firestore/immutable/keys_view.h b/Firestore/core/src/firebase/firestore/immutable/keys_view.h
new file mode 100644
index 0000000..6cf04b6
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/immutable/keys_view.h
@@ -0,0 +1,86 @@
+/*
+ * Copyright 2018 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_IMMUTABLE_KEYS_VIEW_H_
+#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_IMMUTABLE_KEYS_VIEW_H_
+
+#include <utility>
+
+#include "Firestore/core/src/firebase/firestore/util/iterator_adaptors.h"
+#include "Firestore/core/src/firebase/firestore/util/range.h"
+
+namespace firebase {
+namespace firestore {
+namespace immutable {
+namespace impl {
+
+template <typename Iterator>
+using KeysRange = util::range<util::iterator_first<Iterator>>;
+
+template <typename Iterator>
+KeysRange<Iterator> MakeKeysRange(Iterator begin, Iterator end) {
+  auto keys_begin = util::make_iterator_first(begin);
+  auto keys_end = util::make_iterator_first(end);
+  return util::make_range(keys_begin, keys_end);
+}
+
+/**
+ * Returns a view of the keys of the given key-value range.
+ */
+template <typename Range>
+auto KeysView(const Range& range) -> KeysRange<decltype(std::begin(range))> {
+  return MakeKeysRange(std::begin(range), std::end(range));
+}
+
+template <typename Range, typename K>
+auto KeysViewFrom(const Range& range, const K& key)
+    -> KeysRange<decltype(range.lower_bound(key))> {
+  auto keys_begin = util::make_iterator_first(range.lower_bound(key));
+  auto keys_end = util::make_iterator_first(std::end(range));
+  return util::make_range(keys_begin, keys_end);
+}
+
+/**
+ * Returns a view of keys of the given key-value range that are greater than or
+ * equal to the given start_key and less than the given end_key.
+ *
+ * If `end_key` is less than or equal to `start_key`, creates empty range.
+ */
+template <typename Range, typename K, typename C>
+auto KeysViewIn(const Range& range,
+                const K& start_key,
+                const K& end_key,
+                const C& comparator)
+    -> KeysRange<decltype(range.lower_bound(start_key))> {
+  // Forward iterators can't ever reach the end if the end is behind the start:
+  // they just keep incrementing until address space runs out. Adjust the range
+  // accordingly.
+  bool empty_range = !comparator(start_key, end_key);
+  if (empty_range) {
+    return MakeKeysRange(std::end(range), std::end(range));
+  }
+
+  auto range_begin = range.lower_bound(start_key);
+  auto range_end = range.lower_bound(end_key);
+  return MakeKeysRange(std::move(range_begin), std::move(range_end));
+}
+
+}  // namespace impl
+}  // namespace immutable
+}  // namespace firestore
+}  // namespace firebase
+
+#endif  // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_IMMUTABLE_KEYS_VIEW_H_
diff --git a/Firestore/core/src/firebase/firestore/immutable/sorted_map.h b/Firestore/core/src/firebase/firestore/immutable/sorted_map.h
index 6f4d91b..647bab0 100644
--- a/Firestore/core/src/firebase/firestore/immutable/sorted_map.h
+++ b/Firestore/core/src/firebase/firestore/immutable/sorted_map.h
@@ -20,6 +20,7 @@
 #include <utility>
 
 #include "Firestore/core/src/firebase/firestore/immutable/array_sorted_map.h"
+#include "Firestore/core/src/firebase/firestore/immutable/keys_view.h"
 #include "Firestore/core/src/firebase/firestore/immutable/sorted_map_base.h"
 #include "Firestore/core/src/firebase/firestore/immutable/sorted_map_iterator.h"
 #include "Firestore/core/src/firebase/firestore/immutable/tree_sorted_map.h"
@@ -46,6 +47,8 @@ class SortedMap : public impl::SortedMapBase {
       typename impl::FixedArray<value_type>::const_iterator,
       typename impl::LlrbNode<K, V>::const_iterator>;
 
+  using const_key_iterator = util::iterator_first<const_iterator>;
+
   /**
    * Creates an empty SortedMap.
    */
@@ -173,8 +176,7 @@ class SortedMap : public impl::SortedMapBase {
           // exactly where this cut-off happens and just unconditionally
           // converting if the next insertion could overflow keeps things
           // simpler.
-          const C& comparator = array_.comparator().comparator();
-          tree_type tree = tree_type::Create(array_, comparator);
+          tree_type tree = tree_type::Create(array_, comparator());
           return SortedMap{tree.insert(key, value)};
         } else {
           return SortedMap{array_.insert(key, value)};
@@ -249,6 +251,25 @@ class SortedMap : public impl::SortedMapBase {
     FIREBASE_UNREACHABLE();
   }
 
+  /**
+   * Finds the first entry in the map containing a key greater than or equal
+   * to the given key.
+   *
+   * @param key The key to look up.
+   * @return An iterator pointing to the entry containing the key or the next
+   *     largest key. Can return end() if all keys in the map are less than the
+   *     requested key.
+   */
+  const_iterator lower_bound(const K& key) const {
+    switch (tag_) {
+      case Tag::Array:
+        return const_iterator(array_.lower_bound(key));
+      case Tag::Tree:
+        return const_iterator{tree_.lower_bound(key)};
+    }
+    FIREBASE_UNREACHABLE();
+  }
+
   const_iterator min() const {
     switch (tag_) {
       case Tag::Array:
@@ -296,6 +317,32 @@ class SortedMap : public impl::SortedMapBase {
     FIREBASE_UNREACHABLE();
   }
 
+  /**
+   * Returns a view of this SortedMap containing just the keys that have been
+   * inserted.
+   */
+  const util::range<const_key_iterator> keys() const {
+    return impl::KeysView(*this);
+  }
+
+  /**
+   * Returns a view of this SortedMap containing just the keys that have been
+   * inserted that are greater than or equal to the given key.
+   */
+  const util::range<const_key_iterator> keys_from(const K& key) const {
+    return impl::KeysViewFrom(*this, key);
+  }
+
+  /**
+   * Returns a view of this SortedMap containing just the keys that have been
+   * inserted that are greater than or equal to the given start_key and less
+   * than the given end_key.
+   */
+  const util::range<const_key_iterator> keys_in(const K& start_key,
+                                                const K& end_key) const {
+    return impl::KeysViewIn(*this, start_key, end_key, comparator());
+  }
+
  private:
   explicit SortedMap(array_type&& array)
       : tag_{Tag::Array}, array_{std::move(array)} {
@@ -305,6 +352,16 @@ class SortedMap : public impl::SortedMapBase {
       : tag_{Tag::Tree}, tree_{std::move(tree)} {
   }
 
+  const C& comparator() const {
+    switch (tag_) {
+      case Tag::Array:
+        return array_.comparator();
+      case Tag::Tree:
+        return tree_.comparator();
+    }
+    FIREBASE_UNREACHABLE();
+  }
+
   enum class Tag {
     Array,
     Tree,
diff --git a/Firestore/core/src/firebase/firestore/immutable/tree_sorted_map.h b/Firestore/core/src/firebase/firestore/immutable/tree_sorted_map.h
index 609b9da..9fd51c3 100644
--- a/Firestore/core/src/firebase/firestore/immutable/tree_sorted_map.h
+++ b/Firestore/core/src/firebase/firestore/immutable/tree_sorted_map.h
@@ -23,12 +23,12 @@
 #include <memory>
 #include <utility>
 
+#include "Firestore/core/src/firebase/firestore/immutable/keys_view.h"
 #include "Firestore/core/src/firebase/firestore/immutable/llrb_node.h"
 #include "Firestore/core/src/firebase/firestore/immutable/map_entry.h"
 #include "Firestore/core/src/firebase/firestore/immutable/sorted_map_base.h"
 #include "Firestore/core/src/firebase/firestore/util/comparator_holder.h"
 #include "Firestore/core/src/firebase/firestore/util/comparison.h"
-#include "Firestore/core/src/firebase/firestore/util/iterator_adaptors.h"
 
 namespace firebase {
 namespace firestore {
@@ -40,7 +40,7 @@ namespace impl {
  * methods to efficiently create new maps that are mutations of it.
  */
 template <typename K, typename V, typename C = util::Comparator<K>>
-class TreeSortedMap : public SortedMapBase, private util::ComparatorHolder<C> {
+class TreeSortedMap : public SortedMapBase, public util::ComparatorHolder<C> {
  public:
   /**
    * The type of the entries stored in the map.
@@ -52,6 +52,7 @@ class TreeSortedMap : public SortedMapBase, private util::ComparatorHolder<C> {
    */
   using node_type = LlrbNode<K, V>;
   using const_iterator = typename node_type::const_iterator;
+  using const_key_iterator = util::iterator_first<const_iterator>;
 
   /**
    * Creates an empty TreeSortedMap.
@@ -136,7 +137,7 @@ class TreeSortedMap : public SortedMapBase, private util::ComparatorHolder<C> {
    *     not found.
    */
   const_iterator find(const K& key) const {
-    const_iterator found = LowerBound(key);
+    const_iterator found = lower_bound(key);
     if (!found.is_end() && !this->comparator()(key, found->first)) {
       return found;
     } else {
@@ -171,6 +172,19 @@ class TreeSortedMap : public SortedMapBase, private util::ComparatorHolder<C> {
     return npos;
   }
 
+  /**
+   * Finds the first entry in the map containing a key greater than or equal
+   * to the given key.
+   *
+   * @param key The key to look up.
+   * @return An iterator pointing to the entry containing the key or the next
+   *     largest key. Can return end() if all keys in the map are less than the
+   *     requested key.
+   */
+  const_iterator lower_bound(const K& key) const {
+    return const_iterator::LowerBound(&root_, key, this->comparator());
+  }
+
   const_iterator min() const {
     return begin();
   }
@@ -203,15 +217,37 @@ class TreeSortedMap : public SortedMapBase, private util::ComparatorHolder<C> {
     return const_iterator::End();
   }
 
+  /**
+   * Returns a view of this SortedMap containing just the keys that have been
+   * inserted.
+   */
+  const util::range<const_key_iterator> keys() const {
+    return KeysView(*this);
+  }
+
+  /**
+   * Returns a view of this SortedMap containing just the keys that have been
+   * inserted that are greater than or equal to the given key.
+   */
+  const util::range<const_key_iterator> keys_from(const K& key) const {
+    return KeysViewFrom(*this, key);
+  }
+
+  /**
+   * Returns a view of this SortedMap containing just the keys that have been
+   * inserted that are greater than or equal to the given start_key and less
+   * than the given end_key.
+   */
+  const util::range<const_key_iterator> keys_in(const K& start_key,
+                                                const K& end_key) const {
+    return impl::KeysViewIn(*this, start_key, end_key, this->comparator());
+  }
+
  private:
   TreeSortedMap(node_type&& root, const C& comparator) noexcept
       : util::ComparatorHolder<C>{comparator}, root_{std::move(root)} {
   }
 
-  const_iterator LowerBound(const K& key) const noexcept {
-    return const_iterator::LowerBound(&root_, key, this->comparator());
-  }
-
   TreeSortedMap Wrap(node_type&& root) noexcept {
     return TreeSortedMap{std::move(root), this->comparator()};
   }
diff --git a/Firestore/core/src/firebase/firestore/util/CMakeLists.txt b/Firestore/core/src/firebase/firestore/util/CMakeLists.txt
index 701d288..3afead1 100644
--- a/Firestore/core/src/firebase/firestore/util/CMakeLists.txt
+++ b/Firestore/core/src/firebase/firestore/util/CMakeLists.txt
@@ -131,6 +131,7 @@ cc_library(
     iterator_adaptors.h
     ordered_code.cc
     ordered_code.h
+    range.h
     secure_random.h
     status.cc
     status.h
diff --git a/Firestore/core/src/firebase/firestore/util/comparator_holder.h b/Firestore/core/src/firebase/firestore/util/comparator_holder.h
index c7f6144..3147117 100644
--- a/Firestore/core/src/firebase/firestore/util/comparator_holder.h
+++ b/Firestore/core/src/firebase/firestore/util/comparator_holder.h
@@ -35,6 +35,7 @@ class ComparatorHolder {
       : comparator_(comparator) {
   }
 
+ public:
   const C& comparator() const noexcept {
     return comparator_;
   }
@@ -50,6 +51,7 @@ class ComparatorHolder<C, true> : private C {
   explicit ComparatorHolder(const C& /* comparator */) noexcept {
   }
 
+ public:
   const C& comparator() const noexcept {
     return *this;
   }
diff --git a/Firestore/core/src/firebase/firestore/util/range.h b/Firestore/core/src/firebase/firestore/util/range.h
new file mode 100644
index 0000000..9e96c67
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/util/range.h
@@ -0,0 +1,78 @@
+/*
+ * Copyright 2018 Google
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_RANGE_H_
+#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_RANGE_H_
+
+#include <iterator>
+#include <utility>
+
+namespace firebase {
+namespace firestore {
+namespace util {
+
+/**
+ * Adapts a pair of iterators into a range suitable for use with range-based
+ * for loops.
+ */
+template <typename Iterator>
+class range {
+ public:
+  using value_type = typename std::iterator_traits<Iterator>::value_type;
+  using iterator = Iterator;
+  using const_iterator = Iterator;
+
+  /**
+   * Default range which constructs default begin and end pointers. For most
+   * implementations where the end pointer is a null pointer or some other
+   * default value, this ends up constructing the empty range.
+   */
+  range() : begin_{}, end_{} {
+  }
+
+  /**
+   * Creates a half-open range starting from begin up to, but not including end.
+   */
+  range(iterator&& begin, iterator&& end)
+      : begin_{std::move(begin)}, end_{std::move(end)} {
+  }
+
+  iterator begin() const {
+    return begin_;
+  }
+
+  iterator end() const {
+    return end_;
+  }
+
+ private:
+  Iterator begin_;
+  Iterator end_;
+};
+
+/**
+ * Creates ranges with type deduction.
+ */
+template <typename Iterator>
+range<Iterator> make_range(Iterator begin, Iterator end) {
+  return range<Iterator>{std::move(begin), std::move(end)};
+}
+
+}  // namespace util
+}  // namespace firestore
+}  // namespace firebase
+
+#endif  // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_UTIL_RANGE_H_
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 25332c2..bcacb50 100644
--- a/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc
+++ b/Firestore/core/test/firebase/firestore/immutable/sorted_map_test.cc
@@ -403,6 +403,66 @@ TYPED_TEST(SortedMapTest, IteratorInvalidation) {
   ASSERT_EQ(size, result.size());
 }
 
+TYPED_TEST(SortedMapTest, KeyIterator) {
+  std::vector<int> all = Sequence(this->large_number());
+  TypeParam map = ToMap<TypeParam>(Shuffled(all));
+
+  auto begin = map.keys().begin();
+  ASSERT_EQ(0, *begin);
+
+  auto end = map.keys().end();
+  ASSERT_EQ(all.size(), static_cast<size_t>(std::distance(begin, end)));
+
+  ASSERT_SEQ_EQ(all, map.keys());
+}
+
+TYPED_TEST(SortedMapTest, KeysFrom) {
+  std::vector<int> all = Sequence(2, 42, 2);
+  TypeParam map = ToMap<TypeParam>(Shuffled(all));
+  ASSERT_EQ(20u, map.size());
+
+  // Test from before keys.
+  ASSERT_SEQ_EQ(all, map.keys_from(0));
+
+  // Test from after keys.
+  ASSERT_SEQ_EQ(Empty(), map.keys_from(100));
+
+  // Test from a key in the map: should start at that key.
+  ASSERT_SEQ_EQ(Sequence(10, 42, 2), map.keys_from(10));
+
+  // Test from in between keys: should start just after that key.
+  ASSERT_SEQ_EQ(Sequence(12, 42, 2), map.keys_from(11));
+}
+
+TYPED_TEST(SortedMapTest, KeysIn) {
+  std::vector<int> all = Sequence(2, 42, 2);
+  TypeParam map = ToMap<TypeParam>(Shuffled(all));
+  ASSERT_EQ(20u, map.size());
+
+  // Constructs a sequence from `start` up to but not including `end` by 2.
+  auto Seq = [](int start, int end) { return Sequence(start, end, 2); };
+
+  ASSERT_SEQ_EQ(Empty(), map.keys_in(0, 1));   // before to before
+  ASSERT_SEQ_EQ(all, map.keys_in(0, 100))      // before to after
+  ASSERT_SEQ_EQ(Seq(2, 6), map.keys_in(0, 6))  // before to in map
+  ASSERT_SEQ_EQ(Seq(2, 8), map.keys_in(0, 7))  // before to in between
+
+  ASSERT_SEQ_EQ(Empty(), map.keys_in(100, 0));    // after to before
+  ASSERT_SEQ_EQ(Empty(), map.keys_in(100, 110));  // after to after
+  ASSERT_SEQ_EQ(Empty(), map.keys_in(100, 6));    // after to in map
+  ASSERT_SEQ_EQ(Empty(), map.keys_in(100, 7));    // after to in between
+
+  ASSERT_SEQ_EQ(Empty(), map.keys_in(6, 0));       // in map to before
+  ASSERT_SEQ_EQ(Seq(6, 42), map.keys_in(6, 100));  // in map to after
+  ASSERT_SEQ_EQ(Seq(6, 10), map.keys_in(6, 10));   // in map to in map
+  ASSERT_SEQ_EQ(Seq(6, 12), map.keys_in(6, 11));   // in map to in between
+
+  ASSERT_SEQ_EQ(Empty(), map.keys_in(7, 0));       // in between to before
+  ASSERT_SEQ_EQ(Seq(8, 42), map.keys_in(7, 100));  // in between to after
+  ASSERT_SEQ_EQ(Seq(8, 10), map.keys_in(7, 10));   // in between to key in map
+  ASSERT_SEQ_EQ(Seq(8, 14), map.keys_in(7, 13));   // in between to in between
+}
+
 }  // namespace immutable
 }  // namespace firestore
 }  // namespace firebase