Skip to content

Instantly share code, notes, and snippets.

@howardlau1999
Created December 2, 2018 16:12
Show Gist options
  • Save howardlau1999/cacaf41c83511cfd591a40aa2527ec3e to your computer and use it in GitHub Desktop.
Save howardlau1999/cacaf41c83511cfd591a40aa2527ec3e to your computer and use it in GitHub Desktop.
C++ Template Metaprogramming
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment