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