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