#include <iostream>

#include <boost/mpl/integral_c.hpp>
#include <boost/mpl/apply.hpp>
#include <boost/mpl/same_as.hpp>
#include <boost/mpl/list.hpp>

#ifdef TEST1
#include <boost/mpl/count_if.hpp>
#endif

#include <boost/mpl/bool_c.hpp>

#include <boost/static_assert.hpp>

#include "pp.h"

namespace boost{ namespace mpl {

#if defined( TEST1 )
	

#elif defined( TEST2 )

template< typename Sequence, typename Predicate >
struct count_if;

#define BOOST_MPL_PP_COUNT_IF_OPT_DEPTH 8
#define BOOST_MPL_PP_COUNT_IF_OPT_STEP 8

#define BOOST_MPL_PP_COUNT_IF_AUX( i, op ) \
  + apply< Predicate, BOOST_PP_CAT( H, i ) >::type::value \
/**/

#define BOOST_MPL_PP_COUNT_IF_OPT1( i, op ) \
  template< \
    BOOST_MPL_PP_PARAMS( 0, i, typename H ) \
    BOOST_PP_COMMA_IF( i ) \
    typename Predicate > \
  struct count_if< BOOST_MPL_PP_NUMBER_RECURSE( list_node<, H, 0, i, null_node, > ), Predicate > \
  { \
    typedef integral_c< unsigned long, 0 BOOST_PP_REPEAT( i, BOOST_MPL_PP_COUNT_IF_AUX, unsued ) > type; \
  }; \
/**/


BOOST_PP_REPEAT_2ND( BOOST_MPL_PP_COUNT_IF_OPT_DEPTH, BOOST_MPL_PP_COUNT_IF_OPT1, (unused) )

template< BOOST_MPL_PP_PARAMS( 0, BOOST_MPL_PP_COUNT_IF_OPT_STEP, typename H ), typename Tail, typename Predicate >
struct count_if< BOOST_MPL_PP_NUMBER_RECURSE( list_node<, H, 0, BOOST_MPL_PP_COUNT_IF_OPT_STEP, Tail, > ), Predicate >
{
  typedef typename count_if< Tail, Predicate >::type tail_count;
  typedef integral_c< unsigned long, (tail_count::value)
        BOOST_PP_REPEAT( BOOST_MPL_PP_COUNT_IF_OPT_STEP, BOOST_MPL_PP_COUNT_IF_AUX, unsued ) > type;
};

#elif defined( TEST3 )

namespace aux {

template< typename Sequence >
struct unrolling_size;

#define BOOST_MPL_PP_SIZE_OPT_DEPTH 8
#define BOOST_MPL_PP_SIZE_OPT_STEP 8

#define BOOST_MPL_PP_SIZE_OPT1( i, op ) \
  template< BOOST_MPL_PP_PARAMS( 0, i, typename H ) > \
  struct unrolling_size< BOOST_MPL_PP_NUMBER_RECURSE( list_node<, H, 0, i, null_node, > ) > \
  { \
    typedef integral_c< unsigned long, i > type; \
  }; \
/**/

BOOST_PP_REPEAT_2ND( BOOST_MPL_PP_SIZE_OPT_DEPTH, BOOST_MPL_PP_SIZE_OPT1, (unused) )

template< BOOST_MPL_PP_PARAMS( 0, BOOST_MPL_PP_SIZE_OPT_STEP, typename H ), class Tail >
struct unrolling_size< BOOST_MPL_PP_NUMBER_RECURSE( list_node<, H, 0, BOOST_MPL_PP_SIZE_OPT_STEP, Tail, > ) >
{
	typedef typename unrolling_size< Tail >::type tail_size;
        typedef integral_c< unsigned long, tail_size::value + BOOST_MPL_PP_SIZE_OPT_STEP > type;
};

template<
      typename First
    , typename Last
    , typename Predicate
    , long Size
    >
struct do_count_if;

} // namespace aux

template<
      typename Sequence
    , typename Predicate
    >
struct count_if
    : public aux::do_count_if<
          typename begin<Sequence>::type
        , typename end<Sequence>::type
        , Predicate
        , aux::unrolling_size< Sequence >::type::value
        >
{
};

// #define BOOST_MPL_COUNT_IF_UNROLLING_LIMIT BOOST_MPL_UNROLLING_LIMIT
#define BOOST_MPL_COUNT_IF_UNROLLING_LIMIT 8

namespace aux {

#define BOOST_MPL_PP_DO_COUNT_IF_AUX1( i, op ) \
  typedef typename BOOST_PP_CAT( iter, i ) ::next \
      BOOST_PP_CAT( iter, BOOST_PP_ADD( i, 1 ) ); \
/**/

#define BOOST_MPL_PP_DO_COUNT_IF_AUX2( i, op ) \
  + apply< Predicate, typename BOOST_PP_CAT( iter, i )::type >::type::value \
/**/

#define BOOST_MPL_PP_DO_COUNT_IF( i, op ) \
template< \
      typename First \
    , typename Last \
    , typename Predicate \
    > \
struct do_count_if<First,Last,Predicate,i> \
{ \
    typedef First iter0; \
    BOOST_PP_REPEAT( i, BOOST_MPL_PP_DO_COUNT_IF_AUX1, unused ) \
    typedef integral_c<unsigned long, 0 BOOST_PP_REPEAT( i, BOOST_MPL_PP_DO_COUNT_IF_AUX2, unsued )> type; \
    typedef BOOST_PP_CAT( iter, i ) last_iterator; \
}; \
/**/

BOOST_PP_REPEAT_2ND( BOOST_PP_ADD( BOOST_MPL_COUNT_IF_UNROLLING_LIMIT, 1 ), BOOST_MPL_PP_DO_COUNT_IF, unused )


// specialization for sequences with unknown size
template<
      typename First
    , typename Last
    , typename Predicate
    >
struct do_count_if<First,Last,Predicate,-1>
{
    // implement unsophisticated version
    // ...
    BOOST_STATIC_ASSERT( false );
};

// specialization for sequences with known size which
// exceeds BOOST_MPL_COUNT_IF_UNROLLING_LIMIT
template<
      typename First
    , typename Last
    , typename Predicate
    , long Size
    >
struct do_count_if
{
    typedef do_count_if<
          First
        , Last
        , Predicate
        , BOOST_MPL_COUNT_IF_UNROLLING_LIMIT
        > first_segment_;

    typedef do_count_if<
          typename first_segment_::last_iterator
        , Last
        , Predicate
        , Size - BOOST_MPL_COUNT_IF_UNROLLING_LIMIT
        > rest_;

    typedef typename integral_c<
          unsigned long
        , first_segment_::type::value + rest_::type::value
        >::type type;
};

} // namespace aux

#endif

} }

class a;
class b;

#define TEST_LIST_ITEM1( i, op ) \
  list_node< a, \
  list_node< a, \
  list_node< a, \
  list_node< a, \
  list_node< a, \
  list_node< b, \
  list_node< a, \
  list_node< a, \
  list_node< b, \
  list_node< a, \
/**/

#define TEST_LIST_ITEM2( i, op ) \
  > \
  > \
  > \
  > \
  > \
  > \
  > \
  > \
  > \
  > \
/**/

int main()
{
	using boost::mpl::list_node;
	using boost::mpl::null_node;
	using boost::mpl::count_if;
	
	typedef count_if<
		BOOST_PP_REPEAT( TEST_N, TEST_LIST_ITEM1, unused ) null_node
		BOOST_PP_REPEAT( TEST_N, TEST_LIST_ITEM2, unused ),
    boost::mpl::same_as< b > >::type result;
	
  std::cout << result::value << std::endl;
	
	return 0;
}