Debian Codegraph @

src/perfect-hashing/frozen/set.h

raw
1 /*
2 * Frozen
3 * Copyright 2016 QuarksLab
4 *
5 * Licensed to the Apache Software Foundation (ASF) under one
6 * or more contributor license agreements. See the NOTICE file
7 * distributed with this work for additional information
8 * regarding copyright ownership. The ASF licenses this file
9 * to you under the Apache License, Version 2.0 (the
10 * "License"); you may not use this file except in compliance
11 * with the License. You may obtain a copy of the License at
12 *
13 * http://www.apache.org/licenses/LICENSE-2.0
14 *
15 * Unless required by applicable law or agreed to in writing,
16 * software distributed under the License is distributed on an
17 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
18 * KIND, either express or implied. See the License for the
19 * specific language governing permissions and limitations
20 * under the License.
21 */
22
23 #ifndef FROZEN_SET_H
24 #define FROZEN_SET_H
25
26 #include "frozen/bits/algorithms.h"
27 #include "frozen/bits/basic_types.h"
28 #include "frozen/bits/constexpr_assert.h"
29 #include "frozen/bits/version.h"
30
31 #include <utility>
32
33 namespace frozen {
34
35 template <class Key, std::size_t N, class Compare = std::less<Key>> class set {
36 using container_type = bits::carray<Key, N>;
37 Compare less_than_;
38 container_type keys_;
39
40 public:
41 /* container typedefs*/
42 using key_type = Key;
43 using value_type = Key;
44 using size_type = typename container_type::size_type;
45 using difference_type = typename container_type::size_type;
46 using key_compare = Compare;
47 using value_compare = Compare;
48 using reference = typename container_type::const_reference;
49 using const_reference = reference;
50 using pointer = typename container_type::const_pointer;
51 using const_pointer = pointer;
52 using iterator = typename container_type::const_iterator;
53 using reverse_iterator = typename container_type::const_reverse_iterator;
54 using const_iterator = iterator;
55 using const_reverse_iterator = reverse_iterator;
56
57 public:
58 /* constructors */
59 constexpr set(const set &other) = default;
60
61 constexpr set(container_type keys, Compare const &comp) : less_than_{comp}, keys_(bits::quicksort(keys, less_than_)) {}
62
63 explicit constexpr set(container_type keys) : set{keys, Compare{}} {}
64
65 constexpr set(std::initializer_list<Key> keys, Compare const &comp) : set{container_type{keys}, comp} {
66 constexpr_assert(keys.size() == N, "Inconsistent initializer_list size and type size argument");
67 }
68
69 constexpr set(std::initializer_list<Key> keys) : set{keys, Compare{}} {}
70
71 /* capacity */
72 constexpr bool
73 empty() const {
74 return !N;
75 }
76 constexpr size_type
77 size() const {
78 return N;
79 }
80 constexpr size_type
81 max_size() const {
82 return N;
83 }
84
85 /* lookup */
86 constexpr std::size_t
87 count(Key const &key) const {
88 return bits::binary_search<N>(keys_.begin(), key, less_than_);
89 }
90
91 constexpr const_iterator
92 find(Key const &key) const {
93 const_iterator where = lower_bound(key);
94 if ((where != end()) && !less_than_(key, *where)) return where;
95 else return end();
96 }
97
98 constexpr std::pair<const_iterator, const_iterator>
99 equal_range(Key const &key) const {
100 auto const lower = lower_bound(key);
101 if (lower == end()) return {lower, lower};
102 else return {lower, lower + 1};
103 }
104
105 constexpr const_iterator
106 lower_bound(Key const &key) const {
107 auto const where = bits::lower_bound<N>(keys_.begin(), key, less_than_);
108 if ((where != end()) && !less_than_(key, *where)) return where;
109 else return end();
110 }
111
112 constexpr const_iterator
113 upper_bound(Key const &key) const {
114 auto const where = bits::lower_bound<N>(keys_.begin(), key, less_than_);
115 if ((where != end()) && !less_than_(key, *where)) return where + 1;
116 else return end();
117 }
118
119 /* observers */
120 constexpr key_compare
121 key_comp() const {
122 return less_than_;
123 }
124 constexpr key_compare
125 value_comp() const {
126 return less_than_;
127 }
128
129 /* iterators */
130 constexpr const_iterator
131 begin() const {
132 return keys_.begin();
133 }
134 constexpr const_iterator
135 cbegin() const {
136 return keys_.cbegin();
137 }
138 constexpr const_iterator
139 end() const {
140 return keys_.end();
141 }
142 constexpr const_iterator
143 cend() const {
144 return keys_.cend();
145 }
146
147 constexpr const_reverse_iterator
148 rbegin() const {
149 return keys_.rbegin();
150 }
151 constexpr const_reverse_iterator
152 crbegin() const {
153 return keys_.crbegin();
154 }
155 constexpr const_reverse_iterator
156 rend() const {
157 return keys_.rend();
158 }
159 constexpr const_reverse_iterator
160 crend() const {
161 return keys_.crend();
162 }
163
164 /* comparison */
165 constexpr bool
166 operator==(set const &rhs) const {
167 return bits::equal(begin(), end(), rhs.begin());
168 }
169 constexpr bool
170 operator!=(set const &rhs) const {
171 return !(*this == rhs);
172 }
173 constexpr bool
174 operator<(set const &rhs) const {
175 return bits::lexicographical_compare(begin(), end(), rhs.begin(), rhs.end());
176 }
177 constexpr bool
178 operator<=(set const &rhs) const {
179 return (*this < rhs) || (*this == rhs);
180 }
181 constexpr bool
182 operator>(set const &rhs) const {
183 return bits::lexicographical_compare(rhs.begin(), rhs.end(), begin(), end());
184 }
185 constexpr bool
186 operator>=(set const &rhs) const {
187 return (*this > rhs) || (*this == rhs);
188 }
189 };
190
191 template <class Key, class Compare> class set<Key, 0, Compare> {
192 using container_type = bits::carray<Key, 0>; // just for the type definitions
193 Compare less_than_;
194
195 public:
196 /* container typedefs*/
197 using key_type = Key;
198 using value_type = Key;
199 using size_type = typename container_type::size_type;
200 using difference_type = typename container_type::size_type;
201 using key_compare = Compare;
202 using value_compare = Compare;
203 using reference = typename container_type::const_reference;
204 using const_reference = reference;
205 using pointer = typename container_type::const_pointer;
206 using const_pointer = pointer;
207 using iterator = pointer;
208 using reverse_iterator = pointer;
209 using const_iterator = const_pointer;
210 using const_reverse_iterator = const_pointer;
211
212 public:
213 /* constructors */
214 constexpr set(const set &other) = default;
215 constexpr set(bits::carray<Key, 0>, Compare const &) {}
216 explicit constexpr set(bits::carray<Key, 0>) {}
217
218 constexpr set(std::initializer_list<Key>, Compare const &comp) : less_than_{comp} {}
219 constexpr set(std::initializer_list<Key> keys) : set{keys, Compare{}} {}
220
221 /* capacity */
222 constexpr bool
223 empty() const {
224 return true;
225 }
226 constexpr size_type
227 size() const {
228 return 0;
229 }
230 constexpr size_type
231 max_size() const {
232 return 0;
233 }
234
235 /* lookup */
236 constexpr std::size_t
237 count(Key const &) const {
238 return 0;
239 }
240
241 constexpr const_iterator
242 find(Key const &) const {
243 return end();
244 }
245
246 constexpr std::pair<const_iterator, const_iterator>
247 equal_range(Key const &) const {
248 return {end(), end()};
249 }
250
251 constexpr const_iterator
252 lower_bound(Key const &) const {
253 return end();
254 }
255
256 constexpr const_iterator
257 upper_bound(Key const &) const {
258 return end();
259 }
260
261 /* observers */
262 constexpr key_compare
263 key_comp() const {
264 return less_than_;
265 }
266 constexpr key_compare
267 value_comp() const {
268 return less_than_;
269 }
270
271 /* iterators */
272 constexpr const_iterator
273 begin() const {
274 return nullptr;
275 }
276 constexpr const_iterator
277 cbegin() const {
278 return nullptr;
279 }
280 constexpr const_iterator
281 end() const {
282 return nullptr;
283 }
284 constexpr const_iterator
285 cend() const {
286 return nullptr;
287 }
288
289 constexpr const_reverse_iterator
290 rbegin() const {
291 return nullptr;
292 }
293 constexpr const_reverse_iterator
294 crbegin() const {
295 return nullptr;
296 }
297 constexpr const_reverse_iterator
298 rend() const {
299 return nullptr;
300 }
301 constexpr const_reverse_iterator
302 crend() const {
303 return nullptr;
304 }
305 };
306
307 template <typename T>
308 constexpr auto
309 make_set(bits::ignored_arg = {} /* for consistency with the initializer below for N = 0*/) {
310 return set<T, 0>{};
311 }
312
313 template <typename T, std::size_t N>
314 constexpr auto
315 make_set(const T (&args)[N]) {
316 return set<T, N>(args);
317 }
318
319 template <typename T, std::size_t N>
320 constexpr auto
321 make_set(std::array<T, N> const &args) {
322 return set<T, N>(args);
323 }
324
325
326 } // namespace frozen
327
328 #endif