Тіпа сортування

[madf]

Або сортування типів.

Натхненний оцим: "Quick sort in compiltion time using C++11 variadic template", сортуванням списків типів із класичної "Modern C++ Design: Generic Programming and Design Patterns Applied" by Andrei Alexandrescu і необхідністю відсортувати список типових параметрів variadic template так щоб базові типи опинились в кінці я наваяв а-ля Quick Sort для типів.
Це не Quick Sort по тій же причині, по якій і оце:
qsort (p:xs) = qsort [x | x<-xs, x<p] ++ [p] ++ qsort [x | x<-xs, x>=p]
не є реалізацією Quick Sort - бо списки іммутабельні.
Але загальна ідея приблизно та: partitioning і рекурсивний виклик для піддіапазонів.
Enjoy!

#include <type_traits> template <typename ... Ts> struct Sequence; template <typename T, typename ... Ts> struct PushFront; template <typename T, typename ... Ts> struct PushFront<T, Sequence<Ts ...>> { typedef Sequence<T, Ts ...> type; }; template <typename LSeq, typename RSeq> struct Concat; template <typename ... Ts, typename ... Us> struct Concat<Sequence<Ts ...>, Sequence<Us ...>> { typedef Sequence<Ts ..., Us ...> type; }; template <template <typename, typename> class Comp, typename T, typename ... Ts> struct Partition; template <template <typename, typename> class Comp, typename T, typename LSeq, typename RSeq, typename ... Ts> struct PartitionImpl; template <template <typename, typename> class Comp, typename T, typename LSeq, typename RSeq, typename T0> struct PartitionImpl<Comp, T, LSeq, RSeq, Sequence<T0>> { typedef typename std::conditional<Comp<T, T0>::value, typename PushFront<T0, LSeq>::type, LSeq>::type left; typedef typename std::conditional<Comp<T, T0>::value, RSeq, typename PushFront<T0, RSeq>::type>::type right; }; template <template <typename, typename> class Comp, typename T, typename LSeq, typename RSeq, typename Tn, typename ... Ts> struct PartitionImpl<Comp, T, LSeq, RSeq, Sequence<Tn, Ts ...>> { typedef typename std::conditional<Comp<T, Tn>::value, typename PushFront<Tn, LSeq>::type, LSeq>::type tleft; typedef typename std::conditional<Comp<T, Tn>::value, RSeq, typename PushFront<Tn, RSeq>::type>::type tright; typedef typename PartitionImpl<Comp, T, tleft, tright, Sequence<Ts ...>>::left left; typedef typename PartitionImpl<Comp, T, tleft, tright, Sequence<Ts ...>>::right right; }; template <template <typename, typename> class Comp, typename T, typename ... Ts> struct Partition<Comp, T, Sequence<Ts ...>> { typedef typename PartitionImpl<Comp, T, Sequence<>, Sequence<>, Sequence<T, Ts ...>>::left left; typedef typename PartitionImpl<Comp, T, Sequence<>, Sequence<>, Sequence<T, Ts ...>>::right right; }; template <template <typename, typename> class Comp, typename ... Ts> struct Sort; template <template <typename, typename> class Comp> struct Sort<Comp, Sequence<>> { typedef Sequence<> type; }; template <template <typename, typename> class Comp, typename T> struct Sort<Comp, Sequence<T>> { typedef Sequence<T> type; }; template <template <typename, typename> class Comp, typename T, typename ... Ts> struct Sort<Comp, Sequence<T, Ts ...>> { typedef typename Partition<Comp, T, Sequence<Ts ...>>::left left; typedef typename Partition<Comp, T, Sequence<Ts ...>>::right right; typedef typename Concat<typename Sort<Comp, left>::type, typename Sort<Comp, right>::type>::type type; }; template <template <typename ...> class C, typename ... Ts> struct ApplySequence; template <template <typename ...> class C, typename ... Ts> struct ApplySequence<C, Sequence<Ts ...>> { typedef C<Ts ...> type; }; template <template <typename, typename> class Comp, template <typename ...> class C, typename ... Ts> struct ApplySorted { typedef typename Sort<Comp, Sequence<Ts ...>>::type sorted; typedef typename ApplySequence<C, sorted>::type type; };

_Winnie C++ Colorizer

Sequence потрібен щоб передавати списки типів. По суті він і є списком типів. ApplySorted і ApplySequence це такі helpers щоб назовні не стирчали Sequence.
Використовувати все це можна приблизно так (першим параметром йде метафункція less для пари типів, можна задати свою зберігаючи сигнатуру bool less<T1, T2>::value):

    ApplySorted<std::is_base_of, C, B, D1, D2, DD>::type data; // C<DD, D2, D1, B> data;

Щоб пересвідчитись що воно і справді все сортує я не придумав нічого іншого як "зламати" ApplySequence (прибрати спеціалізацію):

$ g++ -W -Wall -Wextra -pedantic -std=c++0x test.cpp -o test
In file included from test.cpp:7:0:
type_sort.h: In instantiation of ‘ApplySorted<std::is_base_of, HContainer, B, D1, D2, DD>’:
test.cpp:119:69:   instantiated from here
type_sort.h:80:53: error: invalid use of incomplete type ‘struct ApplySequence<HContainer, Sequence<DD, D2, D1, B> >’
type_sort.h:70:8: error: declaration of ‘struct ApplySequence<HContainer, Sequence<DD, D2, D1, B> >’

Як бачимо, типи йдуть відсортовані.

А от нафіга все це мені потрібно - розкажу пізніше.