1 /*============================================================================= 2 Copyright (c) 2011 Eric Niebler 3 4 Distributed under the Boost Software License, Version 1.0. (See accompanying 5 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 6 ==============================================================================*/ 7 #if !defined(BOOST_FUSION_SEGMENTED_FOLD_UNTIL_IMPL_HPP_INCLUDED) 8 #define BOOST_FUSION_SEGMENTED_FOLD_UNTIL_IMPL_HPP_INCLUDED 9 10 #include <boost/fusion/support/config.hpp> 11 #include <boost/mpl/bool.hpp> 12 #include <boost/mpl/eval_if.hpp> 13 #include <boost/mpl/identity.hpp> 14 #include <boost/utility/result_of.hpp> 15 #include <boost/type_traits/add_const.hpp> 16 #include <boost/type_traits/remove_reference.hpp> 17 18 #include <boost/fusion/support/void.hpp> 19 #include <boost/fusion/container/list/cons_fwd.hpp> 20 #include <boost/fusion/sequence/intrinsic_fwd.hpp> 21 #include <boost/fusion/iterator/equal_to.hpp> 22 #include <boost/fusion/iterator/deref.hpp> 23 #include <boost/fusion/iterator/next.hpp> 24 #include <boost/fusion/support/is_segmented.hpp> 25 #include <boost/fusion/sequence/intrinsic/segments.hpp> 26 27 // fun(seq, state, context) 28 // seq: a non-segmented range 29 // state: the state of the fold so far 30 // context: the path to the current range 31 // 32 // returns: (state', fcontinue) 33 34 namespace boost { namespace fusion 35 { 36 template <typename First, typename Last> 37 struct iterator_range; 38 39 template <typename Context> 40 struct segmented_iterator; 41 42 namespace result_of 43 { 44 template <typename Cur, typename Context> 45 struct make_segmented_iterator 46 { 47 typedef 48 iterator_range< 49 Cur 50 , typename result_of::end< 51 typename remove_reference< 52 typename add_const< 53 typename result_of::deref< 54 typename Context::car_type::begin_type 55 >::type 56 >::type 57 >::type 58 >::type 59 > 60 range_type; 61 62 typedef 63 segmented_iterator<cons<range_type, Context> > 64 type; 65 }; 66 } 67 68 template <typename Cur, typename Context> 69 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED 70 inline typename result_of::make_segmented_iterator<Cur, Context>::type make_segmented_iterator(Cur const & cur,Context const & context)71 make_segmented_iterator(Cur const& cur, Context const& context) 72 { 73 typedef result_of::make_segmented_iterator<Cur, Context> impl_type; 74 typedef typename impl_type::type type; 75 typedef typename impl_type::range_type range_type; 76 return type(cons<range_type, Context>(range_type(cur, fusion::end(*context.car.first)), context)); 77 } 78 79 namespace detail 80 { 81 template < 82 typename Begin 83 , typename End 84 , typename State 85 , typename Context 86 , typename Fun 87 , bool IsEmpty 88 > 89 struct segmented_fold_until_iterate_skip_empty; 90 91 template < 92 typename Begin 93 , typename End 94 , typename State 95 , typename Context 96 , typename Fun 97 , bool IsDone = result_of::equal_to<Begin, End>::type::value 98 > 99 struct segmented_fold_until_iterate; 100 101 template < 102 typename Sequence 103 , typename State 104 , typename Context 105 , typename Fun 106 , bool IsSegmented = traits::is_segmented<Sequence>::type::value 107 > 108 struct segmented_fold_until_impl; 109 110 template <typename Segments, typename State, typename Context, typename Fun> 111 struct segmented_fold_until_on_segments; 112 113 //auto push_context(cur, end, context) 114 //{ 115 // return push_back(context, segment_sequence(iterator_range(cur, end))); 116 //} 117 118 template <typename Cur, typename End, typename Context> 119 struct push_context 120 { 121 typedef iterator_range<Cur, End> range_type; 122 typedef cons<range_type, Context> type; 123 124 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::push_context125 static type call(Cur const& cur, End const& end, Context const& context) 126 { 127 return cons<range_type, Context>(range_type(cur, end), context); 128 } 129 }; 130 131 //auto make_segmented_iterator(cur, end, context) 132 //{ 133 // return segmented_iterator(push_context(cur, end, context)); 134 //} 135 // 136 //auto segmented_fold_until_impl(seq, state, context, fun) 137 //{ 138 // if (is_segmented(seq)) 139 // { 140 // segmented_fold_until_on_segments(segments(seq), state, context, fun); 141 // } 142 // else 143 // { 144 // return fun(seq, state, context); 145 // } 146 //} 147 148 template < 149 typename Sequence 150 , typename State 151 , typename Context 152 , typename Fun 153 , bool IsSegmented 154 > 155 struct segmented_fold_until_impl 156 { 157 typedef 158 segmented_fold_until_on_segments< 159 typename remove_reference< 160 typename add_const< 161 typename result_of::segments<Sequence>::type 162 >::type 163 >::type 164 , State 165 , Context 166 , Fun 167 > 168 impl; 169 170 typedef typename impl::type type; 171 typedef typename impl::continue_type continue_type; 172 173 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::segmented_fold_until_impl174 static type call(Sequence& seq, State const& state, Context const& context, Fun const& fun) 175 { 176 return impl::call(fusion::segments(seq), state, context, fun); 177 } 178 }; 179 180 template < 181 typename Sequence 182 , typename State 183 , typename Context 184 , typename Fun 185 > 186 struct segmented_fold_until_impl<Sequence, State, Context, Fun, false> 187 { 188 typedef 189 typename Fun::template apply<Sequence, State, Context> 190 apply_type; 191 192 typedef typename apply_type::type type; 193 typedef typename apply_type::continue_type continue_type; 194 195 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::segmented_fold_until_impl196 static type call(Sequence& seq, State const& state, Context const& context, Fun const& fun) 197 { 198 return apply_type::call(seq, state, context, fun); 199 } 200 }; 201 202 //auto segmented_fold_until_on_segments(segs, state, context, fun) 203 //{ 204 // auto cur = begin(segs), end = end(segs); 205 // for (; cur != end; ++cur) 206 // { 207 // if (empty(*cur)) 208 // continue; 209 // auto context` = push_context(cur, end, context); 210 // state = segmented_fold_until_impl(*cur, state, context`, fun); 211 // if (!second(state)) 212 // return state; 213 // } 214 //} 215 216 template <typename Apply> 217 struct continue_wrap 218 { 219 typedef typename Apply::continue_type type; 220 }; 221 222 template <typename Begin, typename End, typename State, typename Context, typename Fun, bool IsEmpty> 223 struct segmented_fold_until_iterate_skip_empty 224 { 225 // begin != end and !empty(*begin) 226 typedef 227 push_context<Begin, End, Context> 228 push_context_impl; 229 230 typedef 231 typename push_context_impl::type 232 next_context_type; 233 234 typedef 235 segmented_fold_until_impl< 236 typename remove_reference< 237 typename add_const< 238 typename result_of::deref<Begin>::type 239 >::type 240 >::type 241 , State 242 , next_context_type 243 , Fun 244 > 245 fold_recurse_impl; 246 247 typedef 248 typename fold_recurse_impl::type 249 next_state_type; 250 251 typedef 252 segmented_fold_until_iterate< 253 typename result_of::next<Begin>::type 254 , End 255 , next_state_type 256 , Context 257 , Fun 258 > 259 next_iteration_impl; 260 261 typedef 262 typename mpl::eval_if< 263 typename fold_recurse_impl::continue_type 264 , next_iteration_impl 265 , mpl::identity<next_state_type> 266 >::type 267 type; 268 269 typedef 270 typename mpl::eval_if< 271 typename fold_recurse_impl::continue_type 272 , continue_wrap<next_iteration_impl> 273 , mpl::identity<mpl::false_> 274 >::type 275 continue_type; 276 277 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::segmented_fold_until_iterate_skip_empty278 static type call(Begin const& beg, End const& end, State const& state 279 , Context const& context, Fun const& fun) 280 { 281 return call(beg, end, state, context, fun, typename fold_recurse_impl::continue_type()); 282 } 283 284 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::segmented_fold_until_iterate_skip_empty285 static type call(Begin const& beg, End const& end, State const& state 286 , Context const& context, Fun const& fun, mpl::true_) // continue 287 { 288 return next_iteration_impl::call( 289 fusion::next(beg) 290 , end 291 , fold_recurse_impl::call( 292 *beg 293 , state 294 , push_context_impl::call(beg, end, context) 295 , fun) 296 , context 297 , fun); 298 } 299 300 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::segmented_fold_until_iterate_skip_empty301 static type call(Begin const& beg, End const& end, State const& state 302 , Context const& context, Fun const& fun, mpl::false_) // break 303 { 304 return fold_recurse_impl::call( 305 *beg 306 , state 307 , push_context_impl::call(beg, end, context) 308 , fun); 309 } 310 }; 311 312 template <typename Begin, typename End, typename State, typename Context, typename Fun> 313 struct segmented_fold_until_iterate_skip_empty<Begin, End, State, Context, Fun, true> 314 { 315 typedef 316 segmented_fold_until_iterate< 317 typename result_of::next<Begin>::type 318 , End 319 , State 320 , Context 321 , Fun 322 > 323 impl; 324 325 typedef typename impl::type type; 326 typedef typename impl::continue_type continue_type; 327 328 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::segmented_fold_until_iterate_skip_empty329 static type call(Begin const& beg, End const& end, State const& state 330 , Context const& context, Fun const& fun) 331 { 332 return impl::call(fusion::next(beg), end, state, context, fun); 333 } 334 }; 335 336 template <typename Begin, typename End, typename State, typename Context, typename Fun, bool IsDone> 337 struct segmented_fold_until_iterate 338 { 339 typedef 340 typename result_of::empty< 341 typename remove_reference< 342 typename result_of::deref<Begin>::type 343 >::type 344 >::type 345 empty_type; 346 347 typedef 348 segmented_fold_until_iterate_skip_empty<Begin, End, State, Context, Fun, empty_type::value> 349 impl; 350 351 typedef typename impl::type type; 352 typedef typename impl::continue_type continue_type; 353 354 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::segmented_fold_until_iterate355 static type call(Begin const& beg, End const& end, State const& state 356 , Context const& context, Fun const& fun) 357 { 358 return impl::call(beg, end, state, context, fun); 359 } 360 }; 361 362 template <typename Begin, typename End, typename State, typename Context, typename Fun> 363 struct segmented_fold_until_iterate<Begin, End, State, Context, Fun, true> 364 { 365 typedef State type; 366 typedef mpl::true_ continue_type; 367 368 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::segmented_fold_until_iterate369 static type call(Begin const&, End const&, State const& state 370 , Context const&, Fun const&) 371 { 372 return state; 373 } 374 }; 375 376 template <typename Segments, typename State, typename Context, typename Fun> 377 struct segmented_fold_until_on_segments 378 { 379 typedef 380 segmented_fold_until_iterate< 381 typename result_of::begin<Segments>::type 382 , typename result_of::end<Segments>::type 383 , State 384 , Context 385 , Fun 386 > 387 impl; 388 389 typedef typename impl::type type; 390 typedef typename impl::continue_type continue_type; 391 392 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::segmented_fold_until_on_segments393 static type call(Segments& segs, State const& state, Context const& context, Fun const& fun) 394 { 395 return impl::call(fusion::begin(segs), fusion::end(segs), state, context, fun); 396 } 397 }; 398 } 399 }} 400 401 #endif 402