1 /*! 2 @file 3 Defines `boost::hana::filter`. 4 5 @copyright Louis Dionne 2013-2017 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_FILTER_HPP 11 #define BOOST_HANA_FILTER_HPP 12 13 #include <boost/hana/fwd/filter.hpp> 14 15 #include <boost/hana/at.hpp> 16 #include <boost/hana/bool.hpp> 17 #include <boost/hana/chain.hpp> 18 #include <boost/hana/concept/monad_plus.hpp> 19 #include <boost/hana/concept/sequence.hpp> 20 #include <boost/hana/config.hpp> 21 #include <boost/hana/core/dispatch.hpp> 22 #include <boost/hana/core/make.hpp> 23 #include <boost/hana/detail/algorithm.hpp> 24 #include <boost/hana/detail/array.hpp> 25 #include <boost/hana/detail/decay.hpp> 26 #include <boost/hana/empty.hpp> 27 #include <boost/hana/lift.hpp> 28 #include <boost/hana/unpack.hpp> 29 30 #include <cstddef> 31 #include <utility> 32 33 34 BOOST_HANA_NAMESPACE_BEGIN 35 //! @cond 36 template <typename Xs, typename Pred> operator ()(Xs && xs,Pred && pred) const37 constexpr auto filter_t::operator()(Xs&& xs, Pred&& pred) const { 38 using M = typename hana::tag_of<Xs>::type; 39 using Filter = BOOST_HANA_DISPATCH_IF(filter_impl<M>, 40 hana::MonadPlus<M>::value 41 ); 42 43 #ifndef BOOST_HANA_CONFIG_DISABLE_CONCEPT_CHECKS 44 static_assert(hana::MonadPlus<M>::value, 45 "hana::filter(xs, pred) requires 'xs' to be a MonadPlus"); 46 #endif 47 48 return Filter::apply(static_cast<Xs&&>(xs), 49 static_cast<Pred&&>(pred)); 50 } 51 //! @endcond 52 53 namespace detail { 54 template <typename Pred, typename M> 55 struct lift_or_empty { 56 template <typename X> helperdetail::lift_or_empty57 static constexpr auto helper(X&& x, hana::true_) 58 { return hana::lift<M>(static_cast<X&&>(x)); } 59 60 template <typename X> helperdetail::lift_or_empty61 static constexpr auto helper(X&&, hana::false_) 62 { return hana::empty<M>(); } 63 64 template <typename X> operator ()detail::lift_or_empty65 constexpr auto operator()(X&& x) const { 66 constexpr bool cond = decltype(std::declval<Pred>()(x))::value; 67 return helper(static_cast<X&&>(x), hana::bool_c<cond>); 68 } 69 }; 70 } 71 72 template <typename M, bool condition> 73 struct filter_impl<M, when<condition>> : default_ { 74 template <typename Xs, typename Pred> applyfilter_impl75 static constexpr decltype(auto) apply(Xs&& xs, Pred const&) { 76 return hana::chain(static_cast<Xs&&>(xs), 77 detail::lift_or_empty<Pred, M>{} 78 ); 79 } 80 }; 81 82 namespace detail { 83 template <bool ...b> 84 struct filter_indices { compute_indicesdetail::filter_indices85 static constexpr auto compute_indices() { 86 constexpr bool bs[] = {b..., false}; // avoid empty array 87 constexpr std::size_t N = detail::count(bs, bs + sizeof(bs), true); 88 detail::array<std::size_t, N> indices{}; 89 std::size_t* keep = &indices[0]; 90 for (std::size_t i = 0; i < sizeof...(b); ++i) 91 if (bs[i]) 92 *keep++ = i; 93 return indices; 94 } 95 96 static constexpr auto cached_indices = compute_indices(); 97 }; 98 99 template <typename Pred> 100 struct make_filter_indices { 101 Pred const& pred; 102 template <typename ...X> operator ()detail::make_filter_indices103 auto operator()(X&& ...x) const -> filter_indices< 104 static_cast<bool>(detail::decay< 105 decltype(pred(static_cast<X&&>(x))) 106 >::type::value)... 107 > { return {}; } 108 }; 109 } 110 111 template <typename S> 112 struct filter_impl<S, when<Sequence<S>::value>> { 113 template <typename Indices, typename Xs, std::size_t ...i> filter_helperfilter_impl114 static constexpr auto filter_helper(Xs&& xs, std::index_sequence<i...>) { 115 return hana::make<S>( 116 hana::at_c<Indices::cached_indices[i]>(static_cast<Xs&&>(xs))... 117 ); 118 } 119 120 template <typename Xs, typename Pred> applyfilter_impl121 static constexpr auto apply(Xs&& xs, Pred const& pred) { 122 using Indices = decltype( 123 hana::unpack(static_cast<Xs&&>(xs), 124 detail::make_filter_indices<Pred>{pred}) 125 ); 126 127 return filter_impl::filter_helper<Indices>( 128 static_cast<Xs&&>(xs), 129 std::make_index_sequence<Indices::cached_indices.size()>{} 130 ); 131 } 132 }; 133 BOOST_HANA_NAMESPACE_END 134 135 #endif // !BOOST_HANA_FILTER_HPP 136