Debian Codegraph @

src/perfect-hashing/frozen/map.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_LETITGO_MAP_H
24 #define FROZEN_LETITGO_MAP_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/exceptions.h"
30 #include "frozen/bits/version.h"
31
32 #include <utility>
33
34 namespace frozen {
35
36 namespace impl {
37
38 template <class Comparator> class CompareKey {
39 Comparator const comparator_;
40
41 public:
42 constexpr CompareKey(Comparator const &comparator) : comparator_(comparator) {}
43
44 template <class Key, class Value>
45 constexpr int
46 operator()(std::pair<Key, Value> const &self, std::pair<Key, Value> const &other) const {
47 return comparator_(std::get<0>(self), std::get<0>(other));
48 }
49
50 template <class Key, class Value>
51 constexpr int
52 operator()(Key const &self_key, std::pair<Key, Value> const &other) const {
53 return comparator_(self_key, std::get<0>(other));
54 }
55
56 template <class Key, class Value>
57 constexpr int
58 operator()(std::pair<Key, Value> const &self, Key const &other_key) const {
59 return comparator_(std::get<0>(self), other_key);
60 }
61
62 template <class Key>
63 constexpr int
64 operator()(Key const &self_key, Key const &other_key) const {
65 return comparator_(self_key, other_key);
66 }
67 };
68
69 } // namespace impl
70
71 template <class Key, class Value, std::size_t N, class Compare = std::less<Key>> class map {
72 using container_type = bits::carray<std::pair<Key, Value>, N>;
73 impl::CompareKey<Compare> less_than_;
74 container_type items_;
75
76 public:
77 using key_type = Key;
78 using mapped_type = Value;
79 using value_type = typename container_type::value_type;
80 using size_type = typename container_type::size_type;
81 using difference_type = typename container_type::difference_type;
82 using key_compare = decltype(less_than_);
83 using reference = typename container_type::reference;
84 using const_reference = typename container_type::const_reference;
85 using pointer = typename container_type::pointer;
86 using const_pointer = typename container_type::const_pointer;
87 using iterator = typename container_type::iterator;
88 using const_iterator = typename container_type::const_iterator;
89 using reverse_iterator = typename container_type::reverse_iterator;
90 using const_reverse_iterator = typename container_type::const_reverse_iterator;
91
92 public:
93 /* constructors */
94 constexpr map(container_type items, Compare const &compare) : less_than_{compare}, items_{bits::quicksort(items, less_than_)} {}
95
96 explicit constexpr map(container_type items) : map{items, Compare{}} {}
97
98 constexpr map(std::initializer_list<value_type> items, Compare const &compare) : map{container_type{items}, compare} {
99 constexpr_assert(items.size() == N, "Inconsistent initializer_list size and type size argument");
100 }
101
102 constexpr map(std::initializer_list<value_type> items) : map{items, Compare{}} {}
103
104 /* element access */
105 constexpr Value const &
106 at(Key const &key) const {
107 return at_impl(*this, key);
108 }
109 constexpr Value &
110 at(Key const &key) {
111 return at_impl(*this, key);
112 }
113
114 /* iterators */
115 constexpr iterator
116 begin() {
117 return items_.begin();
118 }
119 constexpr const_iterator
120 begin() const {
121 return items_.begin();
122 }
123 constexpr const_iterator
124 cbegin() const {
125 return items_.cbegin();
126 }
127 constexpr iterator
128 end() {
129 return items_.end();
130 }
131 constexpr const_iterator
132 end() const {
133 return items_.end();
134 }
135 constexpr const_iterator
136 cend() const {
137 return items_.cend();
138 }
139
140 constexpr reverse_iterator
141 rbegin() {
142 return items_.rbegin();
143 }
144 constexpr const_reverse_iterator
145 rbegin() const {
146 return items_.rbegin();
147 }
148 constexpr const_reverse_iterator
149 crbegin() const {
150 return items_.crbegin();
151 }
152 constexpr reverse_iterator
153 rend() {
154 return items_.rend();
155 }
156 constexpr const_reverse_iterator
157 rend() const {
158 return items_.rend();
159 }
160 constexpr const_reverse_iterator
161 crend() const {
162 return items_.crend();
163 }
164
165 /* capacity */
166 constexpr bool
167 empty() const {
168 return !N;
169 }
170 constexpr size_type
171 size() const {
172 return N;
173 }
174 constexpr size_type
175 max_size() const {
176 return N;
177 }
178
179 /* lookup */
180
181 constexpr std::size_t
182 count(Key const &key) const {
183 return bits::binary_search<N>(items_.begin(), key, less_than_);
184 }
185
186 constexpr const_iterator
187 find(Key const &key) const {
188 return find_impl(*this, key);
189 }
190 constexpr iterator
191 find(Key const &key) {
192 return find_impl(*this, key);
193 }
194
195 constexpr std::pair<const_iterator, const_iterator>
196 equal_range(Key const &key) const {
197 return equal_range_impl(*this, key);
198 }
199 constexpr std::pair<iterator, iterator>
200 equal_range(Key const &key) {
201 return equal_range_impl(*this, key);
202 }
203
204 constexpr const_iterator
205 lower_bound(Key const &key) const {
206 return lower_bound_impl(*this, key);
207 }
208 constexpr iterator
209 lower_bound(Key const &key) {
210 return lower_bound_impl(*this, key);
211 }
212
213 constexpr const_iterator
214 upper_bound(Key const &key) const {
215 return upper_bound_impl(*this, key);
216 }
217 constexpr iterator
218 upper_bound(Key const &key) {
219 return upper_bound_impl(*this, key);
220 }
221
222 /* observers */
223 constexpr key_compare
224 key_comp() const {
225 return less_than_;
226 }
227 constexpr key_compare
228 value_comp() const {
229 return less_than_;
230 }
231
232 private:
233 template <class This>
234 static inline constexpr auto &
235 at_impl(This &&self, Key const &key) {
236 auto where = self.lower_bound(key);
237 if (where != self.end()) return where->second;
238 else FROZEN_THROW_OR_ABORT(std::out_of_range("unknown key"));
239 }
240
241 template <class This>
242 static inline constexpr auto
243 find_impl(This &&self, Key const &key) {
244 auto where = self.lower_bound(key);
245 if ((where != self.end()) && !self.less_than_(key, *where)) return where;
246 else return self.end();
247 }
248
249 template <class This>
250 static inline constexpr auto
251 equal_range_impl(This &&self, Key const &key) {
252 auto lower = self.lower_bound(key);
253 using lower_t = decltype(lower);
254 if (lower == self.end()) return std::pair<lower_t, lower_t>{lower, lower};
255 else return std::pair<lower_t, lower_t>{lower, lower + 1};
256 }
257
258 template <class This>
259 static inline constexpr auto
260 lower_bound_impl(This &&self, Key const &key) -> decltype(self.end()) {
261 auto where = bits::lower_bound<N>(self.items_.begin(), key, self.less_than_);
262 if ((where != self.end()) && !self.less_than_(key, *where)) return where;
263 else return self.end();
264 }
265
266 template <class This>
267 static inline constexpr auto
268 upper_bound_impl(This &&self, Key const &key) -> decltype(self.end()) {
269 auto where = bits::lower_bound<N>(self.items_.begin(), key, self.less_than_);
270 if ((where != self.end()) && !self.less_than_(key, *where)) return where + 1;
271 else return self.end();
272 }
273 };
274
275 template <class Key, class Value, class Compare> class map<Key, Value, 0, Compare> {
276 using container_type = bits::carray<std::pair<Key, Value>, 0>;
277 impl::CompareKey<Compare> less_than_;
278
279 public:
280 using key_type = Key;
281 using mapped_type = Value;
282 using value_type = typename container_type::value_type;
283 using size_type = typename container_type::size_type;
284 using difference_type = typename container_type::difference_type;
285 using key_compare = decltype(less_than_);
286 using reference = typename container_type::reference;
287 using const_reference = typename container_type::const_reference;
288 using pointer = typename container_type::pointer;
289 using const_pointer = typename container_type::const_pointer;
290 using iterator = pointer;
291 using const_iterator = const_pointer;
292 using reverse_iterator = pointer;
293 using const_reverse_iterator = const_pointer;
294
295 public:
296 /* constructors */
297 constexpr map(const map &other) = default;
298 constexpr map(std::initializer_list<value_type>, Compare const &compare) : less_than_{compare} {}
299 constexpr map(std::initializer_list<value_type> items) : map{items, Compare{}} {}
300
301 /* element access */
302 constexpr mapped_type
303 at(Key const &) const {
304 FROZEN_THROW_OR_ABORT(std::out_of_range("invalid key"));
305 }
306 constexpr mapped_type
307 at(Key const &) {
308 FROZEN_THROW_OR_ABORT(std::out_of_range("invalid key"));
309 }
310
311 /* iterators */
312 constexpr iterator
313 begin() {
314 return nullptr;
315 }
316 constexpr const_iterator
317 begin() const {
318 return nullptr;
319 }
320 constexpr const_iterator
321 cbegin() const {
322 return nullptr;
323 }
324 constexpr iterator
325 end() {
326 return nullptr;
327 }
328 constexpr const_iterator
329 end() const {
330 return nullptr;
331 }
332 constexpr const_iterator
333 cend() const {
334 return nullptr;
335 }
336
337 constexpr reverse_iterator
338 rbegin() {
339 return nullptr;
340 }
341 constexpr const_reverse_iterator
342 rbegin() const {
343 return nullptr;
344 }
345 constexpr const_reverse_iterator
346 crbegin() const {
347 return nullptr;
348 }
349 constexpr reverse_iterator
350 rend() {
351 return nullptr;
352 }
353 constexpr const_reverse_iterator
354 rend() const {
355 return nullptr;
356 }
357 constexpr const_reverse_iterator
358 crend() const {
359 return nullptr;
360 }
361
362 /* capacity */
363 constexpr bool
364 empty() const {
365 return true;
366 }
367 constexpr size_type
368 size() const {
369 return 0;
370 }
371 constexpr size_type
372 max_size() const {
373 return 0;
374 }
375
376 /* lookup */
377
378 constexpr std::size_t
379 count(Key const &) const {
380 return 0;
381 }
382
383 constexpr const_iterator
384 find(Key const &) const {
385 return end();
386 }
387 constexpr iterator
388 find(Key const &) {
389 return end();
390 }
391
392 constexpr std::pair<const_iterator, const_iterator>
393 equal_range(Key const &) const {
394 return {end(), end()};
395 }
396 constexpr std::pair<iterator, iterator>
397 equal_range(Key const &) {
398 return {end(), end()};
399 }
400
401 constexpr const_iterator
402 lower_bound(Key const &) const {
403 return end();
404 }
405 constexpr iterator
406 lower_bound(Key const &) {
407 return end();
408 }
409
410 constexpr const_iterator
411 upper_bound(Key const &) const {
412 return end();
413 }
414 constexpr iterator
415 upper_bound(Key const &) {
416 return end();
417 }
418
419 /* observers */
420 constexpr key_compare
421 key_comp() const {
422 return less_than_;
423 }
424 constexpr key_compare
425 value_comp() const {
426 return less_than_;
427 }
428 };
429
430 template <typename T, typename U>
431 constexpr auto
432 make_map(bits::ignored_arg = {} /* for consistency with the initializer below for N = 0*/) {
433 return map<T, U, 0>{};
434 }
435
436 template <typename T, typename U, std::size_t N>
437 constexpr auto
438 make_map(std::pair<T, U> const (&items)[N]) {
439 return map<T, U, N>{items};
440 }
441
442 template <typename T, typename U, std::size_t N>
443 constexpr auto
444 make_map(std::array<std::pair<T, U>, N> const &items) {
445 return map<T, U, N>{items};
446 }
447
448 } // namespace frozen
449
450 #endif