stable_partition.pass.cpp revision a90c6dd46005b2b14de3bb889a8d03bb34bd3256 
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
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}
285
286#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
287
288struct is_null
289{
290    template <class P>
291        bool operator()(const P& p) {return p == 0;}
292};
293
294template <class Iter>
295void
296test1()
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
305int 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