465 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8 9// <algorithm>10 11// template<ShuffleIterator Iter>12// Iter rotate(Iter first, Iter middle, Iter last); // constexpr since C++2013 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 >= 11217 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 >= 11423 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(a.begin(), a.begin() + mid, 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 >= 11442 if (TEST_STD_AT_LEAST_23_OR_RUNTIME_EVALUATED)443 types::for_each(types::forward_iterator_list<std::unique_ptr<int>*>(), TestUniquePtr());444#endif445 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 >= 20460 static_assert(test());461#endif462 463 return 0;464}465