Home | History | Annotate | Download | only in sort 
      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