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