// Copyright David Abrahams 2006. 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)

#include <boost/preprocessor/arithmetic/add.hpp>
#include <boost/preprocessor/arithmetic/div.hpp>
#include <boost/preprocessor/arithmetic/inc.hpp>
#include <boost/preprocessor/arithmetic/dec.hpp>
#include <boost/preprocessor/comparison/greater.hpp>
#include <boost/preprocessor/comparison/equal.hpp>
#include <boost/preprocessor/logical/or.hpp>
#include <boost/preprocessor/seq/elem.hpp>
#include <boost/preprocessor/seq.hpp>
#include <boost/preprocessor/seq/size.hpp>
#include <boost/preprocessor/seq/rest_n.hpp>
#include <boost/preprocessor/control/if.hpp>
#include <boost/preprocessor/control/iif.hpp>
#include <boost/preprocessor/cat.hpp>
#include <boost/preprocessor/comma.hpp>
#include <boost/preprocessor/iteration/local.hpp>

#define NEW_FRAME(level) (BOOST_PP_DIV(BOOST_PP_ADD(level,3), 4))(0)

#define FRAME_INC_CHILDREN(frame) (FRAME_LEVEL(frame))(BOOST_PP_INC(FRAME_CHILDREN(frame)))

#define FRAME_LEVEL(frame) BOOST_PP_SEQ_ELEM(0,frame)
#define FRAME_CHILDREN(frame) BOOST_PP_SEQ_ELEM(1,frame)

#define TOP(stack) BOOST_PP_SEQ_HEAD(stack)

// Instruction computation -- decide whether this iteration is a PUSH
// (opening a new "and" tree), a POP (closing an "and" tree), or a
// PRED (generating a predicate)

#define INSTRUCTION0(i, n, top)                         \
    BOOST_PP_IIF(                                       \
        BOOST_PP_OR(                                    \
            BOOST_PP_EQUAL( i, n )                      \
          , BOOST_PP_EQUAL( FRAME_CHILDREN(top), 4 ))   \
      , GEN_POP                                         \
      , INSTRUCTION1                                    \
    )(i,n,top)

#define GEN_POP(i,n,top) POP

#define INSTRUCTION1(i,n,top)                       \
    BOOST_PP_IIF(                                   \
        BOOST_PP_OR(                                \
            BOOST_PP_EQUAL( FRAME_LEVEL(top), 1 )   \
          , BOOST_PP_EQUAL( i, BOOST_PP_DEC(n) )    \
        )                                           \
      , PRED                                        \
      , PUSH                                        \
   )

// Augment a partial state (i)(n)(frame0)(frame1)... with an
// instruction prefix
#define INSTRUCT(i_n_stack)                     \
    (INSTRUCTION0(                              \
        BOOST_PP_SEQ_ELEM(0, i_n_stack)         \
      , BOOST_PP_SEQ_ELEM(1, i_n_stack)         \
      , BOOST_PP_SEQ_ELEM(2, i_n_stack)))       \
    i_n_stack

// Dispatch to a function implementation (base##instr) based on the
// first element of the 2nd parameter, a SEQ.
#define DO(base, instr_i_n_stack)                               \
    BOOST_PP_CAT(base, BOOST_PP_SEQ_ELEM(0, instr_i_n_stack))(  \
        BOOST_PP_SEQ_ELEM(1, instr_i_n_stack)                   \
      , BOOST_PP_SEQ_ELEM(2, instr_i_n_stack)                   \
      , BOOST_PP_SEQ_REST_N(3, instr_i_n_stack))

// The BOOST_PP_FOR continuation predicate
#define CONT(_, instr_i_n_stack) DO(CONT_, instr_i_n_stack)

// Stop looping when we're about to pop the last item in the stack
#define CONT_POP(i, n, stack) BOOST_PP_GREATER(BOOST_PP_SEQ_SIZE(stack),1)
#define CONT_PRED(i, n, stack) 1
#define CONT_PUSH(i, n, stack) 1

// The BOOST_PP_FOR next-state macro
#define NEXT(_, instr_i_n_stack) INSTRUCT(DO(NEXT_, instr_i_n_stack))

#define NEXT_POP(i, n, stack) \
    (i)(n) BOOST_PP_SEQ_POP_FRONT(stack)

#define NEXT_PRED(i, n, stack)                  \
    (BOOST_PP_INC(i))(n)                        \
    (FRAME_INC_CHILDREN(TOP(stack)))            \
    BOOST_PP_SEQ_TAIL(stack)

#define NEXT_PUSH(i, n, stack)                  \
    (i)(n)                                      \
    (NEW_FRAME(FRAME_LEVEL(TOP(stack))))        \
    (FRAME_INC_CHILDREN(TOP(stack)))            \
    BOOST_PP_SEQ_TAIL(stack)

// The BOOST_PP_FOR "printing" macro
#define M(_, instr_i_n_stack)  DO(M_, instr_i_n_stack)

#define M_POP(i, n, stack) >

#define MPL_AND() mpl::and<

#define M_NO_POP( stack ) \
    BOOST_PP_IF(FRAME_CHILDREN(TOP(stack)), BOOST_PP_COMMA, MPL_AND)()

#define M_PRED(i, n, stack)   \
    M_NO_POP(stack) BOOST_PP_CAT(pred,i)

#define M_PUSH(i, n, stack) M_NO_POP(stack)

#define INITIAL_STATE(n)  INSTRUCT( (0)(n) (NEW_FRAME(n)) )

#define TREE4(n)                                    \
    BOOST_PP_FOR(                                   \
        INITIAL_STATE(n)                            \
      , CONT                                        \
      , NEXT                                        \
      , M) >

// Test the macro
#define BOOST_PP_LOCAL_MACRO(n) TREE4(n)
#define BOOST_PP_LOCAL_LIMITS (1, 30)
#include BOOST_PP_LOCAL_ITERATE()