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
27template <class InIter1, class InIter2, class OutIter>
28void
29test()
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
76int 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