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 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 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 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
