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