btree_set.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 btree_set<> implements the STL unique sorted associative container
32 // interface (a.k.a set<>) using a btree. A btree_multiset<> implements the STL
33 // multiple sorted associative container interface (a.k.a multiset<>) using a
34 // btree. See btree.h for details of the btree implementation and caveats.
35 
36 #ifndef UTIL_BTREE_BTREE_SET_H__
37 #define UTIL_BTREE_BTREE_SET_H__
38 
39 #include <functional>
40 #include <memory>
41 
42 #include "btree.h"
43 #include "btree_container.h"
44 
46 
47 // The btree_set class is needed mainly for its constructors.
48 template <typename Key, typename Compare = std::less<Key>, uint16_t EntriesPerNode = 32,
49  typename Alloc = Bentley::BentleyAllocator<Key> >
50 class bset : public btree_unique_container<
51  btree<btree_set_params<Key, Compare, Alloc, EntriesPerNode*sizeof(Key)> > > {
52 
53  enum { TargetNodeSize = EntriesPerNode*sizeof(Key)};
54  typedef bset<Key, Compare, EntriesPerNode, Alloc> self_type;
55  typedef btree_set_params<Key, Compare, Alloc, TargetNodeSize> params_type;
56  typedef btree<params_type> btree_type;
57  typedef btree_unique_container<btree_type> super_type;
58 
59  public:
60  typedef typename btree_type::key_compare key_compare;
61  typedef typename btree_type::allocator_type allocator_type;
62 
63  public:
64  // Default constructor.
65  bset(const key_compare &comp = key_compare(),
66  const allocator_type &alloc = allocator_type())
67  : super_type(comp, alloc) {
68  }
69 
70  // Copy constructor.
71  bset(const self_type &x)
72  : super_type(x) {
73  }
74 
75  // Range constructor.
76  template <class InputIterator>
77  bset(InputIterator b, InputIterator e,
78  const key_compare &comp = key_compare(),
79  const allocator_type &alloc = allocator_type())
80  : super_type(b, e, comp, alloc) {
81  }
82 
83  bool operator== (self_type const& __y) const {return this->size() == __y.size() && equal (this->begin(), this->end(), __y.begin());}
84  bool operator< (self_type const& __y) const {return lexicographical_compare (this->begin(), this->end(), __y.begin(), __y.end());}
85  bool operator!= (self_type const& __y) const {return !(*this == __y);}
86  bool operator> (self_type const& __y) const {return (__y < *this);}
87  bool operator>= (self_type const& __y) const {return !(*this < __y);}
88  bool operator<= (self_type const& __y) const {return !(__y < *this);}
89 };
90 
91 template <typename K, typename C, int N, typename A>
92 inline void swap(bset<K, C, N, A> &x,
93  bset<K, C, N, A> &y) {
94  x.swap(y);
95 }
96 
97 // The btree_multiset class is needed mainly for its constructors.
98 template <typename Key, typename Compare = std::less<Key>, uint16_t EntriesPerNode = 32,
99  typename Alloc = Bentley::BentleyAllocator<Key> >
100 class bmultiset : public btree_multi_container<
101  btree<btree_set_params<Key, Compare, Alloc, EntriesPerNode*sizeof(Key)> > > {
102 
103  enum { TargetNodeSize = EntriesPerNode*sizeof(Key)};
104  typedef bmultiset<Key, Compare, EntriesPerNode, Alloc> self_type;
105  typedef btree_set_params<Key, Compare, Alloc, TargetNodeSize> params_type;
106  typedef btree<params_type> btree_type;
107  typedef btree_multi_container<btree_type> super_type;
108 
109  public:
110  typedef typename btree_type::key_compare key_compare;
111  typedef typename btree_type::allocator_type allocator_type;
112 
113  public:
114  // Default constructor.
115  bmultiset(const key_compare &comp = key_compare(),
116  const allocator_type &alloc = allocator_type())
117  : super_type(comp, alloc) {
118  }
119 
120  // Copy constructor.
121  bmultiset(const self_type &x)
122  : super_type(x) {
123  }
124 
125  // Range constructor.
126  template <class InputIterator>
127  bmultiset(InputIterator b, InputIterator e,
128  const key_compare &comp = key_compare(),
129  const allocator_type &alloc = allocator_type())
130  : super_type(b, e, comp, alloc) {
131  }
132 
133  bool operator== (self_type const& __y) const {return this->size() == __y.size() && equal (this->begin(), this->end(), __y.begin());}
134  bool operator< (self_type const& __y) const {return lexicographical_compare (this->begin(), this->end(), __y.begin(), __y.end());}
135  bool operator!= (self_type const& __y) const {return !(*this == __y);}
136  bool operator> (self_type const& __y) const {return (__y < *this);}
137  bool operator>= (self_type const& __y) const {return !(*this < __y);}
138  bool operator<= (self_type const& __y) const {return !(__y < *this);}
139 };
140 
141 template <typename K, typename C, int N, typename A>
142 inline void swap(bmultiset<K, C, N, A> &x,
143  bmultiset<K, C, N, A> &y) {
144  x.swap(y);
145 }
146 
148 
149 #endif // UTIL_BTREE_BTREE_SET_H__
150 
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
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
bool operator==(const BentleyAllocator< _Ty > &, const BentleyAllocator< _Other > &)
Definition: BentleyAllocator.h:146

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