Home Explore Help
Sign In
hongwenjun
/
CppTemplateTutorial
mirror of https://github.com/wuye9036/CppTemplateTutorial
1
0
Fork 0
Files Issues 0 Wiki
Branch: master
Branches Tags
CppTemplateTuto...
/
QuickSort.cpp

QuickSort.cpp 4.0 KB
Permalink History Raw

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106 
  1. #include <tuple>
    2. 

  2. #include <type_traits>
    3. 

  3. #include <iostream>
    4. 

  4. 

  5. using std::tuple;
    6. 

  6. using std::integral_constant;
    7. 

  7. using std::is_same;
    8. 

  8. 

  9. template <int... values> struct to_int_types{
    10. 

  10. 	typedef tuple< integral_constant<int, values>... > type;
    11. 

  11. };
    12. 

  12. 

  13. template <typename Pivot> struct Less {
    14. 

  14. 	template <typename X> struct Apply {
    15. 

  15. 		static bool const value = X::value < Pivot::value;
    16. 

  16. 	};
    17. 

  17. };
    18. 

  18. 

  19. template <typename Pivot> struct GE {
    20. 

  20. 	template <typename X> struct Apply {
    21. 

  21. 		static bool const value = X::value >= Pivot::value;
    22. 

  22. 	};
    23. 

  23. };
    24. 

  24. 

  25. template <typename x, bool realAdd, typename tuple>         struct Tuple_PushFront {};
    26. 

  26. template <typename x, typename... tupleElems> struct Tuple_PushFront<x, true, tuple<tupleElems...>> {
    27. 

  27. 	typedef tuple<x, tupleElems...> type;
    28. 

  28. };
    29. 

  29. template <typename x, typename... tupleElems> struct Tuple_PushFront<x, false, tuple<tupleElems...>> {
    30. 

  30. 	typedef tuple<tupleElems...> type;
    31. 

  31. };
    32. 

  32. 

  33. template <typename Pred, typename tuple> struct Filter;
    34. 

  34. template <typename Pred> struct Filter< Pred, tuple<> > {
    35. 

  35. 	typedef tuple<> type;
    36. 

  36. };
    37. 

  37. template <typename Pred, typename Head, typename... Ts> struct Filter< Pred, tuple<Head, Ts...> > {
    38. 

  38. 	typedef typename Tuple_PushFront<
    39. 

  39. 		Head, Pred::template Apply<Head>::value, typename Filter<Pred, tuple<Ts...>>::type
    40. 

  40. 	>::type type;
    41. 

  41. };
    42. 

  42. 

  43. template <typename... Tuples> struct ConcatenateTuple {};
    44. 

  44. template <typename    Tuple0> struct ConcatenateTuple<Tuple0> {
    45. 

  45. 	typedef Tuple0 type;
    46. 

  46. };
    47. 

  47. 

  48. template <typename Tuple0, typename Tuple1> struct ConcatenateTuple<Tuple0, Tuple1> {
    49. 

  49. 	template <typename TupleA> struct ConcatenateImpl {};
    50. 

  50. 	template <typename... TAs> struct ConcatenateImpl< tuple<TAs...> > {
    51. 

  51. 		template <typename TupleB> struct Apply;
    52. 

  52. 		template <typename... TBs> struct Apply< tuple<TBs...> > {
    53. 

  53. 			typedef tuple<TAs..., TBs...> type;
    54. 

  54. 		};
    55. 

  55. 	};
    56. 

  56. 	typedef typename ConcatenateImpl<Tuple0>::template Apply<Tuple1>::type type;
    57. 

  57. };
    58. 

  58. template <typename FirstTuple, typename... Follows> struct ConcatenateTuple<FirstTuple, Follows...> {
    59. 

  59. 	typedef typename ConcatenateTuple<
    60. 

  60. 		FirstTuple, typename ConcatenateTuple<Follows...>::type
    61. 

  61. 	>::type type;
    62. 

  62. };
    63. 

  63. 

  64. template <typename tuple> struct QuickSort {};
    65. 

  65. template <>               struct QuickSort< tuple<  > > { typedef tuple<  > type; };
    66. 

  66. template <typename T0>    struct QuickSort< tuple<T0> > { typedef tuple<T0> type; };
    67. 

  67. template <typename Head, typename... Ts>
    68. 

  68. struct QuickSort< tuple<Head, Ts...> > {
    69. 

  69. 	typedef typename Filter< Less<Head>, tuple<Ts...> >::type LeftElems;
    70. 

  70. 	typedef typename Filter< GE  <Head>, tuple<Ts...> >::type RightElems;
    71. 

  71. 	typedef typename ConcatenateTuple<
    72. 

  72. 		typename QuickSort<LeftElems>::type, tuple<Head>, typename QuickSort<RightElems>::type
    73. 

  73. 	>::type type;
    74. 

  74. };
    75. 

  75. 

  76. void StaticTest()
    77. 

  77. {
    78. 

  78. 	typedef to_int_types<1, 2, 3>::type lst_1_3;
    79. 

  79. 	typedef to_int_types<3, 2, 1>::type lst_3_1;
    80. 

  80. 	typedef to_int_types<3, 7, 1, 6, 5, 22, 5>::type lst;
    81. 

  81. 	typedef to_int_types<1, 3, 5, 5, 6, 7, 22>::type sorted_lst;
    82. 

  82. 

  83. 	typedef integral_constant<int, 1>::type i1;
    84. 

  84. 	typedef integral_constant<int, 2>::type i2;
    85. 

  85. 	typedef integral_constant<int, 3>::type i3;
    86. 

  86. 

  87. 	static_assert(Less<i2>::Apply<i1>::value == true, "");
    88. 

  88. 	static_assert(Less<i1>::Apply<i1>::value == false, "");
    89. 

  89. 	static_assert(Less<i1>::Apply<i2>::value == false, "");
    90. 

  90. 

  91. 	static_assert(GE<i2>::Apply<i3>::value == true, "");
    92. 

  92. 	static_assert(GE<i2>::Apply<i2>::value == true, "");
    93. 

  93. 	static_assert(GE<i3>::Apply<i2>::value == false, "");
    94. 

  94. 

  95. 	static_assert(is_same<Tuple_PushFront<i1, true,  tuple<i2>>::type, tuple<i1, i2>>::value, "");
    96. 

  96. 	static_assert(is_same<Tuple_PushFront<i2, true,  tuple<i1>>::type, tuple<i2, i1>>::value, "");
    97. 

  97. 	static_assert(is_same<Tuple_PushFront<i2, false, tuple<i1>>::type, tuple<i1>>::value,     "");
    98. 

  98. 

  99. 	static_assert(is_same<Filter<Less<i2>, lst_1_3>::type, tuple<i1>>::value, "");
    100. 

  100. 

  101. 	static_assert(is_same<QuickSort<lst_1_3  >::type, lst_1_3>::value, "");
    102. 

  102. 	static_assert(is_same<QuickSort<lst_3_1  >::type, lst_1_3>::value, "");
    103. 

  103. 	static_assert(is_same<QuickSort<tuple<>  >::type, tuple<>>::value, "");
    104. 

  104. 	static_assert(is_same<QuickSort<tuple<i1>>::type, tuple<i1>>::value, "");
    105. 

  105. 	static_assert(is_same<QuickSort<lst      >::type, sorted_lst>::value, "");
    106. 

  106. }
    107.