fork download
copy 
  1. #include <tuple>
  2. #include <algorithm>
  3. #include <type_traits>
  4.  
  5. template <std::size_t A, std::size_t B>
  6. struct compare_pair {
  7.   template <typename T>
  8.   static void apply(T& t) {
  9.     auto& a = std::get<A>(t);
  10.     auto& b = std::get<B>(t);
  11.     using std::swap;
  12.     if (!(a < b))
  13.       swap(a, b);
  14.   }
  15. };
  16.  
  17. template <typename... T> struct join_ { using type = decltype(std::tuple_cat(std::declval<T>()...)); };
  18. template <typename... T> using join = typename join_<typename T::type...>::type;
  19.  
  20. template <std::size_t L, std::size_t R, std::size_t S,
  21.           typename = void>
  22. struct oddeven_range_merger {
  23.   using type = typename join_<
  24.     std::tuple<compare_pair<L, L+S> >,
  25.     typename oddeven_range_merger<L+2*S, R, S>::type
  26.   >::type;
  27. };
  28. template <std::size_t L, std::size_t R, std::size_t S>
  29. struct oddeven_range_merger<L, R, S,
  30.                             typename std::enable_if<(L >= R)>::type> {
  31.   using type = std::tuple<>;
  32. };
  33.  
  34. template <std::size_t L, std::size_t R, std::size_t S,
  35.           typename = void>
  36. struct oddeven_merger {
  37.    using type = join<
  38.      oddeven_merger<L, R, 2*S>,
  39.      oddeven_merger<L+S, R, 2*S>,
  40.      oddeven_range_merger<L+S, R-S, S> >;
  41. };
  42.  
  43. template <std::size_t L, std::size_t R, std::size_t S>
  44. struct oddeven_merger<L, R, S,
  45.                       typename std::enable_if<(2*S+1 >= R-L)>::type> {
  46.   using type = std::tuple<compare_pair<L, L+S> >;
  47. };
  48.  
  49. template <std::size_t L, std::size_t R, typename = void>
  50. struct oddeven_sorter {
  51.   static constexpr std::size_t M = (L+R)/2;
  52.   using type = join<oddeven_sorter<L, M>,
  53.                     oddeven_sorter<M, R>,
  54.                     oddeven_merger<L, R, 1> >;
  55. };
  56. template <std::size_t L, std::size_t R>
  57. struct oddeven_sorter<L, R, typename std::enable_if<(R-L <= 1)>::type> {
  58.   using type = std::tuple<>;
  59. };
  60.  
  61. template <std::size_t Size>
  62. using oddeven = typename oddeven_sorter<0, Size>::type;
  63.  
  64. template <typename... T> struct sorting_network {
  65.   template <typename Tuple>
  66.   static void apply(Tuple&& t) {
  67.     using swallow = int[];
  68.     (void)swallow{0, ((void)T::apply(t), 0)...};
  69.   }
  70. };
  71. template <typename T> struct make_sorting_network {};
  72. template <typename... T> struct make_sorting_network<std::tuple<T...> > { using type = sorting_network<T...>; };
  73.  
  74. template <typename T>
  75. void sort_tuple(T&& tuple) {
  76.   using network = typename make_sorting_network<oddeven<std::tuple_size<typename std::decay<T>::type >::value> >::type;
  77.   network::apply(std::forward<T>(tuple));
  78. }
  79.  
  80. template <typename... Args>
  81. void sort_arguments(Args&&... args) {
  82.   sort_tuple(std::tie(args...));
  83. }
  84.  
  85. template <std::size_t S>
  86. using swaps_needed = std::tuple_size<oddeven<S> >;
  87.  
  88. #include <iostream>
  89. #include <array>
  90. #include <utility>
  91.  
  92. template<class Ch, class Tr, class Tuple, std::size_t... Is>
  93. void print_tuple_impl(std::basic_ostream<Ch,Tr>& os,
  94.                       const Tuple & t,
  95.                       std::index_sequence<Is...>) {
  96.     using swallow = int[];
  97.     (void)swallow{0, (void(os << (Is == 0? "" : ", ") << std::get<Is>(t)), 0)...};
  98. }
  99.  
  100. template<class Ch, class Tr, class... Args>
  101. decltype(auto) operator<<(std::basic_ostream<Ch, Tr>& os,
  102.                           const std::tuple<Args...>& t) {
  103.     os << "(";
  104.     print_tuple_impl(os, t, std::index_sequence_for<Args...>{});
  105.     return os << ")";
  106. }
  107.  
  108. int main()
  109. {
  110.   auto t = std::make_tuple(2, 4, 3, 5, 9, 6, 1, 7, 8);
  111.   sort_tuple(t);
  112.   std::cout << "sorted in "
  113.             << swaps_needed<std::tuple_size<decltype(t)>::value>::value
  114.             << " steps: "
  115.             << t << '\n';
  116. }
  117.  
Success #stdin #stdout 0s 3096KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
sorted in 23 steps: (1, 2, 3, 4, 5, 6, 7, 8, 9)
https://ideone.com/ZDwE1j
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!