1/*!
2@file
3Defines `boost::hana::map`.
4
5Copyright Louis Dionne 2013-2022
6Distributed under the Boost Software License, Version 1.0.
7(See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
8 */
9
10#ifndef BOOST_HANA_MAP_HPP
11#define BOOST_HANA_MAP_HPP
12
13#include <boost/hana/fwd/map.hpp>
14
15#include <boost/hana/all_of.hpp>
16#include <boost/hana/basic_tuple.hpp>
17#include <boost/hana/bool.hpp>
18#include <boost/hana/concept/comparable.hpp>
19#include <boost/hana/concept/constant.hpp>
20#include <boost/hana/concept/product.hpp>
21#include <boost/hana/config.hpp>
22#include <boost/hana/contains.hpp>
23#include <boost/hana/core/is_a.hpp>
24#include <boost/hana/core/make.hpp>
25#include <boost/hana/core/to.hpp>
26#include <boost/hana/detail/decay.hpp>
27#include <boost/hana/detail/fast_and.hpp>
28#include <boost/hana/detail/has_duplicates.hpp>
29#include <boost/hana/detail/hash_table.hpp>
30#include <boost/hana/detail/intrinsics.hpp>
31#include <boost/hana/detail/operators/adl.hpp>
32#include <boost/hana/detail/operators/comparable.hpp>
33#include <boost/hana/detail/operators/searchable.hpp>
34#include <boost/hana/equal.hpp>
35#include <boost/hana/find.hpp>
36#include <boost/hana/first.hpp>
37#include <boost/hana/fold_left.hpp>
38#include <boost/hana/functional/demux.hpp>
39#include <boost/hana/functional/on.hpp>
40#include <boost/hana/functional/partial.hpp>
41#include <boost/hana/fwd/any_of.hpp>
42#include <boost/hana/fwd/at_key.hpp>
43#include <boost/hana/fwd/difference.hpp>
44#include <boost/hana/fwd/erase_key.hpp>
45#include <boost/hana/fwd/intersection.hpp>
46#include <boost/hana/fwd/is_subset.hpp>
47#include <boost/hana/fwd/keys.hpp>
48#include <boost/hana/fwd/union.hpp>
49#include <boost/hana/insert.hpp>
50#include <boost/hana/integral_constant.hpp>
51#include <boost/hana/keys.hpp>
52#include <boost/hana/length.hpp>
53#include <boost/hana/optional.hpp>
54#include <boost/hana/remove_if.hpp>
55#include <boost/hana/second.hpp>
56#include <boost/hana/unpack.hpp>
57#include <boost/hana/value.hpp>
58
59
60#include <cstddef>
61#include <type_traits>
62#include <utility>
63
64
65namespace boost { namespace hana {
66 //////////////////////////////////////////////////////////////////////////
67 // operators
68 //////////////////////////////////////////////////////////////////////////
69 namespace detail {
70 template <>
71 struct comparable_operators<map_tag> {
72 static constexpr bool value = true;
73 };
74 }
75
76 //////////////////////////////////////////////////////////////////////////
77 // map
78 //////////////////////////////////////////////////////////////////////////
79 //! @cond
80 namespace detail {
81 template <typename ...>
82 struct storage_is_default_constructible;
83 template <typename ...T>
84 struct storage_is_default_constructible<hana::basic_tuple<T...>> {
85 static constexpr bool value = detail::fast_and<
86 BOOST_HANA_TT_IS_CONSTRUCTIBLE(T)...
87 >::value;
88 };
89
90 template <typename ...>
91 struct storage_is_copy_constructible;
92 template <typename ...T>
93 struct storage_is_copy_constructible<hana::basic_tuple<T...>> {
94 static constexpr bool value = detail::fast_and<
95 BOOST_HANA_TT_IS_CONSTRUCTIBLE(T, T const&)...
96 >::value;
97 };
98
99 template <typename ...>
100 struct storage_is_move_constructible;
101 template <typename ...T>
102 struct storage_is_move_constructible<hana::basic_tuple<T...>> {
103 static constexpr bool value = detail::fast_and<
104 BOOST_HANA_TT_IS_CONSTRUCTIBLE(T, T&&)...
105 >::value;
106 };
107
108 template <typename ...>
109 struct storage_is_copy_assignable;
110 template <typename ...T>
111 struct storage_is_copy_assignable<hana::basic_tuple<T...>> {
112 static constexpr bool value = detail::fast_and<
113 BOOST_HANA_TT_IS_ASSIGNABLE(T, T const&)...
114 >::value;
115 };
116
117 template <typename ...>
118 struct storage_is_move_assignable;
119 template <typename ...T>
120 struct storage_is_move_assignable<hana::basic_tuple<T...>> {
121 static constexpr bool value = detail::fast_and<
122 BOOST_HANA_TT_IS_ASSIGNABLE(T, T&&)...
123 >::value;
124 };
125
126 template <typename HashTable, typename Storage>
127 struct map_impl final
128 : detail::searchable_operators<map_impl<HashTable, Storage>>
129 , detail::operators::adl<map_impl<HashTable, Storage>>
130 {
131 using hash_table_type = HashTable;
132 using storage_type = Storage;
133
134 Storage storage;
135
136 using hana_tag = map_tag;
137
138 template <typename ...P, typename = typename std::enable_if<
139 std::is_same<
140 Storage,
141 hana::basic_tuple<typename detail::decay<P>::type...>
142 >::value
143 >::type>
144 explicit constexpr map_impl(P&& ...pairs)
145 : storage{static_cast<P&&>(pairs)...}
146 { }
147
148 explicit constexpr map_impl(Storage&& xs)
149 : storage(static_cast<Storage&&>(xs))
150 { }
151
152 template <typename ...Dummy, typename = typename std::enable_if<
153 detail::storage_is_default_constructible<Storage, Dummy...>::value
154 >::type>
155 constexpr map_impl()
156 : storage()
157 { }
158
159 template <typename ...Dummy, typename = typename std::enable_if<
160 detail::storage_is_copy_constructible<Storage, Dummy...>::value
161 >::type>
162 constexpr map_impl(map_impl const& other)
163 : storage(other.storage)
164 { }
165
166 template <typename ...Dummy, typename = typename std::enable_if<
167 detail::storage_is_move_constructible<Storage, Dummy...>::value
168 >::type>
169 constexpr map_impl(map_impl&& other)
170 : storage(static_cast<Storage&&>(other.storage))
171 { }
172
173 template <typename ...Dummy, typename = typename std::enable_if<
174 detail::storage_is_move_assignable<Storage, Dummy...>::value
175 >::type>
176 constexpr map_impl& operator=(map_impl&& other) {
177 storage = static_cast<Storage&&>(other.storage);
178 return *this;
179 }
180
181 template <typename ...Dummy, typename = typename std::enable_if<
182 detail::storage_is_copy_assignable<Storage, Dummy...>::value
183 >::type>
184 constexpr map_impl& operator=(map_impl const& other) {
185 storage = other.storage;
186 return *this;
187 }
188
189 // Prevent the compiler from defining the default copy and move
190 // constructors, which interfere with the SFINAE above.
191 ~map_impl() = default;
192 };
193 //! @endcond
194
195 template <typename Storage>
196 struct KeyAtIndex {
197 template <std::size_t i>
198 using apply = decltype(hana::first(hana::at_c<i>(std::declval<Storage>())));
199 };
200
201 template <typename ...Pairs>
202 struct make_map_type {
203 using Storage = hana::basic_tuple<Pairs...>;
204 using HashTable = typename detail::make_hash_table<
205 detail::KeyAtIndex<Storage>::template apply, sizeof...(Pairs)
206 >::type;
207 using type = detail::map_impl<HashTable, Storage>;
208 };
209 }
210
211 //////////////////////////////////////////////////////////////////////////
212 // make<map_tag>
213 //////////////////////////////////////////////////////////////////////////
214 template <>
215 struct make_impl<map_tag> {
216 template <typename ...Pairs>
217 static constexpr auto apply(Pairs&& ...pairs) {
218#if defined(BOOST_HANA_CONFIG_ENABLE_DEBUG_MODE)
219 static_assert(detail::fast_and<hana::Product<Pairs>::value...>::value,
220 "hana::make_map(pairs...) requires all the 'pairs' to be Products");
221
222 static_assert(detail::fast_and<
223 hana::Comparable<decltype(hana::first(pairs))>::value...
224 >::value,
225 "hana::make_map(pairs...) requires all the keys to be Comparable");
226
227 static_assert(detail::fast_and<
228 hana::Constant<
229 decltype(hana::equal(hana::first(pairs), hana::first(pairs)))
230 >::value...
231 >::value,
232 "hana::make_map(pairs...) requires all the keys to be "
233 "Comparable at compile-time");
234
235 //! @todo
236 //! This can be implemented more efficiently by doing the check
237 //! inside each bucket instead.
238 static_assert(!detail::has_duplicates<decltype(hana::first(pairs))...>::value,
239 "hana::make_map({keys, values}...) requires all the keys to be unique");
240
241 static_assert(!detail::has_duplicates<decltype(hana::hash(hana::first(pairs)))...>::value,
242 "hana::make_map({keys, values}...) requires all the keys to have different hashes");
243#endif
244
245 using Map = typename detail::make_map_type<typename detail::decay<Pairs>::type...>::type;
246 return Map{hana::make_basic_tuple(static_cast<Pairs&&>(pairs)...)};
247 }
248 };
249
250 //////////////////////////////////////////////////////////////////////////
251 // keys
252 //////////////////////////////////////////////////////////////////////////
253 template <>
254 struct keys_impl<map_tag> {
255 template <typename Map>
256 static constexpr decltype(auto) apply(Map&& map) {
257 return hana::transform(static_cast<Map&&>(map).storage, hana::first);
258 }
259 };
260
261 //////////////////////////////////////////////////////////////////////////
262 // values
263 //////////////////////////////////////////////////////////////////////////
264 //! @cond
265 template <typename Map>
266 constexpr decltype(auto) values_t::operator()(Map&& map) const {
267 return hana::transform(static_cast<Map&&>(map).storage, hana::second);
268 }
269 //! @endcond
270
271 //////////////////////////////////////////////////////////////////////////
272 // insert
273 //////////////////////////////////////////////////////////////////////////
274 template <>
275 struct insert_impl<map_tag> {
276 template <typename Map, typename Pair>
277 static constexpr auto helper(Map&& map, Pair&& pair, ...) {
278 using RawMap = typename std::remove_reference<Map>::type;
279 using HashTable = typename RawMap::hash_table_type;
280 using NewHashTable = typename detail::bucket_insert<
281 HashTable,
282 decltype(hana::first(pair)),
283 decltype(hana::length(map.storage))::value
284 >::type;
285
286 using NewStorage = decltype(
287 hana::append(static_cast<Map&&>(map).storage, static_cast<Pair&&>(pair))
288 );
289 return detail::map_impl<NewHashTable, NewStorage>(
290 hana::append(static_cast<Map&&>(map).storage, static_cast<Pair&&>(pair))
291 );
292 }
293
294 template <typename Map, typename Pair, std::size_t i>
295 static constexpr auto
296 helper(Map&& map, Pair&&,
297 hana::optional<std::integral_constant<std::size_t, i>>)
298 {
299 return static_cast<Map&&>(map);
300 }
301
302 //! @todo
303 //! Here, we insert only if the key is not already in the map.
304 //! This should be handled by `bucket_insert`, and that would also
305 //! be more efficient.
306 template <typename Map, typename Pair>
307 static constexpr auto apply(Map&& map, Pair&& pair) {
308 using RawMap = typename std::remove_reference<Map>::type;
309 using Storage = typename RawMap::storage_type;
310 using HashTable = typename RawMap::hash_table_type;
311 using Key = decltype(hana::first(pair));
312 using MaybeIndex = typename detail::find_index<
313 HashTable, Key, detail::KeyAtIndex<Storage>::template apply
314 >::type;
315 return helper(static_cast<Map&&>(map), static_cast<Pair&&>(pair), MaybeIndex{});
316 }
317 };
318
319 //////////////////////////////////////////////////////////////////////////
320 // erase_key
321 //////////////////////////////////////////////////////////////////////////
322 template <>
323 struct erase_key_impl<map_tag> {
324 //! @todo
325 //! We could implement some kind of `bucket_erase` metafunction
326 //! that would be much more efficient than this.
327 template <typename Map, typename Key>
328 static constexpr auto
329 erase_key_helper(Map&& map, Key const&, hana::false_) {
330 return static_cast<Map&&>(map);
331 }
332
333 template <typename Map, typename Key>
334 static constexpr auto
335 erase_key_helper(Map&& map, Key const& key, hana::true_) {
336 return hana::unpack(
337 hana::remove_if(static_cast<Map&&>(map).storage,
338 hana::on(hana::equal.to(key), hana::first)),
339 hana::make_map
340 );
341 }
342
343 template <typename Map, typename Key>
344 static constexpr auto apply_impl(Map&& map, Key const& key, hana::false_) {
345 return erase_key_helper(static_cast<Map&&>(map), key,
346 hana::contains(map, key));
347 }
348
349 template <typename Map, typename Key>
350 static constexpr auto apply_impl(Map&& map, Key const&, hana::true_) {
351 return static_cast<Map&&>(map);
352 }
353
354 template <typename Map, typename Key>
355 static constexpr auto apply(Map&& map, Key const& key) {
356 constexpr bool is_empty = decltype(hana::length(map))::value == 0;
357 return apply_impl(static_cast<Map&&>(map), key, hana::bool_<is_empty>{});
358 }
359 };
360
361 //////////////////////////////////////////////////////////////////////////
362 // Comparable
363 //////////////////////////////////////////////////////////////////////////
364 template <>
365 struct equal_impl<map_tag, map_tag> {
366 template <typename M1, typename M2>
367 static constexpr auto equal_helper(M1 const&, M2 const&, hana::false_) {
368 return hana::false_c;
369 }
370
371 template <typename M1, typename M2>
372 static constexpr auto equal_helper(M1 const& m1, M2 const& m2, hana::true_) {
373 return hana::all_of(hana::keys(m1), hana::demux(equal)(
374 hana::partial(hana::find, m1),
375 hana::partial(hana::find, m2)
376 ));
377 }
378
379 template <typename M1, typename M2>
380 static constexpr auto apply(M1 const& m1, M2 const& m2) {
381 return equal_impl::equal_helper(m1, m2, hana::bool_c<
382 decltype(hana::length(m1.storage))::value ==
383 decltype(hana::length(m2.storage))::value
384 >);
385 }
386 };
387
388 //////////////////////////////////////////////////////////////////////////
389 // Searchable
390 //////////////////////////////////////////////////////////////////////////
391 template <>
392 struct find_impl<map_tag> {
393 template <typename Map>
394 static constexpr auto find_helper(Map&&, ...) {
395 return hana::nothing;
396 }
397
398 template <typename Map, std::size_t i>
399 static constexpr auto
400 find_helper(Map&& map, hana::optional<std::integral_constant<std::size_t, i>>) {
401 return hana::just(hana::second(hana::at_c<i>(static_cast<Map&&>(map).storage)));
402 }
403
404 template <typename Map, typename Key>
405 static constexpr auto apply(Map&& map, Key const&) {
406 using RawMap = typename std::remove_reference<Map>::type;
407 using Storage = typename RawMap::storage_type;
408 using HashTable = typename RawMap::hash_table_type;
409 using MaybeIndex = typename detail::find_index<
410 HashTable, Key, detail::KeyAtIndex<Storage>::template apply
411 >::type;
412 return find_helper(static_cast<Map&&>(map), MaybeIndex{});
413 }
414 };
415
416 template <>
417 struct find_if_impl<map_tag> {
418 template <typename M, typename Pred>
419 static constexpr auto apply(M&& map, Pred&& pred) {
420 return hana::transform(
421 hana::find_if(static_cast<M&&>(map).storage,
422 hana::compose(static_cast<Pred&&>(pred), hana::first)),
423 hana::second
424 );
425 }
426 };
427
428 template <>
429 struct contains_impl<map_tag> {
430 template <typename Map, typename Key>
431 static constexpr auto apply(Map const&, Key const&) {
432 using RawMap = typename std::remove_reference<Map>::type;
433 using HashTable = typename RawMap::hash_table_type;
434 using Storage = typename RawMap::storage_type;
435 using MaybeIndex = typename detail::find_index<
436 HashTable, Key, detail::KeyAtIndex<Storage>::template apply
437 >::type;
438 return hana::bool_<!decltype(hana::is_nothing(MaybeIndex{}))::value>{};
439 }
440 };
441
442 template <>
443 struct any_of_impl<map_tag> {
444 template <typename M, typename Pred>
445 static constexpr auto apply(M const& map, Pred const& pred)
446 { return hana::any_of(hana::keys(map), pred); }
447 };
448
449 template <>
450 struct is_subset_impl<map_tag, map_tag> {
451 template <typename Ys>
452 struct all_contained {
453 Ys const& ys;
454 template <typename ...X>
455 constexpr auto operator()(X const& ...x) const {
456 return hana::bool_c<detail::fast_and<
457 hana::value<decltype(hana::contains(ys, x))>()...
458 >::value>;
459 }
460 };
461
462 template <typename Xs, typename Ys>
463 static constexpr auto apply(Xs const& xs, Ys const& ys) {
464 auto ys_keys = hana::keys(ys);
465 return hana::unpack(hana::keys(xs), all_contained<decltype(ys_keys)>{ys_keys});
466 }
467 };
468
469 template <>
470 struct at_key_impl<map_tag> {
471 template <typename Map, typename Key>
472 static constexpr decltype(auto) apply(Map&& map, Key const&) {
473 using RawMap = typename std::remove_reference<Map>::type;
474 using HashTable = typename RawMap::hash_table_type;
475 using Storage = typename RawMap::storage_type;
476 using MaybeIndex = typename detail::find_index<
477 HashTable, Key, detail::KeyAtIndex<Storage>::template apply
478 >::type;
479 static_assert(!decltype(hana::is_nothing(MaybeIndex{}))::value,
480 "hana::at_key(map, key) requires the 'key' to be present in the 'map'");
481 constexpr std::size_t index = decltype(*MaybeIndex{}){}();
482 return hana::second(hana::at_c<index>(static_cast<Map&&>(map).storage));
483 }
484 };
485
486 //////////////////////////////////////////////////////////////////////////
487 // union_
488 //////////////////////////////////////////////////////////////////////////
489 template <>
490 struct union_impl<map_tag> {
491 template <typename Xs, typename Ys>
492 static constexpr auto apply(Xs&& xs, Ys&& ys) {
493 return hana::fold_left(static_cast<Xs&&>(xs), static_cast<Ys&&>(ys),
494 hana::insert);
495 }
496 };
497
498 //////////////////////////////////////////////////////////////////////////
499 // intersection_
500 //////////////////////////////////////////////////////////////////////////
501 namespace detail {
502 template <typename Ys>
503 struct map_insert_if_contains {
504 Ys const& ys;
505
506 // Second template param will be pair
507 // Get its key and check if it exists, if it does, insert key, value pair.
508 template <typename Result, typename Pair>
509 static constexpr auto helper(Result&& result, Pair&& pair, hana::true_) {
510 return hana::insert(static_cast<Result&&>(result), static_cast<Pair&&>(pair));
511 }
512
513 template <typename Result, typename Pair>
514 static constexpr auto helper(Result&& result, Pair&&, hana::false_) {
515 return static_cast<Result&&>(result);
516 }
517
518 template <typename Result, typename Pair>
519 constexpr auto operator()(Result&& result, Pair&& pair) const {
520 constexpr bool keep = hana::value<decltype(hana::contains(ys, hana::first(pair)))>();
521 return map_insert_if_contains::helper(static_cast<Result&&>(result),
522 static_cast<Pair&&>(pair),
523 hana::bool_c<keep>);
524 }
525 };
526 }
527
528 template <>
529 struct intersection_impl<map_tag> {
530 template <typename Xs, typename Ys>
531 static constexpr auto apply(Xs&& xs, Ys const& ys) {
532 return hana::fold_left(static_cast<Xs&&>(xs), hana::make_map(),
533 detail::map_insert_if_contains<Ys>{ys});
534 }
535 };
536
537 //////////////////////////////////////////////////////////////////////////
538 // difference
539 //////////////////////////////////////////////////////////////////////////
540 template <>
541 struct difference_impl<map_tag> {
542 template <typename Xs, typename Ys>
543 static constexpr auto apply(Xs&& xs, Ys&& ys) {
544 return hana::fold_left(
545 hana::keys(static_cast<Ys&&>(ys)),
546 static_cast<Xs&&>(xs),
547 hana::erase_key);
548 }
549 };
550
551 //////////////////////////////////////////////////////////////////////////
552 // Foldable
553 //////////////////////////////////////////////////////////////////////////
554 template <>
555 struct unpack_impl<map_tag> {
556 template <typename M, typename F>
557 static constexpr decltype(auto) apply(M&& map, F&& f) {
558 return hana::unpack(static_cast<M&&>(map).storage,
559 static_cast<F&&>(f));
560 }
561 };
562
563 //////////////////////////////////////////////////////////////////////////
564 // Construction from a Foldable
565 //////////////////////////////////////////////////////////////////////////
566 template <typename F>
567 struct to_impl<map_tag, F, when<hana::Foldable<F>::value>> {
568 template <typename Xs>
569 static constexpr decltype(auto) apply(Xs&& xs) {
570 return hana::fold_left(
571 static_cast<Xs&&>(xs), hana::make_map(), hana::insert
572 );
573 }
574 };
575}} // end namespace boost::hana
576
577#endif // !BOOST_HANA_MAP_HPP
578

source code of boost/libs/hana/include/boost/hana/map.hpp