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
26struct is_odd
27{
28 bool operator()(const int& i) const {return i & 1;}
29};
30
31struct odd_first
32{
33 bool operator()(const std::pair<int,int>& p) const
34 {return p.first & 1;}
35};
36
37template <class Iter>
38void
39test()
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're no longer using get_temporary_buffer().
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
309struct is_null
310{
311 template <class P>
312 bool operator()(const P& p) {return p == 0;}
313};
314
315template <class Iter>
316void
317test1()
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
327int 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

source code of libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/stable_partition.pass.cpp