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