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