diff options
Diffstat (limited to 'boost/hana/map.hpp')
-rw-r--r-- | boost/hana/map.hpp | 389 |
1 files changed, 389 insertions, 0 deletions
diff --git a/boost/hana/map.hpp b/boost/hana/map.hpp new file mode 100644 index 0000000000..341f1d0517 --- /dev/null +++ b/boost/hana/map.hpp @@ -0,0 +1,389 @@ +/*! +@file +Defines `boost::hana::map`. + +@copyright Louis Dionne 2013-2016 +Distributed under the Boost Software License, Version 1.0. +(See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt) + */ + +#ifndef BOOST_HANA_MAP_HPP +#define BOOST_HANA_MAP_HPP + +#include <boost/hana/fwd/map.hpp> + +#include <boost/hana/all_of.hpp> +#include <boost/hana/basic_tuple.hpp> +#include <boost/hana/bool.hpp> +#include <boost/hana/concept/comparable.hpp> +#include <boost/hana/concept/constant.hpp> +#include <boost/hana/concept/product.hpp> +#include <boost/hana/config.hpp> +#include <boost/hana/contains.hpp> +#include <boost/hana/core/is_a.hpp> +#include <boost/hana/core/make.hpp> +#include <boost/hana/core/to.hpp> +#include <boost/hana/detail/decay.hpp> +#include <boost/hana/detail/fast_and.hpp> +#include <boost/hana/detail/has_duplicates.hpp> +#include <boost/hana/detail/hash_table.hpp> +#include <boost/hana/detail/operators/adl.hpp> +#include <boost/hana/detail/operators/comparable.hpp> +#include <boost/hana/detail/operators/searchable.hpp> +#include <boost/hana/equal.hpp> +#include <boost/hana/find.hpp> +#include <boost/hana/first.hpp> +#include <boost/hana/fold_left.hpp> +#include <boost/hana/functional/demux.hpp> +#include <boost/hana/functional/on.hpp> +#include <boost/hana/functional/partial.hpp> +#include <boost/hana/fwd/any_of.hpp> +#include <boost/hana/fwd/at_key.hpp> +#include <boost/hana/fwd/erase_key.hpp> +#include <boost/hana/fwd/is_subset.hpp> +#include <boost/hana/fwd/keys.hpp> +#include <boost/hana/insert.hpp> +#include <boost/hana/integral_constant.hpp> +#include <boost/hana/keys.hpp> +#include <boost/hana/length.hpp> +#include <boost/hana/optional.hpp> +#include <boost/hana/remove_if.hpp> +#include <boost/hana/second.hpp> +#include <boost/hana/unpack.hpp> +#include <boost/hana/value.hpp> + +#include <cstddef> +#include <utility> + + +BOOST_HANA_NAMESPACE_BEGIN + ////////////////////////////////////////////////////////////////////////// + // operators + ////////////////////////////////////////////////////////////////////////// + namespace detail { + template <> + struct comparable_operators<map_tag> { + static constexpr bool value = true; + }; + } + + ////////////////////////////////////////////////////////////////////////// + // map + ////////////////////////////////////////////////////////////////////////// + //! @cond + template <typename HashTable, typename Storage> + struct map + : detail::searchable_operators<map<HashTable, Storage>> + , detail::operators::adl<map<HashTable, Storage>> + { + using hash_table_type = HashTable; + using storage_type = Storage; + + Storage storage; + + using hana_tag = map_tag; + + explicit constexpr map(Storage const& xs) + : storage(xs) + { } + + explicit constexpr map(Storage&& xs) + : storage(static_cast<Storage&&>(xs)) + { } + + constexpr map() = default; + constexpr map(map const& other) = default; + constexpr map(map&& other) = default; + }; + //! @endcond + + namespace detail { + template <typename Storage> + struct KeyAtIndex { + template <std::size_t i> + using apply = decltype(hana::first(hana::get_impl<i>(std::declval<Storage>()))); + }; + } + + ////////////////////////////////////////////////////////////////////////// + // make<map_tag> + ////////////////////////////////////////////////////////////////////////// + template <> + struct make_impl<map_tag> { + template <typename ...Pairs> + static constexpr auto apply(Pairs&& ...pairs) { +#if defined(BOOST_HANA_CONFIG_ENABLE_DEBUG_MODE) + static_assert(detail::fast_and<hana::Product<Pairs>::value...>::value, + "hana::make_map(pairs...) requires all the 'pairs' to be Products"); + + static_assert(detail::fast_and< + Comparable<decltype(hana::first(pairs))>::value... + >::value, + "hana::make_map(pairs...) requires all the keys to be Comparable"); + + static_assert(detail::fast_and< + Constant< + decltype(hana::equal(hana::first(pairs), hana::first(pairs))) + >::value... + >::value, + "hana::make_map(pairs...) requires all the keys to be " + "Comparable at compile-time"); + + //! @todo + //! This can be implemented more efficiently by doing the check + //! inside each bucket instead. + static_assert(!detail::has_duplicates<decltype(hana::first(pairs))...>::value, + "hana::make_map({keys, values}...) requires all the keys to be unique"); + + static_assert(!detail::has_duplicates<decltype(hana::hash(hana::first(pairs)))...>::value, + "hana::make_map({keys, values}...) requires all the keys to have different hashes"); +#endif + + using Storage = hana::basic_tuple<typename detail::decay<Pairs>::type...>; + using HashTable = typename detail::make_hash_table< + detail::KeyAtIndex<Storage>::template apply, sizeof...(Pairs) + >::type; + + return map<HashTable, Storage>( + hana::make_basic_tuple(static_cast<Pairs&&>(pairs)...) + ); + } + }; + + ////////////////////////////////////////////////////////////////////////// + // keys + ////////////////////////////////////////////////////////////////////////// + template <> + struct keys_impl<map_tag> { + template <typename Map> + static constexpr decltype(auto) apply(Map&& map) { + return hana::transform(static_cast<Map&&>(map).storage, hana::first); + } + }; + + ////////////////////////////////////////////////////////////////////////// + // values + ////////////////////////////////////////////////////////////////////////// + //! @cond + template <typename Map> + constexpr decltype(auto) values_t::operator()(Map&& map) const { + return hana::transform(static_cast<Map&&>(map).storage, hana::second); + } + //! @endcond + + ////////////////////////////////////////////////////////////////////////// + // insert + ////////////////////////////////////////////////////////////////////////// + template <> + struct insert_impl<map_tag> { + template <typename Map, typename Pair> + static constexpr auto helper(Map&& map, Pair&& pair, ...) { + using RawMap = typename std::remove_reference<Map>::type; + using HashTable = typename RawMap::hash_table_type; + using NewHashTable = typename detail::bucket_insert< + HashTable, + decltype(hana::first(pair)), + decltype(hana::length(map.storage))::value + >::type; + + using NewStorage = decltype( + hana::append(static_cast<Map&&>(map).storage, static_cast<Pair&&>(pair)) + ); + return hana::map<NewHashTable, NewStorage>( + hana::append(static_cast<Map&&>(map).storage, static_cast<Pair&&>(pair)) + ); + } + + template <typename Map, typename Pair, std::size_t i> + static constexpr auto + helper(Map&& map, Pair&&, + hana::optional<std::integral_constant<std::size_t, i>>) + { + return static_cast<Map&&>(map); + } + + //! @todo + //! Here, we insert only if the key is not already in the map. + //! This should be handled by `bucket_insert`, and that would also + //! be more efficient. + template <typename Map, typename Pair> + static constexpr auto apply(Map&& map, Pair&& pair) { + using RawMap = typename std::remove_reference<Map>::type; + using Storage = typename RawMap::storage_type; + using HashTable = typename RawMap::hash_table_type; + using Key = decltype(hana::first(pair)); + using MaybeIndex = typename detail::find_index< + HashTable, Key, detail::KeyAtIndex<Storage>::template apply + >::type; + return helper(static_cast<Map&&>(map), static_cast<Pair&&>(pair), MaybeIndex{}); + } + }; + + ////////////////////////////////////////////////////////////////////////// + // erase_key + ////////////////////////////////////////////////////////////////////////// + template <> + struct erase_key_impl<map_tag> { + //! @todo + //! We could implement some kind of `bucket_erase` metafunction + //! that would be much more efficient than this. + template <typename Map, typename Key> + static constexpr auto + erase_key_helper(Map&& map, Key const&, hana::false_) { + return static_cast<Map&&>(map); + } + + template <typename Map, typename Key> + static constexpr auto + erase_key_helper(Map&& map, Key const& key, hana::true_) { + return hana::unpack( + hana::remove_if(static_cast<Map&&>(map).storage, + hana::on(hana::equal.to(key), hana::first)), + hana::make_map + ); + } + + template <typename Map, typename Key> + static constexpr auto apply(Map&& map, Key const& key) { + constexpr bool contains = hana::value<decltype(hana::contains(map, key))>(); + return erase_key_helper(static_cast<Map&&>(map), key, + hana::bool_c<contains>); + } + }; + + ////////////////////////////////////////////////////////////////////////// + // Comparable + ////////////////////////////////////////////////////////////////////////// + template <> + struct equal_impl<map_tag, map_tag> { + template <typename M1, typename M2> + static constexpr auto equal_helper(M1 const&, M2 const&, hana::false_) { + return hana::false_c; + } + + template <typename M1, typename M2> + static constexpr auto equal_helper(M1 const& m1, M2 const& m2, hana::true_) { + return hana::all_of(hana::keys(m1), hana::demux(equal)( + hana::partial(hana::find, m1), + hana::partial(hana::find, m2) + )); + } + + template <typename M1, typename M2> + static constexpr auto apply(M1 const& m1, M2 const& m2) { + return equal_impl::equal_helper(m1, m2, hana::bool_c< + decltype(hana::length(m1.storage))::value == + decltype(hana::length(m2.storage))::value + >); + } + }; + + ////////////////////////////////////////////////////////////////////////// + // Searchable + ////////////////////////////////////////////////////////////////////////// + template <> + struct find_impl<map_tag> { + template <typename Map> + static constexpr auto find_helper(Map&&, ...) { + return hana::nothing; + } + + template <typename Map, std::size_t i> + static constexpr auto + find_helper(Map&& map, hana::optional<std::integral_constant<std::size_t, i>>) { + return hana::just(hana::second(hana::at_c<i>(static_cast<Map&&>(map).storage))); + } + + template <typename Map, typename Key> + static constexpr auto apply(Map&& map, Key const&) { + using RawMap = typename std::remove_reference<Map>::type; + using Storage = typename RawMap::storage_type; + using HashTable = typename RawMap::hash_table_type; + using MaybeIndex = typename detail::find_index< + HashTable, Key, detail::KeyAtIndex<Storage>::template apply + >::type; + return find_helper(static_cast<Map&&>(map), MaybeIndex{}); + } + }; + + template <> + struct find_if_impl<map_tag> { + template <typename M, typename Pred> + static constexpr auto apply(M&& map, Pred&& pred) { + return hana::transform( + hana::find_if(static_cast<M&&>(map).storage, + hana::compose(static_cast<Pred&&>(pred), hana::first)), + hana::second + ); + } + }; + + template <> + struct any_of_impl<map_tag> { + template <typename M, typename Pred> + static constexpr auto apply(M const& map, Pred const& pred) + { return hana::any_of(hana::keys(map), pred); } + }; + + template <> + struct is_subset_impl<map_tag, map_tag> { + template <typename Ys> + struct all_contained { + Ys const& ys; + template <typename ...X> + constexpr auto operator()(X const& ...x) const { + return hana::bool_c<detail::fast_and< + hana::value<decltype(hana::contains(ys, x))>()... + >::value>; + } + }; + + template <typename Xs, typename Ys> + static constexpr auto apply(Xs const& xs, Ys const& ys) { + auto ys_keys = hana::keys(ys); + return hana::unpack(hana::keys(xs), all_contained<decltype(ys_keys)>{ys_keys}); + } + }; + + template <> + struct at_key_impl<map_tag> { + template <typename Map, typename Key> + static constexpr decltype(auto) apply(Map&& map, Key const&) { + using RawMap = typename std::remove_reference<Map>::type; + using HashTable = typename RawMap::hash_table_type; + using Storage = typename RawMap::storage_type; + using MaybeIndex = typename detail::find_index< + HashTable, Key, detail::KeyAtIndex<Storage>::template apply + >::type; + constexpr std::size_t index = decltype(*MaybeIndex{}){}(); + return hana::second(hana::at_c<index>(static_cast<Map&&>(map).storage)); + } + }; + + ////////////////////////////////////////////////////////////////////////// + // Foldable + ////////////////////////////////////////////////////////////////////////// + template <> + struct unpack_impl<map_tag> { + template <typename M, typename F> + static constexpr decltype(auto) apply(M&& map, F&& f) { + return hana::unpack(static_cast<M&&>(map).storage, + static_cast<F&&>(f)); + } + }; + + ////////////////////////////////////////////////////////////////////////// + // Construction from a Foldable + ////////////////////////////////////////////////////////////////////////// + template <typename F> + struct to_impl<map_tag, F, when<hana::Foldable<F>::value>> { + template <typename Xs> + static constexpr decltype(auto) apply(Xs&& xs) { + return hana::fold_left( + static_cast<Xs&&>(xs), hana::make_map(), hana::insert + ); + } + }; +BOOST_HANA_NAMESPACE_END + +#endif // !BOOST_HANA_MAP_HPP |