1 /*!
2 @file
3 Defines `boost::hana::map`.
4 
5 @copyright Louis Dionne 2013-2017
6 Distributed 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 
65 BOOST_HANA_NAMESPACE_BEGIN
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>
map_impldetail::map_impl144             explicit constexpr map_impl(P&& ...pairs)
145                 : storage{static_cast<P&&>(pairs)...}
146             { }
147 
map_impldetail::map_impl148             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>
map_impldetail::map_impl155             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>
map_impldetail::map_impl162             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>
map_impldetail::map_impl169             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>
operator =detail::map_impl176             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>
operator =detail::map_impl184             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>
applymake_impl217         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>
applykeys_impl256         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>
operator ()(Map && map) const266     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>
helperinsert_impl277         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
helperinsert_impl296         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>
applyinsert_impl307         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
erase_key_helpererase_key_impl329         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
erase_key_helpererase_key_impl335         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>
apply_implerase_key_impl344         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>
apply_implerase_key_impl350         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>
applyerase_key_impl355         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>
equal_helperequal_impl367         static constexpr auto equal_helper(M1 const&, M2 const&, hana::false_) {
368             return hana::false_c;
369         }
370 
371         template <typename M1, typename M2>
equal_helperequal_impl372         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>
applyequal_impl380         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>
find_helperfind_impl394         static constexpr auto find_helper(Map&&, ...) {
395             return hana::nothing;
396         }
397 
398         template <typename Map, std::size_t i>
399         static constexpr auto
find_helperfind_impl400         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>
applyfind_impl405         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>
applyfind_if_impl419         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>
applycontains_impl431         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>
applyany_of_impl445         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>
operator ()is_subset_impl::all_contained455             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>
applyis_subset_impl463         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>
applyat_key_impl472         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>
applyunion_impl492         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>
helperdetail::map_insert_if_contains509             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>
helperdetail::map_insert_if_contains514             static constexpr auto helper(Result&& result, Pair&&, hana::false_) {
515                 return static_cast<Result&&>(result);
516             }
517 
518             template <typename Result, typename Pair>
operator ()detail::map_insert_if_contains519             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>
applyintersection_impl531         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>
applydifference_impl543         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>
applyunpack_impl557         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>
applyto_impl569         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 BOOST_HANA_NAMESPACE_END
576 
577 #endif // !BOOST_HANA_MAP_HPP
578