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