merge_comp.pass.cpp (15159B)
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 // constexpr OutIter // constexpr after C++17 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_macros.h" 29 #include "test_iterators.h" 30 #include "counting_predicates.hpp" 31 32 // #if TEST_STD_VER > 17 33 // TEST_CONSTEXPR bool test_constexpr() { 34 // int ia[] = {0, 1, 2, 3, 4}; 35 // int ib[] = {2, 4, 6, 8}; 36 // int ic[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; 37 // const int expected[] = {0, 1, 2, 2, 3, 4, 4, 6, 8}; 38 // 39 // auto it = std::merge(std::begin(ia), std::end(ia), 40 // std::begin(ib), std::end(ib), 41 // std::begin(ic), [](int a, int b) {return a == b; }); 42 // return std::distance(std::begin(ic), it) == (std::size(ia) + std::size(ib)) 43 // && *it == 0 44 // && std::equal(std::begin(ic), it, std::begin(expected), std::end(expected)) 45 // ; 46 // } 47 // #endif 48 49 std::mt19937 randomness; 50 51 template <class InIter1, class InIter2, class OutIter> 52 void 53 test() 54 { 55 { 56 unsigned N = 100000; 57 int* ia = new int[N]; 58 int* ib = new int[N]; 59 int* ic = new int[2*N]; 60 for (unsigned i = 0; i < N; ++i) 61 ia[i] = 2*i; 62 for (unsigned i = 0; i < N; ++i) 63 ib[i] = 2*i+1; 64 std::reverse(ia, ia+N); 65 std::reverse(ib, ib+N); 66 binary_counting_predicate<std::greater<int>, int, int> pred((std::greater<int>())); 67 OutIter r = std::merge(InIter1(ia), InIter1(ia+N), 68 InIter2(ib), InIter2(ib+N), OutIter(ic), pred); 69 assert(base(r) == ic+2*N); 70 assert(ic[0] == static_cast<int>(2*N-1)); 71 assert(ic[2*N-1] == 0); 72 assert(std::is_sorted(ic, ic+2*N, std::greater<int>())); 73 assert(pred.count() <= (N + N - 1)); 74 delete [] ic; 75 delete [] ib; 76 delete [] ia; 77 } 78 { 79 unsigned N = 100; 80 int* ia = new int[N]; 81 int* ib = new int[N]; 82 int* ic = new int[2*N]; 83 for (unsigned i = 0; i < 2*N; ++i) 84 ic[i] = i; 85 std::shuffle(ic, ic+2*N, randomness); 86 std::copy(ic, ic+N, ia); 87 std::copy(ic+N, ic+2*N, ib); 88 std::sort(ia, ia+N, std::greater<int>()); 89 std::sort(ib, ib+N, std::greater<int>()); 90 binary_counting_predicate<std::greater<int>, int, int> pred((std::greater<int>())); 91 OutIter r = std::merge(InIter1(ia), InIter1(ia+N), 92 InIter2(ib), InIter2(ib+N), OutIter(ic), pred); 93 assert(base(r) == ic+2*N); 94 assert(ic[0] == static_cast<int>(2*N-1)); 95 assert(ic[2*N-1] == 0); 96 assert(std::is_sorted(ic, ic+2*N, std::greater<int>())); 97 assert(pred.count() <= (N + N - 1)); 98 delete [] ic; 99 delete [] ib; 100 delete [] ia; 101 } 102 } 103 104 int main() 105 { 106 test<input_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >(); 107 test<input_iterator<const int*>, input_iterator<const int*>, forward_iterator<int*> >(); 108 test<input_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >(); 109 test<input_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >(); 110 test<input_iterator<const int*>, input_iterator<const int*>, int*>(); 111 112 test<input_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >(); 113 test<input_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >(); 114 test<input_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >(); 115 test<input_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >(); 116 test<input_iterator<const int*>, forward_iterator<const int*>, int*>(); 117 118 test<input_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >(); 119 test<input_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >(); 120 test<input_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >(); 121 test<input_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >(); 122 test<input_iterator<const int*>, bidirectional_iterator<const int*>, int*>(); 123 124 test<input_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >(); 125 test<input_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >(); 126 test<input_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >(); 127 test<input_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >(); 128 test<input_iterator<const int*>, random_access_iterator<const int*>, int*>(); 129 130 test<input_iterator<const int*>, const int*, output_iterator<int*> >(); 131 test<input_iterator<const int*>, const int*, forward_iterator<int*> >(); 132 test<input_iterator<const int*>, const int*, bidirectional_iterator<int*> >(); 133 test<input_iterator<const int*>, const int*, random_access_iterator<int*> >(); 134 test<input_iterator<const int*>, const int*, int*>(); 135 136 test<forward_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >(); 137 test<forward_iterator<const int*>, input_iterator<const int*>, forward_iterator<int*> >(); 138 test<forward_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >(); 139 test<forward_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >(); 140 test<forward_iterator<const int*>, input_iterator<const int*>, int*>(); 141 142 test<forward_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >(); 143 test<forward_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >(); 144 test<forward_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >(); 145 test<forward_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >(); 146 test<forward_iterator<const int*>, forward_iterator<const int*>, int*>(); 147 148 test<forward_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >(); 149 test<forward_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >(); 150 test<forward_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >(); 151 test<forward_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >(); 152 test<forward_iterator<const int*>, bidirectional_iterator<const int*>, int*>(); 153 154 test<forward_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >(); 155 test<forward_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >(); 156 test<forward_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >(); 157 test<forward_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >(); 158 test<forward_iterator<const int*>, random_access_iterator<const int*>, int*>(); 159 160 test<forward_iterator<const int*>, const int*, output_iterator<int*> >(); 161 test<forward_iterator<const int*>, const int*, forward_iterator<int*> >(); 162 test<forward_iterator<const int*>, const int*, bidirectional_iterator<int*> >(); 163 test<forward_iterator<const int*>, const int*, random_access_iterator<int*> >(); 164 test<forward_iterator<const int*>, const int*, int*>(); 165 166 test<bidirectional_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >(); 167 test<bidirectional_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >(); 168 test<bidirectional_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >(); 169 test<bidirectional_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >(); 170 test<bidirectional_iterator<const int*>, input_iterator<const int*>, int*>(); 171 172 test<bidirectional_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >(); 173 test<bidirectional_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >(); 174 test<bidirectional_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >(); 175 test<bidirectional_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >(); 176 test<bidirectional_iterator<const int*>, forward_iterator<const int*>, int*>(); 177 178 test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >(); 179 test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >(); 180 test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >(); 181 test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >(); 182 test<bidirectional_iterator<const int*>, bidirectional_iterator<const int*>, int*>(); 183 184 test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >(); 185 test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >(); 186 test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >(); 187 test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >(); 188 test<bidirectional_iterator<const int*>, random_access_iterator<const int*>, int*>(); 189 190 test<bidirectional_iterator<const int*>, const int*, output_iterator<int*> >(); 191 test<bidirectional_iterator<const int*>, const int*, forward_iterator<int*> >(); 192 test<bidirectional_iterator<const int*>, const int*, bidirectional_iterator<int*> >(); 193 test<bidirectional_iterator<const int*>, const int*, random_access_iterator<int*> >(); 194 test<bidirectional_iterator<const int*>, const int*, int*>(); 195 196 test<random_access_iterator<const int*>, input_iterator<const int*>, output_iterator<int*> >(); 197 test<random_access_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >(); 198 test<random_access_iterator<const int*>, input_iterator<const int*>, bidirectional_iterator<int*> >(); 199 test<random_access_iterator<const int*>, input_iterator<const int*>, random_access_iterator<int*> >(); 200 test<random_access_iterator<const int*>, input_iterator<const int*>, int*>(); 201 202 test<random_access_iterator<const int*>, forward_iterator<const int*>, output_iterator<int*> >(); 203 test<random_access_iterator<const int*>, forward_iterator<const int*>, forward_iterator<int*> >(); 204 test<random_access_iterator<const int*>, forward_iterator<const int*>, bidirectional_iterator<int*> >(); 205 test<random_access_iterator<const int*>, forward_iterator<const int*>, random_access_iterator<int*> >(); 206 test<random_access_iterator<const int*>, forward_iterator<const int*>, int*>(); 207 208 test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, output_iterator<int*> >(); 209 test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, forward_iterator<int*> >(); 210 test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >(); 211 test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, random_access_iterator<int*> >(); 212 test<random_access_iterator<const int*>, bidirectional_iterator<const int*>, int*>(); 213 214 test<random_access_iterator<const int*>, random_access_iterator<const int*>, output_iterator<int*> >(); 215 test<random_access_iterator<const int*>, random_access_iterator<const int*>, forward_iterator<int*> >(); 216 test<random_access_iterator<const int*>, random_access_iterator<const int*>, bidirectional_iterator<int*> >(); 217 test<random_access_iterator<const int*>, random_access_iterator<const int*>, random_access_iterator<int*> >(); 218 test<random_access_iterator<const int*>, random_access_iterator<const int*>, int*>(); 219 220 test<random_access_iterator<const int*>, const int*, output_iterator<int*> >(); 221 test<random_access_iterator<const int*>, const int*, forward_iterator<int*> >(); 222 test<random_access_iterator<const int*>, const int*, bidirectional_iterator<int*> >(); 223 test<random_access_iterator<const int*>, const int*, random_access_iterator<int*> >(); 224 test<random_access_iterator<const int*>, const int*, int*>(); 225 226 test<const int*, input_iterator<const int*>, output_iterator<int*> >(); 227 test<const int*, input_iterator<const int*>, bidirectional_iterator<int*> >(); 228 test<const int*, input_iterator<const int*>, bidirectional_iterator<int*> >(); 229 test<const int*, input_iterator<const int*>, random_access_iterator<int*> >(); 230 test<const int*, input_iterator<const int*>, int*>(); 231 232 test<const int*, forward_iterator<const int*>, output_iterator<int*> >(); 233 test<const int*, forward_iterator<const int*>, forward_iterator<int*> >(); 234 test<const int*, forward_iterator<const int*>, bidirectional_iterator<int*> >(); 235 test<const int*, forward_iterator<const int*>, random_access_iterator<int*> >(); 236 test<const int*, forward_iterator<const int*>, int*>(); 237 238 test<const int*, bidirectional_iterator<const int*>, output_iterator<int*> >(); 239 test<const int*, bidirectional_iterator<const int*>, forward_iterator<int*> >(); 240 test<const int*, bidirectional_iterator<const int*>, bidirectional_iterator<int*> >(); 241 test<const int*, bidirectional_iterator<const int*>, random_access_iterator<int*> >(); 242 test<const int*, bidirectional_iterator<const int*>, int*>(); 243 244 test<const int*, random_access_iterator<const int*>, output_iterator<int*> >(); 245 test<const int*, random_access_iterator<const int*>, forward_iterator<int*> >(); 246 test<const int*, random_access_iterator<const int*>, bidirectional_iterator<int*> >(); 247 test<const int*, random_access_iterator<const int*>, random_access_iterator<int*> >(); 248 test<const int*, random_access_iterator<const int*>, int*>(); 249 250 test<const int*, const int*, output_iterator<int*> >(); 251 test<const int*, const int*, forward_iterator<int*> >(); 252 test<const int*, const int*, bidirectional_iterator<int*> >(); 253 test<const int*, const int*, random_access_iterator<int*> >(); 254 test<const int*, const int*, int*>(); 255 256 #if TEST_STD_VER > 17 257 // Not yet - waiting on std::copy 258 // static_assert(test_constexpr()); 259 #endif 260 }