sort.pass.cpp revision b64f8b07c104c6cc986570ac8ee0ed16a9f23976 
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
21template <class RI>
22void
23test_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
40template <class RI>
41void
42test_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
56template <class RI>
57void
58test_sort_driver(RI f, RI l, int start)
59{
60    test_sort_driver_driver(f, l, start, l);
61}
62
63template <unsigned sa>
64void
65test_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
74void
75test_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
114void
115test_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
128int 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