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 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
21 #include <memory>
22 #endif
23
24 #include "test_iterators.h"
25
26 struct is_odd
27 {
operator ()is_odd28 bool operator()(const int& i) const {return i & 1;}
29 };
30
31 struct odd_first
32 {
operator ()odd_first33 bool operator()(const std::pair<int,int>& p) const
34 {return p.first & 1;}
35 };
36
37 template <class Iter>
38 void
test()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 }
285
286 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
287
288 struct is_null
289 {
290 template <class P>
operator ()is_null291 bool operator()(const P& p) {return p == 0;}
292 };
293
294 template <class Iter>
295 void
test1()296 test1()
297 {
298 const unsigned size = 5;
299 std::unique_ptr<int> array[size];
300 Iter r = std::stable_partition(Iter(array), Iter(array+size), is_null());
301 }
302
303 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
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 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
312 test1<bidirectional_iterator<std::unique_ptr<int>*> >();
313 #endif
314 }
315