/* copyright Bram de Greve 2006
 * bram.degreve@gmail.com
 */

#include <iostream>

namespace meta
{

// types

struct null_type 
{
	typedef null_type type;
};

template <int V>
struct value_type
{
	enum { value = V };
	typedef value_type<V> type;
};

template <typename H, typename T>
struct list_type
{
	typedef H head;
	typedef T tail;
	typedef list_type<H, T> type;
};

template <typename T>
struct type_type
{
	typedef T type;
};



// simple type functions

template <typename T> struct not_;
template <int V> struct not_< value_type<V> >: public value_type<!V> {};

template <typename A, typename B> struct and_;
template <int A, int B> struct and_< value_type<A>, value_type<B> >: public value_type<A && B> {};

template <typename A, typename B> struct less;
template <int A, int B> struct less< value_type<A>, value_type<B> >: public value_type< A < B > {};

template <typename A, typename B> struct mod;
template <int A, int B> struct mod< value_type<A>, value_type<B> >: public value_type< A % B > {};

template <typename A, typename B> struct is_same_type_as: public value_type<false> {};
template <typename A> struct is_same_type_as<A, A>: public value_type<true> {};

template <typename From, typename To>
struct is_convertible_to
{
	typedef char small;
	struct big { small foo[2]; };
	static small test(To);
	static big test(...);
	static From dut();
	
	enum { value = sizeof(test(dut())) == sizeof(small) };
	typedef value_type<value> type;
};

template <typename Base, typename Derived>
struct is_base_of: 
	public and_
	<
		typename is_convertible_to<const volatile Derived*, const volatile Base*>::type,
		typename and_
		< 
			typename not_<typename is_same_type_as<
				const volatile Base*, const volatile Derived*>::type>::type,
			typename not_<typename is_same_type_as<
				const volatile Base*, const volatile void*>::type>::type
		>::type
	> {};
	

	
// functors

template <template <typename> class UnFun>
struct unary_fun
{
	template <typename A>
	struct apply: public UnFun<A> {};
};

template <template <typename, typename> class BinFun>
struct binary_fun
{
	template <typename A, typename B>
	struct apply: public BinFun<A, B> {};
};

typedef unary_fun<not_> not_fun;
typedef binary_fun<and_> and_fun;
typedef binary_fun<less> less_fun;
typedef binary_fun<is_base_of> is_base_of_fun;

template <typename BinFun, typename B>
struct bind_2nd_fun
{
	template <typename A>
	struct apply: public BinFun::template apply<A, B> {};
};

template <typename UnF, typename UnG>
struct f_gx_fun
{
	template <typename A>
	struct apply: 
		public UnF::template apply
		< 
			typename UnG::template apply<A>::type
		> {};
};

template <typename UnF, typename BinG>
struct f_gxy_fun
{
	template <typename A, typename B>
	struct apply: 
		public UnF::template apply
		< 
			typename BinG::template apply<A, B>::type
		> {};
};



// type selector

template <typename Expr, typename True, typename False> struct select;

template <typename True, typename False>
struct select<value_type<0>, True, False>: public False {};

template <int V, typename True, typename False>
struct select<value_type<V>, True, False>: public True {};



// some list functions

template <typename L> struct len;

template <>
struct len<null_type>: public value_type<0> {};

template <typename H, typename T>
struct len< list_type<H, T> >: public value_type<1 + len<T>::value> {};




template <typename L, typename I> struct at;

template <typename H, typename T>
struct at< list_type<H, T>, value_type<0> >: public type_type<H> {};

template <typename H, typename T, int I>
struct at< list_type<H, T>, value_type<I> >: public at< T, value_type<I - 1> > {};

template <int I>
struct at< null_type, value_type<I> >: public null_type {};



template <typename L, typename I> struct erase;

template <typename H, typename T>
struct erase< list_type<H, T>, value_type<0> >: public T {};

template <typename H, typename T, int I>
struct erase< list_type<H, T>, value_type<I> >: 
	public list_type<H, typename erase< T, value_type<I-1> >::type>  {};

template <int I>
struct erase< null_type, value_type<I> >: public null_type {};



template <typename L1, typename B> struct append;

template <>
struct append<null_type, null_type>: public null_type {};

template <typename H2, typename T2>
struct append<null_type, list_type<H2, T2> >: public list_type<H2, T2> {};

template <typename H2>
struct append<null_type, H2>: public list_type<H2, null_type> {};

template <typename H1, typename T1>
struct append< list_type<H1, T1>, null_type>: public list_type<H1, T1> {};

template <typename H1, typename T1, typename L2>
struct append< list_type<H1, T1>, L2 >: 
	public list_type
	<
		H1, 
		typename append<T1, L2>::type 
	> {};



template <typename L, typename UnPred> struct filter;

template <typename UnPred>
struct filter<null_type, UnPred>: public null_type {};

template <typename H, typename T, typename UnPred>
struct filter<list_type<H, T>, UnPred>: 
	public select
	< 
		typename UnPred::template apply<H>::type, 
		type_type< list_type<H, typename filter<T, UnPred>::type > >, 
		filter<T, UnPred> 
	> {};



// list generation

template <typename Generator, typename N> struct generate_n;

template <typename Generator, int N>
struct generate_n< Generator, value_type<N> >:
	public list_type
	< 
		typename Generator::head, 
		typename generate_n
		< 
			typename Generator::tail, 
			value_type<N - 1>
		>::type
	> {};

template <typename Generator>
struct generate_n< Generator, value_type<0> >: public null_type {};



// a generator
		
template <typename T = value_type<0> > struct random;

template <int I>
struct random< value_type<I> >
{
private:
	enum
	{
		mask = 123459876,
		a = 16807,
		m = 2147483647,
		q = 127773,
		r = 2836,
		i = I ^ mask,
		k = i / q,
		v = a * (i - k * q) - k * r
	};
public:
	enum { value = v < 0 ? (v + m) : v };
	typedef value_type<value> head;
	typedef random< value_type<value ^ mask> > tail;
};



// shuffle a list

template <typename L, typename Random> 
struct shuffle
{
private:
	typedef typename mod<typename Random::head, typename len<L>::type>::type i;
public:
	typedef list_type
	<
		typename at<L, i>::type,
		typename shuffle<typename erase<L, i>::type, typename Random::tail>::type
	> type;
};
	
template <typename Random> 
struct shuffle<null_type, Random>: public null_type {};




// sort list

template <typename L, typename BinPred = less_fun> struct quick_sort;

template <typename BinPred>
struct quick_sort<null_type, BinPred>: public null_type
{
};

template <typename H, typename T, typename BinPred>
struct quick_sort<list_type<H, T>, BinPred>: public
	append 
	< 
		typename quick_sort
		<
			typename filter
			<
				T, 
				bind_2nd_fun<BinPred, H> 
			>::type,
			BinPred
		>::type, 
		list_type
		<
			H, 
			typename quick_sort
			<
				typename filter
				<
					T, 
					f_gx_fun<not_fun, bind_2nd_fun<BinPred, H> >
				>::type,
				BinPred
			>::type
		>
	> {};

	
	

template <typename T> 
struct Printer
{
	template <typename Char, typename Traits>
	static std::basic_ostream<Char, Traits>& print(std::basic_ostream<Char, Traits>& stream)
	{
		return stream << typeid(T).name();
	}
};

template <> 
struct Printer<null_type>
{
	template <typename Char, typename Traits>
	static std::basic_ostream<Char, Traits>& print(std::basic_ostream<Char, Traits>& stream)
	{
		return stream << "null";
	}
};

template <int V>
struct Printer< value_type<V> >	
{	
	template <typename Char, typename Traits>
	static std::basic_ostream<Char, Traits>& print(std::basic_ostream<Char, Traits>& stream)
	{
		return stream << V;
	}
};

template <typename H, typename T>
struct Printer< list_type<H, T> >
{		
	template <typename Char, typename Traits>
	static std::basic_ostream<Char, Traits>& print(std::basic_ostream<Char, Traits>& stream)
	{
		Printer<H>::print(stream) << ", ";
		return Printer<T>::print(stream);
	}
};

template <typename T>
struct Printer< type_type<T> >
{		
	template <typename Char, typename Traits>
	static std::basic_ostream<Char, Traits>& print(std::basic_ostream<Char, Traits>& stream)
	{
		return Printer<T>::print(stream);
	}
};

}

class A {};
class B: public A {};
class C1: public B {};
class C2: public C1 {};
class D1: public B {};
class D2: public D1 {};

#define EVAL(x)\
	do\
	{\
		std::cout << #x << " = ";\
		Printer<x>::print(std::cout) << std::endl;\
	}\
	while (false)

int main()
{
	using namespace meta;
	
	typedef generate_n<meta::random<>, value_type<10> >::type random_list;
	typedef meta::quick_sort<random_list>::type sorted_list;
	EVAL(random_list);
	EVAL(sorted_list);

	typedef list_type<A, 
		list_type<B,
		list_type<C1,
		list_type<C2,
		list_type<D1,
		list_type<D2,
		null_type> > > > > > my_types;
	typedef shuffle<my_types, meta::random<> >::type random_types;
	typedef meta::quick_sort<random_types, is_base_of_fun>::type sorted_types;
	EVAL(random_types);
	EVAL(sorted_types);
p		
	return 0;
}