9
3

map.hpp 22 KB

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