• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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