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