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