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
24template <class Iter>
25void
26test()
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
218template <class Iter>
219void
220test1()
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
424int 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