1//===----------------------------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9// <algorithm>
10
11// template<ShuffleIterator Iter>
12// Iter rotate(Iter first, Iter middle, Iter last); // constexpr since C++20
13
14#include <algorithm>
15#include <cassert>
16#include <memory>
17#include <type_traits>
18#include <vector>
19
20#include "test_macros.h"
21#include "test_iterators.h"
22#include "type_algorithms.h"
23
24struct TestIter {
25 template <class Iter>
26 TEST_CONSTEXPR_CXX20 void operator()() const {
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
216#if TEST_STD_VER >= 11
217
218struct TestUniquePtr {
219 template <class Iter>
220 TEST_CONSTEXPR_CXX23 void operator()() const {
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
422#endif // TEST_STD_VER >= 11
423
424template <std::size_t N>
425TEST_CONSTEXPR_CXX20 bool test_vector_bool() {
426 for (int offset = -4; offset <= 4; ++offset) {
427 std::vector<bool> a(N, false);
428 std::size_t mid = N / 2 + offset;
429 for (std::size_t i = mid; i < N; ++i)
430 a[i] = true;
431 std::rotate(first: a.begin(), middle: a.begin() + mid, last: a.end());
432 for (std::size_t i = 0; i < N; ++i)
433 assert(a[i] == (i < N - mid));
434 }
435 return true;
436};
437
438TEST_CONSTEXPR_CXX20 bool test() {
439 types::for_each(types::forward_iterator_list<int*>(), TestIter());
440
441#if TEST_STD_VER >= 11
442 if (TEST_STD_AT_LEAST_23_OR_RUNTIME_EVALUATED)
443 types::for_each(types::forward_iterator_list<std::unique_ptr<int>*>(), TestUniquePtr());
444#endif
445
446 test_vector_bool<8>();
447 test_vector_bool<19>();
448 test_vector_bool<32>();
449 test_vector_bool<49>();
450 test_vector_bool<64>();
451 test_vector_bool<199>();
452 test_vector_bool<256>();
453
454 return true;
455}
456
457int main(int, char**) {
458 test();
459#if TEST_STD_VER >= 20
460 static_assert(test());
461#endif
462
463 return 0;
464}
465

source code of libcxx/test/std/algorithms/alg.modifying.operations/alg.rotate/rotate.pass.cpp