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