1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
|
/*
* 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_TREE_SORTED_MAP_H_
#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_IMMUTABLE_TREE_SORTED_MAP_H_
#include <assert.h>
#include <algorithm>
#include <functional>
#include <memory>
#include <utility>
#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 {
namespace immutable {
namespace impl {
/**
* TreeSortedMap is a value type containing a map. It is immutable, but has
* 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> {
public:
/**
* The type of the entries stored in the map.
*/
using value_type = std::pair<K, V>;
/**
* The type of the node containing entries of value_type.
*/
using node_type = LlrbNode<K, V>;
/**
* Creates an empty TreeSortedMap.
*/
explicit TreeSortedMap(const C& comparator = {})
: util::ComparatorHolder<C>{comparator}, root_{node_type::Empty()} {
}
/**
* Creates a new map identical to this one, but with a key-value pair added or
* updated.
*
* @param key The key to insert/update.
* @param value The value to associate with the key.
* @return A new dictionary with the added/updated value.
*/
TreeSortedMap insert(const K& key, const V& value) const {
// TODO(wilhuff): Actually implement insert
(void)key;
(void)value;
return *this;
}
/**
* Creates a new map identical to this one, but with a key removed from it.
*
* @param key The key to remove.
* @return A new map without that value.
*/
TreeSortedMap erase(const K& key) const {
// TODO(wilhuff): Actually implement erase
(void)key;
return *this;
}
/** Returns true if the map contains no elements. */
bool empty() const {
return root_.empty();
}
/** Returns the number of items in this map. */
size_type size() const {
return root_.size();
}
const node_type& root() const {
return root_;
}
private:
TreeSortedMap(node_type&& root, const C& comparator) noexcept
: util::ComparatorHolder<C>{comparator}, root_{std::move(root)} {
}
TreeSortedMap Wrap(node_type&& root) noexcept {
return TreeSortedMap{std::move(root), this->comparator()};
}
node_type root_;
};
} // namespace impl
} // namespace immutable
} // namespace firestore
} // namespace firebase
#endif // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_IMMUTABLE_TREE_SORTED_MAP_H_
|