3 Defines `boost::hana::map`.
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)
10 #ifndef BOOST_HANA_MAP_HPP
11 #define BOOST_HANA_MAP_HPP
13 #include <boost/hana/fwd/map.hpp>
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>
59 BOOST_HANA_NAMESPACE_BEGIN
60 //////////////////////////////////////////////////////////////////////////
62 //////////////////////////////////////////////////////////////////////////
65 struct comparable_operators<map_tag> {
66 static constexpr bool value = true;
70 //////////////////////////////////////////////////////////////////////////
72 //////////////////////////////////////////////////////////////////////////
74 template <typename HashTable, typename Storage>
76 : detail::searchable_operators<map<HashTable, Storage>>
77 , detail::operators::adl<map<HashTable, Storage>>
79 using hash_table_type = HashTable;
80 using storage_type = Storage;
84 using hana_tag = map_tag;
86 explicit constexpr map(Storage const& xs)
90 explicit constexpr map(Storage&& xs)
91 : storage(static_cast<Storage&&>(xs))
94 constexpr map() = default;
95 constexpr map(map const& other) = default;
96 constexpr map(map&& other) = default;
101 template <typename Storage>
103 template <std::size_t i>
104 using apply = decltype(hana::first(hana::get_impl<i>(std::declval<Storage>())));
108 //////////////////////////////////////////////////////////////////////////
110 //////////////////////////////////////////////////////////////////////////
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");
119 static_assert(detail::fast_and<
120 Comparable<decltype(hana::first(pairs))>::value...
122 "hana::make_map(pairs...) requires all the keys to be Comparable");
124 static_assert(detail::fast_and<
126 decltype(hana::equal(hana::first(pairs), hana::first(pairs)))
129 "hana::make_map(pairs...) requires all the keys to be "
130 "Comparable at compile-time");
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");
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");
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)
147 return map<HashTable, Storage>(
148 hana::make_basic_tuple(static_cast<Pairs&&>(pairs)...)
153 //////////////////////////////////////////////////////////////////////////
155 //////////////////////////////////////////////////////////////////////////
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);
164 //////////////////////////////////////////////////////////////////////////
166 //////////////////////////////////////////////////////////////////////////
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);
174 //////////////////////////////////////////////////////////////////////////
176 //////////////////////////////////////////////////////////////////////////
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<
185 decltype(hana::first(pair)),
186 decltype(hana::length(map.storage))::value
189 using NewStorage = decltype(
190 hana::append(static_cast<Map&&>(map).storage, static_cast<Pair&&>(pair))
192 return hana::map<NewHashTable, NewStorage>(
193 hana::append(static_cast<Map&&>(map).storage, static_cast<Pair&&>(pair))
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>>)
202 return static_cast<Map&&>(map);
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
218 return helper(static_cast<Map&&>(map), static_cast<Pair&&>(pair), MaybeIndex{});
222 //////////////////////////////////////////////////////////////////////////
224 //////////////////////////////////////////////////////////////////////////
226 struct erase_key_impl<map_tag> {
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);
236 template <typename Map, typename Key>
237 static constexpr auto
238 erase_key_helper(Map&& map, Key const& key, hana::true_) {
240 hana::remove_if(static_cast<Map&&>(map).storage,
241 hana::on(hana::equal.to(key), hana::first)),
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>);
254 //////////////////////////////////////////////////////////////////////////
256 //////////////////////////////////////////////////////////////////////////
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;
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)
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
281 //////////////////////////////////////////////////////////////////////////
283 //////////////////////////////////////////////////////////////////////////
285 struct find_impl<map_tag> {
286 template <typename Map>
287 static constexpr auto find_helper(Map&&, ...) {
288 return hana::nothing;
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)));
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
305 return find_helper(static_cast<Map&&>(map), MaybeIndex{});
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)),
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); }
329 struct is_subset_impl<map_tag, map_tag> {
330 template <typename Ys>
331 struct all_contained {
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))>()...
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});
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
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));
365 //////////////////////////////////////////////////////////////////////////
367 //////////////////////////////////////////////////////////////////////////
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));
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
389 BOOST_HANA_NAMESPACE_END
391 #endif // !BOOST_HANA_MAP_HPP