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