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
24template <class InIter1, class InIter2, class OutIter>
25void
26test()
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
71int 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