1 // Copyright 2013 Google Inc. All Rights Reserved.
2 //
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
6 //
7 // http://www.apache.org/licenses/LICENSE-2.0
8 //
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.
14 //
15 // A btree_set<> implements the STL unique sorted associative container
16 // interface (a.k.a set<>) using a btree. A btree_multiset<> implements the STL
17 // multiple sorted associative container interface (a.k.a multiset<>) using a
18 // btree. See btree.h for details of the btree implementation and caveats.
19
20 #ifndef UTIL_BTREE_BTREE_SET_H__
21 #define UTIL_BTREE_BTREE_SET_H__
22
23 #include <functional>
24 #include <memory>
25 #include <string>
26
27 #include "btree.h"
28 #include "btree_container.h"
29
30 namespace btree
31 {
32
33 // The btree_set class is needed mainly for its constructors.
34 template <typename Key,
35 typename Compare = std::less<Key>,
36 typename Alloc = std::allocator<Key>,
37 int TargetNodeSize = 256>
38 class btree_set : public btree_unique_container <
39 btree<btree_set_params<Key, Compare, Alloc, TargetNodeSize> > >
40 {
41
42 typedef btree_set<Key, Compare, Alloc, TargetNodeSize> self_type;
43 typedef btree_set_params<Key, Compare, Alloc, TargetNodeSize> params_type;
44 typedef btree<params_type> btree_type;
45 typedef btree_unique_container<btree_type> super_type;
46
47 public:
48 typedef typename btree_type::key_compare key_compare;
49 typedef typename btree_type::allocator_type allocator_type;
50
51 public:
52 // Default constructor.
53 btree_set(const key_compare& comp = key_compare(),
54 const allocator_type& alloc = allocator_type())
super_type(comp,alloc)55 : super_type(comp, alloc)
56 {
57 }
58
59 // Copy constructor.
btree_set(const self_type & x)60 btree_set(const self_type& x)
61 : super_type(x)
62 {
63 }
64
65 // Range constructor.
66 template <class InputIterator>
67 btree_set(InputIterator b, InputIterator e,
68 const key_compare& comp = key_compare(),
69 const allocator_type& alloc = allocator_type())
super_type(b,e,comp,alloc)70 : super_type(b, e, comp, alloc)
71 {
72 }
73 };
74
75 template <typename K, typename C, typename A, int N>
swap(btree_set<K,C,A,N> & x,btree_set<K,C,A,N> & y)76 inline void swap(btree_set<K, C, A, N>& x, btree_set<K, C, A, N>& y)
77 {
78 x.swap(y);
79 }
80
81 // The btree_multiset class is needed mainly for its constructors.
82 template <typename Key,
83 typename Compare = std::less<Key>,
84 typename Alloc = std::allocator<Key>,
85 int TargetNodeSize = 256>
86 class btree_multiset : public btree_multi_container <
87 btree<btree_set_params<Key, Compare, Alloc, TargetNodeSize> > >
88 {
89
90 typedef btree_multiset<Key, Compare, Alloc, TargetNodeSize> self_type;
91 typedef btree_set_params<Key, Compare, Alloc, TargetNodeSize> params_type;
92 typedef btree<params_type> btree_type;
93 typedef btree_multi_container<btree_type> super_type;
94
95 public:
96 typedef typename btree_type::key_compare key_compare;
97 typedef typename btree_type::allocator_type allocator_type;
98
99 public:
100 // Default constructor.
101 btree_multiset(const key_compare& comp = key_compare(),
102 const allocator_type& alloc = allocator_type())
super_type(comp,alloc)103 : super_type(comp, alloc)
104 {
105 }
106
107 // Copy constructor.
btree_multiset(const self_type & x)108 btree_multiset(const self_type& x)
109 : super_type(x)
110 {
111 }
112
113 // Range constructor.
114 template <class InputIterator>
115 btree_multiset(InputIterator b, InputIterator e,
116 const key_compare& comp = key_compare(),
117 const allocator_type& alloc = allocator_type())
super_type(b,e,comp,alloc)118 : super_type(b, e, comp, alloc)
119 {
120 }
121 };
122
123 template <typename K, typename C, typename A, int N>
swap(btree_multiset<K,C,A,N> & x,btree_multiset<K,C,A,N> & y)124 inline void swap(btree_multiset<K, C, A, N>& x,
125 btree_multiset<K, C, A, N>& y)
126 {
127 x.swap(y);
128 }
129
130 } // namespace btree
131
132 #endif // UTIL_BTREE_BTREE_SET_H__
133