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 <iterator> 20 #include <random> 21 #include <cassert> 22 23 std::mt19937 randomness; 24 25 template <class RI> 26 void 27 test_sort_helper(RI f, RI l) 28 { 29 typedef typename std::iterator_traits<RI>::value_type value_type; 30 typedef typename std::iterator_traits<RI>::difference_type difference_type; 31 32 if (f != l) 33 { 34 difference_type len = l - f; 35 value_type* save(new value_type[len]); 36 do 37 { 38 std::copy(f, l, save); 39 std::stable_sort(save, save+len); 40 assert(std::is_sorted(save, save+len)); 41 } while (std::next_permutation(f, l)); 42 delete [] save; 43 } 44 } 45 46 template <class RI> 47 void 48 test_sort_driver_driver(RI f, RI l, int start, RI real_last) 49 { 50 for (RI i = l; i > f + start;) 51 { 52 *--i = start; 53 if (f == i) 54 { 55 test_sort_helper(f, real_last); 56 } 57 if (start > 0) 58 test_sort_driver_driver(f, i, start-1, real_last); 59 } 60 } 61 62 template <class RI> 63 void 64 test_sort_driver(RI f, RI l, int start) 65 { 66 test_sort_driver_driver(f, l, start, l); 67 } 68 69 template <int sa> 70 void 71 test_sort_() 72 { 73 int ia[sa]; 74 for (int i = 0; i < sa; ++i) 75 { 76 test_sort_driver(ia, ia+sa, i); 77 } 78 } 79 80 void 81 test_larger_sorts(int N, int M) 82 { 83 assert(N != 0); 84 assert(M != 0); 85 // create array length N filled with M different numbers 86 int* array = new int[N]; 87 int x = 0; 88 for (int i = 0; i < N; ++i) 89 { 90 array[i] = x; 91 if (++x == M) 92 x = 0; 93 } 94 // test saw tooth pattern 95 std::stable_sort(array, array+N); 96 assert(std::is_sorted(array, array+N)); 97 // test random pattern 98 std::shuffle(array, array+N, randomness); 99 std::stable_sort(array, array+N); 100 assert(std::is_sorted(array, array+N)); 101 // test sorted pattern 102 std::stable_sort(array, array+N); 103 assert(std::is_sorted(array, array+N)); 104 // test reverse sorted pattern 105 std::reverse(array, array+N); 106 std::stable_sort(array, array+N); 107 assert(std::is_sorted(array, array+N)); 108 // test swap ranges 2 pattern 109 std::swap_ranges(array, array+N/2, array+N/2); 110 std::stable_sort(array, array+N); 111 assert(std::is_sorted(array, array+N)); 112 // test reverse swap ranges 2 pattern 113 std::reverse(array, array+N); 114 std::swap_ranges(array, array+N/2, array+N/2); 115 std::stable_sort(array, array+N); 116 assert(std::is_sorted(array, array+N)); 117 delete [] array; 118 } 119 120 void 121 test_larger_sorts(int N) 122 { 123 test_larger_sorts(N, 1); 124 test_larger_sorts(N, 2); 125 test_larger_sorts(N, 3); 126 test_larger_sorts(N, N/2-1); 127 test_larger_sorts(N, N/2); 128 test_larger_sorts(N, N/2+1); 129 test_larger_sorts(N, N-2); 130 test_larger_sorts(N, N-1); 131 test_larger_sorts(N, N); 132 } 133 134 int main() 135 { 136 // test null range 137 int d = 0; 138 std::stable_sort(&d, &d); 139 // exhaustively test all possibilities up to length 8 140 test_sort_<1>(); 141 test_sort_<2>(); 142 test_sort_<3>(); 143 test_sort_<4>(); 144 test_sort_<5>(); 145 test_sort_<6>(); 146 test_sort_<7>(); 147 test_sort_<8>(); 148 149 test_larger_sorts(256); 150 test_larger_sorts(257); 151 test_larger_sorts(499); 152 test_larger_sorts(500); 153 test_larger_sorts(997); 154 test_larger_sorts(1000); 155 test_larger_sorts(1009); 156 } 157
