#include <iostream>
#include <boost/proto/proto.hpp>
#include <boost/proto/proto_typeof.hpp>
#include <boost/fusion/include/vector.hpp>
#include <boost/fusion/include/push_back.hpp>

namespace mpl = boost::mpl;
namespace proto = boost::proto;
namespace fusion = boost::fusion;
using proto::_;

template<typename Int>
struct split_
{
    friend std::ostream &operator<<(std::ostream &sout, split_<Int> const &)
    {
        return sout << "split<" << Int::value << ">";
    }
};

proto::terminal<split_<mpl::int_<0> > >::type split = {{}};

struct first : proto::callable
{
    template<typename Sig>
    struct result;

    template<typename This, typename Pair>
    struct result<This(Pair)>
    {
        typedef typename boost::remove_reference<Pair>::type::first_type type;
    };
    
    template<typename Pair>
    typename Pair::first_type operator()(Pair const &p) const
    {
        return p.first;
    }
};

struct second : proto::callable
{
    template<typename Sig>
    struct result;

    template<typename This, typename Pair>
    struct result<This(Pair)>
    {
        typedef typename boost::remove_reference<Pair>::type::second_type type;
    };
    
    template<typename Pair>
    typename Pair::second_type operator()(Pair const &p) const
    {
        return p.second;
    }
};

struct make_pair : proto::callable
{
    template<typename Sig>
    struct result;

    template<typename This, typename First, typename Second>
    struct result<This(First, Second)>
    {
        typedef
            std::pair<
                typename boost::remove_const<typename boost::remove_reference<First>::type>::type
              , typename boost::remove_const<typename boost::remove_reference<Second>::type>::type
            >
        type;
    };

    template<typename First, typename Second>
    std::pair<First, Second> operator()(First const &first, Second const &second) const
    {
        return std::make_pair(first, second);
    }
};

struct push_back : proto::callable
{
    template<typename Sig>
    struct result;

    template<typename This, typename Cont, typename Elem>
    struct result<This(Cont, Elem)>
      : fusion::result_of::push_back<
            typename boost::add_const<typename boost::remove_reference<Cont>::type>::type
          , typename boost::remove_const<typename boost::remove_reference<Elem>::type>::type
        >
    {};

    template<typename Cont, typename Elem>
    typename fusion::result_of::push_back<Cont const, Elem>::type
    operator()(Cont const &cont, Elem const &elem) const
    {
        return fusion::push_back(cont, elem);
    }
};

#if BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1500))
#define _make_function(x,y) call<proto::_make_function(x,y)>
#define make_pair(x,y) proto::call<make_pair(x,y)>
#define push_back(x,y) proto::call<push_back(x,y)>
#define first(x) proto::call<first(x)>
#define second(x) proto::call<second(x)>
#define Renumber(x,y) proto::call<Renumber(x,y)>
#endif

struct Renumber;

struct Iterate
  : proto::fold<
        _
      , make_pair(
            fusion::vector0()
          , proto::_state
        )
      , make_pair(
            push_back(first(proto::_state), first(Renumber(_, second(proto::_state))))
          , proto::make<second(Renumber(_, second(proto::_state)))>
        )
    >
{};

// A transform that replaces all split_<0> terminals
// with consecutively numbered split_<N> terminals
struct Renumber
  : proto::or_<
        proto::when<
            proto::terminal<_>
          , make_pair(_, proto::_state)
        >
      , proto::when<
            proto::function<proto::terminal<split_<_> >, _>
          , make_pair(
                proto::_make_function(
                    proto::make<split_<proto::_state> >
                  , first(Renumber(proto::_child1, mpl::next<proto::_state>()))
                )
              , second(Renumber(proto::_child1, mpl::next<proto::_state>()))
            )
        >
      , proto::otherwise<
            make_pair(
                proto::lazy<
                    proto::functional::unpack_expr< proto::tag_of<_>() >(first(Iterate))
                >
              , proto::make<second(Iterate)>
            )
        >
    >
{};

#if BOOST_WORKAROUND(BOOST_MSVC, BOOST_TESTED_AT(1500))
#undef _make_function
#undef make_pair
#undef push_back
#undef first
#undef second
#undef Renumber
#endif

int main()
{
    proto::literal<int> i(0);
    BOOST_PROTO_AUTO(e, i + split(split(i)) + split( i * split( i - i ) ));

    proto::display_expr(e);
    std::cout << std::endl;

    proto::display_expr(Renumber()(e, mpl::int_<0>()).first);
    std::cout << std::endl;
}