btree_map.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 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 // A bmap<> implements the STL unique sorted associative container
32 // interface and the pair associative container interface (a.k.a map<>) using a
33 // btree. A btree_multimap<> implements the STL multiple sorted associative
34 // container interface and the pair associtive container interface (a.k.a
35 // multimap<>) using a btree. See btree.h for details of the btree
36 // implementation and caveats.
37 
38 #ifndef BENTLEY_UTIL_BTREE_bmap_H__
39 #define BENTLEY_UTIL_BTREE_bmap_H__
40 
41 #include <algorithm>
42 #include <functional>
43 #include <memory>
44 #include <string>
45 #include <utility>
46 
47 #include "btree.h"
48 #include "btree_container.h"
49 
51 
52 // The bmap class is needed mainly for its constructors.
53 template <typename Key, typename Value, typename Compare = std::less<Key>, uint16_t EntriesPerNode = 32,
54  typename Alloc = Bentley::BentleyAllocator<bpair<const Key, Value> > >
55 class bmap : public bmap_container<
56  btree<bmap_params<Key, Value, Compare, Alloc, EntriesPerNode*sizeof(bpair<Key, Value>) > > > {
57 
58  typedef bpair<Key,Value> pair_type;
59  enum { TargetNodeSize = EntriesPerNode*sizeof(pair_type)};
60 
61  typedef bmap<Key, Value, Compare, EntriesPerNode, Alloc> self_type;
62  typedef bmap_params<Key, Value, Compare, Alloc, TargetNodeSize> params_type;
63  typedef btree<params_type> btree_type;
64  typedef bmap_container<btree_type> super_type;
65 
66  public:
67  typedef typename btree_type::key_compare key_compare;
68  typedef typename btree_type::allocator_type allocator_type;
69  typedef typename btree<bmap_params<Key, Value, Compare, Alloc, EntriesPerNode*sizeof(bpair<Key, Value>) > >::iterator iterator;
70 
71  public:
72  // Default constructor.
73  bmap(const key_compare &comp = key_compare(),
74  const allocator_type &alloc = allocator_type())
75  : super_type(comp, alloc) {
76  }
77 
78  // Copy constructor.
79  bmap(const self_type &x)
80  : super_type(x) {
81  }
82 
83  // Range constructor.
84  template <class InputIterator>
85  bmap(InputIterator b, InputIterator e,
86  const key_compare &comp = key_compare(),
87  const allocator_type &alloc = allocator_type())
88  : super_type(b, e, comp, alloc) {
89  }
90 
91  // shortcut to insert without having to create pair. - BENTLEY Extension
92  bpair<iterator,bool> Insert(Key k, Value v) {return this->insert(pair_type(k,v));}
93 
94  bool operator== (self_type const& __y) const {return this->size() == __y.size() && equal (this->begin(), this->end(), __y.begin());}
95  bool operator< (self_type const& __y) const {return lexicographical_compare (this->begin(), this->end(), __y.begin(), __y.end());}
96  bool operator!= (self_type const& __y) const {return !(*this == __y);}
97  bool operator> (self_type const& __y) const {return (__y < *this);}
98  bool operator>= (self_type const& __y) const {return !(*this < __y);}
99  bool operator<= (self_type const& __y) const {return !(__y < *this);}
100 };
101 
102 template <typename K, typename V, typename C, int N, typename A>
103 inline void swap(bmap<K, V, C, N, A> &x,
104  bmap<K, V, C, N, A> &y) {
105  x.swap(y);
106 }
107 
108 // The btree_multimap class is needed mainly for its constructors.
109 template <typename Key, typename Value, typename Compare = std::less<Key>, uint16_t EntriesPerNode = 32,
110  typename Alloc = Bentley::BentleyAllocator<bpair<const Key, Value> > >
111 class bmultimap : public btree_multi_container<
112  btree<bmap_params<Key, Value, Compare, Alloc, EntriesPerNode*sizeof(bpair<Key, Value>)> > > {
113 
114  typedef bpair<Key,Value> pair_type;
115  enum { TargetNodeSize = EntriesPerNode*sizeof(pair_type)};
116 
117  typedef bmultimap<Key, Value, Compare, EntriesPerNode, Alloc> self_type;
118  typedef bmap_params<Key, Value, Compare, Alloc, TargetNodeSize> params_type;
119  typedef btree<params_type> btree_type;
120  typedef btree_multi_container<btree_type> super_type;
121 
122  public:
123  typedef typename btree_type::key_compare key_compare;
124  typedef typename btree_type::allocator_type allocator_type;
125  typedef typename btree_type::data_type data_type;
126  typedef typename btree_type::mapped_type mapped_type;
127  typedef typename btree<bmap_params<Key, Value, Compare, Alloc, EntriesPerNode*sizeof(bpair<Key, Value>)> >::iterator iterator;
128 
129  public:
130  // Default constructor.
131  bmultimap(const key_compare &comp = key_compare(),
132  const allocator_type &alloc = allocator_type())
133  : super_type(comp, alloc) {
134  }
135 
136  // Copy constructor.
137  bmultimap(const self_type &x)
138  : super_type(x) {
139  }
140 
141  // Range constructor.
142  template <class InputIterator>
143  bmultimap(InputIterator b, InputIterator e,
144  const key_compare &comp = key_compare(),
145  const allocator_type &alloc = allocator_type())
146  : super_type(b, e, comp, alloc) {
147  }
148 
149  // shortcut to insert without having to create pair. - BENTLEY Extension
150  iterator Insert(Key k, Value v) {return this->insert(pair_type(k,v));}
151 
152  bool operator== (self_type const& __y) const {return this->size() == __y.size() && equal (this->begin(), this->end(), __y.begin());}
153  bool operator< (self_type const& __y) const {return lexicographical_compare (this->begin(), this->end(), __y.begin(), __y.end());}
154  bool operator!= (self_type const& __y) const {return !(*this == __y);}
155  bool operator> (self_type const& __y) const {return (__y < *this);}
156  bool operator>= (self_type const& __y) const {return !(*this < __y);}
157  bool operator<= (self_type const& __y) const {return !(__y < *this);}
158 };
159 
160 template <typename K, typename V, typename C, int N, typename A>
161 inline void swap(bmultimap<K, V, C, N, A> &x,
162  bmultimap<K, V, C, N, A> &y) {
163  x.swap(y);
164 }
166 
167 #endif // BENTLEY_UTIL_BTREE_bmap_H__
168 
bool operator<=(const basic_string< _CharT, _Traits, _Allocator > &__lhs, const basic_string< _CharT, _Traits, _Allocator > &__rhs)
Definition: basic_string.h:1376
iterator begin()
Definition: stdcxx/bstdmap.h:178
iterator end()
Definition: stdcxx/bstdmap.h:186
void swap(basic_string< _CharT, _Traits, _Allocator > &__a, basic_string< _CharT, _Traits, _Allocator > &__b)
Definition: basic_string.h:1396
#define BEGIN_BENTLEY_NAMESPACE
Definition: Bentley.r.h:24
bool operator<(const basic_string< _CharT, _Traits, _Allocator > &__lhs, const basic_string< _CharT, _Traits, _Allocator > &__rhs)
Definition: basic_string.h:1326
bool operator>(const basic_string< _CharT, _Traits, _Allocator > &__lhs, const basic_string< _CharT, _Traits, _Allocator > &__rhs)
Definition: basic_string.h:1366
A template that has many of the capabilities of std::pair.
Definition: bpair.h:73
bool operator!=(const BentleyAllocator< _Ty > &, const BentleyAllocator< _Other > &)
Definition: BentleyAllocator.h:152
bool operator>=(const basic_string< _CharT, _Traits, _Allocator > &__lhs, const basic_string< _CharT, _Traits, _Allocator > &__rhs)
Definition: basic_string.h:1386
#define END_BENTLEY_NAMESPACE
Definition: Bentley.r.h:25
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.