C++ Template Metaprogramming

quick_sort.cpp

#include <iostream>

struct TrueType {
    constexpr static bool value = true;
};

struct FalseType {
    constexpr static bool value = false;
};

template <bool, typename T = void>
struct EnableIfT {};

template <typename T>
struct EnableIfT<true, T> {
    using Type = T;
};

template <bool Cond, typename T = void>
using EnableIf = typename EnableIfT<Cond, T>::Type;

template <class T, T Value>
struct CTValue {
    using Type = T;
    constexpr static T value = Value;
};

template <class T>
struct IdentityT {
    using Type = T;
};

template <class T>
using Identity = typename IdentityT<T>::Type;

template <bool COND, typename TrueType, typename FalseType>
struct IfThenElseT {
    using Type = TrueType;
};

template <typename TrueType, typename FalseType>
struct IfThenElseT<false, TrueType, FalseType> {
    using Type = FalseType;
};

template <bool COND, typename TrueType, typename FalseType>
using IfThenElse = typename IfThenElseT<COND, TrueType, FalseType>::Type;

template <class T, T... Values>
struct ValueList {};

template <class ValueList>
struct IsEmpty {};

template <class ValueList>
struct FrontT {};

template <class ValueList>
struct PopFrontT {};

template <class ValueList, class NewValue>
struct PushFrontT {};

template <class ValueList, class NewValue>
struct PushBackT {};

template <class T, class U>
struct LessThanT {};

template <class T, class U>
struct GreaterThanT {};

template <class T, class U>
struct GreaterThanOrEqualT {};

template <class T>
struct IsOddT {};

template <class T, T a, T b>
struct LessThanT<CTValue<T, a>, CTValue<T, b>> {
    constexpr static bool value = a < b;
};

template <class T, T a, T b>
struct GreaterThanT<CTValue<T, a>, CTValue<T, b>> {
    constexpr static bool value = a > b;
};

template <class T, T a, T b>
struct GreaterThanOrEqualT<CTValue<T, a>, CTValue<T, b>> {
    constexpr static bool value = a >= b;
};

template <class T, T Value>
struct IsOddT<CTValue<T, Value>> {
    constexpr static bool value = Value % 2;
};

template <class T, T... Values>
struct IsEmpty<ValueList<T, Values...>> {
    constexpr static bool value = sizeof...(Values) == 0;
};

template <class T, T Head, T... Tail>
struct FrontT<ValueList<T, Head, Tail...>> {
    using Type = CTValue<T, Head>;
    constexpr static T value = Head;
};

template <class List>
using Front = typename FrontT<List>::Type;

template <class T, T Head, T... Tail>
struct PopFrontT<ValueList<T, Head, Tail...>> {
    using Type = ValueList<T, Tail...>;
};

template <class List>
using PopFront = typename PopFrontT<List>::Type;

template <class T, T... Values, T NewValue>
struct PushFrontT<ValueList<T, Values...>, CTValue<T, NewValue>> {
    using Type = ValueList<T, NewValue, Values...>;
};

template <class List, class New>
using PushFront = typename PushFrontT<List, New>::Type;

template <class T, T... Values, T NewValue>
struct PushBackT<ValueList<T, Values...>, CTValue<T, NewValue>> {
    using Type = ValueList<T, NewValue, Values...>;
};


template <class ListA, class ListB, class... Tail>
struct ConcatT {};

template <class T, T... ValuesA, T... ValuesB, class... Tail>
struct ConcatT<ValueList<T, ValuesA...>, ValueList<T, ValuesB...>, Tail...>
    : ConcatT<ValueList<T, ValuesA..., ValuesB...>, Tail...> {};

template <class T, T... ValuesA, T... ValuesB>
struct ConcatT<ValueList<T, ValuesA...>, ValueList<T, ValuesB...>> {
    using Type = ValueList<T, ValuesA..., ValuesB...>;
};

template <class ListA, class ListB, class... Tail>
using Concat = typename ConcatT<ListA, ListB, Tail...>::Type;

template <class List, template <class T> class PredicateT,
          bool = IsEmpty<List>::value>
struct FilterT {};

template <class List, template <class T> class PredicateT,
          bool = IsEmpty<List>::value>
using Filter = typename FilterT<List, PredicateT>::Type;

template <class List, template <class T> class PredicateT>
struct FilterT<List, PredicateT, false> {
    using NewTail = Filter<PopFront<List>, PredicateT>;
    using NewHead = Front<List>;
    using Type = IfThenElse<PredicateT<NewHead>::value,
                            PushFront<NewTail, NewHead>, NewTail>;
};

template <class List, template <class T> class PredicateT>
struct FilterT<List, PredicateT, true> {
    using Type = List;
};

template <class List, template <class T> class PredicateT,
          bool = IsEmpty<List>::value>
struct PartitionT {};

template <class List, template <class T> class PredicateT>
struct PartitionT<List, PredicateT, false> {
    template <class T>
    struct NegationT {
        constexpr static bool value = !PredicateT<T>::value;
    };
    using Left = Filter<List, PredicateT>;
    using Right = Filter<List, NegationT>;
};

template <class List, template <class T> class PredicateT>
struct PartitionT<List, PredicateT, true> {
    using Left = List;
    using Right = List;
};

template <class List, template <class T, class U> class Compare, bool = IsEmpty<List>::value>
struct QuickSortT {};

template <class List, template <class T, class U> class Compare, bool = IsEmpty<List>::value>
using QuickSort = typename QuickSortT<List, Compare>::Type;

template <class List, template <class T, class U> class Compare>
struct QuickSortT<List, Compare, false> {
    using Pilot = Front<List>;

    template <class T>
    using PredicateT = Compare<T, Pilot>;
    using Partitioned = PartitionT<PopFront<List>, PredicateT>;
    using SortedLeft = QuickSort<typename Partitioned::Left, Compare>;
    using SortedRight = QuickSort<typename Partitioned::Right, Compare>;
    using Type = Concat<SortedLeft, ValueList<typename Pilot::Type, Pilot::value>, SortedRight>;
};

template <class List, template <class T, class U> class Compare>
struct QuickSortT<List, Compare, true> {
    using Type = List;
};

template <class T>
void OutputValueList(ValueList<T>) {
    std::cout << std::endl;
}

template <class T, T... Values>
void OutputValueList(ValueList<T, Values...>) {
    std::cout << Front<ValueList<T, Values...>>::value << ' ';
    OutputValueList(PopFront<ValueList<T, Values...>>());
};

int main() {
    using TestList = ValueList<int, 17, 1, 15, 9, 8, 19, 16, 10, 11, 7, 4, 14,
                               18, 13, 3, 12, 2, 5, 6, 20>;
    using SortedList = QuickSort<TestList, LessThanT>;
    using ReverseSortedList = QuickSort<TestList, GreaterThanT>;
    std::cout << "Before sorted" << std::endl;
    OutputValueList(TestList());
    std::cout << "After sorted (from small to great)" << std::endl;
    OutputValueList(SortedList());
    std::cout << "After sorted (from great to small)" << std::endl;
    OutputValueList(ReverseSortedList());
    return 0;
}