]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |