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<ShuffleIterator Iter>
13 // Iter
14 // rotate(Iter first, Iter middle, Iter last);
15
16 #include <algorithm>
17 #include <cassert>
18 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
19 #include <memory>
20 #endif
21
22 #include "test_iterators.h"
23
24 template <class Iter>
25 void
test()26 test()
27 {
28 int ia[] = {0};
29 const unsigned sa = sizeof(ia)/sizeof(ia[0]);
30 Iter r = std::rotate(Iter(ia), Iter(ia), Iter(ia));
31 assert(base(r) == ia);
32 assert(ia[0] == 0);
33 r = std::rotate(Iter(ia), Iter(ia), Iter(ia+sa));
34 assert(base(r) == ia+sa);
35 assert(ia[0] == 0);
36 r = std::rotate(Iter(ia), Iter(ia+sa), Iter(ia+sa));
37 assert(base(r) == ia);
38 assert(ia[0] == 0);
39
40 int ib[] = {0, 1};
41 const unsigned sb = sizeof(ib)/sizeof(ib[0]);
42 r = std::rotate(Iter(ib), Iter(ib), Iter(ib+sb));
43 assert(base(r) == ib+sb);
44 assert(ib[0] == 0);
45 assert(ib[1] == 1);
46 r = std::rotate(Iter(ib), Iter(ib+1), Iter(ib+sb));
47 assert(base(r) == ib+1);
48 assert(ib[0] == 1);
49 assert(ib[1] == 0);
50 r = std::rotate(Iter(ib), Iter(ib+sb), Iter(ib+sb));
51 assert(base(r) == ib);
52 assert(ib[0] == 1);
53 assert(ib[1] == 0);
54
55 int ic[] = {0, 1, 2};
56 const unsigned sc = sizeof(ic)/sizeof(ic[0]);
57 r = std::rotate(Iter(ic), Iter(ic), Iter(ic+sc));
58 assert(base(r) == ic+sc);
59 assert(ic[0] == 0);
60 assert(ic[1] == 1);
61 assert(ic[2] == 2);
62 r = std::rotate(Iter(ic), Iter(ic+1), Iter(ic+sc));
63 assert(base(r) == ic+2);
64 assert(ic[0] == 1);
65 assert(ic[1] == 2);
66 assert(ic[2] == 0);
67 r = std::rotate(Iter(ic), Iter(ic+2), Iter(ic+sc));
68 assert(base(r) == ic+1);
69 assert(ic[0] == 0);
70 assert(ic[1] == 1);
71 assert(ic[2] == 2);
72 r = std::rotate(Iter(ic), Iter(ic+sc), Iter(ic+sc));
73 assert(base(r) == ic);
74 assert(ic[0] == 0);
75 assert(ic[1] == 1);
76 assert(ic[2] == 2);
77
78 int id[] = {0, 1, 2, 3};
79 const unsigned sd = sizeof(id)/sizeof(id[0]);
80 r = std::rotate(Iter(id), Iter(id), Iter(id+sd));
81 assert(base(r) == id+sd);
82 assert(id[0] == 0);
83 assert(id[1] == 1);
84 assert(id[2] == 2);
85 assert(id[3] == 3);
86 r = std::rotate(Iter(id), Iter(id+1), Iter(id+sd));
87 assert(base(r) == id+3);
88 assert(id[0] == 1);
89 assert(id[1] == 2);
90 assert(id[2] == 3);
91 assert(id[3] == 0);
92 r = std::rotate(Iter(id), Iter(id+2), Iter(id+sd));
93 assert(base(r) == id+2);
94 assert(id[0] == 3);
95 assert(id[1] == 0);
96 assert(id[2] == 1);
97 assert(id[3] == 2);
98 r = std::rotate(Iter(id), Iter(id+3), Iter(id+sd));
99 assert(base(r) == id+1);
100 assert(id[0] == 2);
101 assert(id[1] == 3);
102 assert(id[2] == 0);
103 assert(id[3] == 1);
104 r = std::rotate(Iter(id), Iter(id+sd), Iter(id+sd));
105 assert(base(r) == id);
106 assert(id[0] == 2);
107 assert(id[1] == 3);
108 assert(id[2] == 0);
109 assert(id[3] == 1);
110
111 int ie[] = {0, 1, 2, 3, 4};
112 const unsigned se = sizeof(ie)/sizeof(ie[0]);
113 r = std::rotate(Iter(ie), Iter(ie), Iter(ie+se));
114 assert(base(r) == ie+se);
115 assert(ie[0] == 0);
116 assert(ie[1] == 1);
117 assert(ie[2] == 2);
118 assert(ie[3] == 3);
119 assert(ie[4] == 4);
120 r = std::rotate(Iter(ie), Iter(ie+1), Iter(ie+se));
121 assert(base(r) == ie+4);
122 assert(ie[0] == 1);
123 assert(ie[1] == 2);
124 assert(ie[2] == 3);
125 assert(ie[3] == 4);
126 assert(ie[4] == 0);
127 r = std::rotate(Iter(ie), Iter(ie+2), Iter(ie+se));
128 assert(base(r) == ie+3);
129 assert(ie[0] == 3);
130 assert(ie[1] == 4);
131 assert(ie[2] == 0);
132 assert(ie[3] == 1);
133 assert(ie[4] == 2);
134 r = std::rotate(Iter(ie), Iter(ie+3), Iter(ie+se));
135 assert(base(r) == ie+2);
136 assert(ie[0] == 1);
137 assert(ie[1] == 2);
138 assert(ie[2] == 3);
139 assert(ie[3] == 4);
140 assert(ie[4] == 0);
141 r = std::rotate(Iter(ie), Iter(ie+4), Iter(ie+se));
142 assert(base(r) == ie+1);
143 assert(ie[0] == 0);
144 assert(ie[1] == 1);
145 assert(ie[2] == 2);
146 assert(ie[3] == 3);
147 assert(ie[4] == 4);
148 r = std::rotate(Iter(ie), Iter(ie+se), Iter(ie+se));
149 assert(base(r) == ie);
150 assert(ie[0] == 0);
151 assert(ie[1] == 1);
152 assert(ie[2] == 2);
153 assert(ie[3] == 3);
154 assert(ie[4] == 4);
155
156 int ig[] = {0, 1, 2, 3, 4, 5};
157 const unsigned sg = sizeof(ig)/sizeof(ig[0]);
158 r = std::rotate(Iter(ig), Iter(ig), Iter(ig+sg));
159 assert(base(r) == ig+sg);
160 assert(ig[0] == 0);
161 assert(ig[1] == 1);
162 assert(ig[2] == 2);
163 assert(ig[3] == 3);
164 assert(ig[4] == 4);
165 assert(ig[5] == 5);
166 r = std::rotate(Iter(ig), Iter(ig+1), Iter(ig+sg));
167 assert(base(r) == ig+5);
168 assert(ig[0] == 1);
169 assert(ig[1] == 2);
170 assert(ig[2] == 3);
171 assert(ig[3] == 4);
172 assert(ig[4] == 5);
173 assert(ig[5] == 0);
174 r = std::rotate(Iter(ig), Iter(ig+2), Iter(ig+sg));
175 assert(base(r) == ig+4);
176 assert(ig[0] == 3);
177 assert(ig[1] == 4);
178 assert(ig[2] == 5);
179 assert(ig[3] == 0);
180 assert(ig[4] == 1);
181 assert(ig[5] == 2);
182 r = std::rotate(Iter(ig), Iter(ig+3), Iter(ig+sg));
183 assert(base(r) == ig+3);
184 assert(ig[0] == 0);
185 assert(ig[1] == 1);
186 assert(ig[2] == 2);
187 assert(ig[3] == 3);
188 assert(ig[4] == 4);
189 assert(ig[5] == 5);
190 r = std::rotate(Iter(ig), Iter(ig+4), Iter(ig+sg));
191 assert(base(r) == ig+2);
192 assert(ig[0] == 4);
193 assert(ig[1] == 5);
194 assert(ig[2] == 0);
195 assert(ig[3] == 1);
196 assert(ig[4] == 2);
197 assert(ig[5] == 3);
198 r = std::rotate(Iter(ig), Iter(ig+5), Iter(ig+sg));
199 assert(base(r) == ig+1);
200 assert(ig[0] == 3);
201 assert(ig[1] == 4);
202 assert(ig[2] == 5);
203 assert(ig[3] == 0);
204 assert(ig[4] == 1);
205 assert(ig[5] == 2);
206 r = std::rotate(Iter(ig), Iter(ig+sg), Iter(ig+sg));
207 assert(base(r) == ig);
208 assert(ig[0] == 3);
209 assert(ig[1] == 4);
210 assert(ig[2] == 5);
211 assert(ig[3] == 0);
212 assert(ig[4] == 1);
213 assert(ig[5] == 2);
214 }
215
216 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
217
218 template <class Iter>
219 void
test1()220 test1()
221 {
222 std::unique_ptr<int> ia[1];
223 const unsigned sa = sizeof(ia)/sizeof(ia[0]);
224 for (int i = 0; i < sa; ++i)
225 ia[i].reset(new int(i));
226 Iter r = std::rotate(Iter(ia), Iter(ia), Iter(ia));
227 assert(base(r) == ia);
228 assert(*ia[0] == 0);
229 r = std::rotate(Iter(ia), Iter(ia), Iter(ia+sa));
230 assert(base(r) == ia+sa);
231 assert(*ia[0] == 0);
232 r = std::rotate(Iter(ia), Iter(ia+sa), Iter(ia+sa));
233 assert(base(r) == ia);
234 assert(*ia[0] == 0);
235
236 std::unique_ptr<int> ib[2];
237 const unsigned sb = sizeof(ib)/sizeof(ib[0]);
238 for (int i = 0; i < sb; ++i)
239 ib[i].reset(new int(i));
240 r = std::rotate(Iter(ib), Iter(ib), Iter(ib+sb));
241 assert(base(r) == ib+sb);
242 assert(*ib[0] == 0);
243 assert(*ib[1] == 1);
244 r = std::rotate(Iter(ib), Iter(ib+1), Iter(ib+sb));
245 assert(base(r) == ib+1);
246 assert(*ib[0] == 1);
247 assert(*ib[1] == 0);
248 r = std::rotate(Iter(ib), Iter(ib+sb), Iter(ib+sb));
249 assert(base(r) == ib);
250 assert(*ib[0] == 1);
251 assert(*ib[1] == 0);
252
253 std::unique_ptr<int> ic[3];
254 const unsigned sc = sizeof(ic)/sizeof(ic[0]);
255 for (int i = 0; i < sc; ++i)
256 ic[i].reset(new int(i));
257 r = std::rotate(Iter(ic), Iter(ic), Iter(ic+sc));
258 assert(base(r) == ic+sc);
259 assert(*ic[0] == 0);
260 assert(*ic[1] == 1);
261 assert(*ic[2] == 2);
262 r = std::rotate(Iter(ic), Iter(ic+1), Iter(ic+sc));
263 assert(base(r) == ic+2);
264 assert(*ic[0] == 1);
265 assert(*ic[1] == 2);
266 assert(*ic[2] == 0);
267 r = std::rotate(Iter(ic), Iter(ic+2), Iter(ic+sc));
268 assert(base(r) == ic+1);
269 assert(*ic[0] == 0);
270 assert(*ic[1] == 1);
271 assert(*ic[2] == 2);
272 r = std::rotate(Iter(ic), Iter(ic+sc), Iter(ic+sc));
273 assert(base(r) == ic);
274 assert(*ic[0] == 0);
275 assert(*ic[1] == 1);
276 assert(*ic[2] == 2);
277
278 std::unique_ptr<int> id[4];
279 const unsigned sd = sizeof(id)/sizeof(id[0]);
280 for (int i = 0; i < sd; ++i)
281 id[i].reset(new int(i));
282 r = std::rotate(Iter(id), Iter(id), Iter(id+sd));
283 assert(base(r) == id+sd);
284 assert(*id[0] == 0);
285 assert(*id[1] == 1);
286 assert(*id[2] == 2);
287 assert(*id[3] == 3);
288 r = std::rotate(Iter(id), Iter(id+1), Iter(id+sd));
289 assert(base(r) == id+3);
290 assert(*id[0] == 1);
291 assert(*id[1] == 2);
292 assert(*id[2] == 3);
293 assert(*id[3] == 0);
294 r = std::rotate(Iter(id), Iter(id+2), Iter(id+sd));
295 assert(base(r) == id+2);
296 assert(*id[0] == 3);
297 assert(*id[1] == 0);
298 assert(*id[2] == 1);
299 assert(*id[3] == 2);
300 r = std::rotate(Iter(id), Iter(id+3), Iter(id+sd));
301 assert(base(r) == id+1);
302 assert(*id[0] == 2);
303 assert(*id[1] == 3);
304 assert(*id[2] == 0);
305 assert(*id[3] == 1);
306 r = std::rotate(Iter(id), Iter(id+sd), Iter(id+sd));
307 assert(base(r) == id);
308 assert(*id[0] == 2);
309 assert(*id[1] == 3);
310 assert(*id[2] == 0);
311 assert(*id[3] == 1);
312
313 std::unique_ptr<int> ie[5];
314 const unsigned se = sizeof(ie)/sizeof(ie[0]);
315 for (int i = 0; i < se; ++i)
316 ie[i].reset(new int(i));
317 r = std::rotate(Iter(ie), Iter(ie), Iter(ie+se));
318 assert(base(r) == ie+se);
319 assert(*ie[0] == 0);
320 assert(*ie[1] == 1);
321 assert(*ie[2] == 2);
322 assert(*ie[3] == 3);
323 assert(*ie[4] == 4);
324 r = std::rotate(Iter(ie), Iter(ie+1), Iter(ie+se));
325 assert(base(r) == ie+4);
326 assert(*ie[0] == 1);
327 assert(*ie[1] == 2);
328 assert(*ie[2] == 3);
329 assert(*ie[3] == 4);
330 assert(*ie[4] == 0);
331 r = std::rotate(Iter(ie), Iter(ie+2), Iter(ie+se));
332 assert(base(r) == ie+3);
333 assert(*ie[0] == 3);
334 assert(*ie[1] == 4);
335 assert(*ie[2] == 0);
336 assert(*ie[3] == 1);
337 assert(*ie[4] == 2);
338 r = std::rotate(Iter(ie), Iter(ie+3), Iter(ie+se));
339 assert(base(r) == ie+2);
340 assert(*ie[0] == 1);
341 assert(*ie[1] == 2);
342 assert(*ie[2] == 3);
343 assert(*ie[3] == 4);
344 assert(*ie[4] == 0);
345 r = std::rotate(Iter(ie), Iter(ie+4), Iter(ie+se));
346 assert(base(r) == ie+1);
347 assert(*ie[0] == 0);
348 assert(*ie[1] == 1);
349 assert(*ie[2] == 2);
350 assert(*ie[3] == 3);
351 assert(*ie[4] == 4);
352 r = std::rotate(Iter(ie), Iter(ie+se), Iter(ie+se));
353 assert(base(r) == ie);
354 assert(*ie[0] == 0);
355 assert(*ie[1] == 1);
356 assert(*ie[2] == 2);
357 assert(*ie[3] == 3);
358 assert(*ie[4] == 4);
359
360 std::unique_ptr<int> ig[6];
361 const unsigned sg = sizeof(ig)/sizeof(ig[0]);
362 for (int i = 0; i < sg; ++i)
363 ig[i].reset(new int(i));
364 r = std::rotate(Iter(ig), Iter(ig), Iter(ig+sg));
365 assert(base(r) == ig+sg);
366 assert(*ig[0] == 0);
367 assert(*ig[1] == 1);
368 assert(*ig[2] == 2);
369 assert(*ig[3] == 3);
370 assert(*ig[4] == 4);
371 assert(*ig[5] == 5);
372 r = std::rotate(Iter(ig), Iter(ig+1), Iter(ig+sg));
373 assert(base(r) == ig+5);
374 assert(*ig[0] == 1);
375 assert(*ig[1] == 2);
376 assert(*ig[2] == 3);
377 assert(*ig[3] == 4);
378 assert(*ig[4] == 5);
379 assert(*ig[5] == 0);
380 r = std::rotate(Iter(ig), Iter(ig+2), Iter(ig+sg));
381 assert(base(r) == ig+4);
382 assert(*ig[0] == 3);
383 assert(*ig[1] == 4);
384 assert(*ig[2] == 5);
385 assert(*ig[3] == 0);
386 assert(*ig[4] == 1);
387 assert(*ig[5] == 2);
388 r = std::rotate(Iter(ig), Iter(ig+3), Iter(ig+sg));
389 assert(base(r) == ig+3);
390 assert(*ig[0] == 0);
391 assert(*ig[1] == 1);
392 assert(*ig[2] == 2);
393 assert(*ig[3] == 3);
394 assert(*ig[4] == 4);
395 assert(*ig[5] == 5);
396 r = std::rotate(Iter(ig), Iter(ig+4), Iter(ig+sg));
397 assert(base(r) == ig+2);
398 assert(*ig[0] == 4);
399 assert(*ig[1] == 5);
400 assert(*ig[2] == 0);
401 assert(*ig[3] == 1);
402 assert(*ig[4] == 2);
403 assert(*ig[5] == 3);
404 r = std::rotate(Iter(ig), Iter(ig+5), Iter(ig+sg));
405 assert(base(r) == ig+1);
406 assert(*ig[0] == 3);
407 assert(*ig[1] == 4);
408 assert(*ig[2] == 5);
409 assert(*ig[3] == 0);
410 assert(*ig[4] == 1);
411 assert(*ig[5] == 2);
412 r = std::rotate(Iter(ig), Iter(ig+sg), Iter(ig+sg));
413 assert(base(r) == ig);
414 assert(*ig[0] == 3);
415 assert(*ig[1] == 4);
416 assert(*ig[2] == 5);
417 assert(*ig[3] == 0);
418 assert(*ig[4] == 1);
419 assert(*ig[5] == 2);
420 }
421
422 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
423
main()424 int main()
425 {
426 test<forward_iterator<int*> >();
427 test<bidirectional_iterator<int*> >();
428 test<random_access_iterator<int*> >();
429 test<int*>();
430
431 #ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES
432
433 test1<forward_iterator<std::unique_ptr<int>*> >();
434 test1<bidirectional_iterator<std::unique_ptr<int>*> >();
435 test1<random_access_iterator<std::unique_ptr<int>*> >();
436 test1<std::unique_ptr<int>*>();
437
438 #endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES
439 }
440