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