https://gitweb.dealii.org/ - dealii.git/blob

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