boost/fusion/support/detail/segmented_fold_until_impl.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_FOLD_UNTIL_IMPL_HPP_INCLUDED)
   8 #define BOOST_FUSION_SEGMENTED_FOLD_UNTIL_IMPL_HPP_INCLUDED
   9
  10 #include <boost/mpl/bool.hpp>
  11 #include <boost/mpl/eval_if.hpp>
  12 #include <boost/mpl/identity.hpp>
  13 #include <boost/utility/result_of.hpp>
  14 #include <boost/type_traits/add_const.hpp>
  15 #include <boost/type_traits/remove_reference.hpp>
  16
  17 #include <boost/fusion/support/void.hpp>
  18 #include <boost/fusion/container/list/cons_fwd.hpp>
  19 #include <boost/fusion/sequence/intrinsic_fwd.hpp>
  20 #include <boost/fusion/iterator/equal_to.hpp>
  21 #include <boost/fusion/iterator/deref.hpp>
  22 #include <boost/fusion/iterator/next.hpp>
  23 #include <boost/fusion/support/is_segmented.hpp>
  24 #include <boost/fusion/sequence/intrinsic/segments.hpp>
  25
  26 // fun(seq, state, context)
  27 //  seq: a non-segmented range
  28 //  state: the state of the fold so far
  29 //  context: the path to the current range
  30 //
  31 // returns: (state', fcontinue)
  32
  33 namespace boost { namespace fusion
  34 {
  35     template <typename First, typename Last>
  36     struct iterator_range;
  37
  38     template <typename Context>
  39     struct segmented_iterator;
  40
  41     namespace result_of
  42     {
  43         template <typename Cur, typename Context>
  44         struct make_segmented_iterator
  45         {
  46             typedef
  47                 iterator_range<
  48                     Cur
  49                   , typename result_of::end<
  50                         typename remove_reference<
  51                             typename add_const<
  52                                 typename result_of::deref<
  53                                     typename Context::car_type::begin_type
  54                                 >::type
  55                             >::type
  56                         >::type
  57                     >::type
  58                 >
  59             range_type;
  60
  61             typedef
  62                 segmented_iterator<cons<range_type, Context> >
  63             type;
  64         };
  65     }
  66
  67     template <typename Cur, typename Context>
  68     typename result_of::make_segmented_iterator<Cur, Context>::type
  69     make_segmented_iterator(Cur const& cur, Context const& context)
  70     {
  71         typedef result_of::make_segmented_iterator<Cur, Context> impl_type;
  72         typedef typename impl_type::type type;
  73         typedef typename impl_type::range_type range_type;
  74         return type(cons<range_type, Context>(range_type(cur, fusion::end(*context.car.first)), context));
  75     }
  76
  77     namespace detail
  78     {
  79         template <
  80             typename Begin
  81           , typename End
  82           , typename State
  83           , typename Context
  84           , typename Fun
  85           , bool IsEmpty
  86         >
  87         struct segmented_fold_until_iterate_skip_empty;
  88
  89         template <
  90             typename Begin
  91           , typename End
  92           , typename State
  93           , typename Context
  94           , typename Fun
  95           , bool IsDone = result_of::equal_to<Begin, End>::type::value
  96         >
  97         struct segmented_fold_until_iterate;
  98
  99         template <
 100             typename Sequence
 101           , typename State
 102           , typename Context
 103           , typename Fun
 104           , bool IsSegmented = traits::is_segmented<Sequence>::type::value
 105         >
 106         struct segmented_fold_until_impl;
 107
 108         template <typename Segments, typename State, typename Context, typename Fun>
 109         struct segmented_fold_until_on_segments;
 110
 111         //auto push_context(cur, end, context)
 112         //{
 113         //  return push_back(context, segment_sequence(iterator_range(cur, end)));
 114         //}
 115
 116         template <typename Cur, typename End, typename Context>
 117         struct push_context
 118         {
 119             typedef iterator_range<Cur, End>    range_type;
 120             typedef cons<range_type, Context>   type;
 121
 122             static type call(Cur const& cur, End const& end, Context const& context)
 123             {
 124                 return cons<range_type, Context>(range_type(cur, end), context);
 125             }
 126         };
 127
 128         //auto make_segmented_iterator(cur, end, context)
 129         //{
 130         //  return segmented_iterator(push_context(cur, end, context));
 131         //}
 132         //
 133         //auto segmented_fold_until_impl(seq, state, context, fun)
 134         //{
 135         //  if (is_segmented(seq))
 136         //  {
 137         //    segmented_fold_until_on_segments(segments(seq), state, context, fun);
 138         //  }
 139         //  else
 140         //  {
 141         //    return fun(seq, state, context);
 142         //  }
 143         //}
 144
 145         template <
 146             typename Sequence
 147           , typename State
 148           , typename Context
 149           , typename Fun
 150           , bool IsSegmented
 151         >
 152         struct segmented_fold_until_impl
 153         {
 154             typedef
 155                 segmented_fold_until_on_segments<
 156                     typename remove_reference<
 157                         typename add_const<
 158                             typename result_of::segments<Sequence>::type
 159                         >::type
 160                     >::type
 161                   , State
 162                   , Context
 163                   , Fun
 164                 >
 165             impl;
 166
 167             typedef typename impl::type type;
 168             typedef typename impl::continue_type continue_type;
 169
 170             static type call(Sequence& seq, State const& state, Context const& context, Fun const& fun)
 171             {
 172                 return impl::call(fusion::segments(seq), state, context, fun);
 173             }
 174         };
 175
 176         template <
 177             typename Sequence
 178           , typename State
 179           , typename Context
 180           , typename Fun
 181         >
 182         struct segmented_fold_until_impl<Sequence, State, Context, Fun, false>
 183         {
 184             typedef
 185                 typename Fun::template apply<Sequence, State, Context>
 186             apply_type;
 187
 188             typedef typename apply_type::type type;
 189             typedef typename apply_type::continue_type continue_type;
 190
 191             static type call(Sequence& seq, State const& state, Context const& context, Fun const& fun)
 192             {
 193                 return apply_type::call(seq, state, context, fun);
 194             }
 195         };
 196
 197         //auto segmented_fold_until_on_segments(segs, state, context, fun)
 198         //{
 199         //  auto cur = begin(segs), end = end(segs);
 200         //  for (; cur != end; ++cur)
 201         //  {
 202         //    if (empty(*cur))
 203         //      continue;
 204         //    auto context` = push_context(cur, end, context);
 205         //    state = segmented_fold_until_impl(*cur, state, context`, fun);
 206         //    if (!second(state))
 207         //      return state;
 208         //  }
 209         //}
 210
 211         template <typename Apply>
 212         struct continue_wrap
 213         {
 214             typedef typename Apply::continue_type type;
 215         };
 216
 217         template <typename Begin, typename End, typename State, typename Context, typename Fun, bool IsEmpty>
 218         struct segmented_fold_until_iterate_skip_empty
 219         {
 220             // begin != end and !empty(*begin)
 221             typedef
 222                 push_context<Begin, End, Context>
 223             push_context_impl;
 224
 225             typedef
 226                 typename push_context_impl::type
 227             next_context_type;
 228
 229             typedef
 230                 segmented_fold_until_impl<
 231                     typename remove_reference<
 232                         typename add_const<
 233                             typename result_of::deref<Begin>::type
 234                         >::type
 235                     >::type
 236                   , State
 237                   , next_context_type
 238                   , Fun
 239                 >
 240             fold_recurse_impl;
 241
 242             typedef
 243                 typename fold_recurse_impl::type
 244             next_state_type;
 245
 246             typedef
 247                 segmented_fold_until_iterate<
 248                     typename result_of::next<Begin>::type
 249                   , End
 250                   , next_state_type
 251                   , Context
 252                   , Fun
 253                 >
 254             next_iteration_impl;
 255
 256             typedef
 257                 typename mpl::eval_if<
 258                     typename fold_recurse_impl::continue_type
 259                   , next_iteration_impl
 260                   , mpl::identity<next_state_type>
 261                 >::type
 262             type;
 263
 264             typedef
 265                 typename mpl::eval_if<
 266                     typename fold_recurse_impl::continue_type
 267                   , continue_wrap<next_iteration_impl>
 268                   , mpl::identity<mpl::false_>
 269                 >::type
 270             continue_type;
 271
 272             static type call(Begin const& beg, End const& end, State const& state
 273                            , Context const& context, Fun const& fun)
 274             {
 275                 return call(beg, end, state, context, fun, typename fold_recurse_impl::continue_type());
 276             }
 277
 278             static type call(Begin const& beg, End const& end, State const& state
 279                            , Context const& context, Fun const& fun, mpl::true_) // continue
 280             {
 281                 return next_iteration_impl::call(
 282                     fusion::next(beg)
 283                   , end
 284                   , fold_recurse_impl::call(
 285                         *beg
 286                       , state
 287                       , push_context_impl::call(beg, end, context)
 288                       , fun)
 289                   , context
 290                   , fun);
 291             }
 292
 293             static type call(Begin const& beg, End const& end, State const& state
 294                            , Context const& context, Fun const& fun, mpl::false_) // break
 295             {
 296                 return fold_recurse_impl::call(
 297                     *beg
 298                   , state
 299                   , push_context_impl::call(beg, end, context)
 300                   , fun);
 301             }
 302         };
 303
 304         template <typename Begin, typename End, typename State, typename Context, typename Fun>
 305         struct segmented_fold_until_iterate_skip_empty<Begin, End, State, Context, Fun, true>
 306         {
 307             typedef
 308                 segmented_fold_until_iterate<
 309                     typename result_of::next<Begin>::type
 310                   , End
 311                   , State
 312                   , Context
 313                   , Fun
 314                 >
 315             impl;
 316
 317             typedef typename impl::type type;
 318             typedef typename impl::continue_type continue_type;
 319
 320             static type call(Begin const& beg, End const& end, State const& state
 321                            , Context const& context, Fun const& fun)
 322             {
 323                 return impl::call(fusion::next(beg), end, state, context, fun);
 324             }
 325         };
 326
 327         template <typename Begin, typename End, typename State, typename Context, typename Fun, bool IsDone>
 328         struct segmented_fold_until_iterate
 329         {
 330             typedef
 331                 typename result_of::empty<
 332                     typename remove_reference<
 333                         typename result_of::deref<Begin>::type
 334                     >::type
 335                 >::type
 336             empty_type;
 337
 338             typedef
 339                 segmented_fold_until_iterate_skip_empty<Begin, End, State, Context, Fun, empty_type::value>
 340             impl;
 341
 342             typedef typename impl::type type;
 343             typedef typename impl::continue_type continue_type;
 344
 345             static type call(Begin const& beg, End const& end, State const& state
 346                            , Context const& context, Fun const& fun)
 347             {
 348                 return impl::call(beg, end, state, context, fun);
 349             }
 350         };
 351
 352         template <typename Begin, typename End, typename State, typename Context, typename Fun>
 353         struct segmented_fold_until_iterate<Begin, End, State, Context, Fun, true>
 354         {
 355             typedef State type;
 356             typedef mpl::true_ continue_type;
 357
 358             static type call(Begin const&, End const&, State const& state
 359                            , Context const&, Fun const&)
 360             {
 361                 return state;
 362             }
 363         };
 364
 365         template <typename Segments, typename State, typename Context, typename Fun>
 366         struct segmented_fold_until_on_segments
 367         {
 368             typedef
 369                 segmented_fold_until_iterate<
 370                     typename result_of::begin<Segments>::type
 371                   , typename result_of::end<Segments>::type
 372                   , State
 373                   , Context
 374                   , Fun
 375                 >
 376             impl;
 377
 378             typedef typename impl::type type;
 379             typedef typename impl::continue_type continue_type;
 380
 381             static type call(Segments& segs, State const& state, Context const& context, Fun const& fun)
 382             {
 383                 return impl::call(fusion::begin(segs), fusion::end(segs), state, context, fun);
 384             }
 385         };
 386     }
 387 }}
 388
 389 #endif