Add Immutable SortedSet in C++ (#1206)

* Add SortedSet

* Add document_key_set.h

* Add equality to SortedSet

3 files changed, 178 insertions, 0 deletions

diff --git a/Firestore/core/src/firebase/firestore/immutable/CMakeLists.txt b/Firestore/core/src/firebase/firestore/immutable/CMakeLists.txt
index 90ce204..af97b62 100644
--- a/Firestore/core/src/firebase/firestore/immutable/CMakeLists.txt
+++ b/Firestore/core/src/firebase/firestore/immutable/CMakeLists.txt
@@ -24,6 +24,7 @@ cc_library(
     sorted_map_base.h
     sorted_map_base.cc
     sorted_map_iterator.h
+    sorted_set.h
     tree_sorted_map.h
   DEPENDS
     firebase_firestore_util
diff --git a/Firestore/core/src/firebase/firestore/immutable/sorted_set.h b/Firestore/core/src/firebase/firestore/immutable/sorted_set.h
new file mode 100644
index 0000000..6828106
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/immutable/sorted_set.h
@@ -0,0 +1,143 @@
+/*
+ * 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_SORTED_SET_H_
+#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_IMMUTABLE_SORTED_SET_H_
+
+#include <algorithm>
+#include <utility>
+
+#include "Firestore/core/src/firebase/firestore/immutable/sorted_map.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/hashing.h"
+
+namespace firebase {
+namespace firestore {
+namespace immutable {
+
+namespace impl {
+
+// An empty value to associate with keys in the underlying map.
+struct Empty {
+  friend bool operator==(Empty /* left */, Empty /* right */) {
+    return true;
+  }
+};
+
+}  // namespace impl
+
+template <typename K,
+          typename V = impl::Empty,
+          typename C = util::Comparator<K>,
+          typename M = SortedMap<K, V, C>>
+class SortedSet {
+ public:
+  using size_type = typename M::size_type;
+  using value_type = K;
+
+  using const_iterator = typename M::const_key_iterator;
+
+  explicit SortedSet(const C& comparator = C()) : map_{comparator} {
+  }
+
+  explicit SortedSet(const M& map) : map_{map} {
+  }
+
+  explicit SortedSet(M&& map) : map_{std::move(map)} {
+  }
+
+  bool empty() const {
+    return map_.empty();
+  }
+
+  size_type size() const {
+    return map_.size();
+  }
+
+  SortedSet insert(const K& key) const {
+    return SortedSet{map_.insert(key, {})};
+  }
+
+  SortedSet erase(const K& key) const {
+    return SortedSet{map_.erase(key)};
+  }
+
+  bool contains(const K& key) const {
+    return map_.contains(key);
+  }
+
+  const_iterator find(const K& key) const {
+    return const_iterator{map_.find(key)};
+  }
+
+  size_type find_index(const K& key) const {
+    return map_.find_index(key);
+  }
+
+  const_iterator min() const {
+    return const_iterator{map_.min()};
+  }
+
+  const K& max() const {
+    return const_iterator{map_.max()};
+  }
+
+  const_iterator begin() const {
+    return const_iterator{map_.begin()};
+  }
+
+  const_iterator end() const {
+    return const_iterator{map_.end()};
+  }
+
+  /**
+   * Returns a view of this SortedSet containing just the keys that have been
+   * inserted that are greater than or equal to the given key.
+   */
+  const util::range<const_iterator> values_from(const K& key) const {
+    return map_.keys_from(key);
+  }
+
+  /**
+   * Returns a view of this SortedSet 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_iterator> values_in(const K& start_key,
+                                              const K& end_key) const {
+    return map_.keys_in(start_key, end_key);
+  }
+
+  friend bool operator==(const SortedSet& lhs, const SortedSet& rhs) {
+    return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
+  }
+
+ private:
+  M map_;
+};
+
+template <typename K, typename V, typename C>
+SortedSet<K, V, C> MakeSortedSet(const SortedMap<K, V, C>& map) {
+  return SortedSet<K, V, C>{map};
+}
+
+}  // namespace immutable
+}  // namespace firestore
+}  // namespace firebase
+
+#endif  // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_IMMUTABLE_SORTED_SET_H_
diff --git a/Firestore/core/src/firebase/firestore/model/document_key_set.h b/Firestore/core/src/firebase/firestore/model/document_key_set.h
new file mode 100644
index 0000000..1301bf5
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/model/document_key_set.h
@@ -0,0 +1,34 @@
+/*
+ * 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_MODEL_DOCUMENT_KEY_SET_H_
+#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_MODEL_DOCUMENT_KEY_SET_H_
+
+#include "Firestore/core/src/firebase/firestore/immutable/sorted_set.h"
+#include "Firestore/core/src/firebase/firestore/model/document_key.h"
+
+namespace firebase {
+namespace firestore {
+namespace model {
+
+/** Convenience type for a set of keys, since they are so common. */
+using DocumentKeySet = immutable::SortedSet<DocumentKey>;
+
+}  // namespace model
+}  // namespace firestore
+}  // namespace firebase
+
+#endif  // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_MODEL_DOCUMENT_KEY_SET_H_