1 //===----------------------------------------------------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is dual licensed under the MIT and the University of Illinois Open
6 // Source Licenses. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 // <algorithm>
11
12 // template<RandomAccessIterator Iter>
13 // requires ShuffleIterator<Iter>
14 // && LessThanComparable<Iter::value_type>
15 // void
16 // stable_sort(Iter first, Iter last);
17
18 #include <algorithm>
19 #include <cassert>
20
21 template <class RI>
22 void
test_sort_helper(RI f,RI l)23 test_sort_helper(RI f, RI l)
24 {
25 typedef typename std::iterator_traits<RI>::value_type value_type;
26 if (f != l)
27 {
28 long len = l - f;
29 value_type* save(new value_type[len]);
30 do
31 {
32 std::copy(f, l, save);
33 std::stable_sort(save, save+len);
34 assert(std::is_sorted(save, save+len));
35 } while (std::next_permutation(f, l));
36 delete [] save;
37 }
38 }
39
40 template <class RI>
41 void
test_sort_driver_driver(RI f,RI l,int start,RI real_last)42 test_sort_driver_driver(RI f, RI l, int start, RI real_last)
43 {
44 for (RI i = l; i > f + start;)
45 {
46 *--i = start;
47 if (f == i)
48 {
49 test_sort_helper(f, real_last);
50 }
51 if (start > 0)
52 test_sort_driver_driver(f, i, start-1, real_last);
53 }
54 }
55
56 template <class RI>
57 void
test_sort_driver(RI f,RI l,int start)58 test_sort_driver(RI f, RI l, int start)
59 {
60 test_sort_driver_driver(f, l, start, l);
61 }
62
63 template <unsigned sa>
64 void
test_sort_()65 test_sort_()
66 {
67 int ia[sa];
68 for (int i = 0; i < sa; ++i)
69 {
70 test_sort_driver(ia, ia+sa, i);
71 }
72 }
73
74 void
test_larger_sorts(unsigned N,unsigned M)75 test_larger_sorts(unsigned N, unsigned M)
76 {
77 assert(N != 0);
78 assert(M != 0);
79 // create array length N filled with M different numbers
80 int* array = new int[N];
81 int x = 0;
82 for (int i = 0; i < N; ++i)
83 {
84 array[i] = x;
85 if (++x == M)
86 x = 0;
87 }
88 // test saw tooth pattern
89 std::stable_sort(array, array+N);
90 assert(std::is_sorted(array, array+N));
91 // test random pattern
92 std::random_shuffle(array, array+N);
93 std::stable_sort(array, array+N);
94 assert(std::is_sorted(array, array+N));
95 // test sorted pattern
96 std::stable_sort(array, array+N);
97 assert(std::is_sorted(array, array+N));
98 // test reverse sorted pattern
99 std::reverse(array, array+N);
100 std::stable_sort(array, array+N);
101 assert(std::is_sorted(array, array+N));
102 // test swap ranges 2 pattern
103 std::swap_ranges(array, array+N/2, array+N/2);
104 std::stable_sort(array, array+N);
105 assert(std::is_sorted(array, array+N));
106 // test reverse swap ranges 2 pattern
107 std::reverse(array, array+N);
108 std::swap_ranges(array, array+N/2, array+N/2);
109 std::stable_sort(array, array+N);
110 assert(std::is_sorted(array, array+N));
111 delete [] array;
112 }
113
114 void
test_larger_sorts(unsigned N)115 test_larger_sorts(unsigned N)
116 {
117 test_larger_sorts(N, 1);
118 test_larger_sorts(N, 2);
119 test_larger_sorts(N, 3);
120 test_larger_sorts(N, N/2-1);
121 test_larger_sorts(N, N/2);
122 test_larger_sorts(N, N/2+1);
123 test_larger_sorts(N, N-2);
124 test_larger_sorts(N, N-1);
125 test_larger_sorts(N, N);
126 }
127
main()128 int main()
129 {
130 // test null range
131 int d = 0;
132 std::stable_sort(&d, &d);
133 // exhaustively test all possibilities up to length 8
134 test_sort_<1>();
135 test_sort_<2>();
136 test_sort_<3>();
137 test_sort_<4>();
138 test_sort_<5>();
139 test_sort_<6>();
140 test_sort_<7>();
141 test_sort_<8>();
142
143 test_larger_sorts(256);
144 test_larger_sorts(257);
145 test_larger_sorts(499);
146 test_larger_sorts(500);
147 test_larger_sorts(997);
148 test_larger_sorts(1000);
149 test_larger_sorts(1009);
150 }
151