From f86c2ebb3c6f878d65ef32217adc956057ac9649 Mon Sep 17 00:00:00 2001 From: Gil Date: Wed, 2 May 2018 13:32:00 -0700 Subject: Add Immutable SortedSet in C++ (#1206) * Add SortedSet * Add document_key_set.h * Add equality to SortedSet --- .../firebase/firestore/immutable/CMakeLists.txt | 1 + .../src/firebase/firestore/immutable/sorted_set.h | 143 +++++++++++++++++++++ .../firebase/firestore/model/document_key_set.h | 34 +++++ 3 files changed, 178 insertions(+) create mode 100644 Firestore/core/src/firebase/firestore/immutable/sorted_set.h create mode 100644 Firestore/core/src/firebase/firestore/model/document_key_set.h (limited to 'Firestore/core/src') 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 +#include + +#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 M = SortedMap> +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 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 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 +SortedSet MakeSortedSet(const SortedMap& map) { + return SortedSet{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; + +} // namespace model +} // namespace firestore +} // namespace firebase + +#endif // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_MODEL_DOCUMENT_KEY_SET_H_ -- cgit v1.2.3