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_ITERATOR_RANGE_HPP_INCLUDED) 8 #define BOOST_FUSION_SEGMENTED_ITERATOR_RANGE_HPP_INCLUDED 9 10 #include <boost/fusion/support/config.hpp> 11 #include <boost/detail/workaround.hpp> 12 #include <boost/mpl/assert.hpp> 13 #include <boost/type_traits/add_const.hpp> 14 #include <boost/type_traits/remove_reference.hpp> 15 #include <boost/fusion/support/tag_of.hpp> 16 #include <boost/fusion/sequence/intrinsic/begin.hpp> 17 #include <boost/fusion/sequence/intrinsic/end.hpp> 18 #include <boost/fusion/iterator/next.hpp> 19 #include <boost/fusion/iterator/deref.hpp> 20 #include <boost/fusion/sequence/intrinsic/segments.hpp> 21 #include <boost/fusion/algorithm/transformation/push_back.hpp> 22 #include <boost/fusion/algorithm/transformation/push_front.hpp> 23 #include <boost/fusion/iterator/equal_to.hpp> 24 #include <boost/fusion/container/list/detail/reverse_cons.hpp> 25 #include <boost/fusion/iterator/detail/segment_sequence.hpp> 26 #include <boost/fusion/support/is_sequence.hpp> 27 #include <boost/utility/enable_if.hpp> 28 29 // Invariants: 30 // - Each segmented iterator has a stack 31 // - Each value in the stack is an iterator range 32 // - The range at the top of the stack points to values 33 // - All other ranges point to ranges 34 // - The front of each range in the stack (besides the 35 // topmost) is the range above it 36 37 namespace boost { namespace fusion 38 { 39 template <typename First, typename Last> 40 struct iterator_range; 41 42 namespace result_of 43 { 44 template <typename Sequence, typename T> 45 struct push_back; 46 47 template <typename Sequence, typename T> 48 struct push_front; 49 } 50 51 template <typename Sequence, typename T> 52 BOOST_CXX14_CONSTEXPR BOOST_FUSION_GPU_ENABLED 53 inline typename 54 lazy_enable_if< 55 traits::is_sequence<Sequence> 56 , result_of::push_back<Sequence const, T> 57 >::type 58 push_back(Sequence const& seq, T const& x); 59 60 template <typename Sequence, typename T> 61 BOOST_CXX14_CONSTEXPR BOOST_FUSION_GPU_ENABLED 62 inline typename 63 lazy_enable_if< 64 traits::is_sequence<Sequence> 65 , result_of::push_front<Sequence const, T> 66 >::type 67 push_front(Sequence const& seq, T const& x); 68 }} 69 70 namespace boost { namespace fusion { namespace detail 71 { 72 //auto make_segment_sequence_front(stack_begin) 73 //{ 74 // switch (size(stack_begin)) 75 // { 76 // case 1: 77 // return nil_; 78 // case 2: 79 // // car(cdr(stack_begin)) is a range over values. 80 // assert(end(front(car(stack_begin))) == end(car(cdr(stack_begin)))); 81 // return iterator_range(begin(car(cdr(stack_begin))), end(front(car(stack_begin)))); 82 // default: 83 // // car(cdr(stack_begin)) is a range over segments. We replace the 84 // // front with a view that is restricted. 85 // assert(end(segments(front(car(stack_begin)))) == end(car(cdr(stack_begin)))); 86 // return segment_sequence( 87 // push_front( 88 // // The following could be a segment_sequence. It then gets wrapped 89 // // in a single_view, and push_front puts it in a join_view with the 90 // // following iterator_range. 91 // iterator_range(next(begin(car(cdr(stack_begin)))), end(segments(front(car(stack_begin))))), 92 // make_segment_sequence_front(cdr(stack_begin)))); 93 // } 94 //} 95 96 template <typename Stack, std::size_t Size = Stack::size::value> 97 struct make_segment_sequence_front 98 { 99 // assert(end(segments(front(car(stack_begin)))) == end(car(cdr(stack_begin)))); 100 BOOST_MPL_ASSERT(( 101 result_of::equal_to< 102 typename result_of::end< 103 typename remove_reference< 104 typename add_const< 105 typename result_of::segments< 106 typename remove_reference< 107 typename add_const< 108 typename result_of::deref< 109 typename Stack::car_type::begin_type 110 >::type 111 >::type 112 >::type 113 >::type 114 >::type 115 >::type 116 >::type 117 , typename Stack::cdr_type::car_type::end_type 118 >)); 119 120 typedef 121 iterator_range< 122 typename result_of::next< 123 typename Stack::cdr_type::car_type::begin_type 124 >::type 125 , typename result_of::end< 126 typename remove_reference< 127 typename add_const< 128 typename result_of::segments< 129 typename remove_reference< 130 typename add_const< 131 typename result_of::deref< 132 typename Stack::car_type::begin_type 133 >::type 134 >::type 135 >::type 136 >::type 137 >::type 138 >::type 139 >::type 140 > 141 rest_type; 142 143 typedef 144 make_segment_sequence_front<typename Stack::cdr_type> 145 recurse; 146 147 typedef 148 segment_sequence< 149 typename result_of::push_front< 150 rest_type const 151 , typename recurse::type 152 >::type 153 > 154 type; 155 156 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::make_segment_sequence_front157 static type call(Stack const& stack) 158 { 159 //return segment_sequence( 160 // push_front( 161 // iterator_range(next(begin(car(cdr(stack_begin)))), end(segments(front(car(stack_begin))))), 162 // make_segment_sequence_front(cdr(stack_begin)))); 163 return type( 164 fusion::push_front( 165 rest_type(fusion::next(stack.cdr.car.first), fusion::end(fusion::segments(*stack.car.first))) 166 , recurse::call(stack.cdr))); 167 } 168 }; 169 170 template <typename Stack> 171 struct make_segment_sequence_front<Stack, 2> 172 { 173 // assert(end(front(car(stack_begin))) == end(car(cdr(stack_begin)))); 174 BOOST_MPL_ASSERT(( 175 result_of::equal_to< 176 typename result_of::end< 177 typename remove_reference< 178 typename add_const< 179 typename result_of::deref< 180 typename Stack::car_type::begin_type 181 >::type 182 >::type 183 >::type 184 >::type 185 , typename Stack::cdr_type::car_type::end_type 186 >)); 187 188 typedef 189 iterator_range< 190 typename Stack::cdr_type::car_type::begin_type 191 , typename result_of::end< 192 typename remove_reference< 193 typename add_const< 194 typename result_of::deref< 195 typename Stack::car_type::begin_type 196 >::type 197 >::type 198 >::type 199 >::type 200 > 201 type; 202 203 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::make_segment_sequence_front204 static type call(Stack const& stack) 205 { 206 // return iterator_range(begin(car(cdr(stack_begin))), end(front(car(stack_begin)))); 207 return type(stack.cdr.car.first, fusion::end(*stack.car.first)); 208 } 209 }; 210 211 template <typename Stack> 212 struct make_segment_sequence_front<Stack, 1> 213 { 214 typedef typename Stack::cdr_type type; // nil_ 215 216 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::make_segment_sequence_front217 static type call(Stack const &stack) 218 { 219 return stack.cdr; 220 } 221 }; 222 223 //auto make_segment_sequence_back(stack_end) 224 //{ 225 // switch (size(stack_end)) 226 // { 227 // case 1: 228 // return nil_; 229 // case 2: 230 // // car(cdr(stack_back)) is a range over values. 231 // assert(end(front(car(stack_end))) == end(car(cdr(stack_end)))); 232 // return iterator_range(begin(front(car(stack_end))), begin(car(cdr(stack_end)))); 233 // default: 234 // // car(cdr(stack_begin)) is a range over segments. We replace the 235 // // back with a view that is restricted. 236 // assert(end(segments(front(car(stack_end)))) == end(car(cdr(stack_end)))); 237 // return segment_sequence( 238 // push_back( 239 // iterator_range(begin(segments(front(car(stack_end)))), begin(car(cdr(stack_end)))), 240 // make_segment_sequence_back(cdr(stack_end)))); 241 // } 242 //} 243 244 template <typename Stack, std::size_t Size = Stack::size::value> 245 struct make_segment_sequence_back 246 { 247 // assert(end(segments(front(car(stack_begin)))) == end(car(cdr(stack_begin)))); 248 BOOST_MPL_ASSERT(( 249 result_of::equal_to< 250 typename result_of::end< 251 typename remove_reference< 252 typename add_const< 253 typename result_of::segments< 254 typename remove_reference< 255 typename add_const< 256 typename result_of::deref< 257 typename Stack::car_type::begin_type 258 >::type 259 >::type 260 >::type 261 >::type 262 >::type 263 >::type 264 >::type 265 , typename Stack::cdr_type::car_type::end_type 266 >)); 267 268 typedef 269 iterator_range< 270 typename result_of::begin< 271 typename remove_reference< 272 typename add_const< 273 typename result_of::segments< 274 typename remove_reference< 275 typename add_const< 276 typename result_of::deref< 277 typename Stack::car_type::begin_type 278 >::type 279 >::type 280 >::type 281 >::type 282 >::type 283 >::type 284 >::type 285 , typename Stack::cdr_type::car_type::begin_type 286 > 287 rest_type; 288 289 typedef 290 make_segment_sequence_back<typename Stack::cdr_type> 291 recurse; 292 293 typedef 294 segment_sequence< 295 typename result_of::push_back< 296 rest_type const 297 , typename recurse::type 298 >::type 299 > 300 type; 301 302 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::make_segment_sequence_back303 static type call(Stack const& stack) 304 { 305 // return segment_sequence( 306 // push_back( 307 // iterator_range(begin(segments(front(car(stack_end)))), begin(car(cdr(stack_end)))), 308 // make_segment_sequence_back(cdr(stack_end)))); 309 return type( 310 fusion::push_back( 311 rest_type(fusion::begin(fusion::segments(*stack.car.first)), stack.cdr.car.first) 312 , recurse::call(stack.cdr))); 313 } 314 }; 315 316 template <typename Stack> 317 struct make_segment_sequence_back<Stack, 2> 318 { 319 // assert(end(front(car(stack_end))) == end(car(cdr(stack_end)))); 320 BOOST_MPL_ASSERT(( 321 result_of::equal_to< 322 typename result_of::end< 323 typename remove_reference< 324 typename add_const< 325 typename result_of::deref< 326 typename Stack::car_type::begin_type 327 >::type 328 >::type 329 >::type 330 >::type 331 , typename Stack::cdr_type::car_type::end_type 332 >)); 333 334 typedef 335 iterator_range< 336 typename result_of::begin< 337 typename remove_reference< 338 typename add_const< 339 typename result_of::deref< 340 typename Stack::car_type::begin_type 341 >::type 342 >::type 343 >::type 344 >::type 345 , typename Stack::cdr_type::car_type::begin_type 346 > 347 type; 348 349 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::make_segment_sequence_back350 static type call(Stack const& stack) 351 { 352 // return iterator_range(begin(front(car(stack_end))), begin(car(cdr(stack_end)))); 353 return type(fusion::begin(*stack.car.first), stack.cdr.car.first); 354 } 355 }; 356 357 template <typename Stack> 358 struct make_segment_sequence_back<Stack, 1> 359 { 360 typedef typename Stack::cdr_type type; // nil_ 361 362 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::make_segment_sequence_back363 static type call(Stack const& stack) 364 { 365 return stack.cdr; 366 } 367 }; 368 369 //auto make_segmented_range_reduce(stack_begin, stack_end) 370 //{ 371 // if (size(stack_begin) == 1 && size(stack_end) == 1) 372 // { 373 // return segment_sequence( 374 // single_view( 375 // iterator_range(begin(car(stack_begin)), begin(car(stack_end))))); 376 // } 377 // else 378 // { 379 // // We are in the case where both begin_stack and/or end_stack have 380 // // more than one element. Throw away any part of the tree where 381 // // begin and end refer to the same segment. 382 // if (begin(car(stack_begin)) == begin(car(stack_end))) 383 // { 384 // return make_segmented_range_reduce(cdr(stack_begin), cdr(stack_end)); 385 // } 386 // else 387 // { 388 // // We are in the case where begin_stack and end_stack (a) have 389 // // more than one element each, and (b) they point to different 390 // // segments. We must construct a segmented sequence. 391 // return segment_sequence( 392 // push_back( 393 // push_front( 394 // iterator_range( 395 // fusion::next(begin(car(stack_begin))), 396 // begin(car(stack_end))), // a range of (possibly segmented) ranges. 397 // make_segment_sequence_front(stack_begin)), // should be a (possibly segmented) range. 398 // make_segment_sequence_back(stack_end))); // should be a (possibly segmented) range. 399 // } 400 // } 401 //} 402 403 template < 404 typename StackBegin 405 , typename StackEnd 406 , int StackBeginSize = StackBegin::size::value 407 , int StackEndSize = StackEnd::size::value> 408 struct make_segmented_range_reduce; 409 410 template < 411 typename StackBegin 412 , typename StackEnd 413 , bool SameSegment 414 #if !(BOOST_WORKAROUND(BOOST_GCC, >= 40000) && BOOST_WORKAROUND(BOOST_GCC, < 40200)) 415 = result_of::equal_to< 416 typename StackBegin::car_type::begin_type 417 , typename StackEnd::car_type::begin_type 418 >::type::value 419 #endif 420 > 421 struct make_segmented_range_reduce2 422 { 423 typedef 424 iterator_range< 425 typename result_of::next< 426 typename StackBegin::car_type::begin_type 427 >::type 428 , typename StackEnd::car_type::begin_type 429 > 430 rest_type; 431 432 typedef 433 segment_sequence< 434 typename result_of::push_back< 435 typename result_of::push_front< 436 rest_type const 437 , typename make_segment_sequence_front<StackBegin>::type 438 >::type const 439 , typename make_segment_sequence_back<StackEnd>::type 440 >::type 441 > 442 type; 443 444 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::make_segmented_range_reduce2445 static type call(StackBegin stack_begin, StackEnd stack_end) 446 { 447 //return segment_sequence( 448 // push_back( 449 // push_front( 450 // iterator_range( 451 // fusion::next(begin(car(stack_begin))), 452 // begin(car(stack_end))), // a range of (possibly segmented) ranges. 453 // make_segment_sequence_front(stack_begin)), // should be a (possibly segmented) range. 454 // make_segment_sequence_back(stack_end))); // should be a (possibly segmented) range. 455 return type( 456 fusion::push_back( 457 fusion::push_front( 458 rest_type(fusion::next(stack_begin.car.first), stack_end.car.first) 459 , make_segment_sequence_front<StackBegin>::call(stack_begin)) 460 , make_segment_sequence_back<StackEnd>::call(stack_end))); 461 } 462 }; 463 464 template <typename StackBegin, typename StackEnd> 465 struct make_segmented_range_reduce2<StackBegin, StackEnd, true> 466 { 467 typedef 468 make_segmented_range_reduce< 469 typename StackBegin::cdr_type 470 , typename StackEnd::cdr_type 471 > 472 impl; 473 474 typedef 475 typename impl::type 476 type; 477 478 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::make_segmented_range_reduce2479 static type call(StackBegin stack_begin, StackEnd stack_end) 480 { 481 return impl::call(stack_begin.cdr, stack_end.cdr); 482 } 483 }; 484 485 template <typename StackBegin, typename StackEnd, int StackBeginSize, int StackEndSize> 486 struct make_segmented_range_reduce 487 : make_segmented_range_reduce2<StackBegin, StackEnd 488 #if BOOST_WORKAROUND(BOOST_GCC, >= 40000) && BOOST_WORKAROUND(BOOST_GCC, < 40200) 489 , result_of::equal_to< 490 typename StackBegin::car_type::begin_type 491 , typename StackEnd::car_type::begin_type 492 >::type::value 493 #endif 494 > 495 {}; 496 497 template <typename StackBegin, typename StackEnd> 498 struct make_segmented_range_reduce<StackBegin, StackEnd, 1, 1> 499 { 500 typedef 501 iterator_range< 502 typename StackBegin::car_type::begin_type 503 , typename StackEnd::car_type::begin_type 504 > 505 range_type; 506 507 typedef 508 single_view<range_type> 509 segment_type; 510 511 typedef 512 segment_sequence<segment_type> 513 type; 514 515 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::make_segmented_range_reduce516 static type call(StackBegin stack_begin, StackEnd stack_end) 517 { 518 //return segment_sequence( 519 // single_view( 520 // iterator_range(begin(car(stack_begin)), begin(car(stack_end))))); 521 return type(segment_type(range_type(stack_begin.car.first, stack_end.car.first))); 522 } 523 }; 524 525 //auto make_segmented_range(begin, end) 526 //{ 527 // return make_segmented_range_reduce(reverse(begin.context), reverse(end.context)); 528 //} 529 530 template <typename Begin, typename End> 531 struct make_segmented_range 532 { 533 typedef reverse_cons<typename Begin::context_type> reverse_begin_cons; 534 typedef reverse_cons<typename End::context_type> reverse_end_cons; 535 536 typedef 537 make_segmented_range_reduce< 538 typename reverse_begin_cons::type 539 , typename reverse_end_cons::type 540 > 541 impl; 542 543 typedef typename impl::type type; 544 545 BOOST_CONSTEXPR BOOST_FUSION_GPU_ENABLED callboost::fusion::detail::make_segmented_range546 static type call(Begin const& begin, End const& end) 547 { 548 return impl::call( 549 reverse_begin_cons::call(begin.context) 550 , reverse_end_cons::call(end.context)); 551 } 552 }; 553 554 }}} 555 556 #endif 557