query/detail/find_if.hpp

0001 /*=============================================================================
0002     Copyright (c) 2001-2011 Joel de Guzman
0003     Copyright (c) 2007 Dan Marsden
0004     Copyright (c) 2009 Christopher Schmidt
0005     Copyright (c) 2018 Kohei Takahashi
0006
0007     Distributed under the Boost Software License, Version 1.0. (See accompanying
0008     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0009 ==============================================================================*/
0010 #if !defined(FUSION_FIND_IF_05052005_1107)
0011 #define FUSION_FIND_IF_05052005_1107
0012
0013 #include <boost/fusion/support/config.hpp>
0014 #include <boost/mpl/apply.hpp>
0015 #include <boost/mpl/eval_if.hpp>
0016 #include <boost/mpl/identity.hpp>
0017 #include <boost/mpl/or.hpp>
0018 #include <boost/fusion/iterator/advance.hpp>
0019 #include <boost/fusion/iterator/distance.hpp>
0020 #include <boost/fusion/iterator/equal_to.hpp>
0021 #include <boost/fusion/iterator/next.hpp>
0022 #include <boost/fusion/sequence/intrinsic/begin.hpp>
0023 #include <boost/fusion/sequence/intrinsic/end.hpp>
0024 #include <boost/fusion/support/category_of.hpp>
0025 #include <boost/core/enable_if.hpp>
0026
0027 namespace boost { namespace fusion { namespace detail
0028 {
0029     template <typename Iterator, typename Pred>
0030     struct apply_filter
0031     {
0032         typedef typename mpl::apply1<
0033             Pred, Iterator>::type type;
0034         BOOST_STATIC_CONSTANT(int, value = type::value);
0035     };
0036
0037     template <typename First, typename Last, typename Pred>
0038     struct main_find_if;
0039
0040     template <typename First, typename Last, typename Pred>
0041     struct recursive_find_if
0042     {
0043         typedef typename
0044             main_find_if<
0045                 typename result_of::next<First>::type, Last, Pred
0046             >::type
0047         type;
0048     };
0049
0050     template <typename First, typename Last, typename Pred>
0051     struct main_find_if
0052     {
0053         typedef mpl::or_<
0054             result_of::equal_to<First, Last>
0055           , apply_filter<First, Pred> >
0056         filter;
0057
0058         typedef typename
0059             mpl::eval_if<
0060                 filter
0061               , mpl::identity<First>
0062               , recursive_find_if<First, Last, Pred>
0063             >::type
0064         type;
0065     };
0066
0067     template<
0068         typename First, typename Last,
0069         typename Pred, bool>
0070     struct choose_find_if;
0071
0072     template<typename First, typename Last, typename Pred>
0073     struct choose_find_if<First, Last, Pred, false>
0074         : main_find_if<First, Last, Pred>
0075     {};
0076
0077     template<typename Iter, typename Pred, int n, int unrolling>
0078     struct unroll_again;
0079
0080     template <typename Iter, typename Pred, int offset>
0081     struct apply_offset_filter
0082     {
0083         typedef typename result_of::advance_c<Iter, offset>::type Shifted;
0084         typedef typename
0085             mpl::apply1<
0086                 Pred
0087               , Shifted
0088             >::type
0089         type;
0090         BOOST_STATIC_CONSTANT(int, value = type::value);
0091     };
0092
0093     template<typename Iter, typename Pred, int n>
0094     struct unrolled_find_if
0095     {
0096         typedef typename mpl::eval_if<
0097             apply_filter<Iter, Pred>,
0098             mpl::identity<Iter>,
0099             mpl::eval_if<
0100               apply_offset_filter<Iter, Pred, 1>,
0101               result_of::advance_c<Iter, 1>,
0102               mpl::eval_if<
0103                 apply_offset_filter<Iter, Pred, 2>,
0104                 result_of::advance_c<Iter, 2>,
0105                 mpl::eval_if<
0106                   apply_offset_filter<Iter, Pred, 3>,
0107                   result_of::advance_c<Iter, 3>,
0108                   unroll_again<
0109                     Iter,
0110                     Pred,
0111                     n,
0112                     4> > > > >::type type;
0113     };
0114
0115     template<typename Iter, typename Pred>
0116     struct unrolled_find_if<Iter, Pred, 3>
0117     {
0118         typedef typename mpl::eval_if<
0119             apply_filter<Iter, Pred>,
0120             mpl::identity<Iter>,
0121             mpl::eval_if<
0122               apply_offset_filter<Iter, Pred, 1>,
0123               result_of::advance_c<Iter, 1>,
0124               mpl::eval_if<
0125                 apply_offset_filter<Iter, Pred, 2>,
0126                 result_of::advance_c<Iter, 2>,
0127                 result_of::advance_c<Iter, 3> > > >::type type;
0128     };
0129
0130     template<typename Iter, typename Pred>
0131     struct unrolled_find_if<Iter, Pred, 2>
0132     {
0133         typedef typename mpl::eval_if<
0134             apply_filter<Iter, Pred>,
0135             mpl::identity<Iter>,
0136             mpl::eval_if<
0137               apply_offset_filter<Iter, Pred, 1>,
0138               result_of::advance_c<Iter, 1>,
0139               result_of::advance_c<Iter, 2> > >::type type;
0140     };
0141
0142     template<typename Iter, typename Pred>
0143     struct unrolled_find_if<Iter, Pred, 1>
0144     {
0145         typedef typename mpl::eval_if<
0146             apply_filter<Iter, Pred>,
0147             mpl::identity<Iter>,
0148             result_of::advance_c<Iter, 1> >::type type;
0149     };
0150
0151     template<typename Iter, typename Pred, int n, int unrolling>
0152     struct unroll_again
0153     {
0154         typedef typename unrolled_find_if<
0155             typename result_of::advance_c<Iter, unrolling>::type,
0156             Pred,
0157             n-unrolling>::type type;
0158     };
0159
0160     template<typename Iter, typename Pred>
0161     struct unrolled_find_if<Iter, Pred, 0>
0162     {
0163         typedef Iter type;
0164     };
0165
0166     template<typename First, typename Last, typename Pred>
0167     struct choose_find_if<First, Last, Pred, true>
0168     {
0169         typedef typename result_of::distance<First, Last>::type N;
0170         typedef typename unrolled_find_if<First, Pred, N::value>::type type;
0171     };
0172
0173     template <typename First, typename Last, typename Pred>
0174     struct static_find_if
0175     {
0176         typedef typename
0177             choose_find_if<
0178                 First
0179               , Last
0180               , Pred
0181               , traits::is_random_access<First>::value
0182             >::type
0183         type;
0184
0185         template <typename Iterator>
0186         BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
0187         static type
0188         recursive_call(Iterator const& iter, mpl::true_)
0189         {
0190             return iter;
0191         }
0192
0193         template <typename Iterator>
0194         BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
0195         static type
0196         recursive_call(Iterator const& iter, mpl::false_)
0197         {
0198             return recursive_call(fusion::next(iter));
0199         }
0200
0201         template <typename Iterator>
0202         BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
0203         static type
0204         recursive_call(Iterator const& iter)
0205         {
0206             typedef result_of::equal_to<Iterator, type> found;
0207             return recursive_call(iter, found());
0208         }
0209
0210         template <typename Iterator>
0211         BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
0212         static typename boost::disable_if<traits::is_random_access<Iterator>, type>::type
0213         iter_call(Iterator const& iter)
0214         {
0215             return recursive_call(iter);
0216         }
0217
0218         template <typename Iterator>
0219         BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
0220         static typename boost::enable_if<traits::is_random_access<Iterator>, type>::type
0221         iter_call(Iterator const& iter)
0222         {
0223             typedef typename result_of::distance<Iterator, type>::type N;
0224             return fusion::advance<N>(iter);
0225         }
0226
0227         template <typename Sequence>
0228         BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED
0229         static type
0230         call(Sequence& seq)
0231         {
0232             return iter_call(fusion::begin(seq));
0233         }
0234     };
0235
0236     template <typename Sequence, typename Pred>
0237     struct result_of_find_if
0238     {
0239         typedef
0240             static_find_if<
0241                 typename result_of::begin<Sequence>::type
0242               , typename result_of::end<Sequence>::type
0243               , Pred
0244             >
0245         filter;
0246
0247         typedef typename filter::type type;
0248     };
0249 }}}
0250
0251 #endif