test/std/algorithms/alg.sorting/alg.merge/merge_comp.pass.cpp

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