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