fork download
  1. #include <iostream>
  2. #include <functional>
  3. #include <tuple>
  4.  
  5. template <typename Type, typename Comp, Type ... values>
  6. struct Sequence
  7. {};
  8.  
  9. template <typename Type, typename Comp, Type ... values1, Type ... values2>
  10. constexpr decltype (auto) spliceSequences (const Sequence <Type, Comp, values1 ...>,
  11. const Sequence <Type, Comp, values2 ...>)
  12. {
  13. return Sequence <Type, Comp, values1 ..., values2 ...> {};
  14. };
  15.  
  16. template <typename Type, typename Comp, Type ... values>
  17. struct Sort;
  18.  
  19. template <typename Type, typename Comp, Type ... values>
  20. constexpr decltype (auto) makeSort (const Sequence <Type, Comp, values ...>)
  21. {
  22. return typename Sort <Type, Comp, values ...>::seq {};
  23. }
  24.  
  25. template <typename Type, typename Comp, Type pivot, Type head, Type ... tail>
  26. struct GetLess
  27. {
  28. private:
  29.  
  30. using first = typename std::conditional <
  31. Comp {} (head, pivot),
  32. Sequence <Type, Comp, head>,
  33. Sequence < Type, Comp >
  34. >::type ;
  35.  
  36. using second = typename GetLess <Type, Comp, pivot, tail ...>::seq;
  37.  
  38. public:
  39.  
  40. using seq = decltype (spliceSequences (first {}, second {}));
  41. };
  42.  
  43. template <typename Type, typename Comp, Type pivot, Type head>
  44. struct GetLess <Type, Comp, pivot, head>
  45. {
  46. using seq = typename std::conditional <
  47. Comp {} (head, pivot),
  48. Sequence <Type, Comp, head>,
  49. Sequence < Type, Comp >>::type ;
  50. };
  51.  
  52. template <typename Type, typename Comp, Type pivot, Type head, Type ... tail>
  53. struct GetEqual
  54. {
  55. private:
  56.  
  57. using first = typename std::conditional <
  58. (Comp {} (head, pivot) || Comp {} (pivot, head)),
  59. Sequence <Type, Comp>,
  60. Sequence <Type, Comp, head >
  61. >::type ;
  62.  
  63. using second = typename GetEqual <Type, Comp, pivot, tail ...>::seq;
  64.  
  65. public:
  66.  
  67. using seq = decltype (spliceSequences (first {}, second {}));
  68. };
  69.  
  70. template <typename Type, typename Comp, Type pivot, Type head>
  71. struct GetEqual <Type, Comp, pivot, head>
  72. {
  73. using seq = typename std::conditional <
  74. (Comp {} (head, pivot) || Comp {} (pivot, head)),
  75. Sequence <Type, Comp>,
  76. Sequence <Type, Comp, head >
  77. >::type ;
  78. };
  79.  
  80. template <typename Type, typename Comp, Type pivot, Type head, Type ... tail>
  81. struct GetGreater
  82. {
  83. private:
  84.  
  85. using first = typename std::conditional <
  86. Comp {} (pivot, head),
  87. Sequence <Type, Comp, head>,
  88. Sequence < Type, Comp >
  89. >::type ;
  90.  
  91. using second = typename GetGreater <Type, Comp, pivot, tail ...>::seq;
  92.  
  93. public:
  94.  
  95. using seq = decltype (spliceSequences (first {}, second {}));
  96. };
  97.  
  98. template <typename Type, typename Comp, Type pivot, Type head>
  99. struct GetGreater <Type, Comp, pivot, head>
  100. {
  101. using seq = typename std::conditional <
  102. Comp {} (pivot, head),
  103. Sequence <Type, Comp, head>,
  104. Sequence < Type, Comp >
  105. >::type ;
  106. };
  107.  
  108. template <typename Type, typename Comp, Type ... values>
  109. struct Sort
  110. {
  111. private:
  112.  
  113. constexpr static Type pivot =
  114. std::get <sizeof ... (values) / 2> (std::make_tuple (values ...));
  115.  
  116. public:
  117.  
  118. using seq = decltype (spliceSequences (
  119. makeSort (typename GetLess <Type, Comp, pivot, values ...>::seq {}),
  120. spliceSequences (typename GetEqual <Type, Comp, pivot, values ...>::seq {},
  121. makeSort (typename GetGreater <Type, Comp, pivot, values ...>::seq {}))
  122. ));
  123. };
  124.  
  125. template <typename Type, typename Comp, Type head>
  126. struct Sort <Type, Comp, head>
  127. {
  128. using seq = Sequence <Type, Comp, head>;
  129. };
  130.  
  131. template <typename Type, typename Comp>
  132. struct Sort <Type, Comp>
  133. {
  134. using seq = Sequence <Type, Comp>;
  135. };
  136.  
  137. template <typename Type, typename Comp, Type head, Type ... tail>
  138. void printSequence (Sequence <Type, Comp, head, tail ...>)
  139. {
  140. std::cout << head << ' ';
  141. printSequence (Sequence <Type, Comp, tail ...> {});
  142. }
  143.  
  144. template <typename Type, typename Comp, Type head>
  145. void printSequence (Sequence <Type, Comp, head>)
  146. {
  147. std::cout << head << std::endl;
  148. }
  149.  
  150. int main ()
  151. {
  152. 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 {});
  153.  
  154. return 0;
  155. }
Success #stdin #stdout 0s 3456KB
stdin
Standard input is empty
stdout
1488 25 25 14 8 7 7 7 3 2 2 1 1 1 1 1 -1 -1