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); count_if(Sequence const & seq,F f)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 252