1 // Copyright 2013 Google Inc. All Rights Reserved.
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
7 // http://www.apache.org/licenses/LICENSE-2.0
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
15 #ifndef UTIL_BTREE_BTREE_CONTAINER_H__
16 #define UTIL_BTREE_BTREE_CONTAINER_H__
25 // A common base class for btree_set, btree_map, btree_multiset and
27 template <typename Tree>
28 class btree_container {
29 typedef btree_container<Tree> self_type;
32 typedef typename Tree::params_type params_type;
33 typedef typename Tree::key_type key_type;
34 typedef typename Tree::value_type value_type;
35 typedef typename Tree::key_compare key_compare;
36 typedef typename Tree::allocator_type allocator_type;
37 typedef typename Tree::pointer pointer;
38 typedef typename Tree::const_pointer const_pointer;
39 typedef typename Tree::reference reference;
40 typedef typename Tree::const_reference const_reference;
41 typedef typename Tree::size_type size_type;
42 typedef typename Tree::difference_type difference_type;
43 typedef typename Tree::iterator iterator;
44 typedef typename Tree::const_iterator const_iterator;
45 typedef typename Tree::reverse_iterator reverse_iterator;
46 typedef typename Tree::const_reverse_iterator const_reverse_iterator;
49 // Default constructor.
50 btree_container(const key_compare &comp, const allocator_type &alloc)
51 : tree_(comp, alloc) {
55 btree_container(const self_type &x)
60 iterator begin() { return tree_.begin(); }
61 const_iterator begin() const { return tree_.begin(); }
62 iterator end() { return tree_.end(); }
63 const_iterator end() const { return tree_.end(); }
64 reverse_iterator rbegin() { return tree_.rbegin(); }
65 const_reverse_iterator rbegin() const { return tree_.rbegin(); }
66 reverse_iterator rend() { return tree_.rend(); }
67 const_reverse_iterator rend() const { return tree_.rend(); }
70 iterator lower_bound(const key_type &key) {
71 return tree_.lower_bound(key);
73 const_iterator lower_bound(const key_type &key) const {
74 return tree_.lower_bound(key);
76 iterator upper_bound(const key_type &key) {
77 return tree_.upper_bound(key);
79 const_iterator upper_bound(const key_type &key) const {
80 return tree_.upper_bound(key);
82 std::pair<iterator,iterator> equal_range(const key_type &key) {
83 return tree_.equal_range(key);
85 std::pair<const_iterator,const_iterator> equal_range(const key_type &key) const {
86 return tree_.equal_range(key);
93 void swap(self_type &x) {
96 void dump(std::ostream &os) const {
104 size_type size() const { return tree_.size(); }
105 size_type max_size() const { return tree_.max_size(); }
106 bool empty() const { return tree_.empty(); }
107 size_type height() const { return tree_.height(); }
108 size_type internal_nodes() const { return tree_.internal_nodes(); }
109 size_type leaf_nodes() const { return tree_.leaf_nodes(); }
110 size_type nodes() const { return tree_.nodes(); }
111 size_type bytes_used() const { return tree_.bytes_used(); }
112 static double average_bytes_per_value() {
113 return Tree::average_bytes_per_value();
115 double fullness() const { return tree_.fullness(); }
116 double overhead() const { return tree_.overhead(); }
118 bool operator==(const self_type& x) const {
119 if (size() != x.size()) {
122 for (const_iterator i = begin(), xi = x.begin(); i != end(); ++i, ++xi) {
130 bool operator!=(const self_type& other) const {
131 return !operator==(other);
139 template <typename T>
140 inline std::ostream& operator<<(std::ostream &os, const btree_container<T> &b) {
145 // A common base class for btree_set and safe_btree_set.
146 template <typename Tree>
147 class btree_unique_container : public btree_container<Tree> {
148 typedef btree_unique_container<Tree> self_type;
149 typedef btree_container<Tree> super_type;
152 typedef typename Tree::key_type key_type;
153 typedef typename Tree::value_type value_type;
154 typedef typename Tree::size_type size_type;
155 typedef typename Tree::key_compare key_compare;
156 typedef typename Tree::allocator_type allocator_type;
157 typedef typename Tree::iterator iterator;
158 typedef typename Tree::const_iterator const_iterator;
161 // Default constructor.
162 btree_unique_container(const key_compare &comp = key_compare(),
163 const allocator_type &alloc = allocator_type())
164 : super_type(comp, alloc) {
168 btree_unique_container(const self_type &x)
172 // Range constructor.
173 template <class InputIterator>
174 btree_unique_container(InputIterator b, InputIterator e,
175 const key_compare &comp = key_compare(),
176 const allocator_type &alloc = allocator_type())
177 : super_type(comp, alloc) {
182 iterator find(const key_type &key) {
183 return this->tree_.find_unique(key);
185 const_iterator find(const key_type &key) const {
186 return this->tree_.find_unique(key);
188 size_type count(const key_type &key) const {
189 return this->tree_.count_unique(key);
192 // Insertion routines.
193 std::pair<iterator,bool> insert(const value_type &x) {
194 return this->tree_.insert_unique(x);
196 iterator insert(iterator position, const value_type &x) {
197 return this->tree_.insert_unique(position, x);
199 template <typename InputIterator>
200 void insert(InputIterator b, InputIterator e) {
201 this->tree_.insert_unique(b, e);
204 // Deletion routines.
205 int erase(const key_type &key) {
206 return this->tree_.erase_unique(key);
208 // Erase the specified iterator from the btree. The iterator must be valid
209 // (i.e. not equal to end()). Return an iterator pointing to the node after
210 // the one that was erased (or end() if none exists).
211 iterator erase(const iterator &iter) {
212 return this->tree_.erase(iter);
214 void erase(const iterator &first, const iterator &last) {
215 this->tree_.erase(first, last);
219 // A common base class for btree_map and safe_btree_map.
220 template <typename Tree>
221 class btree_map_container : public btree_unique_container<Tree> {
222 typedef btree_map_container<Tree> self_type;
223 typedef btree_unique_container<Tree> super_type;
226 typedef typename Tree::key_type key_type;
227 typedef typename Tree::data_type data_type;
228 typedef typename Tree::value_type value_type;
229 typedef typename Tree::mapped_type mapped_type;
230 typedef typename Tree::key_compare key_compare;
231 typedef typename Tree::allocator_type allocator_type;
234 // A pointer-like object which only generates its value when
235 // dereferenced. Used by operator[] to avoid constructing an empty data_type
236 // if the key already exists in the map.
237 struct generate_value {
238 generate_value(const key_type &k)
241 value_type operator*() const {
242 return std::make_pair(key, data_type());
248 // Default constructor.
249 btree_map_container(const key_compare &comp = key_compare(),
250 const allocator_type &alloc = allocator_type())
251 : super_type(comp, alloc) {
255 btree_map_container(const self_type &x)
259 // Range constructor.
260 template <class InputIterator>
261 btree_map_container(InputIterator b, InputIterator e,
262 const key_compare &comp = key_compare(),
263 const allocator_type &alloc = allocator_type())
264 : super_type(b, e, comp, alloc) {
267 // Insertion routines.
268 data_type& operator[](const key_type &key) {
269 return this->tree_.insert_unique(key, generate_value(key)).first->second;
273 // A common base class for btree_multiset and btree_multimap.
274 template <typename Tree>
275 class btree_multi_container : public btree_container<Tree> {
276 typedef btree_multi_container<Tree> self_type;
277 typedef btree_container<Tree> super_type;
280 typedef typename Tree::key_type key_type;
281 typedef typename Tree::value_type value_type;
282 typedef typename Tree::size_type size_type;
283 typedef typename Tree::key_compare key_compare;
284 typedef typename Tree::allocator_type allocator_type;
285 typedef typename Tree::iterator iterator;
286 typedef typename Tree::const_iterator const_iterator;
289 // Default constructor.
290 btree_multi_container(const key_compare &comp = key_compare(),
291 const allocator_type &alloc = allocator_type())
292 : super_type(comp, alloc) {
296 btree_multi_container(const self_type &x)
300 // Range constructor.
301 template <class InputIterator>
302 btree_multi_container(InputIterator b, InputIterator e,
303 const key_compare &comp = key_compare(),
304 const allocator_type &alloc = allocator_type())
305 : super_type(comp, alloc) {
310 iterator find(const key_type &key) {
311 return this->tree_.find_multi(key);
313 const_iterator find(const key_type &key) const {
314 return this->tree_.find_multi(key);
316 size_type count(const key_type &key) const {
317 return this->tree_.count_multi(key);
320 // Insertion routines.
321 iterator insert(const value_type &x) {
322 return this->tree_.insert_multi(x);
324 iterator insert(iterator position, const value_type &x) {
325 return this->tree_.insert_multi(position, x);
327 template <typename InputIterator>
328 void insert(InputIterator b, InputIterator e) {
329 this->tree_.insert_multi(b, e);
332 // Deletion routines.
333 int erase(const key_type &key) {
334 return this->tree_.erase_multi(key);
336 // Erase the specified iterator from the btree. The iterator must be valid
337 // (i.e. not equal to end()). Return an iterator pointing to the node after
338 // the one that was erased (or end() if none exists).
339 iterator erase(const iterator &iter) {
340 return this->tree_.erase(iter);
342 void erase(const iterator &first, const iterator &last) {
343 this->tree_.erase(first, last);
349 #endif // UTIL_BTREE_BTREE_CONTAINER_H__