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