boost/hana/filter.hpp

0001 /*!
0002 @file
0003 Defines `boost::hana::filter`.
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_FILTER_HPP
0011 #define BOOST_HANA_FILTER_HPP
0012
0013 #include <boost/hana/fwd/filter.hpp>
0014
0015 #include <boost/hana/at.hpp>
0016 #include <boost/hana/bool.hpp>
0017 #include <boost/hana/chain.hpp>
0018 #include <boost/hana/concept/monad_plus.hpp>
0019 #include <boost/hana/concept/sequence.hpp>
0020 #include <boost/hana/config.hpp>
0021 #include <boost/hana/core/dispatch.hpp>
0022 #include <boost/hana/core/make.hpp>
0023 #include <boost/hana/detail/algorithm.hpp>
0024 #include <boost/hana/detail/array.hpp>
0025 #include <boost/hana/detail/decay.hpp>
0026 #include <boost/hana/empty.hpp>
0027 #include <boost/hana/lift.hpp>
0028 #include <boost/hana/unpack.hpp>
0029
0030 #include <cstddef>
0031 #include <utility>
0032
0033
0034 namespace boost { namespace hana {
0035     //! @cond
0036     template <typename Xs, typename Pred>
0037     constexpr auto filter_t::operator()(Xs&& xs, Pred&& pred) const {
0038         using M = typename hana::tag_of<Xs>::type;
0039         using Filter = BOOST_HANA_DISPATCH_IF(filter_impl<M>,
0040             hana::MonadPlus<M>::value
0041         );
0042
0043     #ifndef BOOST_HANA_CONFIG_DISABLE_CONCEPT_CHECKS
0044         static_assert(hana::MonadPlus<M>::value,
0045         "hana::filter(xs, pred) requires 'xs' to be a MonadPlus");
0046     #endif
0047
0048         return Filter::apply(static_cast<Xs&&>(xs),
0049                              static_cast<Pred&&>(pred));
0050     }
0051     //! @endcond
0052
0053     namespace detail {
0054         template <typename Pred, typename M>
0055         struct lift_or_empty {
0056             template <typename X>
0057             static constexpr auto helper(X&& x, hana::true_)
0058             { return hana::lift<M>(static_cast<X&&>(x)); }
0059
0060             template <typename X>
0061             static constexpr auto helper(X&&, hana::false_)
0062             { return hana::empty<M>(); }
0063
0064             template <typename X>
0065             constexpr auto operator()(X&& x) const {
0066                 constexpr bool cond = decltype(std::declval<Pred>()(x))::value;
0067                 return helper(static_cast<X&&>(x), hana::bool_c<cond>);
0068             }
0069         };
0070     }
0071
0072     template <typename M, bool condition>
0073     struct filter_impl<M, when<condition>> : default_ {
0074         template <typename Xs, typename Pred>
0075         static constexpr decltype(auto) apply(Xs&& xs, Pred const&) {
0076             return hana::chain(static_cast<Xs&&>(xs),
0077                 detail::lift_or_empty<Pred, M>{}
0078             );
0079         }
0080     };
0081
0082     namespace detail {
0083         template <bool ...b>
0084         struct filter_indices {
0085             static constexpr auto compute_indices() {
0086                 constexpr bool bs[] = {b..., false}; // avoid empty array
0087                 constexpr std::size_t N = detail::count(bs, bs + sizeof(bs), true);
0088                 detail::array<std::size_t, N> indices{};
0089                 std::size_t* keep = &indices[0];
0090                 for (std::size_t i = 0; i < sizeof...(b); ++i)
0091                     if (bs[i])
0092                         *keep++ = i;
0093                 return indices;
0094             }
0095
0096             static constexpr auto cached_indices = compute_indices();
0097         };
0098
0099         template <typename Pred>
0100         struct make_filter_indices {
0101             Pred const& pred;
0102             template <typename ...X>
0103             auto operator()(X&& ...x) const -> filter_indices<
0104                 static_cast<bool>(detail::decay<
0105                     decltype(pred(static_cast<X&&>(x)))
0106                 >::type::value)...
0107             > { return {}; }
0108         };
0109     }
0110
0111     template <typename S>
0112     struct filter_impl<S, when<Sequence<S>::value>> {
0113         template <typename Indices, typename Xs, std::size_t ...i>
0114         static constexpr auto filter_helper(Xs&& xs, std::index_sequence<i...>) {
0115             return hana::make<S>(
0116                 hana::at_c<Indices::cached_indices[i]>(static_cast<Xs&&>(xs))...
0117             );
0118         }
0119
0120         template <typename Xs, typename Pred>
0121         static constexpr auto apply(Xs&& xs, Pred const& pred) {
0122             using Indices = decltype(
0123                 hana::unpack(static_cast<Xs&&>(xs),
0124                              detail::make_filter_indices<Pred>{pred})
0125             );
0126
0127             return filter_impl::filter_helper<Indices>(
0128                 static_cast<Xs&&>(xs),
0129                 std::make_index_sequence<Indices::cached_indices.size()>{}
0130             );
0131         }
0132     };
0133 }} // end namespace boost::hana
0134
0135 #endif // !BOOST_HANA_FILTER_HPP