/*=============================================================================

    Copyright (c) 2003 Joel de Guzman

    Copyright (c) 2004 Peder Holt



    Use, modification and distribution is subject to 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(FUSION_ALGORITHM_DETAIL_FOLD_IPP)

#define FUSION_ALGORITHM_DETAIL_FOLD_IPP



#include <boost/mpl/bool.hpp>

#include <boost/type_traits/is_same.hpp>

#include <boost/spirit/fusion/sequence/begin.hpp>

#include <boost/spirit/fusion/sequence/end.hpp>

#include <boost/spirit/fusion/iterator/value_of.hpp>

#include <boost/spirit/fusion/iterator/next.hpp>



namespace boost { namespace fusion { namespace detail

{

    template <typename Iterator, typename State, typename F>

    struct fold_apply

    {

        typedef typename fusion_apply2<F,

            typename meta::value_of<Iterator>::type, 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 meta::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_<

                is_same<First, Last>

              , mpl::identity<State>

              , next_result_of_fold<First, Last, State, F>

            >::type

        result;



        typedef typename result::type type;

    };



    // terminal case

    template <typename First, typename Last, typename State, typename F>

    inline State const&

    fold(First const&, Last const&, State const& state, F const&, 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

    fold(

        First const& first

      , Last const& last

      , State const& state

      , F const& f

      , mpl::false_)

    {

        return detail::fold(

            fusion::next(first)

          , last

          , f(*first, state)

          , f

          , is_same<BOOST_DEDUCED_TYPENAME meta::next<First>::type, Last>()

        );

    }

}}}



#endif



