#ifndef BOOST_MPL_WHILE_HPP_INCLUDED
#define BOOST_MPL_WHILE_HPP_INCLUDED
// Copyright Larry Evans 2009
//

// $Id: while.cpp,v 1.51 2009/06/05 15:55:23 evansl Exp $
// $Date: 2009/06/05 15:55:23 $
// $Revision: 1.51 $

#include <boost/mpl/eval_if.hpp>
#include <boost/mpl/apply.hpp>
#include <boost/mpl/identity.hpp>
#include <boost/mpl/arg.hpp>
#include <boost/mpl/always.hpp>
#include <boost/mpl/equal.hpp>
#define USE_WHILE_UNROLL
#ifdef USE_WHILE_UNROLL
#   include <boost/preprocessor/repeat.hpp>
#   include <boost/preprocessor/inc.hpp>
#   include <boost/preprocessor/cat.hpp>
#endif

namespace boost
{
namespace mpl
{
    //Notation:
    //  MFC_or_LE = Metafunction class or Lambda Expression
    //    (See Description on libs/mpl/doc/refmanual/apply.html)
    //
    //  State = Any type.
    //    (this is term used in libs/mpl/doc/refmanual/fold.html)
    //
      template
      < class StateMeta//nullary metafunction returning current State.
      , class OpPred=always<false_>//unary MFC_or_LE from State to Bool.
      , class OpThen=identity<arg<1> >//unary MFC_or_LE from State to State,
      >
    struct while_recur
    {
            typedef        
          typename eval_if
          < typename apply<OpPred,typename StateMeta::type>::type
          , while_recur
            < apply<OpThen,typename StateMeta::type>
            , OpPred
            , OpThen
            >
          , StateMeta
          >::type
        type
        ;
    };
    
      template
      < class OpPred
      , class OpThen
      , class OpElse=identity<arg<1> >
      >
    struct while_step
    /**@brief
     *  metafunction class whose nested apply template 
     *  represents one iteration in a while_recur loop with
     *  given OpPred and Opthen.
     *  i.e. one iteration of the "loop":
     *
     *    while_recur<State,OpPred,OpThen>
     *
     */
    {
          template
          < class StateOld
          >
        struct apply
        /**@brief
         *  Calculates new state from old state, StateOld.
         */
        : eval_if
          < typename ::boost::mpl::apply
            < OpPred
            , StateOld
            >::type
          , ::boost::mpl::apply
            < OpThen
            , StateOld
            >
          , ::boost::mpl::apply
            < OpElse
            , StateOld
            >
          >
        {};
          
    };

#ifdef USE_WHILE_UNROLL    

// local macros, #undef-ined at the end of the header
//
//   Acknowledegement:
//     Thr following macros are modelled after:
//       AUX_ITER_FOLD_FORWARD_STEP
//       AUX_LAST_FORWARD_STEP
//     at:
//       https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/aux_/iter_fold_if_impl.hpp#L124
//     on:
//        2009-06-02(revision 29239)
//

#   define AUX_WHILE_UNROLL_STEP(unused, i, unused2) \
          typedef \
        typename while_unroller::template apply \
        < typename BOOST_PP_CAT(while_unroll_step,i)::type \
        > \
     BOOST_PP_CAT(while_unroll_step, BOOST_PP_INC(i)); \
    /**/
    
#   define AUX_LAST_UNROLL_STEP \
    BOOST_PP_CAT(while_unroll_step, BOOST_MPL_LIMIT_UNROLLING) \
    /**/
    
      template
      < class StateMeta//nullary metafunction returning current State.
      , class OpPred=always<false_>//unary MFC_or_LE from State to Bool.
      , class OpThen=identity<arg<1> >//unary MFC_or_LE from State to State,
      >
    struct while_unroll_recur
    /**@brief
     *  Purpose is same as while_recur; however, lessens the template recursion
     *  depth problem.
     **@references
     *  [1] http://www.mywikinet.com/mpl/paper/mpl_paper.html#sequences.unrolling
     *      (NOTE: there's a typo.  The `recursion` typedef should have
     *      `fold_impl` instead of `fold_impl_step` as its template name.
     *      Also, the recursion typedef here uses eval_if *and* while_unroll_recur
     *      instead of just the enclosing while_unroll_recur {fold_impl in [1]} .)
     */
    {
     private:
            typedef
          while_step
          < OpPred
          , OpThen
          >
        while_unroller
        ;
            typedef
          StateMeta
        while_unroll_step0
        ;

        //The following BOOST_PP_REPEAT call corresponds to the
        //1st one inside the `struct iter_fold_if_impl` of
        //https://svn.boost.org/trac/boost/browser/trunk/boost/mpl/aux_/iter_fold_if_impl.hpp
        BOOST_PP_REPEAT(
              BOOST_MPL_LIMIT_UNROLLING
            , AUX_WHILE_UNROLL_STEP
            , unused
            )
            
            typedef
          AUX_LAST_UNROLL_STEP
        last_unroll_step
        ; 
            typedef 
          eval_if
          < typename apply<OpPred,typename last_unroll_step::type>::type
          , while_unroll_recur
            < apply<OpThen,typename last_unroll_step::type>
            , OpPred
            , OpThen
            >
          , last_unroll_step
          > 
        recursion
        ;

     public:
            typedef 
          typename recursion::type 
        type
        ;
          
    };
#   undef AUX_WHILE_UNROLL_STEP
#   undef AUX_LAST_UNROLL_STEP

#endif //USE_WHILE_UNROLL
    
      template
      < class StateNow
      , class OpStateState
      , class OpStatesEqual=is_same<arg<1>,arg<2> >
      >
    struct fix_point
    /**@brief
     *   Finds the fixed point of unary metafunction
     *   class, OpStateState.
     */
    {
            typedef
          StateNow
        state_now
        ;
            typedef
          typename OpStateState::template apply
          < state_now
          >::type
        state_next
        ;
            typedef
          fix_point
          < state_next
          , OpStateState
          , OpStatesEqual
          >
        op_recur
        ;
            typedef
          typename apply
          < OpStatesEqual
          , state_now
          , state_next
          >::type
        done
        ;
            typedef
          typename eval_if
          < done
          , identity<state_now>
          , op_recur
          >::type
        type
        ;
    };
    
}//exit mpl namespace
}//exit boost namespace
#endif

#ifndef BOOST_MPL_WHILE_RECUR_SEQ_HPP_INCLUDED
#define BOOST_MPL_WHILE_RECUR_SEQ_HPP_INCLUDED
//#include <boost/mpl/while.hpp>
#include <boost/mpl/begin_end.hpp>
#include <boost/mpl/next.hpp>
#include <boost/mpl/deref.hpp>
#include <boost/mpl/push_front.hpp>
#include <boost/mpl/and.hpp>
#include <boost/mpl/list.hpp>

namespace boost
{
namespace mpl
{
namespace aux
{
namespace while_recur_seq
{

  template
  < typename State
  >
struct while_state
{
    typedef State state;
    typedef while_state type;
};
  template
  < typename Stack
  , typename State
  >
struct while_stack_state
: while_state<State>
{
    typedef Stack stack;
    typedef while_stack_state type;
};
  template
  < typename State
  , typename Iter
  >
struct while_state_iter
: State //either while_state or while_stack_state
{
    typedef Iter iter;
    typedef while_state_iter type;
};

  template
  < typename State
  , typename Op
  >
struct forward_step
{
        typedef
      typename deref<typename State::iter>::type
    item;
        typedef
      while_state_iter
      < while_stack_state
        < typename push_front<typename State::stack, item>::type
        , typename apply<Op,typename State::state,item>::type
        >
      , typename next<typename State::iter>::type
      >
    type;
    
};

  template
  < typename State
  , typename Op
  >
struct backward_step
{
        typedef
      typename deref<typename State::iter>::type
    item;
        typedef
      while_state_iter
      < while_state<typename apply<Op,typename State::state,item>::type>
      , typename next<typename State::iter>::type
      >
    type;
    
};

  template
  < typename State
  , typename Op
  >
struct direction_step
;

  template
  < typename State
  , typename Iter
  , typename Op
  >
struct direction_step
  < while_state_iter
    < while_state<State>
    , Iter
    >
  , Op
  >
: backward_step
  < while_state_iter<State,Iter>
  , Op
  >
{  
};

  template
  < typename Stack
  , typename State
  , typename Iter
  , typename Op
  >
struct direction_step
  < while_state_iter
    < while_stack_state<Stack,State>
    , Iter
    >
  , Op
  >
: forward_step
  < while_state_iter
    < while_stack_state<Stack,State>
    , Iter
    >
  , Op
  >
{  
};

  template
  < typename StateNow
  , typename IterLast
  >
struct not_iter_last
: not_
  < is_same
    < typename StateNow::iter
    , IterLast
    >
  >
{
};

  template
  < typename Op
  , typename LazyExpr
  >
struct apply_lazy1
{
    typedef typename apply<Op,typename LazyExpr::type>::type type;
};  
  template
  < typename StateNow
  , typename IterLast
  , typename Predicate=always<true_>
  >
struct not_iter_last_pred
: and_
  < not_iter_last<StateNow,IterLast>
  , apply_lazy1<Predicate, deref<typename StateNow::iter> >
  >
{
};

}//exit while_recur_seq namespace

}//exit aux namespace

  template
  < typename Seq
  , typename State
  , typename OperStateVal
  , typename PredicateVal=always<true_>
  , template<class,class>class Step=aux::while_recur_seq::backward_step
  >
struct while_seq_directed
{
        typedef
      typename begin<Seq>::type
    first;
        typedef
      typename end<Seq>::type
    last;
        typedef
      aux::while_recur_seq::while_state_iter<State,first>
    state_iter;
        typedef
      Step
      < arg<1>
      , typename lambda<OperStateVal>::type
      >
    oper_state_ref;
        typedef
      aux::while_recur_seq::not_iter_last_pred
      < arg<1>
      , last
      , typename lambda<PredicateVal>::type
      >
    predicate_ref;
        typedef
      typename 
    #ifdef USE_WHILE_UNROLL
      while_unroll_recur
    #else
      while_recur
    #endif
      < state_iter
      , predicate_ref
      , oper_state_ref
      >::type
    type;
};

  template
  < typename BOOST_MPL_AUX_NA_PARAM(Sequence)
  , typename BOOST_MPL_AUX_NA_PARAM(State)
  , typename BOOST_MPL_AUX_NA_PARAM(ForwardOp)
  , typename BOOST_MPL_AUX_NA_PARAM(ForwardPredicate)
  , typename BOOST_MPL_AUX_NA_PARAM(BackwardOp)
  , typename BOOST_MPL_AUX_NA_PARAM(BackwardPredicate)
  >
struct while_recur_seq
{
  #define WHILE_RECUR_SEQ_USE_WHILE_SEQ_DIRECTED
    struct forward
    {
        typedef list<> stack0;
        typedef Sequence seq;
        typedef State state_0;
      #ifndef WHILE_RECUR_SEQ_USE_WHILE_SEQ_DIRECTED
        typedef typename begin<seq>::type first;
        typedef typename end<seq>::type last;
        typedef typename lambda<ForwardOp>::type state_op;
        typedef typename lambda<ForwardPredicate>::type pred_op;
        
            typedef 
          aux::while_recur_seq::while_state_iter
          < aux::while_recur_seq::while_stack_state<stack0,state_0>
          , first
          > 
        state_aux_0;
        typedef aux::while_recur_seq::not_iter_last_pred< arg<1>, last, pred_op> pred_aux_op;
        typedef aux::while_recur_seq::forward_step< arg<1>, state_op> state_aux_op;
        
        typedef typename while_recur<state_aux_0,pred_aux_op,state_aux_op>::type result;
      #else
            typedef
          typename while_seq_directed
          < seq
          , aux::while_recur_seq::while_stack_state<stack0,state_0>
          , ForwardOp
          , ForwardPredicate
          , aux::while_recur_seq::forward_step
          >::type
        result
        ;
      #endif
    };

    struct backward
    {
        typedef typename forward::result::stack seq;
        typedef typename forward::result::state state_0;
      #ifndef WHILE_RECUR_SEQ_USE_WHILE_SEQ_DIRECTED
        typedef typename begin<seq>::type first;
        typedef typename end<seq>::type last;
        typedef typename lambda<BackwardOp>::type state_op;
        typedef typename lambda<BackwardPredicate>::type pred_op;
        
            typedef 
          aux::while_recur_seq::while_state_iter
          < aux::while_recur_seq::while_state<state_0>
          , first
          > 
        state_aux_0;
        typedef aux::while_recur_seq::not_iter_last_pred< arg<1>, last, pred_op> pred_aux_op;
        typedef aux::while_recur_seq::backward_step<arg<1>,state_op> state_aux_op;
        
        typedef typename while_recur<state_aux_0,pred_aux_op,state_aux_op>::type result;
      #else
            typedef
          typename while_seq_directed
          < seq
          , aux::while_recur_seq::while_state<state_0>
          , BackwardOp
          , BackwardPredicate
          , aux::while_recur_seq::backward_step
          >::type
        result
        ;
      #endif
    };

    typedef typename backward::result::state type;
        
};

}//exit mpl namespace
}//exit boost namespace
#endif

//-{--while_recur_seq_test--
#include <boost/mpl/list.hpp>
#include <boost/mpl/list_c.hpp>
#include <boost/mpl/range_c.hpp>
#include <boost/mpl/vector.hpp>
#include <boost/mpl/vector_c.hpp>

#include <boost/mpl/less.hpp>
#include <boost/mpl/greater.hpp>
#include <boost/mpl/equal_to.hpp>
#include <boost/mpl/equal.hpp>
#include <boost/mpl/pair.hpp>

#include <boost/mpl/aux_/test.hpp>

namespace boost
{
namespace mpl
{
namespace test_while
{
    typedef
  int
int_type
;  
    typedef
#if 0
  range_c< int_type, 9, 13>
#else
  list_c< int_type, 9, 10, 11, 12>
#endif
numbers
;
  namespace palindrome
  {
        typedef
      while_recur_seq
      < numbers
      , vector<>
      , push_front<arg<1>, arg<2> >
      , always<true_>
      , push_front<arg<1>, arg<2> >
      , always<true_>
      >
    while_result
    ;
        typedef
      while_result::type
    actual_result
    ;
        typedef
      vector_c<int_type, 9,10,11,12,12,11,10,9>
    expected_result
    ;
    BOOST_MPL_ASSERT((equal<actual_result,expected_result>))
    ;
  
  }//exit palindrome namespace
  
  namespace palindrome_pred_fwd
  {
        typedef
      while_recur_seq
      < numbers
      , vector<>
      , push_front<arg<1>, arg<2> >
      , less<arg<1>,integral_c<int_type,12> >
      , push_front<arg<1>, arg<2> >
      , always<true_>
      >
    while_result
    ;
        typedef
      while_result::type
    actual_result
    ;
        typedef
      vector_c<int, 9,10,11,11,10,9>
    expected_result
    ;
    BOOST_MPL_ASSERT((equal<actual_result,expected_result>))
    ;
  
  }//exit palindrome_pred_fwd namespace
   
  namespace palindrome_pred_both
  {
        typedef
      while_recur_seq
      < numbers
      , vector<>
      , push_front<arg<1>, arg<2> >
      , less<arg<1>,integral_c<int_type,12> >
      , push_front<arg<1>, arg<2> >
      , greater<arg<1>,integral_c<int_type,9> >
      >
    while_result
    ;
        typedef
      while_result::type
    actual_result
    ;
        typedef
      vector_c<int, 10,11,11,10,9>
    expected_result
    ;
    BOOST_MPL_ASSERT((equal<actual_result,expected_result>))
    ;
  
  }//exit palindrome_pred_both namespace
   
}//exit test_while namespace

namespace test_fix_point
{
    typedef
  int
int_type
;  
  namespace int_dec_to_0
  {
        typedef
      integral_c<int_type,0>
    expected_fix_down_result
    ;
      int_type const
    val0_down=3
    ;
        typedef
      integral_c<int_type,val0_down>
    state0_down
    ;
        typedef
      greater<arg<1>,expected_fix_down_result>
    op_pred_down
    ;  
        typedef
      apply
      < op_pred_down
      , state0_down
      >::type
    actual_pred_down_result
    ;
    BOOST_MPL_ASSERT((actual_pred_down_result))
    ;
        typedef
      prior<arg<1> >
    op_state_down
    ;
  #if 1
        typedef
      while_step
      < op_pred_down
      , op_state_down
      >
    op_step_down
    ;
        typedef
      op_step_down::apply<state0_down>::type
    actual_step_down_result
    ;
        typedef
      prior<state0_down>::type
    expected_step_down_result
    ;
    BOOST_MPL_ASSERT((equal_to<actual_step_down_result,expected_step_down_result>))
    ;
  #endif
  #if 1
        typedef
      fix_point
      < state0_down
      , op_step_down
      , equal_to<arg<1>,arg<2> >
      >::type
    actual_fix_down_result
    ;
    BOOST_MPL_ASSERT((equal_to<actual_fix_down_result,expected_fix_down_result>))
    ;
  #endif
        typedef
      op_step_down::apply<state0_down>::type
    state1_down
    ;
        typedef
      op_step_down::apply<state1_down>::type
    state2_down
    ;
    BOOST_MPL_ASSERT_NOT((equal_to<state2_down,expected_fix_down_result>))
    ;
        typedef
      op_step_down::apply<state2_down>::type
    state3_down
    ;
    BOOST_MPL_ASSERT((equal_to<state3_down,expected_fix_down_result>))
    ;
        typedef
      integral_c<int_type,val0_down+2>
    expected_fix_up_result
    ;
        typedef
      and_
      < greater<first<arg<1> >,expected_fix_down_result>
      , less<second<arg<1> >,expected_fix_up_result>
      >
    op_pred_up
    ;  
        typedef
      next<second<arg<1> > >
    op_state_up
    ;
        typedef
      while_step
      < op_pred_up
      , op_state_up
      , second<arg<1> >
      >
    op_step_up
    ;
        typedef
      pair<state3_down,state3_down>
    state3_pair
    ;
        typedef
      apply
      < op_pred_up
      , state3_pair
      >::type
    actual_op_pred_state3_up
    ;
    BOOST_MPL_ASSERT_NOT((actual_op_pred_state3_up))
    ;
        typedef
      apply
      < op_state_up
      , state3_pair
      >::type
    actual_op_state_state3_up
    ;
    BOOST_MPL_ASSERT((is_same<actual_op_state_state3_up,next<state3_down>::type>))
    ;
        typedef
      op_step_up::apply
      < state3_pair
      >::type
    state3_up
    ;
    BOOST_MPL_ASSERT((equal_to<state3_up,state3_down>))
    ;
        typedef
      pair<state2_down,state3_up>
    state2_pair
    ;
        typedef
      apply
      < op_pred_up
      , state2_pair
      >::type
    actual_op_pred_state2_up
    ;
    BOOST_MPL_ASSERT((actual_op_pred_state2_up))
    ;
        typedef
      op_step_up::apply
      < state2_pair
      >::type
    state2_up
    ;
    BOOST_MPL_ASSERT((equal_to<state2_up,state2_down>))
    ;
        typedef
      pair<state1_down,state2_up>
    state1_pair
    ;
        typedef
      op_step_up::apply
      < state1_pair
      >::type
    state1_up
    ;
    BOOST_MPL_ASSERT((equal_to<state1_up,state1_down>))
    ;
        typedef
      pair<state0_down,state1_up>
    state0_pair
    ;
        typedef
      op_step_up::apply
      < state0_pair
      >::type
    state0_up
    ;
    BOOST_MPL_ASSERT((equal_to<state0_up,state0_down>))
    ;
  #if 0
  #endif
        
  }//exit int_dec_to_0 namespace
  
}//exit test_fix_point namespace

}//exit mpl namespace
}//exit boost namespace
//-}--while_recur_seq_test--