summaryrefslogtreecommitdiff
path: root/boost/hana/map.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/hana/map.hpp')
-rw-r--r--boost/hana/map.hpp389
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