boost/fusion/algorithm/query/detail/find_if.hpp

   1 /*=============================================================================
   2     Copyright (c) 2001-2011 Joel de Guzman
   3     Copyright (c) 2007 Dan Marsden
   4     Copyright (c) 2009 Christopher Schmidt
   5
   6     Distributed under the Boost Software License, Version 1.0. (See accompanying
   7     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   8 ==============================================================================*/
   9 #if !defined(FUSION_FIND_IF_05052005_1107)
  10 #define FUSION_FIND_IF_05052005_1107
  11
  12 #include <boost/fusion/support/config.hpp>
  13 #include <boost/mpl/apply.hpp>
  14 #include <boost/mpl/eval_if.hpp>
  15 #include <boost/mpl/identity.hpp>
  16 #include <boost/mpl/lambda.hpp>
  17 #include <boost/mpl/or.hpp>
  18 #include <boost/fusion/iterator/advance.hpp>
  19 #include <boost/fusion/iterator/distance.hpp>
  20 #include <boost/fusion/iterator/equal_to.hpp>
  21 #include <boost/fusion/iterator/next.hpp>
  22 #include <boost/fusion/sequence/intrinsic/begin.hpp>
  23 #include <boost/fusion/sequence/intrinsic/end.hpp>
  24 #include <boost/fusion/support/category_of.hpp>
  25
  26 namespace boost { namespace fusion {
  27     struct random_access_traversal_tag;
  28 namespace detail
  29 {
  30     template <typename Iterator, typename Pred>
  31     struct apply_filter
  32     {
  33         typedef typename mpl::apply1<
  34             Pred, Iterator>::type type;
  35         BOOST_STATIC_CONSTANT(int, value = type::value);
  36     };
  37
  38     template <typename First, typename Last, typename Pred>
  39     struct main_find_if;
  40
  41     template <typename First, typename Last, typename Pred>
  42     struct recursive_find_if
  43     {
  44         typedef typename
  45             main_find_if<
  46                 typename result_of::next<First>::type, Last, Pred
  47             >::type
  48         type;
  49     };
  50
  51     template <typename First, typename Last, typename Pred>
  52     struct main_find_if
  53     {
  54         typedef mpl::or_<
  55             result_of::equal_to<First, Last>
  56           , apply_filter<First, Pred> >
  57         filter;
  58
  59         typedef typename
  60             mpl::eval_if<
  61                 filter
  62               , mpl::identity<First>
  63               , recursive_find_if<First, Last, Pred>
  64             >::type
  65         type;
  66     };
  67
  68     template<
  69         typename First, typename Last,
  70         typename Pred, bool>
  71     struct choose_find_if;
  72
  73     template<typename First, typename Last, typename Pred>
  74     struct choose_find_if<First, Last, Pred, false>
  75         : main_find_if<First, Last, Pred>
  76     {};
  77
  78     template<typename Iter, typename Pred, int n, int unrolling>
  79     struct unroll_again;
  80
  81     template <typename Iter, typename Pred, int offset>
  82     struct apply_offset_filter
  83     {
  84         typedef typename result_of::advance_c<Iter, offset>::type Shifted;
  85         typedef typename
  86             mpl::apply1<
  87                 Pred
  88               , Shifted
  89             >::type
  90         type;
  91         BOOST_STATIC_CONSTANT(int, value = type::value);
  92     };
  93
  94     template<typename Iter, typename Pred, int n>
  95     struct unrolled_find_if
  96     {
  97         typedef typename mpl::eval_if<
  98             apply_filter<Iter, Pred>,
  99             mpl::identity<Iter>,
 100             mpl::eval_if<
 101               apply_offset_filter<Iter, Pred, 1>,
 102               result_of::advance_c<Iter, 1>,
 103               mpl::eval_if<
 104                 apply_offset_filter<Iter, Pred, 2>,
 105                 result_of::advance_c<Iter, 2>,
 106                 mpl::eval_if<
 107                   apply_offset_filter<Iter, Pred, 3>,
 108                   result_of::advance_c<Iter, 3>,
 109                   unroll_again<
 110                     Iter,
 111                     Pred,
 112                     n,
 113                     4> > > > >::type type;
 114     };
 115
 116     template<typename Iter, typename Pred>
 117     struct unrolled_find_if<Iter, Pred, 3>
 118     {
 119         typedef typename mpl::eval_if<
 120             apply_filter<Iter, Pred>,
 121             mpl::identity<Iter>,
 122             mpl::eval_if<
 123               apply_offset_filter<Iter, Pred, 1>,
 124               result_of::advance_c<Iter, 1>,
 125               mpl::eval_if<
 126                 apply_offset_filter<Iter, Pred, 2>,
 127                 result_of::advance_c<Iter, 2>,
 128                 result_of::advance_c<Iter, 3> > > >::type type;
 129     };
 130
 131     template<typename Iter, typename Pred>
 132     struct unrolled_find_if<Iter, Pred, 2>
 133     {
 134         typedef typename mpl::eval_if<
 135             apply_filter<Iter, Pred>,
 136             mpl::identity<Iter>,
 137             mpl::eval_if<
 138               apply_offset_filter<Iter, Pred, 1>,
 139               result_of::advance_c<Iter, 1>,
 140               result_of::advance_c<Iter, 2> > >::type type;
 141     };
 142
 143     template<typename Iter, typename Pred>
 144     struct unrolled_find_if<Iter, Pred, 1>
 145     {
 146         typedef typename mpl::eval_if<
 147             apply_filter<Iter, Pred>,
 148             mpl::identity<Iter>,
 149             result_of::advance_c<Iter, 1> >::type type;
 150     };
 151
 152     template<typename Iter, typename Pred, int n, int unrolling>
 153     struct unroll_again
 154     {
 155         typedef typename unrolled_find_if<
 156             typename result_of::advance_c<Iter, unrolling>::type,
 157             Pred,
 158             n-unrolling>::type type;
 159     };
 160
 161     template<typename Iter, typename Pred>
 162     struct unrolled_find_if<Iter, Pred, 0>
 163     {
 164         typedef Iter type;
 165     };
 166
 167     template<typename First, typename Last, typename Pred>
 168     struct choose_find_if<First, Last, Pred, true>
 169     {
 170         typedef typename result_of::distance<First, Last>::type N;
 171         typedef typename unrolled_find_if<First, Pred, N::value>::type type;
 172     };
 173
 174     template <typename First, typename Last, typename Pred>
 175     struct static_find_if
 176     {
 177         typedef typename
 178             choose_find_if<
 179                 First
 180               , Last
 181               , typename mpl::lambda<Pred>::type
 182               , is_base_of<random_access_traversal_tag, typename traits::category_of<First>::type>::value
 183             >::type
 184         type;
 185
 186         template <typename Iterator>
 187         BOOST_FUSION_GPU_ENABLED
 188         static type
 189         recursive_call(Iterator const& iter, mpl::true_)
 190         {
 191             return iter;
 192         }
 193
 194         template <typename Iterator>
 195         BOOST_FUSION_GPU_ENABLED
 196         static type
 197         recursive_call(Iterator const& iter, mpl::false_)
 198         {
 199             return recursive_call(fusion::next(iter));
 200         }
 201
 202         template <typename Iterator>
 203         BOOST_FUSION_GPU_ENABLED
 204         static type
 205         recursive_call(Iterator const& iter)
 206         {
 207             typedef result_of::equal_to<Iterator, type> found;
 208             return recursive_call(iter, found());
 209         }
 210
 211         template <typename Iterator, typename Tag>
 212         BOOST_FUSION_GPU_ENABLED
 213         static type
 214         choose_call(Iterator const& iter, Tag)
 215         {
 216             return recursive_call(iter);
 217         }
 218
 219         template <typename Iterator>
 220         BOOST_FUSION_GPU_ENABLED
 221         static type
 222         choose_call(Iterator const& iter, random_access_traversal_tag)
 223         {
 224             typedef typename result_of::distance<Iterator, type>::type N;
 225             return fusion::advance<N>(iter);
 226         }
 227
 228         template <typename Iterator>
 229         BOOST_FUSION_GPU_ENABLED
 230         static type
 231         iter_call(Iterator const& iter)
 232         {
 233             return choose_call(iter, typename traits::category_of<Iterator>::type());
 234         }
 235
 236         template <typename Sequence>
 237         BOOST_FUSION_GPU_ENABLED
 238         static type
 239         call(Sequence& seq)
 240         {
 241             return iter_call(fusion::begin(seq));
 242         }
 243     };
 244
 245     template <typename Sequence, typename Pred>
 246     struct result_of_find_if
 247     {
 248         typedef
 249             static_find_if<
 250                 typename result_of::begin<Sequence>::type
 251               , typename result_of::end<Sequence>::type
 252               , Pred
 253             >
 254         filter;
 255
 256         typedef typename filter::type type;
 257     };
 258 }}}
 259
 260 #endif