boost/hana/set.hpp

0001 /*!
0002 @file
0003 Defines `boost::hana::set`.
0004
0005 Copyright Louis Dionne 2013-2022
0006 Distributed under the Boost Software License, Version 1.0.
0007 (See accompanying file LICENSE.md or copy at http://boost.org/LICENSE_1_0.txt)
0008  */
0009
0010 #ifndef BOOST_HANA_SET_HPP
0011 #define BOOST_HANA_SET_HPP
0012
0013 #include <boost/hana/fwd/set.hpp>
0014
0015 #include <boost/hana/at.hpp>
0016 #include <boost/hana/bool.hpp>
0017 #include <boost/hana/concept/comparable.hpp>
0018 #include <boost/hana/concept/constant.hpp>
0019 #include <boost/hana/concept/hashable.hpp>
0020 #include <boost/hana/config.hpp>
0021 #include <boost/hana/contains.hpp>
0022 #include <boost/hana/core/make.hpp>
0023 #include <boost/hana/core/to.hpp>
0024 #include <boost/hana/detail/decay.hpp>
0025 #include <boost/hana/detail/fast_and.hpp>
0026 #include <boost/hana/detail/has_duplicates.hpp>
0027 #include <boost/hana/detail/operators/adl.hpp>
0028 #include <boost/hana/detail/operators/comparable.hpp>
0029 #include <boost/hana/detail/operators/searchable.hpp>
0030 #include <boost/hana/equal.hpp>
0031 #include <boost/hana/erase_key.hpp>
0032 #include <boost/hana/find_if.hpp>
0033 #include <boost/hana/fold_left.hpp>
0034 #include <boost/hana/fwd/any_of.hpp>
0035 #include <boost/hana/fwd/core/to.hpp>
0036 #include <boost/hana/fwd/difference.hpp>
0037 #include <boost/hana/fwd/intersection.hpp>
0038 #include <boost/hana/fwd/union.hpp>
0039 #include <boost/hana/insert.hpp>
0040 #include <boost/hana/is_subset.hpp>
0041 #include <boost/hana/length.hpp>
0042 #include <boost/hana/or.hpp>
0043 #include <boost/hana/remove.hpp>
0044 #include <boost/hana/tuple.hpp>
0045 #include <boost/hana/unpack.hpp>
0046 #include <boost/hana/value.hpp>
0047
0048 #include <cstddef>
0049 #include <type_traits>
0050 #include <utility>
0051
0052
0053 namespace boost { namespace hana {
0054     //////////////////////////////////////////////////////////////////////////
0055     // set
0056     //////////////////////////////////////////////////////////////////////////
0057     //! @cond
0058     template <typename ...Xs>
0059     struct set final
0060         : detail::operators::adl<set<Xs...>>
0061         , detail::searchable_operators<set<Xs...>>
0062     {
0063         tuple<Xs...> storage;
0064         using hana_tag = set_tag;
0065         static constexpr std::size_t size = sizeof...(Xs);
0066
0067         explicit constexpr set(tuple<Xs...> const& xs)
0068             : storage(xs)
0069         { }
0070
0071         explicit constexpr set(tuple<Xs...>&& xs)
0072             : storage(static_cast<tuple<Xs...>&&>(xs))
0073         { }
0074
0075         constexpr set() = default;
0076         constexpr set(set const& other) = default;
0077         constexpr set(set&& other) = default;
0078     };
0079     //! @endcond
0080
0081     //////////////////////////////////////////////////////////////////////////
0082     // Operators
0083     //////////////////////////////////////////////////////////////////////////
0084     namespace detail {
0085         template <>
0086         struct comparable_operators<set_tag> {
0087             static constexpr bool value = true;
0088         };
0089     }
0090
0091     //////////////////////////////////////////////////////////////////////////
0092     // make<set_tag>
0093     //////////////////////////////////////////////////////////////////////////
0094     template <>
0095     struct make_impl<set_tag> {
0096         template <typename ...Xs>
0097         static constexpr auto apply(Xs&& ...xs) {
0098 #if defined(BOOST_HANA_CONFIG_ENABLE_DEBUG_MODE)
0099             static_assert(detail::fast_and<hana::Comparable<Xs>::value...>::value,
0100             "hana::make_set(xs...) requires all the 'xs' to be Comparable");
0101
0102             static_assert(detail::fast_and<hana::Hashable<Xs>::value...>::value,
0103             "hana::make_set(xs...) requires all the 'xs' to be Hashable");
0104
0105             static_assert(detail::fast_and<
0106                 Constant<decltype(hana::equal(xs, xs))>::value...
0107             >::value,
0108             "hana::make_set(xs...) requires all the 'xs' to be "
0109             "Comparable at compile-time");
0110
0111             static_assert(!detail::has_duplicates<Xs&&...>::value,
0112             "hana::make_set(xs...) requires all the 'xs' to be unique");
0113 #endif
0114
0115             return set<typename detail::decay<Xs>::type...>{
0116                 hana::make_tuple(static_cast<Xs&&>(xs)...)
0117             };
0118         }
0119     };
0120
0121     //////////////////////////////////////////////////////////////////////////
0122     // Comparable
0123     //////////////////////////////////////////////////////////////////////////
0124     template <>
0125     struct equal_impl<set_tag, set_tag> {
0126         template <typename S1, typename S2>
0127         static constexpr auto equal_helper(S1 const& s1, S2 const& s2, hana::true_)
0128         { return hana::is_subset(s1, s2); }
0129
0130         template <typename S1, typename S2>
0131         static constexpr auto equal_helper(S1 const&, S2 const&, hana::false_)
0132         { return hana::false_c; }
0133
0134         template <typename S1, typename S2>
0135         static constexpr decltype(auto) apply(S1&& s1, S2&& s2) {
0136             return equal_impl::equal_helper(s1, s2, hana::bool_c<
0137                 decltype(hana::length(s1.storage))::value ==
0138                 decltype(hana::length(s2.storage))::value
0139             >);
0140         }
0141     };
0142
0143     //////////////////////////////////////////////////////////////////////////
0144     // Foldable
0145     //////////////////////////////////////////////////////////////////////////
0146     template <>
0147     struct unpack_impl<set_tag> {
0148         template <typename Set, typename F>
0149         static constexpr decltype(auto) apply(Set&& set, F&& f) {
0150             return hana::unpack(static_cast<Set&&>(set).storage,
0151                                 static_cast<F&&>(f));
0152         }
0153     };
0154
0155     //////////////////////////////////////////////////////////////////////////
0156     // Searchable
0157     //////////////////////////////////////////////////////////////////////////
0158     template <>
0159     struct find_if_impl<set_tag> {
0160         template <typename Xs, typename Pred>
0161         static constexpr auto apply(Xs&& xs, Pred&& pred) {
0162             return hana::find_if(static_cast<Xs&&>(xs).storage, static_cast<Pred&&>(pred));
0163         }
0164     };
0165
0166     template <>
0167     struct any_of_impl<set_tag> {
0168         template <typename Pred>
0169         struct any_of_helper {
0170             Pred const& pred;
0171             template <typename ...X>
0172             constexpr auto operator()(X const& ...x) const {
0173                 return hana::or_(pred(x)...);
0174             }
0175             constexpr auto operator()() const {
0176                 return hana::false_c;
0177             }
0178         };
0179
0180         template <typename Xs, typename Pred>
0181         static constexpr auto apply(Xs const& xs, Pred const& pred) {
0182             return hana::unpack(xs.storage, any_of_helper<Pred>{pred});
0183         }
0184     };
0185
0186     template <>
0187     struct is_subset_impl<set_tag, set_tag> {
0188         template <typename Ys>
0189         struct all_contained {
0190             Ys const& ys;
0191             template <typename ...X>
0192             constexpr auto operator()(X const& ...x) const {
0193                 return hana::bool_c<detail::fast_and<
0194                     hana::value<decltype(hana::contains(ys, x))>()...
0195                 >::value>;
0196             }
0197         };
0198
0199         template <typename Xs, typename Ys>
0200         static constexpr auto apply(Xs const& xs, Ys const& ys) {
0201             return hana::unpack(xs, all_contained<Ys>{ys});
0202         }
0203     };
0204
0205     //////////////////////////////////////////////////////////////////////////
0206     // Conversions
0207     //////////////////////////////////////////////////////////////////////////
0208     template <typename F>
0209     struct to_impl<set_tag, F, when<hana::Foldable<F>::value>> {
0210         template <typename Xs>
0211         static constexpr decltype(auto) apply(Xs&& xs) {
0212             return hana::fold_left(static_cast<Xs&&>(xs),
0213                                    hana::make_set(),
0214                                    hana::insert);
0215         }
0216     };
0217
0218     //////////////////////////////////////////////////////////////////////////
0219     // insert
0220     //////////////////////////////////////////////////////////////////////////
0221     template <>
0222     struct insert_impl<set_tag> {
0223         template <typename Xs, typename X, typename Indices>
0224         static constexpr auto
0225         insert_helper(Xs&& xs, X&&, hana::true_, Indices) {
0226             return static_cast<Xs&&>(xs);
0227         }
0228
0229         template <typename Xs, typename X, std::size_t ...n>
0230         static constexpr auto
0231         insert_helper(Xs&& xs, X&& x, hana::false_, std::index_sequence<n...>) {
0232             return hana::make_set(
0233                 hana::at_c<n>(static_cast<Xs&&>(xs).storage)..., static_cast<X&&>(x)
0234             );
0235         }
0236
0237         template <typename Xs, typename X>
0238         static constexpr auto apply(Xs&& xs, X&& x) {
0239             constexpr bool c = hana::value<decltype(hana::contains(xs, x))>();
0240             constexpr std::size_t size = std::remove_reference<Xs>::type::size;
0241             return insert_helper(static_cast<Xs&&>(xs), static_cast<X&&>(x),
0242                                  hana::bool_c<c>, std::make_index_sequence<size>{});
0243         }
0244     };
0245
0246     //////////////////////////////////////////////////////////////////////////
0247     // erase_key
0248     //////////////////////////////////////////////////////////////////////////
0249     template <>
0250     struct erase_key_impl<set_tag> {
0251         template <typename Xs, typename X>
0252         static constexpr decltype(auto) apply(Xs&& xs, X&& x) {
0253             return hana::unpack(
0254                 hana::remove(static_cast<Xs&&>(xs).storage,
0255                              static_cast<X&&>(x)),
0256                 hana::make_set
0257             );
0258         }
0259     };
0260
0261     //////////////////////////////////////////////////////////////////////////
0262     // intersection
0263     //////////////////////////////////////////////////////////////////////////
0264     namespace detail {
0265         template <typename Ys>
0266         struct set_insert_if_contains {
0267             Ys const& ys;
0268
0269             template <typename Result, typename Key>
0270             static constexpr auto helper(Result&& result, Key&& key, hana::true_) {
0271                 return hana::insert(static_cast<Result&&>(result), static_cast<Key&&>(key));
0272             }
0273
0274             template <typename Result, typename Key>
0275             static constexpr auto helper(Result&& result, Key&&, hana::false_) {
0276                 return static_cast<Result&&>(result);
0277             }
0278
0279             template <typename Result, typename Key>
0280             constexpr auto operator()(Result&& result, Key&& key) const {
0281                 constexpr bool keep = hana::value<decltype(hana::contains(ys, key))>();
0282                 return set_insert_if_contains::helper(static_cast<Result&&>(result),
0283                                                       static_cast<Key&&>(key),
0284                                                       hana::bool_c<keep>);
0285             }
0286         };
0287     }
0288
0289     template <>
0290     struct intersection_impl<set_tag> {
0291         template <typename Xs, typename Ys>
0292         static constexpr auto apply(Xs&& xs, Ys const& ys) {
0293             return hana::fold_left(static_cast<Xs&&>(xs), hana::make_set(),
0294                                    detail::set_insert_if_contains<Ys>{ys});
0295         }
0296     };
0297
0298     //////////////////////////////////////////////////////////////////////////
0299     // union_
0300     //////////////////////////////////////////////////////////////////////////
0301     template <>
0302     struct union_impl<set_tag> {
0303         template <typename Xs, typename Ys>
0304         static constexpr auto apply(Xs&& xs, Ys&& ys) {
0305             return hana::fold_left(static_cast<Xs&&>(xs), static_cast<Ys&&>(ys),
0306                                    hana::insert);
0307         }
0308     };
0309
0310     //////////////////////////////////////////////////////////////////////////
0311     // difference
0312     //////////////////////////////////////////////////////////////////////////
0313     template <>
0314     struct difference_impl<set_tag> {
0315         template <typename Xs, typename Ys>
0316         static constexpr auto apply(Xs&& xs, Ys&& ys) {
0317             return hana::fold_left(static_cast<Ys&&>(ys), static_cast<Xs&&>(xs),
0318                                    hana::erase_key);
0319         }
0320     };
0321 }} // end namespace boost::hana
0322
0323 #endif // !BOOST_HANA_SET_HPP