]>
Commit | Line | Data |
---|---|---|
31f18b77 FG |
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 | // The btree_set class is needed mainly for its constructors. | |
33 | template <typename Key, | |
34 | typename Compare = std::less<Key>, | |
35 | typename Alloc = std::allocator<Key>, | |
36 | int TargetNodeSize = 256> | |
37 | class btree_set : public btree_unique_container< | |
38 | btree<btree_set_params<Key, Compare, Alloc, TargetNodeSize> > > { | |
39 | ||
40 | typedef btree_set<Key, Compare, Alloc, TargetNodeSize> self_type; | |
41 | typedef btree_set_params<Key, Compare, Alloc, TargetNodeSize> params_type; | |
42 | typedef btree<params_type> btree_type; | |
43 | typedef btree_unique_container<btree_type> super_type; | |
44 | ||
45 | public: | |
46 | typedef typename btree_type::key_compare key_compare; | |
47 | typedef typename btree_type::allocator_type allocator_type; | |
48 | ||
49 | public: | |
50 | // Default constructor. | |
51 | btree_set(const key_compare &comp = key_compare(), | |
52 | const allocator_type &alloc = allocator_type()) | |
53 | : super_type(comp, alloc) { | |
54 | } | |
55 | ||
56 | // Copy constructor. | |
57 | btree_set(const self_type &x) | |
58 | : super_type(x) { | |
59 | } | |
60 | ||
61 | // Range constructor. | |
62 | template <class InputIterator> | |
63 | btree_set(InputIterator b, InputIterator e, | |
64 | const key_compare &comp = key_compare(), | |
65 | const allocator_type &alloc = allocator_type()) | |
66 | : super_type(b, e, comp, alloc) { | |
67 | } | |
68 | }; | |
69 | ||
70 | template <typename K, typename C, typename A, int N> | |
71 | inline void swap(btree_set<K, C, A, N> &x, btree_set<K, C, A, N> &y) { | |
72 | x.swap(y); | |
73 | } | |
74 | ||
75 | // The btree_multiset class is needed mainly for its constructors. | |
76 | template <typename Key, | |
77 | typename Compare = std::less<Key>, | |
78 | typename Alloc = std::allocator<Key>, | |
79 | int TargetNodeSize = 256> | |
80 | class btree_multiset : public btree_multi_container< | |
81 | btree<btree_set_params<Key, Compare, Alloc, TargetNodeSize> > > { | |
82 | ||
83 | typedef btree_multiset<Key, Compare, Alloc, TargetNodeSize> self_type; | |
84 | typedef btree_set_params<Key, Compare, Alloc, TargetNodeSize> params_type; | |
85 | typedef btree<params_type> btree_type; | |
86 | typedef btree_multi_container<btree_type> super_type; | |
87 | ||
88 | public: | |
89 | typedef typename btree_type::key_compare key_compare; | |
90 | typedef typename btree_type::allocator_type allocator_type; | |
91 | ||
92 | public: | |
93 | // Default constructor. | |
94 | btree_multiset(const key_compare &comp = key_compare(), | |
95 | const allocator_type &alloc = allocator_type()) | |
96 | : super_type(comp, alloc) { | |
97 | } | |
98 | ||
99 | // Copy constructor. | |
100 | btree_multiset(const self_type &x) | |
101 | : super_type(x) { | |
102 | } | |
103 | ||
104 | // Range constructor. | |
105 | template <class InputIterator> | |
106 | btree_multiset(InputIterator b, InputIterator e, | |
107 | const key_compare &comp = key_compare(), | |
108 | const allocator_type &alloc = allocator_type()) | |
109 | : super_type(b, e, comp, alloc) { | |
110 | } | |
111 | }; | |
112 | ||
113 | template <typename K, typename C, typename A, int N> | |
114 | inline void swap(btree_multiset<K, C, A, N> &x, | |
115 | btree_multiset<K, C, A, N> &y) { | |
116 | x.swap(y); | |
117 | } | |
118 | ||
119 | } // namespace btree | |
120 | ||
121 | #endif // UTIL_BTREE_BTREE_SET_H__ |