boost/fusion/algorithm/iteration/detail/fold.hpp

   1 /*=============================================================================
   2     Copyright (c) 2001-2006 Joel de Guzman
   3     Copyright (c) 2006 Dan Marsden
   4
   5     Distributed under the Boost Software License, Version 1.0. (See accompanying
   6     file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   7 ==============================================================================*/
   8 #if !defined(BOOST_FUSION_FOLD_HPP_20070528_1253)
   9 #define BOOST_FUSION_FOLD_HPP_20070528_1253
  10
  11 #include <boost/mpl/bool.hpp>
  12 #include <boost/mpl/apply.hpp>
  13 #include <boost/mpl/identity.hpp>
  14 #include <boost/fusion/iterator/equal_to.hpp>
  15 #include <boost/fusion/sequence/intrinsic/begin.hpp>
  16 #include <boost/fusion/sequence/intrinsic/end.hpp>
  17 #include <boost/fusion/iterator/deref.hpp>
  18 #include <boost/fusion/iterator/value_of.hpp>
  19 #include <boost/fusion/iterator/next.hpp>
  20 #include <boost/fusion/iterator/distance.hpp>
  21 #include <boost/utility/result_of.hpp>
  22
  23 #include <boost/type_traits/add_const.hpp>
  24 #include <boost/type_traits/add_reference.hpp>
  25
  26 namespace boost { namespace fusion {
  27 namespace result_of
  28 {
  29     template <typename Sequence, typename State, typename F>
  30     struct fold;
  31 }
  32 namespace detail
  33 {
  34     template <typename F>
  35     struct apply_fold_result
  36     {
  37         template <typename Value, typename State>
  38         struct apply
  39             : boost::result_of<F(Value,State)>
  40         {};
  41     };
  42
  43     template <typename Iterator, typename State, typename F>
  44     struct fold_apply
  45     {
  46         typedef typename result_of::deref<Iterator>::type dereferenced;
  47         typedef typename add_reference<typename add_const<State>::type>::type lvalue_state;
  48         typedef typename boost::result_of<F(dereferenced, lvalue_state)>::type type;
  49     };
  50
  51     template <typename First, typename Last, typename State, typename F>
  52     struct static_fold;
  53
  54     template <typename First, typename Last, typename State, typename F>
  55     struct next_result_of_fold
  56     {
  57         typedef typename
  58         static_fold<
  59             typename result_of::next<First>::type
  60             , Last
  61             , typename fold_apply<First, State, F>::type
  62             , F
  63             >::type
  64         type;
  65     };
  66
  67     template <typename First, typename Last, typename State, typename F>
  68     struct static_fold
  69     {
  70         typedef typename
  71         mpl::if_<
  72             result_of::equal_to<First, Last>
  73             , mpl::identity<State>
  74             , next_result_of_fold<First, Last, State, F>
  75         >::type
  76         result;
  77
  78         typedef typename result::type type;
  79     };
  80
  81     template<typename I0, typename State, typename F, int N>
  82     struct result_of_unrolled_fold;
  83
  84     template<int N>
  85     struct unrolled_fold
  86     {
  87         template<typename I0, typename State, typename F>
  88         static typename result_of_unrolled_fold<I0, State, F, N>::type
  89         call(I0 const& i0, State const& state, F f)
  90         {
  91             typedef typename result_of::next<I0>::type I1;
  92             I1 i1 = fusion::next(i0);
  93             typedef typename result_of::next<I1>::type I2;
  94             I2 i2 = fusion::next(i1);
  95             typedef typename result_of::next<I2>::type I3;
  96             I3 i3 = fusion::next(i2);
  97             typedef typename result_of::next<I3>::type I4;
  98             I4 i4 = fusion::next(i3);
  99
 100             return unrolled_fold<N-4>::call(i4, f(*i3, f(*i2, f(*i1, f(*i0, state)))), f);
 101         }
 102     };
 103
 104     template<>
 105     struct unrolled_fold<3>
 106     {
 107         template<typename I0, typename State, typename F>
 108         static typename result_of_unrolled_fold<I0, State, F, 3>::type
 109         call(I0 const& i0, State const& state, F f)
 110         {
 111             typedef typename result_of::next<I0>::type I1;
 112             I1 i1 = fusion::next(i0);
 113             typedef typename result_of::next<I1>::type I2;
 114             I2 i2 = fusion::next(i1);
 115             return f(*i2, f(*i1, f(*i0, state)));
 116         }
 117     };
 118
 119     template<>
 120     struct unrolled_fold<2>
 121     {
 122         template<typename I0, typename State, typename F>
 123         static typename result_of_unrolled_fold<I0, State, F, 2>::type
 124         call(I0 const& i0, State const& state, F f)
 125         {
 126             typedef typename result_of::next<I0>::type I1;
 127             I1 i1 = fusion::next(i0);
 128             return f(*i1, f(*i0, state));
 129         }
 130     };
 131
 132     template<>
 133     struct unrolled_fold<1>
 134     {
 135         template<typename I0, typename State, typename F>
 136         static typename result_of_unrolled_fold<I0, State, F, 1>::type
 137         call(I0 const& i0, State const& state, F f)
 138         {
 139             return f(*i0, state);
 140         }
 141     };
 142
 143     template<>
 144     struct unrolled_fold<0>
 145     {
 146         template<typename I0, typename State, typename F>
 147         static State call(I0 const&, State const& state, F)
 148         {
 149             return state;
 150         }
 151     };
 152
 153     // terminal case
 154     template <typename First, typename Last, typename State, typename F>
 155     inline State const&
 156     linear_fold(First const&, Last const&, State const& state, F, mpl::true_)
 157     {
 158         return state;
 159     }
 160
 161     // non-terminal case
 162     template <typename First, typename Last, typename State, typename F>
 163     inline typename static_fold<First, Last, State, F>::type
 164     linear_fold(
 165         First const& first
 166       , Last const& last
 167       , State const& state
 168       , F f
 169       , mpl::false_)
 170     {
 171         return detail::linear_fold(
 172             fusion::next(first)
 173           , last
 174           , f(*first, state)
 175           , f
 176           , result_of::equal_to<typename result_of::next<First>::type, Last>()
 177         );
 178     }
 179
 180     template<typename I0, typename State, typename F, int N>
 181     struct result_of_unrolled_fold
 182     {
 183         typedef typename result_of::next<I0>::type I1;
 184         typedef typename result_of::next<I1>::type I2;
 185         typedef typename result_of::next<I2>::type I3;
 186         typedef typename result_of::next<I3>::type I4;
 187         typedef typename fold_apply<I0, State, F>::type Rest1;
 188         typedef typename fold_apply<I1, Rest1, F>::type Rest2;
 189         typedef typename fold_apply<I2, Rest2, F>::type Rest3;
 190         typedef typename fold_apply<I3, Rest3, F>::type Rest4;
 191
 192         typedef typename result_of_unrolled_fold<I4, Rest4, F, N-4>::type type;
 193     };
 194
 195     template<typename I0, typename State, typename F>
 196     struct result_of_unrolled_fold<I0, State, F, 3>
 197     {
 198         typedef typename result_of::next<I0>::type I1;
 199         typedef typename result_of::next<I1>::type I2;
 200         typedef typename fold_apply<I0, State, F>::type Rest;
 201         typedef typename fold_apply<I1, Rest, F>::type Rest2;
 202         typedef typename fold_apply<I2, Rest2, F>::type type;
 203     };
 204
 205     template<typename I0, typename State, typename F>
 206     struct result_of_unrolled_fold<I0, State, F, 2>
 207     {
 208         typedef typename result_of::next<I0>::type I1;
 209         typedef typename fold_apply<I0, State, F>::type Rest;
 210         typedef typename fold_apply<I1, Rest, F>::type type;
 211     };
 212
 213     template<typename I0, typename State, typename F>
 214     struct result_of_unrolled_fold<I0, State, F, 1>
 215     {
 216         typedef typename fold_apply<I0, State, F>::type type;
 217     };
 218
 219     template<typename I0, typename State, typename F>
 220     struct result_of_unrolled_fold<I0, State, F, 0>
 221     {
 222         typedef State type;
 223     };
 224
 225     template<typename Sequence, typename State, typename F, bool>
 226     struct choose_fold;
 227
 228     template<typename Sequence, typename State, typename F>
 229     struct choose_fold<Sequence, State, F, true>
 230     {
 231         typedef typename result_of::begin<Sequence>::type begin;
 232         typedef typename result_of::end<Sequence>::type end;
 233         typedef typename result_of_unrolled_fold<
 234             begin, State, F, result_of::distance<begin, end>::type::value>::type type;
 235     };
 236
 237     template<typename Sequence, typename State, typename F>
 238     struct choose_fold<Sequence, State, F, false>
 239     {
 240         typedef typename
 241         detail::static_fold<
 242             typename result_of::begin<Sequence>::type
 243             , typename result_of::end<Sequence>::type
 244             , State
 245             , F
 246             >::type
 247         type;
 248     };
 249
 250     template<typename Sequence, typename State, typename F, typename Tag>
 251     typename result_of::fold<Sequence, State, F>::type
 252     fold(Sequence& seq, State const& state, F f, Tag)
 253     {
 254         return linear_fold(
 255             fusion::begin(seq)
 256           , fusion::end(seq)
 257           , state
 258           , f
 259           , result_of::equal_to<
 260                 typename result_of::begin<Sequence>::type
 261               , typename result_of::end<Sequence>::type>()
 262         );
 263     }
 264
 265     template<typename Sequence, typename State, typename F>
 266     typename result_of::fold<Sequence, State, F>::type
 267     fold(Sequence& seq, State const& state, F f, random_access_traversal_tag)
 268     {
 269         typedef typename result_of::begin<Sequence>::type begin;
 270         typedef typename result_of::end<Sequence>::type end;
 271         return unrolled_fold<result_of::distance<begin, end>::type::value>::call(
 272             fusion::begin(seq)
 273             , state
 274             , f);
 275     }
 276 }}}
 277
 278 #endif