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/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_FUSION_GPU_ENABLED
  52     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_FUSION_GPU_ENABLED
  61     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_FUSION_GPU_ENABLED
 156         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_FUSION_GPU_ENABLED
 203         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_FUSION_GPU_ENABLED
 216         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_FUSION_GPU_ENABLED
 302         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_FUSION_GPU_ENABLED
 349         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_FUSION_GPU_ENABLED
 362         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_FUSION_GPU_ENABLED
 441         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_FUSION_GPU_ENABLED
 475         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_FUSION_GPU_ENABLED
 505         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_FUSION_GPU_ENABLED
 535         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