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