btree_container.h
Go to the documentation of this file.
1 /*--------------------------------------------------------------------------------------+
2 |
3 | Supplied under applicable software license agreement.
4 |
5 | Copyright (c) 2018 Bentley Systems, Incorporated. All rights reserved.
6 |
7 +---------------------------------------------------------------------------------------*/
8 #pragma once
9 
11 // **************************************************************************
12 // *
13 // * NOTICE: This File contains modifications made by Bentley Systems Inc. where designated.
14 // *
15 // *************************************************************************/
16 
17 // Copyright 2013 Google Inc. All Rights Reserved.
18 //
19 // Licensed under the Apache License, Version 2.0 (the "License");
20 // you may not use this file except in compliance with the License.
21 // You may obtain a copy of the License at
22 //
23 // http://www.apache.org/licenses/LICENSE-2.0
24 //
25 // Unless required by applicable law or agreed to in writing, software
26 // distributed under the License is distributed on an "AS IS" BASIS,
27 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
28 // See the License for the specific language governing permissions and
29 // limitations under the License.
30 
31 
32 #ifndef BENTLEY_UTIL_BTREE_BTREE_CONTAINER_H__
33 #define BENTLEY_UTIL_BTREE_BTREE_CONTAINER_H__
34 
35 #include <iosfwd>
36 #include <utility>
37 
38 #include "btree.h"
39 
41 
42 // A common base class for btree_set, bmap, btree_multiset and
43 // btree_multimap.
44 template <typename Tree>
45 class btree_container {
46  typedef btree_container<Tree> self_type;
47 
48  public:
49  typedef typename Tree::params_type params_type;
50  typedef typename Tree::key_type key_type;
51  typedef typename Tree::value_type value_type;
52  typedef typename Tree::key_compare key_compare;
53  typedef typename Tree::allocator_type allocator_type;
54  typedef typename Tree::pointer pointer;
55  typedef typename Tree::const_pointer const_pointer;
56  typedef typename Tree::reference reference;
57  typedef typename Tree::const_reference const_reference;
58  typedef typename Tree::size_type size_type;
59  typedef typename Tree::difference_type difference_type;
60  typedef typename Tree::iterator iterator;
61  typedef typename Tree::const_iterator const_iterator;
62  typedef typename Tree::reverse_iterator reverse_iterator;
63  typedef typename Tree::const_reverse_iterator const_reverse_iterator;
64 
65  public:
66  // Default constructor.
67  btree_container(const key_compare &comp, const allocator_type &alloc)
68  : tree_(comp, alloc) {
69  }
70 
71  // Copy constructor.
72  btree_container(const self_type &x)
73  : tree_(x.tree_) {
74  }
75 
76  // Iterator routines.
77  iterator begin() { return tree_.begin(); }
78  const_iterator begin() const { return tree_.begin(); }
79  iterator end() { return tree_.end(); }
80  const_iterator end() const { return tree_.end(); }
81  reverse_iterator rbegin() { return tree_.rbegin(); }
82  const_reverse_iterator rbegin() const { return tree_.rbegin(); }
83  reverse_iterator rend() { return tree_.rend(); }
84  const_reverse_iterator rend() const { return tree_.rend(); }
85 
86  // Lookup routines.
87  iterator lower_bound(const key_type &key) {
88  return tree_.lower_bound(key);
89  }
90  const_iterator lower_bound(const key_type &key) const {
91  return tree_.lower_bound(key);
92  }
93  iterator upper_bound(const key_type &key) {
94  return tree_.upper_bound(key);
95  }
96  const_iterator upper_bound(const key_type &key) const {
97  return tree_.upper_bound(key);
98  }
99  bpair<iterator,iterator> equal_range(const key_type &key) {
100  return tree_.equal_range(key);
101  }
102  bpair<const_iterator,const_iterator> equal_range(const key_type &key) const {
103  return tree_.equal_range(key);
104  }
105 
106  // Utility routines.
107  void clear() {
108  tree_.clear();
109  }
110  void swap(self_type &x) {
111  tree_.swap(x.tree_);
112  }
113 #if defined COMPILE_BTREE_DUMP
114  void dump(std::ostream &os) const {
115  tree_.dump(os);
116  }
117 #endif
118  void verify() const {
119  tree_.verify();
120  }
121 
122  // Size routines.
123  size_type size() const { return tree_.size(); }
124  size_type max_size() const { return tree_.max_size(); }
125  bool empty() const { return tree_.empty(); }
126  size_type height() const { return tree_.height(); }
127  size_type internal_nodes() const { return tree_.internal_nodes(); }
128  size_type leaf_nodes() const { return tree_.leaf_nodes(); }
129  size_type nodes() const { return tree_.nodes(); }
130  size_type bytes_used() const { return tree_.bytes_used(); }
131  static double average_bytes_per_value() {
132  return Tree::average_bytes_per_value();
133  }
134  double fullness() const { return tree_.fullness(); }
135  double overhead() const { return tree_.overhead(); }
136 
137  bool operator==(const self_type& x) const {
138  if (size() != x.size()) {
139  return false;
140  }
141  for (const_iterator i = begin(), xi = x.begin(); i != end(); ++i, ++xi) {
142  if (*i != *xi) {
143  return false;
144  }
145  }
146  return true;
147  }
148 
149  bool operator!=(const self_type& other) const {
150  return !operator==(other);
151  }
152 
153 
154  protected:
155  Tree tree_;
156 };
157 
158 #if defined COMPILE_BTREE_DUMP
159 template <typename T>
160 inline std::ostream& operator<<(std::ostream &os, const btree_container<T> &b) {
161  b.dump(os);
162  return os;
163 }
164 #endif
165 
166 // A common base class for btree_set and safe_btree_set.
167 template <typename Tree>
168 class btree_unique_container : public btree_container<Tree> {
169  typedef btree_unique_container<Tree> self_type;
170  typedef btree_container<Tree> super_type;
171 
172  public:
173  typedef typename Tree::key_type key_type;
174  typedef typename Tree::value_type value_type;
175  typedef typename Tree::size_type size_type;
176  typedef typename Tree::key_compare key_compare;
177  typedef typename Tree::allocator_type allocator_type;
178  typedef typename Tree::iterator iterator;
179  typedef typename Tree::const_iterator const_iterator;
180 
181  public:
182  // Default constructor.
183  btree_unique_container(const key_compare &comp = key_compare(),
184  const allocator_type &alloc = allocator_type())
185  : super_type(comp, alloc) {
186  }
187 
188  // Copy constructor.
189  btree_unique_container(const self_type &x)
190  : super_type(x) {
191  }
192 
193  // Range constructor.
194  template <class InputIterator>
195  btree_unique_container(InputIterator b, InputIterator e,
196  const key_compare &comp = key_compare(),
197  const allocator_type &alloc = allocator_type())
198  : super_type(comp, alloc) {
199  insert(b, e);
200  }
201 
202  // Lookup routines.
203  iterator find(const key_type &key) {
204  return this->tree_.find_unique(key);
205  }
206  const_iterator find(const key_type &key) const {
207  return this->tree_.find_unique(key);
208  }
209  size_type count(const key_type &key) const {
210  return this->tree_.count_unique(key);
211  }
212 
213  // Insertion routines.
214  bpair<iterator,bool> insert(const value_type &x) {
215  return this->tree_.insert_unique(x);
216  }
217  iterator insert(iterator position, const value_type &x) {
218  return this->tree_.insert_unique(position, x);
219  }
220  template <typename InputIterator>
221  void insert(InputIterator b, InputIterator e) {
222  this->tree_.insert_unique(b, e);
223  }
224 
225  // Deletion routines.
226  int erase(const key_type &key) {
227  return this->tree_.erase_unique(key);
228  }
229  // Erase the specified iterator from the btree. The iterator must be valid
230  // (i.e. not equal to end()). Return an iterator pointing to the node after
231  // the one that was erased (or end() if none exists).
232  iterator erase(const iterator &iter) {
233  return this->tree_.erase(iter);
234  }
235  void erase(const iterator &first, const iterator &last) {
236  this->tree_.erase(first, last);
237  }
238 };
239 
240 // A common base class for bmap and safe_bmap.
241 template <typename Tree>
242 class bmap_container : public btree_unique_container<Tree> {
243  typedef bmap_container<Tree> self_type;
244  typedef btree_unique_container<Tree> super_type;
245 
246  public:
247  typedef typename Tree::key_type key_type;
248  typedef typename Tree::data_type data_type;
249  typedef typename Tree::value_type value_type;
250  typedef typename Tree::mapped_type mapped_type;
251  typedef typename Tree::key_compare key_compare;
252  typedef typename Tree::allocator_type allocator_type;
253 
254  private:
255  // A pointer-like object which only generates its value when
256  // dereferenced. Used by operator[] to avoid constructing an empty data_type
257  // if the key already exists in the map.
258  struct generate_value {
259  generate_value(const key_type &k)
260  : key(k) {
261  }
262  value_type operator*() const {
263  return make_bpair(key, data_type());
264  }
265  const key_type &key;
266  };
267 
268  public:
269  // Default constructor.
270  bmap_container(const key_compare &comp = key_compare(),
271  const allocator_type &alloc = allocator_type())
272  : super_type(comp, alloc) {
273  }
274 
275  // Copy constructor.
276  bmap_container(const self_type &x)
277  : super_type(x) {
278  }
279 
280  // Range constructor.
281  template <class InputIterator>
282  bmap_container(InputIterator b, InputIterator e,
283  const key_compare &comp = key_compare(),
284  const allocator_type &alloc = allocator_type())
285  : super_type(b, e, comp, alloc) {
286  }
287 
288  // Insertion routines.
289  data_type& operator[](const key_type &key) {
290  return this->tree_.insert_unique(key, generate_value(key)).first->second;
291  }
292 };
293 
294 // A common base class for btree_multiset and btree_multimap.
295 template <typename Tree>
296 class btree_multi_container : public btree_container<Tree> {
297  typedef btree_multi_container<Tree> self_type;
298  typedef btree_container<Tree> super_type;
299 
300  public:
301  typedef typename Tree::key_type key_type;
302  typedef typename Tree::value_type value_type;
303  typedef typename Tree::size_type size_type;
304  typedef typename Tree::key_compare key_compare;
305  typedef typename Tree::allocator_type allocator_type;
306  typedef typename Tree::iterator iterator;
307  typedef typename Tree::const_iterator const_iterator;
308 
309  public:
310  // Default constructor.
311  btree_multi_container(const key_compare &comp = key_compare(),
312  const allocator_type &alloc = allocator_type())
313  : super_type(comp, alloc) {
314  }
315 
316  // Copy constructor.
317  btree_multi_container(const self_type &x)
318  : super_type(x) {
319  }
320 
321  // Range constructor.
322  template <class InputIterator>
323  btree_multi_container(InputIterator b, InputIterator e,
324  const key_compare &comp = key_compare(),
325  const allocator_type &alloc = allocator_type())
326  : super_type(comp, alloc) {
327  insert(b, e);
328  }
329 
330  // Lookup routines.
331  iterator find(const key_type &key) {
332  return this->tree_.find_multi(key);
333  }
334  const_iterator find(const key_type &key) const {
335  return this->tree_.find_multi(key);
336  }
337  size_type count(const key_type &key) const {
338  return this->tree_.count_multi(key);
339  }
340 
341  // Insertion routines.
342  iterator insert(const value_type &x) {
343  return this->tree_.insert_multi(x);
344  }
345  iterator insert(iterator position, const value_type &x) {
346  return this->tree_.insert_multi(position, x);
347  }
348  template <typename InputIterator>
349  void insert(InputIterator b, InputIterator e) {
350  this->tree_.insert_multi(b, e);
351  }
352 
353  // Deletion routines.
354  int erase(const key_type &key) {
355  return this->tree_.erase_multi(key);
356  }
357  // Erase the specified iterator from the btree. The iterator must be valid
358  // (i.e. not equal to end()). Return an iterator pointing to the node after
359  // the one that was erased (or end() if none exists).
360  iterator erase(const iterator &iter) {
361  return this->tree_.erase(iter);
362  }
363  void erase(const iterator &first, const iterator &last) {
364  this->tree_.erase(first, last);
365  }
366 };
367 
369 
370 #endif // BENTLEY_UTIL_BTREE_BTREE_CONTAINER_H__
371 
iterator find(const key_type &__x)
Definition: stdcxx/bstdmap.h:269
bool empty() const
Definition: stdcxx/bstdmap.h:210
reverse_iterator rend()
Definition: stdcxx/bstdmap.h:202
iterator lower_bound(const key_type &__x)
Definition: stdcxx/bstdmap.h:281
iterator begin()
Definition: stdcxx/bstdmap.h:178
iterator upper_bound(const key_type &__x)
Definition: stdcxx/bstdmap.h:285
iterator end()
Definition: stdcxx/bstdmap.h:186
size_type count(const key_type &__x) const
Definition: stdcxx/bstdmap.h:277
void swap(basic_string< _CharT, _Traits, _Allocator > &__a, basic_string< _CharT, _Traits, _Allocator > &__b)
Definition: basic_string.h:1396
bpair< iterator, iterator > equal_range(const key_type &__x)
Definition: stdcxx/bstdmap.h:297
iterator erase(iterator __it)
Definition: stdcxx/bstdmap.h:242
#define BEGIN_BENTLEY_NAMESPACE
Definition: Bentley.r.h:24
A template that has many of the capabilities of std::pair.
Definition: bpair.h:73
size_type max_size() const
Definition: stdcxx/bstdmap.h:218
bpair< _TypeT, _TypeU > make_bpair(_TypeT __x, _TypeU __y)
Definition: bpair.h:177
DVec3d operator*(Transform const &transform, DVec3d const &vector)
operator overload for multiplication of a transform and a vector li>The vector appears on the left as...
bool operator!=(const BentleyAllocator< _Ty > &, const BentleyAllocator< _Other > &)
Definition: BentleyAllocator.h:152
mapped_type & operator[](const key_type &__k)
Definition: stdcxx/bstdmap.h:222
#define END_BENTLEY_NAMESPACE
Definition: Bentley.r.h:25
void clear()
Definition: stdcxx/bstdmap.h:257
reverse_iterator rbegin()
Definition: stdcxx/bstdmap.h:194
size_type size() const
Definition: stdcxx/bstdmap.h:214
bpair< iterator, bool > insert(const value_type &__x)
Definition: stdcxx/bstdmap.h:228
bool operator==(const BentleyAllocator< _Ty > &, const BentleyAllocator< _Other > &)
Definition: BentleyAllocator.h:146

Copyright © 2017 Bentley Systems, Incorporated. All rights reserved.