Back to home page

EIC code displayed by LXR
 
 

    

File indexing completed on 2025-01-18 09:38:03 

0001 /*!
0002 @file
0003 Defines `boost::hana::map`.
0004 
0005 Copyright Louis Dionne 2013-2022
0006 Distributed under the Boost Software License, Version 1.0.
0007 (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
0008  */
0009 
0010 #ifndef BOOST_HANA_MAP_HPP
0011 #define BOOST_HANA_MAP_HPP
0012 
0013 #include <boost/hana/fwd/map.hpp>
0014 
0015 #include <boost/hana/all_of.hpp>
0016 #include <boost/hana/basic_tuple.hpp>
0017 #include <boost/hana/bool.hpp>
0018 #include <boost/hana/concept/comparable.hpp>
0019 #include <boost/hana/concept/constant.hpp>
0020 #include <boost/hana/concept/product.hpp>
0021 #include <boost/hana/config.hpp>
0022 #include <boost/hana/contains.hpp>
0023 #include <boost/hana/core/is_a.hpp>
0024 #include <boost/hana/core/make.hpp>
0025 #include <boost/hana/core/to.hpp>
0026 #include <boost/hana/detail/decay.hpp>
0027 #include <boost/hana/detail/fast_and.hpp>
0028 #include <boost/hana/detail/has_duplicates.hpp>
0029 #include <boost/hana/detail/hash_table.hpp>
0030 #include <boost/hana/detail/intrinsics.hpp>
0031 #include <boost/hana/detail/operators/adl.hpp>
0032 #include <boost/hana/detail/operators/comparable.hpp>
0033 #include <boost/hana/detail/operators/searchable.hpp>
0034 #include <boost/hana/equal.hpp>
0035 #include <boost/hana/find.hpp>
0036 #include <boost/hana/first.hpp>
0037 #include <boost/hana/fold_left.hpp>
0038 #include <boost/hana/functional/demux.hpp>
0039 #include <boost/hana/functional/on.hpp>
0040 #include <boost/hana/functional/partial.hpp>
0041 #include <boost/hana/fwd/any_of.hpp>
0042 #include <boost/hana/fwd/at_key.hpp>
0043 #include <boost/hana/fwd/difference.hpp>
0044 #include <boost/hana/fwd/erase_key.hpp>
0045 #include <boost/hana/fwd/intersection.hpp>
0046 #include <boost/hana/fwd/is_subset.hpp>
0047 #include <boost/hana/fwd/keys.hpp>
0048 #include <boost/hana/fwd/union.hpp>
0049 #include <boost/hana/insert.hpp>
0050 #include <boost/hana/integral_constant.hpp>
0051 #include <boost/hana/keys.hpp>
0052 #include <boost/hana/length.hpp>
0053 #include <boost/hana/optional.hpp>
0054 #include <boost/hana/remove_if.hpp>
0055 #include <boost/hana/second.hpp>
0056 #include <boost/hana/unpack.hpp>
0057 #include <boost/hana/value.hpp>
0058 
0059 
0060 #include <cstddef>
0061 #include <type_traits>
0062 #include <utility>
0063 
0064 
0065 namespace boost { namespace hana {
0066     //////////////////////////////////////////////////////////////////////////
0067     // operators
0068     //////////////////////////////////////////////////////////////////////////
0069     namespace detail {
0070         template <>
0071         struct comparable_operators<map_tag> {
0072             static constexpr bool value = true;
0073         };
0074     }
0075 
0076     //////////////////////////////////////////////////////////////////////////
0077     // map
0078     //////////////////////////////////////////////////////////////////////////
0079     //! @cond
0080     namespace detail {
0081         template <typename ...>
0082         struct storage_is_default_constructible;
0083         template <typename ...T>
0084         struct storage_is_default_constructible<hana::basic_tuple<T...>> {
0085             static constexpr bool value = detail::fast_and<
0086                 BOOST_HANA_TT_IS_CONSTRUCTIBLE(T)...
0087             >::value;
0088         };
0089 
0090         template <typename ...>
0091         struct storage_is_copy_constructible;
0092         template <typename ...T>
0093         struct storage_is_copy_constructible<hana::basic_tuple<T...>> {
0094             static constexpr bool value = detail::fast_and<
0095                 BOOST_HANA_TT_IS_CONSTRUCTIBLE(T, T const&)...
0096             >::value;
0097         };
0098 
0099         template <typename ...>
0100         struct storage_is_move_constructible;
0101         template <typename ...T>
0102         struct storage_is_move_constructible<hana::basic_tuple<T...>> {
0103             static constexpr bool value = detail::fast_and<
0104                 BOOST_HANA_TT_IS_CONSTRUCTIBLE(T, T&&)...
0105             >::value;
0106         };
0107 
0108         template <typename ...>
0109         struct storage_is_copy_assignable;
0110         template <typename ...T>
0111         struct storage_is_copy_assignable<hana::basic_tuple<T...>> {
0112             static constexpr bool value = detail::fast_and<
0113                 BOOST_HANA_TT_IS_ASSIGNABLE(T, T const&)...
0114             >::value;
0115         };
0116 
0117         template <typename ...>
0118         struct storage_is_move_assignable;
0119         template <typename ...T>
0120         struct storage_is_move_assignable<hana::basic_tuple<T...>> {
0121             static constexpr bool value = detail::fast_and<
0122                 BOOST_HANA_TT_IS_ASSIGNABLE(T, T&&)...
0123             >::value;
0124         };
0125 
0126         template <typename HashTable, typename Storage>
0127         struct map_impl final
0128             : detail::searchable_operators<map_impl<HashTable, Storage>>
0129             , detail::operators::adl<map_impl<HashTable, Storage>>
0130         {
0131             using hash_table_type = HashTable;
0132             using storage_type = Storage;
0133 
0134             Storage storage;
0135 
0136             using hana_tag = map_tag;
0137 
0138             template <typename ...P, typename = typename std::enable_if<
0139                 std::is_same<
0140                     Storage,
0141                     hana::basic_tuple<typename detail::decay<P>::type...>
0142                 >::value
0143             >::type>
0144             explicit constexpr map_impl(P&& ...pairs)
0145                 : storage{static_cast<P&&>(pairs)...}
0146             { }
0147 
0148             explicit constexpr map_impl(Storage&& xs)
0149                 : storage(static_cast<Storage&&>(xs))
0150             { }
0151 
0152             template <typename ...Dummy, typename = typename std::enable_if<
0153                 detail::storage_is_default_constructible<Storage, Dummy...>::value
0154             >::type>
0155             constexpr map_impl()
0156                 : storage()
0157             { }
0158 
0159             template <typename ...Dummy, typename = typename std::enable_if<
0160                 detail::storage_is_copy_constructible<Storage, Dummy...>::value
0161             >::type>
0162             constexpr map_impl(map_impl const& other)
0163                 : storage(other.storage)
0164             { }
0165 
0166             template <typename ...Dummy, typename = typename std::enable_if<
0167                 detail::storage_is_move_constructible<Storage, Dummy...>::value
0168             >::type>
0169             constexpr map_impl(map_impl&& other)
0170                 : storage(static_cast<Storage&&>(other.storage))
0171             { }
0172 
0173             template <typename ...Dummy, typename = typename std::enable_if<
0174                 detail::storage_is_move_assignable<Storage, Dummy...>::value
0175             >::type>
0176             constexpr map_impl& operator=(map_impl&& other) {
0177                 storage = static_cast<Storage&&>(other.storage);
0178                 return *this;
0179             }
0180 
0181             template <typename ...Dummy, typename = typename std::enable_if<
0182                 detail::storage_is_copy_assignable<Storage, Dummy...>::value
0183             >::type>
0184             constexpr map_impl& operator=(map_impl const& other) {
0185                 storage = other.storage;
0186                 return *this;
0187             }
0188 
0189             // Prevent the compiler from defining the default copy and move
0190             // constructors, which interfere with the SFINAE above.
0191             ~map_impl() = default;
0192         };
0193         //! @endcond
0194 
0195         template <typename Storage>
0196         struct KeyAtIndex {
0197             template <std::size_t i>
0198             using apply = decltype(hana::first(hana::at_c<i>(std::declval<Storage>())));
0199         };
0200 
0201         template <typename ...Pairs>
0202         struct make_map_type {
0203             using Storage = hana::basic_tuple<Pairs...>;
0204             using HashTable = typename detail::make_hash_table<
0205                 detail::KeyAtIndex<Storage>::template apply, sizeof...(Pairs)
0206             >::type;
0207             using type = detail::map_impl<HashTable, Storage>;
0208         };
0209     }
0210 
0211     //////////////////////////////////////////////////////////////////////////
0212     // make<map_tag>
0213     //////////////////////////////////////////////////////////////////////////
0214     template <>
0215     struct make_impl<map_tag> {
0216         template <typename ...Pairs>
0217         static constexpr auto apply(Pairs&& ...pairs) {
0218 #if defined(BOOST_HANA_CONFIG_ENABLE_DEBUG_MODE)
0219             static_assert(detail::fast_and<hana::Product<Pairs>::value...>::value,
0220             "hana::make_map(pairs...) requires all the 'pairs' to be Products");
0221 
0222             static_assert(detail::fast_and<
0223                 hana::Comparable<decltype(hana::first(pairs))>::value...
0224             >::value,
0225             "hana::make_map(pairs...) requires all the keys to be Comparable");
0226 
0227             static_assert(detail::fast_and<
0228                 hana::Constant<
0229                     decltype(hana::equal(hana::first(pairs), hana::first(pairs)))
0230                 >::value...
0231             >::value,
0232             "hana::make_map(pairs...) requires all the keys to be "
0233             "Comparable at compile-time");
0234 
0235             //! @todo
0236             //! This can be implemented more efficiently by doing the check
0237             //! inside each bucket instead.
0238             static_assert(!detail::has_duplicates<decltype(hana::first(pairs))...>::value,
0239             "hana::make_map({keys, values}...) requires all the keys to be unique");
0240 
0241             static_assert(!detail::has_duplicates<decltype(hana::hash(hana::first(pairs)))...>::value,
0242             "hana::make_map({keys, values}...) requires all the keys to have different hashes");
0243 #endif
0244 
0245             using Map = typename detail::make_map_type<typename detail::decay<Pairs>::type...>::type;
0246             return Map{hana::make_basic_tuple(static_cast<Pairs&&>(pairs)...)};
0247         }
0248     };
0249 
0250     //////////////////////////////////////////////////////////////////////////
0251     // keys
0252     //////////////////////////////////////////////////////////////////////////
0253     template <>
0254     struct keys_impl<map_tag> {
0255         template <typename Map>
0256         static constexpr decltype(auto) apply(Map&& map) {
0257             return hana::transform(static_cast<Map&&>(map).storage, hana::first);
0258         }
0259     };
0260 
0261     //////////////////////////////////////////////////////////////////////////
0262     // values
0263     //////////////////////////////////////////////////////////////////////////
0264     //! @cond
0265     template <typename Map>
0266     constexpr decltype(auto) values_t::operator()(Map&& map) const {
0267         return hana::transform(static_cast<Map&&>(map).storage, hana::second);
0268     }
0269     //! @endcond
0270 
0271     //////////////////////////////////////////////////////////////////////////
0272     // insert
0273     //////////////////////////////////////////////////////////////////////////
0274     template <>
0275     struct insert_impl<map_tag> {
0276         template <typename Map, typename Pair>
0277         static constexpr auto helper(Map&& map, Pair&& pair, ...) {
0278             using RawMap = typename std::remove_reference<Map>::type;
0279             using HashTable = typename RawMap::hash_table_type;
0280             using NewHashTable = typename detail::bucket_insert<
0281                 HashTable,
0282                 decltype(hana::first(pair)),
0283                 decltype(hana::length(map.storage))::value
0284             >::type;
0285 
0286             using NewStorage = decltype(
0287                 hana::append(static_cast<Map&&>(map).storage, static_cast<Pair&&>(pair))
0288             );
0289             return detail::map_impl<NewHashTable, NewStorage>(
0290                 hana::append(static_cast<Map&&>(map).storage, static_cast<Pair&&>(pair))
0291             );
0292         }
0293 
0294         template <typename Map, typename Pair, std::size_t i>
0295         static constexpr auto
0296         helper(Map&& map, Pair&&,
0297                hana::optional<std::integral_constant<std::size_t, i>>)
0298         {
0299             return static_cast<Map&&>(map);
0300         }
0301 
0302         //! @todo
0303         //! Here, we insert only if the key is not already in the map.
0304         //! This should be handled by `bucket_insert`, and that would also
0305         //! be more efficient.
0306         template <typename Map, typename Pair>
0307         static constexpr auto apply(Map&& map, Pair&& pair) {
0308             using RawMap = typename std::remove_reference<Map>::type;
0309             using Storage = typename RawMap::storage_type;
0310             using HashTable = typename RawMap::hash_table_type;
0311             using Key = decltype(hana::first(pair));
0312             using MaybeIndex = typename detail::find_index<
0313               HashTable, Key, detail::KeyAtIndex<Storage>::template apply
0314             >::type;
0315             return helper(static_cast<Map&&>(map), static_cast<Pair&&>(pair), MaybeIndex{});
0316         }
0317     };
0318 
0319     //////////////////////////////////////////////////////////////////////////
0320     // erase_key
0321     //////////////////////////////////////////////////////////////////////////
0322     template <>
0323     struct erase_key_impl<map_tag> {
0324         //! @todo
0325         //! We could implement some kind of `bucket_erase` metafunction
0326         //! that would be much more efficient than this.
0327         template <typename Map, typename Key>
0328         static constexpr auto
0329         erase_key_helper(Map&& map, Key const&, hana::false_) {
0330             return static_cast<Map&&>(map);
0331         }
0332 
0333         template <typename Map, typename Key>
0334         static constexpr auto
0335         erase_key_helper(Map&& map, Key const& key, hana::true_) {
0336             return hana::unpack(
0337                 hana::remove_if(static_cast<Map&&>(map).storage,
0338                                 hana::on(hana::equal.to(key), hana::first)),
0339                 hana::make_map
0340             );
0341         }
0342 
0343         template <typename Map, typename Key>
0344         static constexpr auto apply_impl(Map&& map, Key const& key, hana::false_) {
0345             return erase_key_helper(static_cast<Map&&>(map), key,
0346                                     hana::contains(map, key));
0347         }
0348 
0349         template <typename Map, typename Key>
0350         static constexpr auto apply_impl(Map&& map, Key const&, hana::true_) {
0351             return static_cast<Map&&>(map);
0352         }
0353 
0354         template <typename Map, typename Key>
0355         static constexpr auto apply(Map&& map, Key const& key) {
0356             constexpr bool is_empty = decltype(hana::length(map))::value == 0;
0357             return apply_impl(static_cast<Map&&>(map), key, hana::bool_<is_empty>{});
0358         }
0359     };
0360 
0361     //////////////////////////////////////////////////////////////////////////
0362     // Comparable
0363     //////////////////////////////////////////////////////////////////////////
0364     template <>
0365     struct equal_impl<map_tag, map_tag> {
0366         template <typename M1, typename M2>
0367         static constexpr auto equal_helper(M1 const&, M2 const&, hana::false_) {
0368             return hana::false_c;
0369         }
0370 
0371         template <typename M1, typename M2>
0372         static constexpr auto equal_helper(M1 const& m1, M2 const& m2, hana::true_) {
0373             return hana::all_of(hana::keys(m1), hana::demux(equal)(
0374                 hana::partial(hana::find, m1),
0375                 hana::partial(hana::find, m2)
0376             ));
0377         }
0378 
0379         template <typename M1, typename M2>
0380         static constexpr auto apply(M1 const& m1, M2 const& m2) {
0381             return equal_impl::equal_helper(m1, m2, hana::bool_c<
0382                 decltype(hana::length(m1.storage))::value ==
0383                 decltype(hana::length(m2.storage))::value
0384             >);
0385         }
0386     };
0387 
0388     //////////////////////////////////////////////////////////////////////////
0389     // Searchable
0390     //////////////////////////////////////////////////////////////////////////
0391     template <>
0392     struct find_impl<map_tag> {
0393         template <typename Map>
0394         static constexpr auto find_helper(Map&&, ...) {
0395             return hana::nothing;
0396         }
0397 
0398         template <typename Map, std::size_t i>
0399         static constexpr auto
0400         find_helper(Map&& map, hana::optional<std::integral_constant<std::size_t, i>>) {
0401             return hana::just(hana::second(hana::at_c<i>(static_cast<Map&&>(map).storage)));
0402         }
0403 
0404         template <typename Map, typename Key>
0405         static constexpr auto apply(Map&& map, Key const&) {
0406             using RawMap = typename std::remove_reference<Map>::type;
0407             using Storage = typename RawMap::storage_type;
0408             using HashTable = typename RawMap::hash_table_type;
0409             using MaybeIndex = typename detail::find_index<
0410               HashTable, Key, detail::KeyAtIndex<Storage>::template apply
0411             >::type;
0412             return find_helper(static_cast<Map&&>(map), MaybeIndex{});
0413         }
0414     };
0415 
0416     template <>
0417     struct find_if_impl<map_tag> {
0418         template <typename M, typename Pred>
0419         static constexpr auto apply(M&& map, Pred&& pred) {
0420             return hana::transform(
0421                 hana::find_if(static_cast<M&&>(map).storage,
0422                     hana::compose(static_cast<Pred&&>(pred), hana::first)),
0423                 hana::second
0424             );
0425         }
0426     };
0427 
0428     template <>
0429     struct contains_impl<map_tag> {
0430         template <typename Map, typename Key>
0431         static constexpr auto apply(Map const&, Key const&) {
0432             using RawMap = typename std::remove_reference<Map>::type;
0433             using HashTable = typename RawMap::hash_table_type;
0434             using Storage = typename RawMap::storage_type;
0435             using MaybeIndex = typename detail::find_index<
0436                 HashTable, Key, detail::KeyAtIndex<Storage>::template apply
0437             >::type;
0438             return hana::bool_<!decltype(hana::is_nothing(MaybeIndex{}))::value>{};
0439         }
0440     };
0441 
0442     template <>
0443     struct any_of_impl<map_tag> {
0444         template <typename M, typename Pred>
0445         static constexpr auto apply(M const& map, Pred const& pred)
0446         { return hana::any_of(hana::keys(map), pred); }
0447     };
0448 
0449     template <>
0450     struct is_subset_impl<map_tag, map_tag> {
0451         template <typename Ys>
0452         struct all_contained {
0453             Ys const& ys;
0454             template <typename ...X>
0455             constexpr auto operator()(X const& ...x) const {
0456                 return hana::bool_c<detail::fast_and<
0457                     hana::value<decltype(hana::contains(ys, x))>()...
0458                 >::value>;
0459             }
0460         };
0461 
0462         template <typename Xs, typename Ys>
0463         static constexpr auto apply(Xs const& xs, Ys const& ys) {
0464             auto ys_keys = hana::keys(ys);
0465             return hana::unpack(hana::keys(xs), all_contained<decltype(ys_keys)>{ys_keys});
0466         }
0467     };
0468 
0469     template <>
0470     struct at_key_impl<map_tag> {
0471         template <typename Map, typename Key>
0472         static constexpr decltype(auto) apply(Map&& map, Key const&) {
0473             using RawMap = typename std::remove_reference<Map>::type;
0474             using HashTable = typename RawMap::hash_table_type;
0475             using Storage = typename RawMap::storage_type;
0476             using MaybeIndex = typename detail::find_index<
0477                 HashTable, Key, detail::KeyAtIndex<Storage>::template apply
0478             >::type;
0479             static_assert(!decltype(hana::is_nothing(MaybeIndex{}))::value,
0480                 "hana::at_key(map, key) requires the 'key' to be present in the 'map'");
0481             constexpr std::size_t index = decltype(*MaybeIndex{}){}();
0482             return hana::second(hana::at_c<index>(static_cast<Map&&>(map).storage));
0483         }
0484     };
0485 
0486     //////////////////////////////////////////////////////////////////////////
0487     // union_
0488     //////////////////////////////////////////////////////////////////////////
0489     template <>
0490     struct union_impl<map_tag> {
0491         template <typename Xs, typename Ys>
0492         static constexpr auto apply(Xs&& xs, Ys&& ys) {
0493             return hana::fold_left(static_cast<Xs&&>(xs), static_cast<Ys&&>(ys),
0494                                    hana::insert);
0495         }
0496     };
0497 
0498     //////////////////////////////////////////////////////////////////////////
0499     // intersection_
0500     //////////////////////////////////////////////////////////////////////////
0501     namespace detail {
0502         template <typename Ys>
0503         struct map_insert_if_contains {
0504             Ys const& ys;
0505 
0506             // Second template param will be pair
0507             // Get its key and check if it exists, if it does, insert key, value pair.
0508             template <typename Result, typename Pair>
0509             static constexpr auto helper(Result&& result, Pair&& pair, hana::true_) {
0510                 return hana::insert(static_cast<Result&&>(result), static_cast<Pair&&>(pair));
0511             }
0512 
0513             template <typename Result, typename Pair>
0514             static constexpr auto helper(Result&& result, Pair&&, hana::false_) {
0515                 return static_cast<Result&&>(result);
0516             }
0517 
0518             template <typename Result, typename Pair>
0519             constexpr auto operator()(Result&& result, Pair&& pair) const {
0520                 constexpr bool keep = hana::value<decltype(hana::contains(ys, hana::first(pair)))>();
0521                 return map_insert_if_contains::helper(static_cast<Result&&>(result),
0522                                                       static_cast<Pair&&>(pair),
0523                                                       hana::bool_c<keep>);
0524             }
0525         };
0526     }
0527 
0528     template <>
0529     struct intersection_impl<map_tag> {
0530         template <typename Xs, typename Ys>
0531         static constexpr auto apply(Xs&& xs, Ys const& ys) {
0532             return hana::fold_left(static_cast<Xs&&>(xs), hana::make_map(),
0533                                    detail::map_insert_if_contains<Ys>{ys});
0534         }
0535     };
0536 
0537     //////////////////////////////////////////////////////////////////////////
0538     // difference
0539     //////////////////////////////////////////////////////////////////////////
0540     template <>
0541     struct difference_impl<map_tag> {
0542         template <typename Xs, typename Ys>
0543         static constexpr auto apply(Xs&& xs, Ys&& ys) {
0544             return hana::fold_left(
0545                     hana::keys(static_cast<Ys&&>(ys)),
0546                     static_cast<Xs&&>(xs),
0547                     hana::erase_key);
0548         }
0549     };
0550 
0551     //////////////////////////////////////////////////////////////////////////
0552     // Foldable
0553     //////////////////////////////////////////////////////////////////////////
0554     template <>
0555     struct unpack_impl<map_tag> {
0556         template <typename M, typename F>
0557         static constexpr decltype(auto) apply(M&& map, F&& f) {
0558             return hana::unpack(static_cast<M&&>(map).storage,
0559                                 static_cast<F&&>(f));
0560         }
0561     };
0562 
0563     //////////////////////////////////////////////////////////////////////////
0564     // Construction from a Foldable
0565     //////////////////////////////////////////////////////////////////////////
0566     template <typename F>
0567     struct to_impl<map_tag, F, when<hana::Foldable<F>::value>> {
0568         template <typename Xs>
0569         static constexpr decltype(auto) apply(Xs&& xs) {
0570             return hana::fold_left(
0571                 static_cast<Xs&&>(xs), hana::make_map(), hana::insert
0572             );
0573         }
0574     };
0575 }} // end namespace boost::hana
0576 
0577 #endif // !BOOST_HANA_MAP_HPP
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.3.7 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!