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

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