#include <iostream>
#include <functional>
#include <tuple>
template <typename Type, typename Comp, Type ... values>
struct Sequence
{};
template <typename Type, typename Comp, Type ... values1, Type ... values2>
constexpr decltype (auto) spliceSequences (const Sequence <Type, Comp, values1 ...>,
const Sequence <Type, Comp, values2 ...>)
{
return Sequence <Type, Comp, values1 ..., values2 ...> {};
};
template <typename Type, typename Comp, Type ... values>
struct Sort;
template <typename Type, typename Comp, Type ... values>
constexpr decltype (auto) makeSort (const Sequence <Type, Comp, values ...>)
{
return typename Sort <Type, Comp, values ...>::seq {};
}
template <typename Type, typename Comp, Type pivot, Type head, Type ... tail>
struct GetLess
{
private:
using first = typename std::conditional <
Comp {} (head, pivot),
Sequence <Type, Comp, head>,
Sequence < Type, Comp >
>::type ;
using second = typename GetLess <Type, Comp, pivot, tail ...>::seq;
public:
using seq = decltype (spliceSequences (first {}, second {}));
};
template <typename Type, typename Comp, Type pivot, Type head>
struct GetLess <Type, Comp, pivot, head>
{
using seq = typename std::conditional <
Comp {} (head, pivot),
Sequence <Type, Comp, head>,
Sequence < Type, Comp >>::type ;
};
template <typename Type, typename Comp, Type pivot, Type head, Type ... tail>
struct GetEqual
{
private:
using first = typename std::conditional <
(Comp {} (head, pivot) || Comp {} (pivot, head)),
Sequence <Type, Comp>,
Sequence <Type, Comp, head >
>::type ;
using second = typename GetEqual <Type, Comp, pivot, tail ...>::seq;
public:
using seq = decltype (spliceSequences (first {}, second {}));
};
template <typename Type, typename Comp, Type pivot, Type head>
struct GetEqual <Type, Comp, pivot, head>
{
using seq = typename std::conditional <
(Comp {} (head, pivot) || Comp {} (pivot, head)),
Sequence <Type, Comp>,
Sequence <Type, Comp, head >
>::type ;
};
template <typename Type, typename Comp, Type pivot, Type head, Type ... tail>
struct GetGreater
{
private:
using first = typename std::conditional <
Comp {} (pivot, head),
Sequence <Type, Comp, head>,
Sequence < Type, Comp >
>::type ;
using second = typename GetGreater <Type, Comp, pivot, tail ...>::seq;
public:
using seq = decltype (spliceSequences (first {}, second {}));
};
template <typename Type, typename Comp, Type pivot, Type head>
struct GetGreater <Type, Comp, pivot, head>
{
using seq = typename std::conditional <
Comp {} (pivot, head),
Sequence <Type, Comp, head>,
Sequence < Type, Comp >
>::type ;
};
template <typename Type, typename Comp, Type ... values>
struct Sort
{
private:
constexpr static Type pivot =
std::get <sizeof ... (values) / 2> (std::make_tuple (values ...));
public:
using seq = decltype (spliceSequences (
makeSort (typename GetLess <Type, Comp, pivot, values ...>::seq {}),
spliceSequences (typename GetEqual <Type, Comp, pivot, values ...>::seq {},
makeSort (typename GetGreater <Type, Comp, pivot, values ...>::seq {}))
));
};
template <typename Type, typename Comp, Type head>
struct Sort <Type, Comp, head>
{
using seq = Sequence <Type, Comp, head>;
};
template <typename Type, typename Comp>
struct Sort <Type, Comp>
{
using seq = Sequence <Type, Comp>;
};
template <typename Type, typename Comp, Type head, Type ... tail>
void printSequence (Sequence <Type, Comp, head, tail ...>)
{
std::cout << head << ' ';
printSequence (Sequence <Type, Comp, tail ...> {});
}
template <typename Type, typename Comp, Type head>
void printSequence (Sequence <Type, Comp, head>)
{
std::cout << head << std::endl;
}
int main ()
{
printSequence (Sort <int, std::greater <int>, 3, 2, 7, 1, -1, 1, 1488, 1, 1, 1, 2, -1, 25, 14, 7, 8, 7, 25>::seq {});
return 0;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8ZnVuY3Rpb25hbD4KI2luY2x1ZGUgPHR1cGxlPgoKdGVtcGxhdGUgPHR5cGVuYW1lIFR5cGUsIHR5cGVuYW1lIENvbXAsIFR5cGUgLi4uIHZhbHVlcz4Kc3RydWN0IFNlcXVlbmNlCnt9OwoKdGVtcGxhdGUgPHR5cGVuYW1lIFR5cGUsIHR5cGVuYW1lIENvbXAsIFR5cGUgLi4uIHZhbHVlczEsIFR5cGUgLi4uIHZhbHVlczI+CmNvbnN0ZXhwciBkZWNsdHlwZSAoYXV0bykgc3BsaWNlU2VxdWVuY2VzIChjb25zdCBTZXF1ZW5jZSA8VHlwZSwgQ29tcCwgdmFsdWVzMSAuLi4+LAoJCQkJCQkJCQkJICAgY29uc3QgU2VxdWVuY2UgPFR5cGUsIENvbXAsIHZhbHVlczIgLi4uPikKewoJcmV0dXJuIFNlcXVlbmNlIDxUeXBlLCBDb21wLCB2YWx1ZXMxIC4uLiwgdmFsdWVzMiAuLi4+IHt9Owp9OwoKdGVtcGxhdGUgPHR5cGVuYW1lIFR5cGUsIHR5cGVuYW1lIENvbXAsIFR5cGUgLi4uIHZhbHVlcz4Kc3RydWN0IFNvcnQ7Cgp0ZW1wbGF0ZSA8dHlwZW5hbWUgVHlwZSwgdHlwZW5hbWUgQ29tcCwgVHlwZSAuLi4gdmFsdWVzPgpjb25zdGV4cHIgZGVjbHR5cGUgKGF1dG8pIG1ha2VTb3J0IChjb25zdCBTZXF1ZW5jZSA8VHlwZSwgQ29tcCwgdmFsdWVzIC4uLj4pCnsKCXJldHVybiB0eXBlbmFtZSBTb3J0IDxUeXBlLCBDb21wLCB2YWx1ZXMgLi4uPjo6c2VxIHt9Owp9Cgp0ZW1wbGF0ZSA8dHlwZW5hbWUgVHlwZSwgdHlwZW5hbWUgQ29tcCwgVHlwZSBwaXZvdCwgVHlwZSBoZWFkLCBUeXBlIC4uLiB0YWlsPgpzdHJ1Y3QgR2V0TGVzcwp7CnByaXZhdGU6CgoJdXNpbmcgZmlyc3QgPSB0eXBlbmFtZSBzdGQ6OmNvbmRpdGlvbmFsIDwKCQlDb21wIHt9IChoZWFkLCBwaXZvdCksCgkJU2VxdWVuY2UgPFR5cGUsIENvbXAsIGhlYWQ+LAoJCVNlcXVlbmNlIDwgVHlwZSwgQ29tcCA+Cgk+Ojp0eXBlIDsKCgl1c2luZyBzZWNvbmQgPSB0eXBlbmFtZSBHZXRMZXNzIDxUeXBlLCBDb21wLCBwaXZvdCwgdGFpbCAuLi4+OjpzZXE7CgpwdWJsaWM6CgoJdXNpbmcgc2VxID0gZGVjbHR5cGUgKHNwbGljZVNlcXVlbmNlcyAoZmlyc3Qge30sIHNlY29uZCB7fSkpOwp9OwoKdGVtcGxhdGUgPHR5cGVuYW1lIFR5cGUsIHR5cGVuYW1lIENvbXAsIFR5cGUgcGl2b3QsIFR5cGUgaGVhZD4Kc3RydWN0IEdldExlc3MgPFR5cGUsIENvbXAsIHBpdm90LCBoZWFkPgp7Cgl1c2luZyBzZXEgPSB0eXBlbmFtZSBzdGQ6OmNvbmRpdGlvbmFsIDwKCQlDb21wIHt9IChoZWFkLCBwaXZvdCksCgkJU2VxdWVuY2UgPFR5cGUsIENvbXAsIGhlYWQ+LAoJCVNlcXVlbmNlIDwgVHlwZSwgQ29tcCA+Pjo6dHlwZSA7Cn07Cgp0ZW1wbGF0ZSA8dHlwZW5hbWUgVHlwZSwgdHlwZW5hbWUgQ29tcCwgVHlwZSBwaXZvdCwgVHlwZSBoZWFkLCBUeXBlIC4uLiB0YWlsPgpzdHJ1Y3QgR2V0RXF1YWwKewpwcml2YXRlOgoKCXVzaW5nIGZpcnN0ID0gdHlwZW5hbWUgc3RkOjpjb25kaXRpb25hbCA8CgkJKENvbXAge30gKGhlYWQsIHBpdm90KSB8fCBDb21wIHt9IChwaXZvdCwgaGVhZCkpLAoJCVNlcXVlbmNlIDxUeXBlLCBDb21wPiwKCQlTZXF1ZW5jZSA8VHlwZSwgQ29tcCwgaGVhZCA+Cgk+Ojp0eXBlIDsKCgl1c2luZyBzZWNvbmQgPSB0eXBlbmFtZSBHZXRFcXVhbCA8VHlwZSwgQ29tcCwgcGl2b3QsIHRhaWwgLi4uPjo6c2VxOwoKcHVibGljOgoKCXVzaW5nIHNlcSA9IGRlY2x0eXBlIChzcGxpY2VTZXF1ZW5jZXMgKGZpcnN0IHt9LCBzZWNvbmQge30pKTsKfTsKCnRlbXBsYXRlIDx0eXBlbmFtZSBUeXBlLCB0eXBlbmFtZSBDb21wLCBUeXBlIHBpdm90LCBUeXBlIGhlYWQ+CnN0cnVjdCBHZXRFcXVhbCA8VHlwZSwgQ29tcCwgcGl2b3QsIGhlYWQ+CnsKCXVzaW5nIHNlcSA9IHR5cGVuYW1lIHN0ZDo6Y29uZGl0aW9uYWwgPAoJCShDb21wIHt9IChoZWFkLCBwaXZvdCkgfHwgQ29tcCB7fSAocGl2b3QsIGhlYWQpKSwKCQlTZXF1ZW5jZSA8VHlwZSwgQ29tcD4sCgkJU2VxdWVuY2UgPFR5cGUsIENvbXAsIGhlYWQgPgoJPjo6dHlwZSA7Cn07Cgp0ZW1wbGF0ZSA8dHlwZW5hbWUgVHlwZSwgdHlwZW5hbWUgQ29tcCwgVHlwZSBwaXZvdCwgVHlwZSBoZWFkLCBUeXBlIC4uLiB0YWlsPgpzdHJ1Y3QgR2V0R3JlYXRlcgp7CnByaXZhdGU6CgoJdXNpbmcgZmlyc3QgPSB0eXBlbmFtZSBzdGQ6OmNvbmRpdGlvbmFsIDwKCQlDb21wIHt9IChwaXZvdCwgaGVhZCksCgkJU2VxdWVuY2UgPFR5cGUsIENvbXAsIGhlYWQ+LAoJCVNlcXVlbmNlIDwgVHlwZSwgQ29tcCA+Cgk+Ojp0eXBlIDsKCgl1c2luZyBzZWNvbmQgPSB0eXBlbmFtZSBHZXRHcmVhdGVyIDxUeXBlLCBDb21wLCBwaXZvdCwgdGFpbCAuLi4+OjpzZXE7CgpwdWJsaWM6CgoJdXNpbmcgc2VxID0gZGVjbHR5cGUgKHNwbGljZVNlcXVlbmNlcyAoZmlyc3Qge30sIHNlY29uZCB7fSkpOwp9OwoKdGVtcGxhdGUgPHR5cGVuYW1lIFR5cGUsIHR5cGVuYW1lIENvbXAsIFR5cGUgcGl2b3QsIFR5cGUgaGVhZD4Kc3RydWN0IEdldEdyZWF0ZXIgPFR5cGUsIENvbXAsIHBpdm90LCBoZWFkPgp7Cgl1c2luZyBzZXEgPSB0eXBlbmFtZSBzdGQ6OmNvbmRpdGlvbmFsIDwKCQlDb21wIHt9IChwaXZvdCwgaGVhZCksCgkJU2VxdWVuY2UgPFR5cGUsIENvbXAsIGhlYWQ+LAoJCVNlcXVlbmNlIDwgVHlwZSwgQ29tcCA+Cgk+Ojp0eXBlIDsKfTsKCnRlbXBsYXRlIDx0eXBlbmFtZSBUeXBlLCB0eXBlbmFtZSBDb21wLCBUeXBlIC4uLiB2YWx1ZXM+CnN0cnVjdCBTb3J0CnsKcHJpdmF0ZToKCgljb25zdGV4cHIgc3RhdGljIFR5cGUgcGl2b3QgPQoJCXN0ZDo6Z2V0IDxzaXplb2YgLi4uICh2YWx1ZXMpIC8gMj4gKHN0ZDo6bWFrZV90dXBsZSAodmFsdWVzIC4uLikpOwoKcHVibGljOgoKCXVzaW5nIHNlcSA9IGRlY2x0eXBlIChzcGxpY2VTZXF1ZW5jZXMgKAoJCW1ha2VTb3J0ICh0eXBlbmFtZSBHZXRMZXNzIDxUeXBlLCBDb21wLCBwaXZvdCwgdmFsdWVzIC4uLj46OnNlcSB7fSksCgkJc3BsaWNlU2VxdWVuY2VzICh0eXBlbmFtZSBHZXRFcXVhbCA8VHlwZSwgQ29tcCwgcGl2b3QsIHZhbHVlcyAuLi4+OjpzZXEge30sCgkJCQkJCSBtYWtlU29ydCAodHlwZW5hbWUgR2V0R3JlYXRlciA8VHlwZSwgQ29tcCwgcGl2b3QsIHZhbHVlcyAuLi4+OjpzZXEge30pKQoJCSkpOwp9OwoKdGVtcGxhdGUgPHR5cGVuYW1lIFR5cGUsIHR5cGVuYW1lIENvbXAsIFR5cGUgaGVhZD4Kc3RydWN0IFNvcnQgPFR5cGUsIENvbXAsIGhlYWQ+CnsKCXVzaW5nIHNlcSA9IFNlcXVlbmNlIDxUeXBlLCBDb21wLCBoZWFkPjsKfTsKCnRlbXBsYXRlIDx0eXBlbmFtZSBUeXBlLCB0eXBlbmFtZSBDb21wPgpzdHJ1Y3QgU29ydCA8VHlwZSwgQ29tcD4KewoJdXNpbmcgc2VxID0gU2VxdWVuY2UgPFR5cGUsIENvbXA+Owp9OwoKdGVtcGxhdGUgPHR5cGVuYW1lIFR5cGUsIHR5cGVuYW1lIENvbXAsIFR5cGUgaGVhZCwgVHlwZSAuLi4gdGFpbD4Kdm9pZCBwcmludFNlcXVlbmNlIChTZXF1ZW5jZSA8VHlwZSwgQ29tcCwgaGVhZCwgdGFpbCAuLi4+KQp7CglzdGQ6OmNvdXQgPDwgaGVhZCA8PCAnICc7CglwcmludFNlcXVlbmNlIChTZXF1ZW5jZSA8VHlwZSwgQ29tcCwgdGFpbCAuLi4+IHt9KTsKfQoKdGVtcGxhdGUgPHR5cGVuYW1lIFR5cGUsIHR5cGVuYW1lIENvbXAsIFR5cGUgaGVhZD4Kdm9pZCBwcmludFNlcXVlbmNlIChTZXF1ZW5jZSA8VHlwZSwgQ29tcCwgaGVhZD4pCnsKCXN0ZDo6Y291dCA8PCBoZWFkIDw8IHN0ZDo6ZW5kbDsKfQoKaW50IG1haW4gKCkKewoJcHJpbnRTZXF1ZW5jZSAoU29ydCA8aW50LCBzdGQ6OmdyZWF0ZXIgPGludD4sIDMsIDIsIDcsIDEsIC0xLCAxLCAxNDg4LCAxLCAxLCAxLCAyLCAtMSwgMjUsIDE0LCA3LCA4LCA3LCAyNT46OnNlcSB7fSk7CgoJcmV0dXJuIDA7Cn0=