1 files changed, 143 insertions, 0 deletions
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_