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 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 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::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 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::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