#include <boost/preprocessor/arithmetic/inc.hpp>
#include <boost/preprocessor/arithmetic/dec.hpp>
#include <boost/preprocessor/arithmetic/mul.hpp>
#include <boost/preprocessor/logical/and.hpp>
#include <boost/preprocessor/comparison/equal.hpp>
#include <boost/preprocessor/seq/push_front.hpp>
#include <boost/preprocessor/seq/fold_right.hpp>
#include <boost/preprocessor/seq/elem.hpp>
#include <boost/preprocessor/seq/enum.hpp>
#include <boost/preprocessor/seq/pop_back.hpp>
#include <boost/preprocessor/seq/pop_front.hpp>
#include <boost/preprocessor/seq/rest_n.hpp>
#include <boost/preprocessor/seq/seq.hpp>
#include <boost/preprocessor/while.hpp>
#include <boost/preprocessor/if.hpp>
#include <boost/preprocessor/selection/min.hpp>
#include <boost/preprocessor/comparison/less_equal.hpp>
#include <boost/preprocessor/comparison/greater.hpp>


// Take a SEQ of MPL predicates and form a 4-ary tree using mpl::and.
#define AND_TREE(predicates)   \
    BOOST_PP_SEQ_ENUM(                              \
        tree_VAL( BOOST_PP_SEQ_HEAD(                \
            AND_FINALIZE( AND_PARSE( predicates ))  \
         ))                                         \
    )

// Use a shift-reduce LR(0) style algorithm to do most of the work of
// forming a balanced tree.  The ((0)()) is a "dummy" start symbol; we
// toss it out after the parse is complete.  The result is a SEQ
// representing the parse stack.  Symbols in the stack are "and" trees.
#define AND_PARSE( predicates )                                         \
    BOOST_PP_SEQ_POP_BACK(                                              \
          BOOST_PP_SEQ_FOLD_RIGHT( AND_SHIFT, ((0)()), predicates ))

// When this is called, stack is a SEQ containing only fully-balanced
// and<...> trees of different depths.  All that remains is to sew them
// together with a few more and<...> layers.
#define AND_FINALIZE( stack )                                   \
    BOOST_PP_WHILE(stack_IS_MULTIPLE, stack_REDUCE_final, stack)

// A reduce operation for the finalization steps, where we can't count
// on every and<...> having 4 children.
#define stack_REDUCE_final(d, stack)                                 \
    stack_REDUCE_n(stack, BOOST_PP_MIN(4,BOOST_PP_SEQ_SIZE(stack)))

// True iff there are multiple items in stack
#define stack_IS_MULTIPLE(d, stack) BOOST_PP_GREATER(BOOST_PP_SEQ_SIZE(stack),1)

// Given a stack and a new predicate, add the predicate to the stack
// and perform any eligible reduce operations.
#define AND_SHIFT(s, stack, pred)  \
    BOOST_PP_WHILE( stack_REDUCIBLE, stack_REDUCE, ((1)(pred)) stack )

// Replace the first 4 stack elements with a single element that
// combines them into a deeper tree
#define stack_REDUCE(d,stack) stack_REDUCE_n(stack,4)                                   

// Replace the first n symbols on the stack with a single element that
// combines them into a deeper tree
#define stack_REDUCE_n(stack,n)                              \
    (                                                       \
     tree_WRAP(                                             \
         stack_CAT_VALS( BOOST_PP_SEQ_FIRST_N(n,stack) ))   \
    ) BOOST_PP_SEQ_REST_N(n, stack)

// Wrap an "and<...>" around the given SEQ.  Prepend "and<" to its
// first element and append ">" to its last element.
#define tree_WRAP(seq) tree_WRAP_(BOOST_PP_SEQ_SIZE(seq),seq)
#define tree_WRAP_(len,seq) (len)(mpl::and< BOOST_PP_SEQ_HEAD(seq)) BOOST_PP_SEQ_POP_BACK(BOOST_PP_SEQ_POP_FRONT(seq)) (BOOST_PP_SEQ_ELEM(BOOST_PP_DEC(len),seq) >)


// Each "symbol" on the stack is an "and tree".
//
// An "and tree" is just a SEQ whose first element is the SEQ's
// length-1.  Each element of the SEQ represents a comma-separated
// token sequence in the generated result.
#define tree_LEN(t) BOOST_PP_SEQ_HEAD(t)
#define tree_VAL(t) BOOST_PP_SEQ_TAIL(t)

//
// Determine whether we can do a REDUCE operation when building a
// balanced tree.
//
#define stack_REDUCIBLE( d, stack )                         \
    BOOST_PP_IIF(                                           \
        BOOST_PP_LESS_EQUAL(BOOST_PP_SEQ_SIZE(stack), 4)    \
      , stack_FALSE                                         \
      , stack_SAME_LEN4) (stack)

// Do the first four elements of the stack have the
// same depth?
#define stack_SAME_LEN4(stack)                                                                 \
    BOOST_PP_AND(                                                                               \
        BOOST_PP_AND(                                                                           \
            BOOST_PP_EQUAL(tree_LEN(BOOST_PP_SEQ_ELEM(0,stack)),tree_LEN(BOOST_PP_SEQ_ELEM(1,stack)))   \
          , BOOST_PP_EQUAL(tree_LEN(BOOST_PP_SEQ_ELEM(0,stack)),tree_LEN(BOOST_PP_SEQ_ELEM(2,stack))))  \
      , BOOST_PP_EQUAL(tree_LEN(BOOST_PP_SEQ_ELEM(0,stack)),tree_LEN(BOOST_PP_SEQ_ELEM(3,stack))))

// helper
#define stack_FALSE(stack) 0

// Return a SEQ consisting of the VAL parts of all the trees in stack,
// concatenated
#define stack_CAT_VALS(stack) \
    BOOST_PP_SEQ_POP_FRONT(BOOST_PP_SEQ_FOLD_LEFT(stack_CAT, (-), stack))
#define stack_CAT(s, state, elem) state tree_VAL(elem) 
    

AND_TREE( (p0) )
AND_TREE( (p0)(p1) )
AND_TREE( (p0)(p1)(p2) )
AND_TREE( (p0)(p1)(p2)(p3) )
AND_TREE( (p0)(p1)(p2)(p3)(p4) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11)(p12) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11)(p12)(p13) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11)(p12)(p13)(p14) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11)(p12)(p13)(p14)(p15) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11)(p12)(p13)(p14)(p15)(p16) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11)(p12)(p13)(p14)(p15)(p16)(p17) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11)(p12)(p13)(p14)(p15)(p16)(p17)(p18) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11)(p12)(p13)(p14)(p15)(p16)(p17)(p18)(p19) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11)(p12)(p13)(p14)(p15)(p16)(p17)(p18)(p19)(p20) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11)(p12)(p13)(p14)(p15)(p16)(p17)(p18)(p19)(p20)(p21) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11)(p12)(p13)(p14)(p15)(p16)(p17)(p18)(p19)(p20)(p21)(p22) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11)(p12)(p13)(p14)(p15)(p16)(p17)(p18)(p19)(p20)(p21)(p22)(p23) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11)(p12)(p13)(p14)(p15)(p16)(p17)(p18)(p19)(p20)(p21)(p22)(p23)(p24) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11)(p12)(p13)(p14)(p15)(p16)(p17)(p18)(p19)(p20)(p21)(p22)(p23)(p24)(p25) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11)(p12)(p13)(p14)(p15)(p16)(p17)(p18)(p19)(p20)(p21)(p22)(p23)(p24)(p25)(p26) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11)(p12)(p13)(p14)(p15)(p16)(p17)(p18)(p19)(p20)(p21)(p22)(p23)(p24)(p25)(p26)(p27) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11)(p12)(p13)(p14)(p15)(p16)(p17)(p18)(p19)(p20)(p21)(p22)(p23)(p24)(p25)(p26)(p27)(p28) )
AND_TREE( (p0)(p1)(p2)(p3)(p4)(p5)(p6)(p7)(p8)(p9)(p10)(p11)(p12)(p13)(p14)(p15)(p16)(p17)(p18)(p19)(p20)(p21)(p22)(p23)(p24)(p25)(p26)(p27)(p28)(p29) )