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 //   sort(Iter first, Iter last);
17 
18 #include <algorithm>
19 #include <cassert>
20 
21 template <class RI>
22 void
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::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
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
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
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
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::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::sort(array, array+N);
94     assert(std::is_sorted(array, array+N));
95     // test sorted pattern
96     std::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::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::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::sort(array, array+N);
110     assert(std::is_sorted(array, array+N));
111     delete [] array;
112 }
113 
114 void
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 
128 int main()
129 {
130     // test null range
131     int d = 0;
132     std::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