Skip to content

Instantly share code, notes, and snippets.

@howardlau1999
Last active December 1, 2018 14:22
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save howardlau1999/cd90d591869a98ac72f92ad02b29d9c2 to your computer and use it in GitHub Desktop.
C++ Templates 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, 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... 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 ValueList, class Element,
template <class T, class U> class Compare,
bool = IsEmpty<ValueList>::value>
struct InsertSortedT;
template <class ValueList, class Element,
template <class T, class U> class Compare>
using InsertSorted = typename InsertSortedT<ValueList, Element, Compare>::Type;
template <class ValueList, class Element,
template <class T, class U> class Compare>
struct InsertSortedT<ValueList, Element, Compare, false> {
using NewTail =
IfThenElse<Compare<Element, Front<ValueList>>::value,
Identity<ValueList>,
InsertSorted<PopFront<ValueList>, Element, Compare>>;
using NewHead = IfThenElse<Compare<Element, Front<ValueList>>::value,
Element, Front<ValueList>>;
using Type = PushFront<NewTail, NewHead>;
};
template <class List, class Element,
template <class T, class U> class Compare>
struct InsertSortedT<List, Element, Compare, true>
: PushFrontT<List, Element> {};
template <class List, template <class T, class U> class Compare,
bool = IsEmpty<List>::value>
struct InsertionSortT;
template <class List, template <class T, class U> class Compare>
using InsertionSort = typename InsertionSortT<List, Compare>::Type;
template <class List, template <class T, class U> class Compare>
struct InsertionSortT<List, Compare, false>
: InsertSortedT<InsertionSort<PopFront<List>, Compare>,
Front<List>, Compare> {};
template <class List, template <class T, class U> class Compare>
struct InsertionSortT<List, Compare, true> {
using Type = List;
};
template <typename List, typename Element,
template <typename T, typename U> class Compare>
using InsertSorted = typename InsertSortedT<List, Element, Compare>::Type;
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 = InsertionSort<TestList, LessThanT>;
using ReverseSortedList = InsertionSort<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