| /*============================================================================= |
| Copyright (c) 2001-2006 Joel de Guzman |
| Copyright (c) 2006 Dan Marsden |
| |
| Distributed under the Boost Software License, Version 1.0. (See accompanying |
| file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
| ==============================================================================*/ |
| #if !defined(BOOST_FUSION_FOLD_HPP_20070528_1253) |
| #define BOOST_FUSION_FOLD_HPP_20070528_1253 |
| |
| #include <boost/mpl/bool.hpp> |
| #include <boost/mpl/apply.hpp> |
| #include <boost/mpl/identity.hpp> |
| #include <boost/fusion/iterator/equal_to.hpp> |
| #include <boost/fusion/sequence/intrinsic/begin.hpp> |
| #include <boost/fusion/sequence/intrinsic/end.hpp> |
| #include <boost/fusion/iterator/deref.hpp> |
| #include <boost/fusion/iterator/value_of.hpp> |
| #include <boost/fusion/iterator/next.hpp> |
| #include <boost/fusion/iterator/distance.hpp> |
| #include <boost/utility/result_of.hpp> |
| |
| #include <boost/type_traits/add_const.hpp> |
| #include <boost/type_traits/add_reference.hpp> |
| |
| namespace boost { namespace fusion { |
| namespace result_of |
| { |
| template <typename Sequence, typename State, typename F> |
| struct fold; |
| } |
| namespace detail |
| { |
| template <typename F> |
| struct apply_fold_result |
| { |
| template <typename Value, typename State> |
| struct apply |
| : boost::result_of<F(Value,State)> |
| {}; |
| }; |
| |
| template <typename Iterator, typename State, typename F> |
| struct fold_apply |
| { |
| typedef typename result_of::deref<Iterator>::type dereferenced; |
| typedef typename add_reference<typename add_const<State>::type>::type lvalue_state; |
| typedef typename boost::result_of<F(dereferenced, lvalue_state)>::type type; |
| }; |
| |
| template <typename First, typename Last, typename State, typename F> |
| struct static_fold; |
| |
| template <typename First, typename Last, typename State, typename F> |
| struct next_result_of_fold |
| { |
| typedef typename |
| static_fold< |
| typename result_of::next<First>::type |
| , Last |
| , typename fold_apply<First, State, F>::type |
| , F |
| >::type |
| type; |
| }; |
| |
| template <typename First, typename Last, typename State, typename F> |
| struct static_fold |
| { |
| typedef typename |
| mpl::if_< |
| result_of::equal_to<First, Last> |
| , mpl::identity<State> |
| , next_result_of_fold<First, Last, State, F> |
| >::type |
| result; |
| |
| typedef typename result::type type; |
| }; |
| |
| template<typename I0, typename State, typename F, int N> |
| struct result_of_unrolled_fold; |
| |
| template<int N> |
| struct unrolled_fold |
| { |
| template<typename I0, typename State, typename F> |
| static typename result_of_unrolled_fold<I0, State, F, N>::type |
| call(I0 const& i0, State const& state, F f) |
| { |
| typedef typename result_of::next<I0>::type I1; |
| I1 i1 = fusion::next(i0); |
| typedef typename result_of::next<I1>::type I2; |
| I2 i2 = fusion::next(i1); |
| typedef typename result_of::next<I2>::type I3; |
| I3 i3 = fusion::next(i2); |
| typedef typename result_of::next<I3>::type I4; |
| I4 i4 = fusion::next(i3); |
| |
| return unrolled_fold<N-4>::call(i4, f(*i3, f(*i2, f(*i1, f(*i0, state)))), f); |
| } |
| }; |
| |
| template<> |
| struct unrolled_fold<3> |
| { |
| template<typename I0, typename State, typename F> |
| static typename result_of_unrolled_fold<I0, State, F, 3>::type |
| call(I0 const& i0, State const& state, F f) |
| { |
| typedef typename result_of::next<I0>::type I1; |
| I1 i1 = fusion::next(i0); |
| typedef typename result_of::next<I1>::type I2; |
| I2 i2 = fusion::next(i1); |
| return f(*i2, f(*i1, f(*i0, state))); |
| } |
| }; |
| |
| template<> |
| struct unrolled_fold<2> |
| { |
| template<typename I0, typename State, typename F> |
| static typename result_of_unrolled_fold<I0, State, F, 2>::type |
| call(I0 const& i0, State const& state, F f) |
| { |
| typedef typename result_of::next<I0>::type I1; |
| I1 i1 = fusion::next(i0); |
| return f(*i1, f(*i0, state)); |
| } |
| }; |
| |
| template<> |
| struct unrolled_fold<1> |
| { |
| template<typename I0, typename State, typename F> |
| static typename result_of_unrolled_fold<I0, State, F, 1>::type |
| call(I0 const& i0, State const& state, F f) |
| { |
| return f(*i0, state); |
| } |
| }; |
| |
| template<> |
| struct unrolled_fold<0> |
| { |
| template<typename I0, typename State, typename F> |
| static State call(I0 const&, State const& state, F) |
| { |
| return state; |
| } |
| }; |
| |
| // terminal case |
| template <typename First, typename Last, typename State, typename F> |
| inline State const& |
| linear_fold(First const&, Last const&, State const& state, F, mpl::true_) |
| { |
| return state; |
| } |
| |
| // non-terminal case |
| template <typename First, typename Last, typename State, typename F> |
| inline typename static_fold<First, Last, State, F>::type |
| linear_fold( |
| First const& first |
| , Last const& last |
| , State const& state |
| , F f |
| , mpl::false_) |
| { |
| return detail::linear_fold( |
| fusion::next(first) |
| , last |
| , f(*first, state) |
| , f |
| , result_of::equal_to<typename result_of::next<First>::type, Last>() |
| ); |
| } |
| |
| template<typename I0, typename State, typename F, int N> |
| struct result_of_unrolled_fold |
| { |
| typedef typename result_of::next<I0>::type I1; |
| typedef typename result_of::next<I1>::type I2; |
| typedef typename result_of::next<I2>::type I3; |
| typedef typename result_of::next<I3>::type I4; |
| typedef typename fold_apply<I0, State, F>::type Rest1; |
| typedef typename fold_apply<I1, Rest1, F>::type Rest2; |
| typedef typename fold_apply<I2, Rest2, F>::type Rest3; |
| typedef typename fold_apply<I3, Rest3, F>::type Rest4; |
| |
| typedef typename result_of_unrolled_fold<I4, Rest4, F, N-4>::type type; |
| }; |
| |
| template<typename I0, typename State, typename F> |
| struct result_of_unrolled_fold<I0, State, F, 3> |
| { |
| typedef typename result_of::next<I0>::type I1; |
| typedef typename result_of::next<I1>::type I2; |
| typedef typename fold_apply<I0, State, F>::type Rest; |
| typedef typename fold_apply<I1, Rest, F>::type Rest2; |
| typedef typename fold_apply<I2, Rest2, F>::type type; |
| }; |
| |
| template<typename I0, typename State, typename F> |
| struct result_of_unrolled_fold<I0, State, F, 2> |
| { |
| typedef typename result_of::next<I0>::type I1; |
| typedef typename fold_apply<I0, State, F>::type Rest; |
| typedef typename fold_apply<I1, Rest, F>::type type; |
| }; |
| |
| template<typename I0, typename State, typename F> |
| struct result_of_unrolled_fold<I0, State, F, 1> |
| { |
| typedef typename fold_apply<I0, State, F>::type type; |
| }; |
| |
| template<typename I0, typename State, typename F> |
| struct result_of_unrolled_fold<I0, State, F, 0> |
| { |
| typedef State type; |
| }; |
| |
| template<typename Sequence, typename State, typename F, bool> |
| struct choose_fold; |
| |
| template<typename Sequence, typename State, typename F> |
| struct choose_fold<Sequence, State, F, true> |
| { |
| typedef typename result_of::begin<Sequence>::type begin; |
| typedef typename result_of::end<Sequence>::type end; |
| typedef typename result_of_unrolled_fold< |
| begin, State, F, result_of::distance<begin, end>::type::value>::type type; |
| }; |
| |
| template<typename Sequence, typename State, typename F> |
| struct choose_fold<Sequence, State, F, false> |
| { |
| typedef typename |
| detail::static_fold< |
| typename result_of::begin<Sequence>::type |
| , typename result_of::end<Sequence>::type |
| , State |
| , F |
| >::type |
| type; |
| }; |
| |
| template<typename Sequence, typename State, typename F, typename Tag> |
| typename result_of::fold<Sequence, State, F>::type |
| fold(Sequence& seq, State const& state, F f, Tag) |
| { |
| return linear_fold( |
| fusion::begin(seq) |
| , fusion::end(seq) |
| , state |
| , f |
| , result_of::equal_to< |
| typename result_of::begin<Sequence>::type |
| , typename result_of::end<Sequence>::type>() |
| ); |
| } |
| |
| template<typename Sequence, typename State, typename F> |
| typename result_of::fold<Sequence, State, F>::type |
| fold(Sequence& seq, State const& state, F f, random_access_traversal_tag) |
| { |
| typedef typename result_of::begin<Sequence>::type begin; |
| typedef typename result_of::end<Sequence>::type end; |
| return unrolled_fold<result_of::distance<begin, end>::type::value>::call( |
| fusion::begin(seq) |
| , state |
| , f); |
| } |
| }}} |
| |
| #endif |
