32 #ifndef BENTLEY_UTIL_BTREE_BTREE_CONTAINER_H__
33 #define BENTLEY_UTIL_BTREE_BTREE_CONTAINER_H__
44 template <
typename Tree>
45 class btree_container {
46 typedef btree_container<Tree> self_type;
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;
67 btree_container(
const key_compare &comp,
const allocator_type &alloc)
68 : tree_(comp, alloc) {
72 btree_container(
const self_type &x)
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(); }
88 return tree_.lower_bound(key);
90 const_iterator
lower_bound(
const key_type &key)
const {
91 return tree_.lower_bound(key);
94 return tree_.upper_bound(key);
96 const_iterator
upper_bound(
const key_type &key)
const {
97 return tree_.upper_bound(key);
100 return tree_.equal_range(key);
103 return tree_.equal_range(key);
110 void swap(self_type &x) {
113 #if defined COMPILE_BTREE_DUMP
114 void dump(std::ostream &os)
const {
118 void verify()
const {
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();
134 double fullness()
const {
return tree_.fullness(); }
135 double overhead()
const {
return tree_.overhead(); }
138 if (
size() != x.size()) {
141 for (const_iterator i =
begin(), xi = x.begin(); i !=
end(); ++i, ++xi) {
149 bool operator!=(
const self_type& other)
const {
158 #if defined COMPILE_BTREE_DUMP
159 template <
typename T>
160 inline std::ostream& operator<<(std::ostream &os, const btree_container<T> &b) {
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;
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;
183 btree_unique_container(
const key_compare &comp = key_compare(),
184 const allocator_type &alloc = allocator_type())
185 : super_type(comp, alloc) {
189 btree_unique_container(
const self_type &x)
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) {
203 iterator
find(
const key_type &key) {
204 return this->tree_.find_unique(key);
206 const_iterator
find(
const key_type &key)
const {
207 return this->tree_.find_unique(key);
209 size_type
count(
const key_type &key)
const {
210 return this->tree_.count_unique(key);
215 return this->tree_.insert_unique(x);
217 iterator
insert(iterator position,
const value_type &x) {
218 return this->tree_.insert_unique(position, x);
220 template <
typename InputIterator>
221 void insert(InputIterator b, InputIterator e) {
222 this->tree_.insert_unique(b, e);
226 int erase(
const key_type &key) {
227 return this->tree_.erase_unique(key);
232 iterator
erase(
const iterator &iter) {
233 return this->tree_.erase(iter);
235 void erase(
const iterator &first,
const iterator &last) {
236 this->tree_.erase(first, last);
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;
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;
258 struct generate_value {
259 generate_value(
const key_type &k)
270 bmap_container(
const key_compare &comp = key_compare(),
271 const allocator_type &alloc = allocator_type())
272 : super_type(comp, alloc) {
276 bmap_container(
const self_type &x)
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) {
290 return this->tree_.insert_unique(key, generate_value(key)).first->second;
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;
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;
311 btree_multi_container(
const key_compare &comp = key_compare(),
312 const allocator_type &alloc = allocator_type())
313 : super_type(comp, alloc) {
317 btree_multi_container(
const self_type &x)
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) {
331 iterator
find(
const key_type &key) {
332 return this->tree_.find_multi(key);
334 const_iterator
find(
const key_type &key)
const {
335 return this->tree_.find_multi(key);
337 size_type
count(
const key_type &key)
const {
338 return this->tree_.count_multi(key);
342 iterator
insert(
const value_type &x) {
343 return this->tree_.insert_multi(x);
345 iterator
insert(iterator position,
const value_type &x) {
346 return this->tree_.insert_multi(position, x);
348 template <
typename InputIterator>
349 void insert(InputIterator b, InputIterator e) {
350 this->tree_.insert_multi(b, e);
354 int erase(
const key_type &key) {
355 return this->tree_.erase_multi(key);
360 iterator
erase(
const iterator &iter) {
361 return this->tree_.erase(iter);
363 void erase(
const iterator &first,
const iterator &last) {
364 this->tree_.erase(first, last);
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.