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