3rdparty/boost/boost/fusion/view/iterator_range/detail/segmented_iterator_range.hpp

   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
 157         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
 204         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
 217         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
 303         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
 350         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
 363         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
 445         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
 479         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
 516         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
 546         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