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