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