Home | History | Annotate | Download | only in alg.merge 
      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<InputIterator InIter1, InputIterator InIter2, typename OutIter,
     13 //          Predicate<auto, InIter2::value_type, InIter1::value_type> Compare>
     14 //   requires OutputIterator<OutIter, InIter1::reference>
     15 //         && OutputIterator<OutIter, InIter2::reference>
     16 //         && CopyConstructible<Compare>
     17 //   OutIter
     18 //   merge(InIter1 first1, InIter1 last1,
     19 //         InIter2 first2, InIter2 last2, OutIter result, Compare comp);
     20 
     21 #include <algorithm>
     22 #include <functional>
     23 #include <cassert>
     24 
     25 #include "test_iterators.h"
     26 
     27 template <class InIter1, class InIter2, class OutIter>
     28 void
     29 test()
     30 {
     31     {
     32     unsigned N = 100000;
     33     int* ia = new int[N];
     34     int* ib = new int[N];
     35     int* ic = new int[2*N];
     36     for (unsigned i = 0; i < N; ++i)
     37         ia[i] = 2*i;
     38     for (unsigned i = 0; i < N; ++i)
     39         ib[i] = 2*i+1;
     40     std::reverse(ia, ia+N);
     41     std::reverse(ib, ib+N);
     42     OutIter r = std::merge(InIter1(ia), InIter1(ia+N),
     43                            InIter2(ib), InIter2(ib+N), OutIter(ic), std::greater<int>());
     44     assert(base(r) == ic+2*N);
     45     assert(ic[0] == 2*N-1);
     46     assert(ic[2*N-1] == 0);
     47     assert(std::is_sorted(ic, ic+2*N, std::greater<int>()));
     48     delete [] ic;
     49     delete [] ib;
     50     delete [] ia;
     51     }
     52     {
     53     unsigned N = 100;
     54     int* ia = new int[N];
     55     int* ib = new int[N];
     56     int* ic = new int[2*N];
     57     for (unsigned i = 0; i < 2*N; ++i)
     58         ic[i] = i;
     59     std::random_shuffle(ic, ic+2*N);
     60     std::copy(ic, ic+N, ia);
     61     std::copy(ic+N, ic+2*N, ib);
     62     std::sort(ia, ia+N, std::greater<int>());
     63     std::sort(ib, ib+N, std::greater<int>());
     64     OutIter r = std::merge(InIter1(ia), InIter1(ia+N),
     65                            InIter2(ib), InIter2(ib+N), OutIter(ic), std::greater<int>());
     66     assert(base(r) == ic+2*N);
     67     assert(ic[0] == 2*N-1);
     68     assert(ic[2*N-1] == 0);
     69     assert(std::is_sorted(ic, ic+2*N, std::greater<int>()));
     70     delete [] ic;
     71     delete [] ib;
     72     delete [] ia;
     73     }
     74 }
     75 
     76 int main()
     77 {
     78     test<input_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >();
     79     test<input_iterator<const int*>, input_iterator<const int*>, forward_iterator<int*> >();
     80     test<input_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >();
     81     test<input_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >();
     82     test<input_iterator<const int*>, input_iterator<const int*>, int*>();
     83 
     84     test<input_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >();
     85     test<input_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >();
     86     test<input_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >();
     87     test<input_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >();
     88     test<input_iterator<const int*>, forward_iterator<const int*>, int*>();
     89 
     90     test<input_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >();
     91     test<input_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >();
     92     test<input_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >();
     93     test<input_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >();
     94     test<input_iterator<const int*>, bidirectional_iterator<const int*>, int*>();
     95 
     96     test<input_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >();
     97     test<input_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >();
     98     test<input_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >();
     99     test<input_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >();
    100     test<input_iterator<const int*>, random_access_iterator<const int*>, int*>();
    101 
    102     test<input_iterator<const int*>, const int*, output_iterator<int*> >();
    103     test<input_iterator<const int*>, const int*, forward_iterator<int*> >();
    104     test<input_iterator<const int*>, const int*, bidirectional_iterator<int*> >();
    105     test<input_iterator<const int*>, const int*, random_access_iterator<int*> >();
    106     test<input_iterator<const int*>, const int*, int*>();
    107 
    108     test<forward_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >();
    109     test<forward_iterator<const int*>, input_iterator<const int*>, forward_iterator<int*> >();
    110     test<forward_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >();
    111     test<forward_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >();
    112     test<forward_iterator<const int*>, input_iterator<const int*>, int*>();
    113 
    114     test<forward_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >();
    115     test<forward_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >();
    116     test<forward_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >();
    117     test<forward_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >();
    118     test<forward_iterator<const int*>, forward_iterator<const int*>, int*>();
    119 
    120     test<forward_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >();
    121     test<forward_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >();
    122     test<forward_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >();
    123     test<forward_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >();
    124     test<forward_iterator<const int*>, bidirectional_iterator<const int*>, int*>();
    125 
    126     test<forward_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >();
    127     test<forward_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >();
    128     test<forward_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >();
    129     test<forward_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >();
    130     test<forward_iterator<const int*>, random_access_iterator<const int*>, int*>();
    131 
    132     test<forward_iterator<const int*>, const int*, output_iterator<int*> >();
    133     test<forward_iterator<const int*>, const int*, forward_iterator<int*> >();
    134     test<forward_iterator<const int*>, const int*, bidirectional_iterator<int*> >();
    135     test<forward_iterator<const int*>, const int*, random_access_iterator<int*> >();
    136     test<forward_iterator<const int*>, const int*, int*>();
    137 
    138     test<bidirectional_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >();
    139     test<bidirectional_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >();
    140     test<bidirectional_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >();
    141     test<bidirectional_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >();
    142     test<bidirectional_iterator<const int*>, input_iterator<const int*>, int*>();
    143 
    144     test<bidirectional_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >();
    145     test<bidirectional_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >();
    146     test<bidirectional_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >();
    147     test<bidirectional_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >();
    148     test<bidirectional_iterator<const int*>, forward_iterator<const int*>, int*>();
    149 
    150     test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >();
    151     test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >();
    152     test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >();
    153     test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >();
    154     test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, int*>();
    155 
    156     test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >();
    157     test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >();
    158     test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >();
    159     test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >();
    160     test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, int*>();
    161 
    162     test<bidirectional_iterator<const int*>, const int*, output_iterator<int*> >();
    163     test<bidirectional_iterator<const int*>, const int*, forward_iterator<int*> >();
    164     test<bidirectional_iterator<const int*>, const int*, bidirectional_iterator<int*> >();
    165     test<bidirectional_iterator<const int*>, const int*, random_access_iterator<int*> >();
    166     test<bidirectional_iterator<const int*>, const int*, int*>();
    167 
    168     test<random_access_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >();
    169     test<random_access_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >();
    170     test<random_access_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >();
    171     test<random_access_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >();
    172     test<random_access_iterator<const int*>, input_iterator<const int*>, int*>();
    173 
    174     test<random_access_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >();
    175     test<random_access_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >();
    176     test<random_access_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >();
    177     test<random_access_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >();
    178     test<random_access_iterator<const int*>, forward_iterator<const int*>, int*>();
    179 
    180     test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >();
    181     test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >();
    182     test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >();
    183     test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >();
    184     test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, int*>();
    185 
    186     test<random_access_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >();
    187     test<random_access_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >();
    188     test<random_access_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >();
    189     test<random_access_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >();
    190     test<random_access_iterator<const int*>, random_access_iterator<const int*>, int*>();
    191 
    192     test<random_access_iterator<const int*>, const int*, output_iterator<int*> >();
    193     test<random_access_iterator<const int*>, const int*, forward_iterator<int*> >();
    194     test<random_access_iterator<const int*>, const int*, bidirectional_iterator<int*> >();
    195     test<random_access_iterator<const int*>, const int*, random_access_iterator<int*> >();
    196     test<random_access_iterator<const int*>, const int*, int*>();
    197 
    198     test<const int*, input_iterator<const int*>, output_iterator<int*> >();
    199     test<const int*, input_iterator<const int*>, bidirectional_iterator<int*> >();
    200     test<const int*, input_iterator<const int*>, bidirectional_iterator<int*> >();
    201     test<const int*, input_iterator<const int*>, random_access_iterator<int*> >();
    202     test<const int*, input_iterator<const int*>, int*>();
    203 
    204     test<const int*, forward_iterator<const int*>, output_iterator<int*> >();
    205     test<const int*, forward_iterator<const int*>, forward_iterator<int*> >();
    206     test<const int*, forward_iterator<const int*>, bidirectional_iterator<int*> >();
    207     test<const int*, forward_iterator<const int*>, random_access_iterator<int*> >();
    208     test<const int*, forward_iterator<const int*>, int*>();
    209 
    210     test<const int*, bidirectional_iterator<const int*>, output_iterator<int*> >();
    211     test<const int*, bidirectional_iterator<const int*>, forward_iterator<int*> >();
    212     test<const int*, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >();
    213     test<const int*, bidirectional_iterator<const int*>, random_access_iterator<int*> >();
    214     test<const int*, bidirectional_iterator<const int*>, int*>();
    215 
    216     test<const int*, random_access_iterator<const int*>, output_iterator<int*> >();
    217     test<const int*, random_access_iterator<const int*>, forward_iterator<int*> >();
    218     test<const int*, random_access_iterator<const int*>, bidirectional_iterator<int*> >();
    219     test<const int*, random_access_iterator<const int*>, random_access_iterator<int*> >();
    220     test<const int*, random_access_iterator<const int*>, int*>();
    221 
    222     test<const int*, const int*, output_iterator<int*> >();
    223     test<const int*, const int*, forward_iterator<int*> >();
    224     test<const int*, const int*, bidirectional_iterator<int*> >();
    225     test<const int*, const int*, random_access_iterator<int*> >();
    226     test<const int*, const int*, int*>();
    227 }
    228