ceph/src/boost/libs/hana/include/boost/hana/map.hpp

   1 /*!
   2 @file
   3 Defines `boost::hana::map`.
   4
   5 @copyright Louis Dionne 2013-2016
   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/operators/adl.hpp>
  31 #include <boost/hana/detail/operators/comparable.hpp>
  32 #include <boost/hana/detail/operators/searchable.hpp>
  33 #include <boost/hana/equal.hpp>
  34 #include <boost/hana/find.hpp>
  35 #include <boost/hana/first.hpp>
  36 #include <boost/hana/fold_left.hpp>
  37 #include <boost/hana/functional/demux.hpp>
  38 #include <boost/hana/functional/on.hpp>
  39 #include <boost/hana/functional/partial.hpp>
  40 #include <boost/hana/fwd/any_of.hpp>
  41 #include <boost/hana/fwd/at_key.hpp>
  42 #include <boost/hana/fwd/erase_key.hpp>
  43 #include <boost/hana/fwd/is_subset.hpp>
  44 #include <boost/hana/fwd/keys.hpp>
  45 #include <boost/hana/insert.hpp>
  46 #include <boost/hana/integral_constant.hpp>
  47 #include <boost/hana/keys.hpp>
  48 #include <boost/hana/length.hpp>
  49 #include <boost/hana/optional.hpp>
  50 #include <boost/hana/remove_if.hpp>
  51 #include <boost/hana/second.hpp>
  52 #include <boost/hana/unpack.hpp>
  53 #include <boost/hana/value.hpp>
  54
  55 #include <cstddef>
  56 #include <utility>
  57
  58
  59 BOOST_HANA_NAMESPACE_BEGIN
  60     //////////////////////////////////////////////////////////////////////////
  61     // operators
  62     //////////////////////////////////////////////////////////////////////////
  63     namespace detail {
  64         template <>
  65         struct comparable_operators<map_tag> {
  66             static constexpr bool value = true;
  67         };
  68     }
  69
  70     //////////////////////////////////////////////////////////////////////////
  71     // map
  72     //////////////////////////////////////////////////////////////////////////
  73     //! @cond
  74     template <typename HashTable, typename Storage>
  75     struct map
  76         : detail::searchable_operators<map<HashTable, Storage>>
  77         , detail::operators::adl<map<HashTable, Storage>>
  78     {
  79         using hash_table_type = HashTable;
  80         using storage_type = Storage;
  81
  82         Storage storage;
  83
  84         using hana_tag = map_tag;
  85
  86         explicit constexpr map(Storage const& xs)
  87             : storage(xs)
  88         { }
  89
  90         explicit constexpr map(Storage&& xs)
  91             : storage(static_cast<Storage&&>(xs))
  92         { }
  93
  94         constexpr map() = default;
  95         constexpr map(map const& other) = default;
  96         constexpr map(map&& other) = default;
  97     };
  98     //! @endcond
  99
 100     namespace detail {
 101         template <typename Storage>
 102         struct KeyAtIndex {
 103             template <std::size_t i>
 104             using apply = decltype(hana::first(hana::get_impl<i>(std::declval<Storage>())));
 105         };
 106     }
 107
 108     //////////////////////////////////////////////////////////////////////////
 109     // make<map_tag>
 110     //////////////////////////////////////////////////////////////////////////
 111     template <>
 112     struct make_impl<map_tag> {
 113         template <typename ...Pairs>
 114         static constexpr auto apply(Pairs&& ...pairs) {
 115 #if defined(BOOST_HANA_CONFIG_ENABLE_DEBUG_MODE)
 116             static_assert(detail::fast_and<hana::Product<Pairs>::value...>::value,
 117             "hana::make_map(pairs...) requires all the 'pairs' to be Products");
 118
 119             static_assert(detail::fast_and<
 120                 Comparable<decltype(hana::first(pairs))>::value...
 121             >::value,
 122             "hana::make_map(pairs...) requires all the keys to be Comparable");
 123
 124             static_assert(detail::fast_and<
 125                 Constant<
 126                     decltype(hana::equal(hana::first(pairs), hana::first(pairs)))
 127                 >::value...
 128             >::value,
 129             "hana::make_map(pairs...) requires all the keys to be "
 130             "Comparable at compile-time");
 131
 132             //! @todo
 133             //! This can be implemented more efficiently by doing the check
 134             //! inside each bucket instead.
 135             static_assert(!detail::has_duplicates<decltype(hana::first(pairs))...>::value,
 136             "hana::make_map({keys, values}...) requires all the keys to be unique");
 137
 138             static_assert(!detail::has_duplicates<decltype(hana::hash(hana::first(pairs)))...>::value,
 139             "hana::make_map({keys, values}...) requires all the keys to have different hashes");
 140 #endif
 141
 142             using Storage = hana::basic_tuple<typename detail::decay<Pairs>::type...>;
 143             using HashTable = typename detail::make_hash_table<
 144                 detail::KeyAtIndex<Storage>::template apply, sizeof...(Pairs)
 145             >::type;
 146
 147             return map<HashTable, Storage>(
 148                 hana::make_basic_tuple(static_cast<Pairs&&>(pairs)...)
 149             );
 150         }
 151     };
 152
 153     //////////////////////////////////////////////////////////////////////////
 154     // keys
 155     //////////////////////////////////////////////////////////////////////////
 156     template <>
 157     struct keys_impl<map_tag> {
 158         template <typename Map>
 159         static constexpr decltype(auto) apply(Map&& map) {
 160             return hana::transform(static_cast<Map&&>(map).storage, hana::first);
 161         }
 162     };
 163
 164     //////////////////////////////////////////////////////////////////////////
 165     // values
 166     //////////////////////////////////////////////////////////////////////////
 167     //! @cond
 168     template <typename Map>
 169     constexpr decltype(auto) values_t::operator()(Map&& map) const {
 170         return hana::transform(static_cast<Map&&>(map).storage, hana::second);
 171     }
 172     //! @endcond
 173
 174     //////////////////////////////////////////////////////////////////////////
 175     // insert
 176     //////////////////////////////////////////////////////////////////////////
 177     template <>
 178     struct insert_impl<map_tag> {
 179         template <typename Map, typename Pair>
 180         static constexpr auto helper(Map&& map, Pair&& pair, ...) {
 181             using RawMap = typename std::remove_reference<Map>::type;
 182             using HashTable = typename RawMap::hash_table_type;
 183             using NewHashTable = typename detail::bucket_insert<
 184                 HashTable,
 185                 decltype(hana::first(pair)),
 186                 decltype(hana::length(map.storage))::value
 187             >::type;
 188
 189             using NewStorage = decltype(
 190                 hana::append(static_cast<Map&&>(map).storage, static_cast<Pair&&>(pair))
 191             );
 192             return hana::map<NewHashTable, NewStorage>(
 193                 hana::append(static_cast<Map&&>(map).storage, static_cast<Pair&&>(pair))
 194             );
 195         }
 196
 197         template <typename Map, typename Pair, std::size_t i>
 198         static constexpr auto
 199         helper(Map&& map, Pair&&,
 200                hana::optional<std::integral_constant<std::size_t, i>>)
 201         {
 202             return static_cast<Map&&>(map);
 203         }
 204
 205         //! @todo
 206         //! Here, we insert only if the key is not already in the map.
 207         //! This should be handled by `bucket_insert`, and that would also
 208         //! be more efficient.
 209         template <typename Map, typename Pair>
 210         static constexpr auto apply(Map&& map, Pair&& pair) {
 211             using RawMap = typename std::remove_reference<Map>::type;
 212             using Storage = typename RawMap::storage_type;
 213             using HashTable = typename RawMap::hash_table_type;
 214             using Key = decltype(hana::first(pair));
 215             using MaybeIndex = typename detail::find_index<
 216               HashTable, Key, detail::KeyAtIndex<Storage>::template apply
 217             >::type;
 218             return helper(static_cast<Map&&>(map), static_cast<Pair&&>(pair), MaybeIndex{});
 219         }
 220     };
 221
 222     //////////////////////////////////////////////////////////////////////////
 223     // erase_key
 224     //////////////////////////////////////////////////////////////////////////
 225     template <>
 226     struct erase_key_impl<map_tag> {
 227         //! @todo
 228         //! We could implement some kind of `bucket_erase` metafunction
 229         //! that would be much more efficient than this.
 230         template <typename Map, typename Key>
 231         static constexpr auto
 232         erase_key_helper(Map&& map, Key const&, hana::false_) {
 233             return static_cast<Map&&>(map);
 234         }
 235
 236         template <typename Map, typename Key>
 237         static constexpr auto
 238         erase_key_helper(Map&& map, Key const& key, hana::true_) {
 239             return hana::unpack(
 240                 hana::remove_if(static_cast<Map&&>(map).storage,
 241                                 hana::on(hana::equal.to(key), hana::first)),
 242                 hana::make_map
 243             );
 244         }
 245
 246         template <typename Map, typename Key>
 247         static constexpr auto apply(Map&& map, Key const& key) {
 248             constexpr bool contains = hana::value<decltype(hana::contains(map, key))>();
 249             return erase_key_helper(static_cast<Map&&>(map), key,
 250                                     hana::bool_c<contains>);
 251         }
 252     };
 253
 254     //////////////////////////////////////////////////////////////////////////
 255     // Comparable
 256     //////////////////////////////////////////////////////////////////////////
 257     template <>
 258     struct equal_impl<map_tag, map_tag> {
 259         template <typename M1, typename M2>
 260         static constexpr auto equal_helper(M1 const&, M2 const&, hana::false_) {
 261             return hana::false_c;
 262         }
 263
 264         template <typename M1, typename M2>
 265         static constexpr auto equal_helper(M1 const& m1, M2 const& m2, hana::true_) {
 266             return hana::all_of(hana::keys(m1), hana::demux(equal)(
 267                 hana::partial(hana::find, m1),
 268                 hana::partial(hana::find, m2)
 269             ));
 270         }
 271
 272         template <typename M1, typename M2>
 273         static constexpr auto apply(M1 const& m1, M2 const& m2) {
 274             return equal_impl::equal_helper(m1, m2, hana::bool_c<
 275                 decltype(hana::length(m1.storage))::value ==
 276                 decltype(hana::length(m2.storage))::value
 277             >);
 278         }
 279     };
 280
 281     //////////////////////////////////////////////////////////////////////////
 282     // Searchable
 283     //////////////////////////////////////////////////////////////////////////
 284     template <>
 285     struct find_impl<map_tag> {
 286         template <typename Map>
 287         static constexpr auto find_helper(Map&&, ...) {
 288             return hana::nothing;
 289         }
 290
 291         template <typename Map, std::size_t i>
 292         static constexpr auto
 293         find_helper(Map&& map, hana::optional<std::integral_constant<std::size_t, i>>) {
 294             return hana::just(hana::second(hana::at_c<i>(static_cast<Map&&>(map).storage)));
 295         }
 296
 297         template <typename Map, typename Key>
 298         static constexpr auto apply(Map&& map, Key const&) {
 299             using RawMap = typename std::remove_reference<Map>::type;
 300             using Storage = typename RawMap::storage_type;
 301             using HashTable = typename RawMap::hash_table_type;
 302             using MaybeIndex = typename detail::find_index<
 303               HashTable, Key, detail::KeyAtIndex<Storage>::template apply
 304             >::type;
 305             return find_helper(static_cast<Map&&>(map), MaybeIndex{});
 306         }
 307     };
 308
 309     template <>
 310     struct find_if_impl<map_tag> {
 311         template <typename M, typename Pred>
 312         static constexpr auto apply(M&& map, Pred&& pred) {
 313             return hana::transform(
 314                 hana::find_if(static_cast<M&&>(map).storage,
 315                     hana::compose(static_cast<Pred&&>(pred), hana::first)),
 316                 hana::second
 317             );
 318         }
 319     };
 320
 321     template <>
 322     struct any_of_impl<map_tag> {
 323         template <typename M, typename Pred>
 324         static constexpr auto apply(M const& map, Pred const& pred)
 325         { return hana::any_of(hana::keys(map), pred); }
 326     };
 327
 328     template <>
 329     struct is_subset_impl<map_tag, map_tag> {
 330         template <typename Ys>
 331         struct all_contained {
 332             Ys const& ys;
 333             template <typename ...X>
 334             constexpr auto operator()(X const& ...x) const {
 335                 return hana::bool_c<detail::fast_and<
 336                     hana::value<decltype(hana::contains(ys, x))>()...
 337                 >::value>;
 338             }
 339         };
 340
 341         template <typename Xs, typename Ys>
 342         static constexpr auto apply(Xs const& xs, Ys const& ys) {
 343             auto ys_keys = hana::keys(ys);
 344             return hana::unpack(hana::keys(xs), all_contained<decltype(ys_keys)>{ys_keys});
 345         }
 346     };
 347
 348     template <>
 349     struct at_key_impl<map_tag> {
 350         template <typename Map, typename Key>
 351         static constexpr decltype(auto) apply(Map&& map, Key const&) {
 352             using RawMap = typename std::remove_reference<Map>::type;
 353             using HashTable = typename RawMap::hash_table_type;
 354             using Storage = typename RawMap::storage_type;
 355             using MaybeIndex = typename detail::find_index<
 356                 HashTable, Key, detail::KeyAtIndex<Storage>::template apply
 357             >::type;
 358             static_assert(!decltype(hana::is_nothing(MaybeIndex{}))::value,
 359                 "hana::at_key(map, key) requires the 'key' to be present in the 'map'");
 360             constexpr std::size_t index = decltype(*MaybeIndex{}){}();
 361             return hana::second(hana::at_c<index>(static_cast<Map&&>(map).storage));
 362         }
 363     };
 364
 365     //////////////////////////////////////////////////////////////////////////
 366     // Foldable
 367     //////////////////////////////////////////////////////////////////////////
 368     template <>
 369     struct unpack_impl<map_tag> {
 370         template <typename M, typename F>
 371         static constexpr decltype(auto) apply(M&& map, F&& f) {
 372             return hana::unpack(static_cast<M&&>(map).storage,
 373                                 static_cast<F&&>(f));
 374         }
 375     };
 376
 377     //////////////////////////////////////////////////////////////////////////
 378     // Construction from a Foldable
 379     //////////////////////////////////////////////////////////////////////////
 380     template <typename F>
 381     struct to_impl<map_tag, F, when<hana::Foldable<F>::value>> {
 382         template <typename Xs>
 383         static constexpr decltype(auto) apply(Xs&& xs) {
 384             return hana::fold_left(
 385                 static_cast<Xs&&>(xs), hana::make_map(), hana::insert
 386             );
 387         }
 388     };
 389 BOOST_HANA_NAMESPACE_END
 390
 391 #endif // !BOOST_HANA_MAP_HPP