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