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<BidirectionalIterator Iter, Predicate<auto, Iter::value_type> Pred>
13 //   requires ShuffleIterator<Iter>
14 //         && CopyConstructible<Pred>
15 //   Iter
16 //   stable_partition(Iter first, Iter last, Pred pred);
17 
18 #include <algorithm>
19 #include <cassert>
20 #include <memory>
21 
22 #include "test_macros.h"
23 #include "test_iterators.h"
24 
25 struct is_odd
26 {
operator ()is_odd27     bool operator()(const int& i) const {return i & 1;}
28 };
29 
30 struct odd_first
31 {
operator ()odd_first32     bool operator()(const std::pair<int,int>& p) const
33         {return p.first & 1;}
34 };
35 
36 template <class Iter>
37 void
test()38 test()
39 {
40     {  // check mixed
41     typedef std::pair<int,int> P;
42     P array[] =
43     {
44         P(0, 1),
45         P(0, 2),
46         P(1, 1),
47         P(1, 2),
48         P(2, 1),
49         P(2, 2),
50         P(3, 1),
51         P(3, 2),
52         P(4, 1),
53         P(4, 2)
54     };
55     const unsigned size = sizeof(array)/sizeof(array[0]);
56     Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
57     assert(base(r) == array + 4);
58     assert(array[0] == P(1, 1));
59     assert(array[1] == P(1, 2));
60     assert(array[2] == P(3, 1));
61     assert(array[3] == P(3, 2));
62     assert(array[4] == P(0, 1));
63     assert(array[5] == P(0, 2));
64     assert(array[6] == P(2, 1));
65     assert(array[7] == P(2, 2));
66     assert(array[8] == P(4, 1));
67     assert(array[9] == P(4, 2));
68     }
69     {
70     typedef std::pair<int,int> P;
71     P array[] =
72     {
73         P(0, 1),
74         P(0, 2),
75         P(1, 1),
76         P(1, 2),
77         P(2, 1),
78         P(2, 2),
79         P(3, 1),
80         P(3, 2),
81         P(4, 1),
82         P(4, 2)
83     };
84     const unsigned size = sizeof(array)/sizeof(array[0]);
85     Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
86     assert(base(r) == array + 4);
87     assert(array[0] == P(1, 1));
88     assert(array[1] == P(1, 2));
89     assert(array[2] == P(3, 1));
90     assert(array[3] == P(3, 2));
91     assert(array[4] == P(0, 1));
92     assert(array[5] == P(0, 2));
93     assert(array[6] == P(2, 1));
94     assert(array[7] == P(2, 2));
95     assert(array[8] == P(4, 1));
96     assert(array[9] == P(4, 2));
97     // check empty
98     r = std::stable_partition(Iter(array), Iter(array), odd_first());
99     assert(base(r) == array);
100     // check one true
101     r = std::stable_partition(Iter(array), Iter(array+1), odd_first());
102     assert(base(r) == array+1);
103     assert(array[0] == P(1, 1));
104     // check one false
105     r = std::stable_partition(Iter(array+4), Iter(array+5), odd_first());
106     assert(base(r) == array+4);
107     assert(array[4] == P(0, 1));
108     }
109     {  // check all false
110     typedef std::pair<int,int> P;
111     P array[] =
112     {
113         P(0, 1),
114         P(0, 2),
115         P(2, 1),
116         P(2, 2),
117         P(4, 1),
118         P(4, 2),
119         P(6, 1),
120         P(6, 2),
121         P(8, 1),
122         P(8, 2)
123     };
124     const unsigned size = sizeof(array)/sizeof(array[0]);
125     Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
126     assert(base(r) == array);
127     assert(array[0] == P(0, 1));
128     assert(array[1] == P(0, 2));
129     assert(array[2] == P(2, 1));
130     assert(array[3] == P(2, 2));
131     assert(array[4] == P(4, 1));
132     assert(array[5] == P(4, 2));
133     assert(array[6] == P(6, 1));
134     assert(array[7] == P(6, 2));
135     assert(array[8] == P(8, 1));
136     assert(array[9] == P(8, 2));
137     }
138     {  // check all true
139     typedef std::pair<int,int> P;
140     P array[] =
141     {
142         P(1, 1),
143         P(1, 2),
144         P(3, 1),
145         P(3, 2),
146         P(5, 1),
147         P(5, 2),
148         P(7, 1),
149         P(7, 2),
150         P(9, 1),
151         P(9, 2)
152     };
153     const unsigned size = sizeof(array)/sizeof(array[0]);
154     Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
155     assert(base(r) == array + size);
156     assert(array[0] == P(1, 1));
157     assert(array[1] == P(1, 2));
158     assert(array[2] == P(3, 1));
159     assert(array[3] == P(3, 2));
160     assert(array[4] == P(5, 1));
161     assert(array[5] == P(5, 2));
162     assert(array[6] == P(7, 1));
163     assert(array[7] == P(7, 2));
164     assert(array[8] == P(9, 1));
165     assert(array[9] == P(9, 2));
166     }
167     {  // check all false but first true
168     typedef std::pair<int,int> P;
169     P array[] =
170     {
171         P(1, 1),
172         P(0, 2),
173         P(2, 1),
174         P(2, 2),
175         P(4, 1),
176         P(4, 2),
177         P(6, 1),
178         P(6, 2),
179         P(8, 1),
180         P(8, 2)
181     };
182     const unsigned size = sizeof(array)/sizeof(array[0]);
183     Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
184     assert(base(r) == array + 1);
185     assert(array[0] == P(1, 1));
186     assert(array[1] == P(0, 2));
187     assert(array[2] == P(2, 1));
188     assert(array[3] == P(2, 2));
189     assert(array[4] == P(4, 1));
190     assert(array[5] == P(4, 2));
191     assert(array[6] == P(6, 1));
192     assert(array[7] == P(6, 2));
193     assert(array[8] == P(8, 1));
194     assert(array[9] == P(8, 2));
195     }
196     {  // check all false but last true
197     typedef std::pair<int,int> P;
198     P array[] =
199     {
200         P(0, 1),
201         P(0, 2),
202         P(2, 1),
203         P(2, 2),
204         P(4, 1),
205         P(4, 2),
206         P(6, 1),
207         P(6, 2),
208         P(8, 1),
209         P(1, 2)
210     };
211     const unsigned size = sizeof(array)/sizeof(array[0]);
212     Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
213     assert(base(r) == array + 1);
214     assert(array[0] == P(1, 2));
215     assert(array[1] == P(0, 1));
216     assert(array[2] == P(0, 2));
217     assert(array[3] == P(2, 1));
218     assert(array[4] == P(2, 2));
219     assert(array[5] == P(4, 1));
220     assert(array[6] == P(4, 2));
221     assert(array[7] == P(6, 1));
222     assert(array[8] == P(6, 2));
223     assert(array[9] == P(8, 1));
224     }
225     {  // check all true but first false
226     typedef std::pair<int,int> P;
227     P array[] =
228     {
229         P(0, 1),
230         P(1, 2),
231         P(3, 1),
232         P(3, 2),
233         P(5, 1),
234         P(5, 2),
235         P(7, 1),
236         P(7, 2),
237         P(9, 1),
238         P(9, 2)
239     };
240     const unsigned size = sizeof(array)/sizeof(array[0]);
241     Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
242     assert(base(r) == array + size-1);
243     assert(array[0] == P(1, 2));
244     assert(array[1] == P(3, 1));
245     assert(array[2] == P(3, 2));
246     assert(array[3] == P(5, 1));
247     assert(array[4] == P(5, 2));
248     assert(array[5] == P(7, 1));
249     assert(array[6] == P(7, 2));
250     assert(array[7] == P(9, 1));
251     assert(array[8] == P(9, 2));
252     assert(array[9] == P(0, 1));
253     }
254     {  // check all true but last false
255     typedef std::pair<int,int> P;
256     P array[] =
257     {
258         P(1, 1),
259         P(1, 2),
260         P(3, 1),
261         P(3, 2),
262         P(5, 1),
263         P(5, 2),
264         P(7, 1),
265         P(7, 2),
266         P(9, 1),
267         P(0, 2)
268     };
269     const unsigned size = sizeof(array)/sizeof(array[0]);
270     Iter r = std::stable_partition(Iter(array), Iter(array+size), odd_first());
271     assert(base(r) == array + size-1);
272     assert(array[0] == P(1, 1));
273     assert(array[1] == P(1, 2));
274     assert(array[2] == P(3, 1));
275     assert(array[3] == P(3, 2));
276     assert(array[4] == P(5, 1));
277     assert(array[5] == P(5, 2));
278     assert(array[6] == P(7, 1));
279     assert(array[7] == P(7, 2));
280     assert(array[8] == P(9, 1));
281     assert(array[9] == P(0, 2));
282     }
283 }
284 
285 #if TEST_STD_VER >= 11
286 
287 struct is_null
288 {
289     template <class P>
operator ()is_null290         bool operator()(const P& p) {return p == 0;}
291 };
292 
293 template <class Iter>
294 void
test1()295 test1()
296 {
297     const unsigned size = 5;
298     std::unique_ptr<int> array[size];
299     Iter r = std::stable_partition(Iter(array), Iter(array+size), is_null());
300     assert(r == Iter(array+size));
301 }
302 
303 #endif  // TEST_STD_VER >= 11
304 
main()305 int main()
306 {
307     test<bidirectional_iterator<std::pair<int,int>*> >();
308     test<random_access_iterator<std::pair<int,int>*> >();
309     test<std::pair<int,int>*>();
310 
311 #if TEST_STD_VER >= 11
312     test1<bidirectional_iterator<std::unique_ptr<int>*> >();
313 #endif
314 }
315