CppTemplateTutorial
/
QuickSort.cpp

#include <tuple>
#include <type_traits>
#include <iostream>

using std::tuple;
using std::integral_constant;
using std::is_same;

template <int... values> struct to_int_types{
	typedef tuple< integral_constant<int, values>... > type;
};

template <typename Pivot> struct Less {
	template <typename X> struct Apply {
		static bool const value = X::value < Pivot::value;
	};
};

template <typename Pivot> struct GE {
	template <typename X> struct Apply {
		static bool const value = X::value >= Pivot::value;
	};
};

template <typename x, bool realAdd, typename tuple>         struct Tuple_PushFront {};
template <typename x, typename... tupleElems> struct Tuple_PushFront<x, true, tuple<tupleElems...>> {
	typedef tuple<x, tupleElems...> type;
};
template <typename x, typename... tupleElems> struct Tuple_PushFront<x, false, tuple<tupleElems...>> {
	typedef tuple<tupleElems...> type;
};

template <typename Pred, typename tuple> struct Filter;
template <typename Pred> struct Filter< Pred, tuple<> > {
	typedef tuple<> type;
};
template <typename Pred, typename Head, typename... Ts> struct Filter< Pred, tuple<Head, Ts...> > {
	typedef typename Tuple_PushFront<
		Head, Pred::template Apply<Head>::value, typename Filter<Pred, tuple<Ts...>>::type
	>::type type;
};

template <typename... Tuples> struct ConcatenateTuple {};
template <typename    Tuple0> struct ConcatenateTuple<Tuple0> {
	typedef Tuple0 type;
};

template <typename Tuple0, typename Tuple1> struct ConcatenateTuple<Tuple0, Tuple1> {
	template <typename TupleA> struct ConcatenateImpl {};
	template <typename... TAs> struct ConcatenateImpl< tuple<TAs...> > {
		template <typename TupleB> struct Apply;
		template <typename... TBs> struct Apply< tuple<TBs...> > {
			typedef tuple<TAs..., TBs...> type;
		};
	};
	typedef typename ConcatenateImpl<Tuple0>::template Apply<Tuple1>::type type;
};
template <typename FirstTuple, typename... Follows> struct ConcatenateTuple<FirstTuple, Follows...> {
	typedef typename ConcatenateTuple<
		FirstTuple, typename ConcatenateTuple<Follows...>::type
	>::type type;
};

template <typename tuple> struct QuickSort {};
template <>               struct QuickSort< tuple<  > > { typedef tuple<  > type; };
template <typename T0>    struct QuickSort< tuple<T0> > { typedef tuple<T0> type; };
template <typename Head, typename... Ts>
struct QuickSort< tuple<Head, Ts...> > {
	typedef typename Filter< Less<Head>, tuple<Ts...> >::type LeftElems;
	typedef typename Filter< GE  <Head>, tuple<Ts...> >::type RightElems;
	typedef typename ConcatenateTuple<
		typename QuickSort<LeftElems>::type, tuple<Head>, typename QuickSort<RightElems>::type
	>::type type;
};

void StaticTest()
{
	typedef to_int_types<1, 2, 3>::type lst_1_3;
	typedef to_int_types<3, 2, 1>::type lst_3_1;
	typedef to_int_types<3, 7, 1, 6, 5, 22, 5>::type lst;
	typedef to_int_types<1, 3, 5, 5, 6, 7, 22>::type sorted_lst;

	typedef integral_constant<int, 1>::type i1;
	typedef integral_constant<int, 2>::type i2;
	typedef integral_constant<int, 3>::type i3;

	static_assert(Less<i2>::Apply<i1>::value == true, "");
	static_assert(Less<i1>::Apply<i1>::value == false, "");
	static_assert(Less<i1>::Apply<i2>::value == false, "");

	static_assert(GE<i2>::Apply<i3>::value == true, "");
	static_assert(GE<i2>::Apply<i2>::value == true, "");
	static_assert(GE<i3>::Apply<i2>::value == false, "");

	static_assert(is_same<Tuple_PushFront<i1, true,  tuple<i2>>::type, tuple<i1, i2>>::value, "");
	static_assert(is_same<Tuple_PushFront<i2, true,  tuple<i1>>::type, tuple<i2, i1>>::value, "");
	static_assert(is_same<Tuple_PushFront<i2, false, tuple<i1>>::type, tuple<i1>>::value,     "");

	static_assert(is_same<Filter<Less<i2>, lst_1_3>::type, tuple<i1>>::value, "");

	static_assert(is_same<QuickSort<lst_1_3  >::type, lst_1_3>::value, "");
	static_assert(is_same<QuickSort<lst_3_1  >::type, lst_1_3>::value, "");
	static_assert(is_same<QuickSort<tuple<>  >::type, tuple<>>::value, "");
	static_assert(is_same<QuickSort<tuple<i1>>::type, tuple<i1>>::value, "");
	static_assert(is_same<QuickSort<lst      >::type, sorted_lst>::value, "");
}