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