forked from wuye9036/CppTemplateTutorial
-
Notifications
You must be signed in to change notification settings - Fork 4
Expand file tree FF8
/
Copy pathQuickSort.cpp
More file actions
106 lines (90 loc) · 4.01 KB
/
QuickSort.cpp
File metadata and controls
106 lines (90 loc) · 4.01 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include <tuple>
#include <type_traits>
#include <iostream>
using std::tuple;
using std::integral_constant;
using std::is_same;
template <int... values> struct to_int_types{
typedef tuple< integral_constant<int, values>... > type;
};
template <typename Pivot> struct Less {
template <typename X> struct Apply {
static bool const value = X::value < Pivot::value;
};
};
template <typename Pivot> struct GE {
template <typename X> struct Apply {
static bool const value = X::value >= Pivot::value;
};
};
template <typename x, bool realAdd, typename tuple> struct Tuple_PushFront {};
template <typename x, typename... tupleElems> struct Tuple_PushFront<x, true, tuple<tupleElems...>> {
typedef tuple<x, tupleElems...> type;
};
template <typename x, typename... tupleElems> struct Tuple_PushFront<x, false, tuple<tupleElems...>> {
typedef tuple<tupleElems...> type;
};
template <typename Pred, typename tuple> struct Filter;
template <typename Pred> struct Filter< Pred, tuple<> > {
typedef tuple<> type;
};
template <typename Pred, typename Head, typename... Ts> struct Filter< Pred, tuple<Head, Ts...> > {
typedef typename Tuple_PushFront<
Head, Pred::template Apply<Head>::value, typename Filter<Pred, tuple<Ts...>>::type
>::type type;
};
template <typename... Tuples> struct ConcatenateTuple {};
template <typename Tuple0> struct ConcatenateTuple<Tuple0> {
typedef Tuple0 type;
};
template <typename Tuple0, typename Tuple1> struct ConcatenateTuple<Tuple0, Tuple1> {
template <typename TupleA> struct ConcatenateImpl {};
template <typename... TAs> struct ConcatenateImpl< tuple<TAs...> > {
template <typename TupleB> struct Apply;
template <typename... TBs> struct Apply< tuple<TBs...> > {
typedef tuple<TAs..., TBs...> type;
};
};
typedef typename ConcatenateImpl<Tuple0>::template Apply<Tuple1>::type type;
};
template <typename FirstTuple, typename... Follows> struct ConcatenateTuple<FirstTuple, Follows...> {
typedef typename ConcatenateTuple<
FirstTuple, typename ConcatenateTuple<Follows...>::type
>::type type;
};
template <typename tuple> struct QuickSort {};
template <> struct QuickSort< tuple< > > { typedef tuple< > type; };
template <typename T0> struct QuickSort< tuple<T0> > { typedef tuple<T0> type; };
template <typename Head, typename... Ts>
struct QuickSort< tuple<Head, Ts...> > {
typedef typename Filter< Less<Head>, tuple<Ts...> >::type LeftElems;
typedef typename Filter< GE <Head>, tuple<Ts...> >::type RightElems;
typedef typename ConcatenateTuple<
typename QuickSort<LeftElems>::type, tuple<Head>, typename QuickSort<RightElems>::type
>::type type;
};
void StaticTest()
{
typedef to_int_types<1, 2, 3>::type lst_1_3;
typedef to_int_types<3, 2, 1>::type lst_3_1;
typedef to_int_types<3, 7, 1, 6, 5, 22, 5>::type lst;
typedef to_int_types<1, 3, 5, 5, 6, 7, 22>::type sorted_lst;
typedef integral_constant<int, 1>::type i1;
typedef integral_constant<int, 2>::type i2;
typedef integral_constant<int, 3>::type i3;
static_assert(Less<i2>::Apply<i1>::value == true, "");
static_assert(Less<i1>::Apply<i1>::value == false, "");
static_assert(Less<i1>::Apply<i2>::value == false, "");
static_assert(GE<i2>::Apply<i3>::value == true, "");
static_assert(GE<i2>::Apply<i2>::value == true, "");
static_assert(GE<i3>::Apply<i2>::value == false, "");
static_assert(is_same<Tuple_PushFront<i1, true, tuple<i2>>::type, tuple<i1, i2>>::value, "");
static_assert(is_same<Tuple_PushFront<i2, true, tuple<i1>>::type, tuple<i2, i1>>::value, "");
static_assert(is_same<Tuple_PushFront<i2, false, tuple<i1>>::type, tuple<i1>>::value, "");
static_assert(is_same<Filter<Less<i2>, lst_1_3>::type, tuple<i1>>::value, "");
static_assert(is_same<QuickSort<lst_1_3 >::type, lst_1_3>::value, "");
static_assert(is_same<QuickSort<lst_3_1 >::type, lst_1_3>::value, "");
static_assert(is_same<QuickSort<tuple<> >::type, tuple<>>::value, "");
static_assert(is_same<QuickSort<tuple<i1>>::type, tuple<i1>>::value, "");
static_assert(is_same<QuickSort<lst >::type, sorted_lst>::value, "");
}