boost/fusion/view/ext_/segmented_iterator_range.hpp

   1 /*=============================================================================
   2  Copyright (c) 2006 Eric Niebler
   3
   4  Use, modification and distribution is subject to the Boost Software
   5  License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6  http://www.boost.org/LICENSE_1_0.txt)
   7 ==============================================================================*/
   8 #ifndef FUSION_SEGMENTED_ITERATOR_RANGE_EAN_05032006_1027
   9 #define FUSION_SEGMENTED_ITERATOR_RANGE_EAN_05032006_1027
  10
  11 #include <boost/mpl/bool.hpp>
  12 #include <boost/mpl/minus.hpp>
  13 #include <boost/mpl/next_prior.hpp>
  14 #include <boost/mpl/and.hpp>
  15 #include <boost/type_traits/remove_cv.hpp>
  16 #include <boost/type_traits/remove_reference.hpp>
  17 #include <boost/fusion/iterator/mpl/convert_iterator.hpp>
  18 #include <boost/fusion/container/list/cons.hpp>
  19 #include <boost/fusion/view/joint_view.hpp>
  20 #include <boost/fusion/view/single_view.hpp>
  21 #include <boost/fusion/view/transform_view.hpp>
  22 #include <boost/fusion/view/iterator_range.hpp>
  23 #include <boost/fusion/view/ext_/multiple_view.hpp>
  24 #include <boost/fusion/view/ext_/segmented_iterator.hpp>
  25 #include <boost/fusion/adapted/mpl/mpl_iterator.hpp>
  26
  27 namespace boost { namespace fusion
  28 {
  29     namespace detail
  30     {
  31         ////////////////////////////////////////////////////////////////////////////
  32         template<typename Cons, typename State = nil>
  33         struct reverse_cons;
  34
  35         template<typename Car, typename Cdr, typename State>
  36         struct reverse_cons<cons<Car, Cdr>, State>
  37         {
  38             typedef reverse_cons<Cdr, cons<Car, State> > reverse;
  39             typedef typename reverse::type type;
  40
  41             static type call(cons<Car, Cdr> const &cons, State const &state = State())
  42             {
  43                 return reverse::call(cons.cdr, fusion::make_cons(cons.car, state));
  44             }
  45         };
  46
  47         template<typename State>
  48         struct reverse_cons<nil, State>
  49         {
  50             typedef State type;
  51
  52             static State const &call(nil const &, State const &state = State())
  53             {
  54                 return state;
  55             }
  56         };
  57
  58         ////////////////////////////////////////////////////////////////////////////
  59         // tags
  60         struct full_view {};
  61         struct left_view {};
  62         struct right_view {};
  63         struct center_view {};
  64
  65         template<typename Tag>
  66         struct segmented_view_tag;
  67
  68         ////////////////////////////////////////////////////////////////////////////
  69         // a segmented view of that includes all elements either to the
  70         // right or the left of a segmented iterator.
  71         template<typename Tag, typename Cons1, typename Cons2 = void_>
  72         struct segmented_view
  73           : sequence_base<segmented_view<Tag, Cons1, Cons2> >
  74         {
  75             typedef segmented_view_tag<Tag> fusion_tag;
  76             typedef fusion_sequence_tag tag; // this gets picked up by MPL
  77             typedef mpl::true_ is_view;
  78             typedef forward_traversal_tag category;
  79
  80             explicit segmented_view(Cons1 const &cons)
  81               : cons(cons)
  82             {}
  83
  84             typedef Cons1 cons_type;
  85             cons_type const &cons;
  86         };
  87
  88         // a segmented view that contains all the elements in between
  89         // two segmented iterators
  90         template<typename Cons1, typename Cons2>
  91         struct segmented_view<center_view, Cons1, Cons2>
  92           : sequence_base<segmented_view<center_view, Cons1, Cons2> >
  93         {
  94             typedef segmented_view_tag<center_view> fusion_tag;
  95             typedef fusion_sequence_tag tag; // this gets picked up by MPL
  96             typedef mpl::true_ is_view;
  97             typedef forward_traversal_tag category;
  98
  99             segmented_view(Cons1 const &lcons, Cons2 const &rcons)
 100               : left_cons(lcons)
 101               , right_cons(rcons)
 102             {}
 103
 104             typedef Cons1 left_cons_type;
 105             typedef Cons2 right_cons_type;
 106
 107             left_cons_type const &left_cons;
 108             right_cons_type const &right_cons;
 109         };
 110
 111         ////////////////////////////////////////////////////////////////////////////
 112         // Used to transform a sequence of segments. The first segment is
 113         // bounded by RightCons, and the last segment is bounded by LeftCons
 114         // and all the others are passed through unchanged.
 115         template<typename RightCons, typename LeftCons = RightCons>
 116         struct segments_transform
 117         {
 118             explicit segments_transform(RightCons const &cons_)
 119               : right_cons(cons_)
 120               , left_cons(cons_)
 121             {}
 122
 123             segments_transform(RightCons const &right_cons_, LeftCons const &left_cons_)
 124               : right_cons(right_cons_)
 125               , left_cons(left_cons_)
 126             {}
 127
 128             template<typename First, typename Second>
 129             struct result_;
 130
 131             template<typename Second>
 132             struct result_<right_view, Second>
 133             {
 134                 typedef segmented_view<right_view, RightCons> type;
 135             };
 136
 137             template<typename Second>
 138             struct result_<left_view, Second>
 139             {
 140                 typedef segmented_view<left_view, LeftCons> type;
 141             };
 142
 143             template<typename Second>
 144             struct result_<full_view, Second>
 145             {
 146                 typedef Second type;
 147             };
 148
 149             template<typename Sig>
 150             struct result;
 151
 152             template<typename This, typename First, typename Second>
 153             struct result<This(First, Second)>
 154               : result_<
 155                     typename remove_cv<typename remove_reference<First>::type>::type
 156                   , typename remove_cv<typename remove_reference<Second>::type>::type
 157                 >
 158             {};
 159
 160             template<typename Second>
 161             segmented_view<right_view, RightCons> operator ()(right_view, Second &second) const
 162             {
 163                 return segmented_view<right_view, RightCons>(this->right_cons);
 164             }
 165
 166             template<typename Second>
 167             segmented_view<left_view, LeftCons> operator ()(left_view, Second &second) const
 168             {
 169                 return segmented_view<left_view, LeftCons>(this->left_cons);
 170             }
 171
 172             template<typename Second>
 173             Second &operator ()(full_view, Second &second) const
 174             {
 175                 return second;
 176             }
 177
 178         private:
 179             RightCons const &right_cons;
 180             LeftCons const &left_cons;
 181         };
 182
 183     } // namespace detail
 184
 185     namespace extension
 186     {
 187         ////////////////////////////////////////////////////////////////////////////
 188         template<typename Tag>
 189         struct is_segmented_impl<detail::segmented_view_tag<Tag> >
 190         {
 191             template<typename Sequence>
 192             struct apply
 193               : mpl::true_
 194             {};
 195         };
 196
 197         ////////////////////////////////////////////////////////////////////////////
 198         template<>
 199         struct segments_impl<detail::segmented_view_tag<detail::right_view> >
 200         {
 201             template<
 202                 typename Sequence
 203               , typename Cdr = typename Sequence::cons_type::cdr_type
 204             >
 205             struct apply
 206             {
 207                 typedef typename Sequence::cons_type::car_type segmented_range;
 208                 typedef typename result_of::size<segmented_range>::type size;
 209                 typedef typename mpl::prior<size>::type size_minus_1;
 210                 typedef detail::segments_transform<Cdr> tfx;
 211                 typedef joint_view<
 212                     single_view<detail::right_view> const
 213                   , multiple_view<size_minus_1, detail::full_view> const
 214                 > mask;
 215                 typedef transform_view<mask const, segmented_range const, tfx> type;
 216
 217                 static type call(Sequence &seq)
 218                 {
 219                     return type(
 220                         mask(
 221                             make_single_view(detail::right_view())
 222                           , make_multiple_view<size_minus_1>(detail::full_view())
 223                         )
 224                       , seq.cons.car
 225                       , tfx(seq.cons.cdr)
 226                     );
 227                 }
 228             };
 229
 230             template<typename Sequence>
 231             struct apply<Sequence, nil>
 232             {
 233                 typedef typename Sequence::cons_type::car_type segmented_range;
 234                 typedef typename segmented_range::iterator_type begin;
 235                 typedef typename segmented_range::sequence_non_ref_type sequence_type;
 236                 typedef typename result_of::end<sequence_type>::type end;
 237                 typedef iterator_range<begin, end> range;
 238                 typedef single_view<range> type;
 239
 240                 static type call(Sequence &seq)
 241                 {
 242                     return type(range(seq.cons.car.where_, fusion::end(seq.cons.car.sequence)));
 243                 }
 244             };
 245         };
 246
 247         ////////////////////////////////////////////////////////////////////////////
 248         template<>
 249         struct segments_impl<detail::segmented_view_tag<detail::left_view> >
 250         {
 251             template<
 252                 typename Sequence
 253               , typename Cdr = typename Sequence::cons_type::cdr_type
 254             >
 255             struct apply
 256             {
 257                 typedef typename Sequence::cons_type::car_type right_segmented_range;
 258                 typedef typename right_segmented_range::sequence_type sequence_type;
 259                 typedef typename right_segmented_range::iterator_type iterator_type;
 260
 261                 typedef iterator_range<
 262                     typename result_of::begin<sequence_type>::type
 263                   , typename result_of::next<iterator_type>::type
 264                 > segmented_range;
 265
 266                 typedef detail::segments_transform<Cdr> tfx;
 267                 typedef typename result_of::size<segmented_range>::type size;
 268                 typedef typename mpl::prior<size>::type size_minus_1;
 269                 typedef joint_view<
 270                     multiple_view<size_minus_1, detail::full_view> const
 271                   , single_view<detail::left_view> const
 272                 > mask;
 273                 typedef transform_view<mask const, segmented_range const, tfx> type;
 274
 275                 static type call(Sequence &seq)
 276                 {
 277                     return type(
 278                         mask(
 279                             make_multiple_view<size_minus_1>(detail::full_view())
 280                           , make_single_view(detail::left_view())
 281                         )
 282                       , segmented_range(fusion::begin(seq.cons.car.sequence), fusion::next(seq.cons.car.where_))
 283                       , tfx(seq.cons.cdr)
 284                     );
 285                 }
 286             };
 287
 288             template<typename Sequence>
 289             struct apply<Sequence, nil>
 290             {
 291                 typedef typename Sequence::cons_type::car_type segmented_range;
 292                 typedef typename segmented_range::sequence_non_ref_type sequence_type;
 293                 typedef typename result_of::begin<sequence_type>::type begin;
 294                 typedef typename segmented_range::iterator_type end;
 295                 typedef iterator_range<begin, end> range;
 296                 typedef single_view<range> type;
 297
 298                 static type call(Sequence &seq)
 299                 {
 300                     return type(range(fusion::begin(seq.cons.car.sequence), seq.cons.car.where_));
 301                 }
 302             };
 303         };
 304
 305         ////////////////////////////////////////////////////////////////////////////
 306         template<>
 307         struct segments_impl<detail::segmented_view_tag<detail::center_view> >
 308         {
 309             template<typename Sequence>
 310             struct apply
 311             {
 312                 typedef typename Sequence::right_cons_type right_cons_type;
 313                 typedef typename Sequence::left_cons_type left_cons_type;
 314                 typedef typename right_cons_type::car_type right_segmented_range;
 315                 typedef typename left_cons_type::car_type left_segmented_range;
 316
 317                 typedef iterator_range<
 318                     typename result_of::begin<left_segmented_range>::type
 319                   , typename result_of::next<typename result_of::begin<right_segmented_range>::type>::type
 320                 > segmented_range;
 321
 322                 typedef typename mpl::minus<
 323                     typename result_of::size<segmented_range>::type
 324                   , mpl::int_<2>
 325                 >::type size_minus_2;
 326
 327                 BOOST_MPL_ASSERT_RELATION(0, <=, size_minus_2::value);
 328
 329                 typedef detail::segments_transform<
 330                     typename left_cons_type::cdr_type
 331                   , typename right_cons_type::cdr_type
 332                 > tfx;
 333
 334                 typedef joint_view<
 335                     multiple_view<size_minus_2, detail::full_view> const
 336                   , single_view<detail::left_view> const
 337                 > left_mask;
 338
 339                 typedef joint_view<
 340                     single_view<detail::right_view> const
 341                   , left_mask const
 342                 > mask;
 343
 344                 typedef transform_view<mask const, segmented_range const, tfx> type;
 345
 346                 static type call(Sequence &seq)
 347                 {
 348                     left_mask lmask(
 349                         make_multiple_view<size_minus_2>(detail::full_view())
 350                       , make_single_view(detail::left_view())
 351                     );
 352                     return type(
 353                         mask(make_single_view(detail::right_view()), lmask)
 354                       , segmented_range(fusion::begin(seq.left_cons.car), fusion::next(fusion::begin(seq.right_cons.car)))
 355                       , tfx(seq.left_cons.cdr, seq.right_cons.cdr)
 356                     );
 357                 }
 358             };
 359         };
 360     }
 361
 362     // specialize iterator_range for use with segmented iterators, so that
 363     // it presents a segmented view of the range.
 364     template<typename First, typename Last>
 365     struct iterator_range;
 366
 367     template<typename First, typename Last>
 368     struct iterator_range<segmented_iterator<First>, segmented_iterator<Last> >
 369       : sequence_base<iterator_range<segmented_iterator<First>, segmented_iterator<Last> > >
 370     {
 371         typedef typename convert_iterator<segmented_iterator<First> >::type begin_type;
 372         typedef typename convert_iterator<segmented_iterator<Last> >::type end_type;
 373         typedef typename detail::reverse_cons<First>::type begin_cons_type;
 374         typedef typename detail::reverse_cons<Last>::type end_cons_type;
 375         typedef iterator_range_tag fusion_tag;
 376         typedef fusion_sequence_tag tag; // this gets picked up by MPL
 377         typedef typename traits::category_of<begin_type>::type category;
 378         typedef typename result_of::distance<begin_type, end_type>::type size;
 379         typedef mpl::true_ is_view;
 380
 381         iterator_range(segmented_iterator<First> const& first_, segmented_iterator<Last> const& last_)
 382           : first(convert_iterator<segmented_iterator<First> >::call(first_))
 383           , last(convert_iterator<segmented_iterator<Last> >::call(last_))
 384           , first_cons(detail::reverse_cons<First>::call(first_.cons()))
 385           , last_cons(detail::reverse_cons<Last>::call(last_.cons()))
 386         {}
 387
 388         begin_type first;
 389         end_type last;
 390
 391         begin_cons_type first_cons;
 392         end_cons_type last_cons;
 393     };
 394
 395     namespace detail
 396     {
 397
 398         template<typename Cons1, typename Cons2>
 399         struct same_segment
 400           : mpl::false_
 401         {};
 402
 403         template<typename Car1, typename Cdr1, typename Car2, typename Cdr2>
 404         struct same_segment<cons<Car1, Cdr1>, cons<Car2, Cdr2> >
 405           : mpl::and_<
 406                 traits::is_segmented<Car1>
 407               , is_same<Car1, Car2>
 408             >
 409         {};
 410
 411         ////////////////////////////////////////////////////////////////////////////
 412         template<typename Cons1, typename Cons2>
 413         struct segments_gen;
 414
 415         ////////////////////////////////////////////////////////////////////////////
 416         template<typename Cons1, typename Cons2, bool SameSegment>
 417         struct segments_gen2
 418         {
 419             typedef segments_gen<typename Cons1::cdr_type, typename Cons2::cdr_type> gen;
 420             typedef typename gen::type type;
 421
 422             static type call(Cons1 const &cons1, Cons2 const &cons2)
 423             {
 424                 return gen::call(cons1.cdr, cons2.cdr);
 425             }
 426         };
 427
 428         template<typename Cons1, typename Cons2>
 429         struct segments_gen2<Cons1, Cons2, false>
 430         {
 431             typedef segmented_view<center_view, Cons1, Cons2> view;
 432             typedef typename result_of::segments<view>::type type;
 433
 434             static type call(Cons1 const &cons1, Cons2 const &cons2)
 435             {
 436                 view v(cons1, cons2);
 437                 return fusion::segments(v);
 438             }
 439         };
 440
 441         template<typename Car1, typename Car2>
 442         struct segments_gen2<cons<Car1>, cons<Car2>, false>
 443         {
 444             typedef iterator_range<
 445                 typename Car1::iterator_type
 446               , typename Car2::iterator_type
 447             > range;
 448
 449             typedef single_view<range> type;
 450
 451             static type call(cons<Car1> const &cons1, cons<Car2> const &cons2)
 452             {
 453                 return type(range(cons1.car.where_, cons2.car.where_));
 454             }
 455         };
 456
 457         ////////////////////////////////////////////////////////////////////////////
 458         template<typename Cons1, typename Cons2>
 459         struct segments_gen
 460           : segments_gen2<Cons1, Cons2, same_segment<Cons1, Cons2>::value>
 461         {};
 462
 463         template<typename Car, typename Cdr>
 464         struct segments_gen<cons<Car, Cdr>, nil>
 465         {
 466             typedef segmented_view<right_view, cons<Car, Cdr> > view;
 467             typedef typename result_of::segments<view>::type type;
 468
 469             static type call(cons<Car, Cdr> const &cons, nil const &)
 470             {
 471                 view v(cons);
 472                 return fusion::segments(v);
 473             }
 474         };
 475
 476         template<>
 477         struct segments_gen<nil, nil>
 478         {
 479             typedef nil type;
 480
 481             static type call(nil const &, nil const &)
 482             {
 483                 return nil();
 484             }
 485         };
 486     } // namespace detail
 487
 488     namespace extension
 489     {
 490         template<typename Tag>
 491         struct is_segmented_impl;
 492
 493         // An iterator_range of segmented_iterators is segmented
 494         template<>
 495         struct is_segmented_impl<iterator_range_tag>
 496         {
 497             template<typename Iterator>
 498             struct is_segmented_iterator : mpl::false_ {};
 499
 500             template<typename Cons>
 501             struct is_segmented_iterator<segmented_iterator<Cons> > : mpl::true_ {};
 502
 503             template<typename Sequence>
 504             struct apply
 505               : mpl::and_<
 506                     is_segmented_iterator<typename Sequence::begin_type>
 507                   , is_segmented_iterator<typename Sequence::end_type>
 508                 >
 509             {};
 510         };
 511
 512         template<typename Sequence>
 513         struct segments_impl;
 514
 515         template<>
 516         struct segments_impl<iterator_range_tag>
 517         {
 518             template<typename Sequence>
 519             struct apply
 520             {
 521                 typedef typename Sequence::begin_cons_type begin_cons;
 522                 typedef typename Sequence::end_cons_type end_cons;
 523
 524                 typedef detail::segments_gen<begin_cons, end_cons> gen;
 525                 typedef typename gen::type type;
 526
 527                 static type call(Sequence &sequence)
 528                 {
 529                     return gen::call(sequence.first_cons, sequence.last_cons);
 530                 }
 531             };
 532         };
 533     }
 534
 535 }}
 536
 537 #endif