src/liballoc/tests/vec_deque.rs

   1 use std::fmt::Debug;
   2 use std::collections::{VecDeque, vec_deque::Drain};
   3 use std::collections::CollectionAllocErr::*;
   4 use std::mem::size_of;
   5 use std::{usize, isize};
   6
   7 use crate::hash;
   8
   9 use Taggy::*;
  10 use Taggypar::*;
  11
  12 #[test]
  13 fn test_simple() {
  14     let mut d = VecDeque::new();
  15     assert_eq!(d.len(), 0);
  16     d.push_front(17);
  17     d.push_front(42);
  18     d.push_back(137);
  19     assert_eq!(d.len(), 3);
  20     d.push_back(137);
  21     assert_eq!(d.len(), 4);
  22     assert_eq!(*d.front().unwrap(), 42);
  23     assert_eq!(*d.back().unwrap(), 137);
  24     let mut i = d.pop_front();
  25     assert_eq!(i, Some(42));
  26     i = d.pop_back();
  27     assert_eq!(i, Some(137));
  28     i = d.pop_back();
  29     assert_eq!(i, Some(137));
  30     i = d.pop_back();
  31     assert_eq!(i, Some(17));
  32     assert_eq!(d.len(), 0);
  33     d.push_back(3);
  34     assert_eq!(d.len(), 1);
  35     d.push_front(2);
  36     assert_eq!(d.len(), 2);
  37     d.push_back(4);
  38     assert_eq!(d.len(), 3);
  39     d.push_front(1);
  40     assert_eq!(d.len(), 4);
  41     assert_eq!(d[0], 1);
  42     assert_eq!(d[1], 2);
  43     assert_eq!(d[2], 3);
  44     assert_eq!(d[3], 4);
  45 }
  46
  47 #[cfg(test)]
  48 fn test_parameterized<T: Clone + PartialEq + Debug>(a: T, b: T, c: T, d: T) {
  49     let mut deq = VecDeque::new();
  50     assert_eq!(deq.len(), 0);
  51     deq.push_front(a.clone());
  52     deq.push_front(b.clone());
  53     deq.push_back(c.clone());
  54     assert_eq!(deq.len(), 3);
  55     deq.push_back(d.clone());
  56     assert_eq!(deq.len(), 4);
  57     assert_eq!((*deq.front().unwrap()).clone(), b.clone());
  58     assert_eq!((*deq.back().unwrap()).clone(), d.clone());
  59     assert_eq!(deq.pop_front().unwrap(), b.clone());
  60     assert_eq!(deq.pop_back().unwrap(), d.clone());
  61     assert_eq!(deq.pop_back().unwrap(), c.clone());
  62     assert_eq!(deq.pop_back().unwrap(), a.clone());
  63     assert_eq!(deq.len(), 0);
  64     deq.push_back(c.clone());
  65     assert_eq!(deq.len(), 1);
  66     deq.push_front(b.clone());
  67     assert_eq!(deq.len(), 2);
  68     deq.push_back(d.clone());
  69     assert_eq!(deq.len(), 3);
  70     deq.push_front(a.clone());
  71     assert_eq!(deq.len(), 4);
  72     assert_eq!(deq[0].clone(), a.clone());
  73     assert_eq!(deq[1].clone(), b.clone());
  74     assert_eq!(deq[2].clone(), c.clone());
  75     assert_eq!(deq[3].clone(), d.clone());
  76 }
  77
  78 #[test]
  79 fn test_push_front_grow() {
  80     let mut deq = VecDeque::new();
  81     for i in 0..66 {
  82         deq.push_front(i);
  83     }
  84     assert_eq!(deq.len(), 66);
  85
  86     for i in 0..66 {
  87         assert_eq!(deq[i], 65 - i);
  88     }
  89
  90     let mut deq = VecDeque::new();
  91     for i in 0..66 {
  92         deq.push_back(i);
  93     }
  94
  95     for i in 0..66 {
  96         assert_eq!(deq[i], i);
  97     }
  98 }
  99
 100 #[test]
 101 fn test_index() {
 102     let mut deq = VecDeque::new();
 103     for i in 1..4 {
 104         deq.push_front(i);
 105     }
 106     assert_eq!(deq[1], 2);
 107 }
 108
 109 #[test]
 110 #[should_panic]
 111 #[cfg(not(miri))]
 112 fn test_index_out_of_bounds() {
 113     let mut deq = VecDeque::new();
 114     for i in 1..4 {
 115         deq.push_front(i);
 116     }
 117     deq[3];
 118 }
 119
 120 #[derive(Clone, PartialEq, Debug)]
 121 enum Taggy {
 122     One(i32),
 123     Two(i32, i32),
 124     Three(i32, i32, i32),
 125 }
 126
 127 #[derive(Clone, PartialEq, Debug)]
 128 enum Taggypar<T> {
 129     Onepar(T),
 130     Twopar(T, T),
 131     Threepar(T, T, T),
 132 }
 133
 134 #[derive(Clone, PartialEq, Debug)]
 135 struct RecCy {
 136     x: i32,
 137     y: i32,
 138     t: Taggy,
 139 }
 140
 141 #[test]
 142 fn test_param_int() {
 143     test_parameterized::<i32>(5, 72, 64, 175);
 144 }
 145
 146 #[test]
 147 fn test_param_taggy() {
 148     test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
 149 }
 150
 151 #[test]
 152 fn test_param_taggypar() {
 153     test_parameterized::<Taggypar<i32>>(Onepar::<i32>(1),
 154                                         Twopar::<i32>(1, 2),
 155                                         Threepar::<i32>(1, 2, 3),
 156                                         Twopar::<i32>(17, 42));
 157 }
 158
 159 #[test]
 160 fn test_param_reccy() {
 161     let reccy1 = RecCy {
 162         x: 1,
 163         y: 2,
 164         t: One(1),
 165     };
 166     let reccy2 = RecCy {
 167         x: 345,
 168         y: 2,
 169         t: Two(1, 2),
 170     };
 171     let reccy3 = RecCy {
 172         x: 1,
 173         y: 777,
 174         t: Three(1, 2, 3),
 175     };
 176     let reccy4 = RecCy {
 177         x: 19,
 178         y: 252,
 179         t: Two(17, 42),
 180     };
 181     test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
 182 }
 183
 184 #[test]
 185 fn test_with_capacity() {
 186     let mut d = VecDeque::with_capacity(0);
 187     d.push_back(1);
 188     assert_eq!(d.len(), 1);
 189     let mut d = VecDeque::with_capacity(50);
 190     d.push_back(1);
 191     assert_eq!(d.len(), 1);
 192 }
 193
 194 #[test]
 195 fn test_with_capacity_non_power_two() {
 196     let mut d3 = VecDeque::with_capacity(3);
 197     d3.push_back(1);
 198
 199     // X = None, | = lo
 200     // [|1, X, X]
 201     assert_eq!(d3.pop_front(), Some(1));
 202     // [X, |X, X]
 203     assert_eq!(d3.front(), None);
 204
 205     // [X, |3, X]
 206     d3.push_back(3);
 207     // [X, |3, 6]
 208     d3.push_back(6);
 209     // [X, X, |6]
 210     assert_eq!(d3.pop_front(), Some(3));
 211
 212     // Pushing the lo past half way point to trigger
 213     // the 'B' scenario for growth
 214     // [9, X, |6]
 215     d3.push_back(9);
 216     // [9, 12, |6]
 217     d3.push_back(12);
 218
 219     d3.push_back(15);
 220     // There used to be a bug here about how the
 221     // VecDeque made growth assumptions about the
 222     // underlying Vec which didn't hold and lead
 223     // to corruption.
 224     // (Vec grows to next power of two)
 225     // good- [9, 12, 15, X, X, X, X, |6]
 226     // bug-  [15, 12, X, X, X, |6, X, X]
 227     assert_eq!(d3.pop_front(), Some(6));
 228
 229     // Which leads us to the following state which
 230     // would be a failure case.
 231     // bug-  [15, 12, X, X, X, X, |X, X]
 232     assert_eq!(d3.front(), Some(&9));
 233 }
 234
 235 #[test]
 236 fn test_reserve_exact() {
 237     let mut d = VecDeque::new();
 238     d.push_back(0);
 239     d.reserve_exact(50);
 240     assert!(d.capacity() >= 51);
 241 }
 242
 243 #[test]
 244 fn test_reserve() {
 245     let mut d = VecDeque::new();
 246     d.push_back(0);
 247     d.reserve(50);
 248     assert!(d.capacity() >= 51);
 249 }
 250
 251 #[test]
 252 fn test_swap() {
 253     let mut d: VecDeque<_> = (0..5).collect();
 254     d.pop_front();
 255     d.swap(0, 3);
 256     assert_eq!(d.iter().cloned().collect::<Vec<_>>(), [4, 2, 3, 1]);
 257 }
 258
 259 #[test]
 260 fn test_iter() {
 261     let mut d = VecDeque::new();
 262     assert_eq!(d.iter().next(), None);
 263     assert_eq!(d.iter().size_hint(), (0, Some(0)));
 264
 265     for i in 0..5 {
 266         d.push_back(i);
 267     }
 268     {
 269         let b: &[_] = &[&0, &1, &2, &3, &4];
 270         assert_eq!(d.iter().collect::<Vec<_>>(), b);
 271     }
 272
 273     for i in 6..9 {
 274         d.push_front(i);
 275     }
 276     {
 277         let b: &[_] = &[&8, &7, &6, &0, &1, &2, &3, &4];
 278         assert_eq!(d.iter().collect::<Vec<_>>(), b);
 279     }
 280
 281     let mut it = d.iter();
 282     let mut len = d.len();
 283     loop {
 284         match it.next() {
 285             None => break,
 286             _ => {
 287                 len -= 1;
 288                 assert_eq!(it.size_hint(), (len, Some(len)))
 289             }
 290         }
 291     }
 292 }
 293
 294 #[test]
 295 fn test_rev_iter() {
 296     let mut d = VecDeque::new();
 297     assert_eq!(d.iter().rev().next(), None);
 298
 299     for i in 0..5 {
 300         d.push_back(i);
 301     }
 302     {
 303         let b: &[_] = &[&4, &3, &2, &1, &0];
 304         assert_eq!(d.iter().rev().collect::<Vec<_>>(), b);
 305     }
 306
 307     for i in 6..9 {
 308         d.push_front(i);
 309     }
 310     let b: &[_] = &[&4, &3, &2, &1, &0, &6, &7, &8];
 311     assert_eq!(d.iter().rev().collect::<Vec<_>>(), b);
 312 }
 313
 314 #[test]
 315 fn test_mut_rev_iter_wrap() {
 316     let mut d = VecDeque::with_capacity(3);
 317     assert!(d.iter_mut().rev().next().is_none());
 318
 319     d.push_back(1);
 320     d.push_back(2);
 321     d.push_back(3);
 322     assert_eq!(d.pop_front(), Some(1));
 323     d.push_back(4);
 324
 325     assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<_>>(),
 326                vec![4, 3, 2]);
 327 }
 328
 329 #[test]
 330 fn test_mut_iter() {
 331     let mut d = VecDeque::new();
 332     assert!(d.iter_mut().next().is_none());
 333
 334     for i in 0..3 {
 335         d.push_front(i);
 336     }
 337
 338     for (i, elt) in d.iter_mut().enumerate() {
 339         assert_eq!(*elt, 2 - i);
 340         *elt = i;
 341     }
 342
 343     {
 344         let mut it = d.iter_mut();
 345         assert_eq!(*it.next().unwrap(), 0);
 346         assert_eq!(*it.next().unwrap(), 1);
 347         assert_eq!(*it.next().unwrap(), 2);
 348         assert!(it.next().is_none());
 349     }
 350 }
 351
 352 #[test]
 353 fn test_mut_rev_iter() {
 354     let mut d = VecDeque::new();
 355     assert!(d.iter_mut().rev().next().is_none());
 356
 357     for i in 0..3 {
 358         d.push_front(i);
 359     }
 360
 361     for (i, elt) in d.iter_mut().rev().enumerate() {
 362         assert_eq!(*elt, i);
 363         *elt = i;
 364     }
 365
 366     {
 367         let mut it = d.iter_mut().rev();
 368         assert_eq!(*it.next().unwrap(), 0);
 369         assert_eq!(*it.next().unwrap(), 1);
 370         assert_eq!(*it.next().unwrap(), 2);
 371         assert!(it.next().is_none());
 372     }
 373 }
 374
 375 #[test]
 376 fn test_into_iter() {
 377
 378     // Empty iter
 379     {
 380         let d: VecDeque<i32> = VecDeque::new();
 381         let mut iter = d.into_iter();
 382
 383         assert_eq!(iter.size_hint(), (0, Some(0)));
 384         assert_eq!(iter.next(), None);
 385         assert_eq!(iter.size_hint(), (0, Some(0)));
 386     }
 387
 388     // simple iter
 389     {
 390         let mut d = VecDeque::new();
 391         for i in 0..5 {
 392             d.push_back(i);
 393         }
 394
 395         let b = vec![0, 1, 2, 3, 4];
 396         assert_eq!(d.into_iter().collect::<Vec<_>>(), b);
 397     }
 398
 399     // wrapped iter
 400     {
 401         let mut d = VecDeque::new();
 402         for i in 0..5 {
 403             d.push_back(i);
 404         }
 405         for i in 6..9 {
 406             d.push_front(i);
 407         }
 408
 409         let b = vec![8, 7, 6, 0, 1, 2, 3, 4];
 410         assert_eq!(d.into_iter().collect::<Vec<_>>(), b);
 411     }
 412
 413     // partially used
 414     {
 415         let mut d = VecDeque::new();
 416         for i in 0..5 {
 417             d.push_back(i);
 418         }
 419         for i in 6..9 {
 420             d.push_front(i);
 421         }
 422
 423         let mut it = d.into_iter();
 424         assert_eq!(it.size_hint(), (8, Some(8)));
 425         assert_eq!(it.next(), Some(8));
 426         assert_eq!(it.size_hint(), (7, Some(7)));
 427         assert_eq!(it.next_back(), Some(4));
 428         assert_eq!(it.size_hint(), (6, Some(6)));
 429         assert_eq!(it.next(), Some(7));
 430         assert_eq!(it.size_hint(), (5, Some(5)));
 431     }
 432 }
 433
 434 #[test]
 435 fn test_drain() {
 436
 437     // Empty iter
 438     {
 439         let mut d: VecDeque<i32> = VecDeque::new();
 440
 441         {
 442             let mut iter = d.drain(..);
 443
 444             assert_eq!(iter.size_hint(), (0, Some(0)));
 445             assert_eq!(iter.next(), None);
 446             assert_eq!(iter.size_hint(), (0, Some(0)));
 447         }
 448
 449         assert!(d.is_empty());
 450     }
 451
 452     // simple iter
 453     {
 454         let mut d = VecDeque::new();
 455         for i in 0..5 {
 456             d.push_back(i);
 457         }
 458
 459         assert_eq!(d.drain(..).collect::<Vec<_>>(), [0, 1, 2, 3, 4]);
 460         assert!(d.is_empty());
 461     }
 462
 463     // wrapped iter
 464     {
 465         let mut d = VecDeque::new();
 466         for i in 0..5 {
 467             d.push_back(i);
 468         }
 469         for i in 6..9 {
 470             d.push_front(i);
 471         }
 472
 473         assert_eq!(d.drain(..).collect::<Vec<_>>(), [8, 7, 6, 0, 1, 2, 3, 4]);
 474         assert!(d.is_empty());
 475     }
 476
 477     // partially used
 478     {
 479         let mut d: VecDeque<_> = VecDeque::new();
 480         for i in 0..5 {
 481             d.push_back(i);
 482         }
 483         for i in 6..9 {
 484             d.push_front(i);
 485         }
 486
 487         {
 488             let mut it = d.drain(..);
 489             assert_eq!(it.size_hint(), (8, Some(8)));
 490             assert_eq!(it.next(), Some(8));
 491             assert_eq!(it.size_hint(), (7, Some(7)));
 492             assert_eq!(it.next_back(), Some(4));
 493             assert_eq!(it.size_hint(), (6, Some(6)));
 494             assert_eq!(it.next(), Some(7));
 495             assert_eq!(it.size_hint(), (5, Some(5)));
 496         }
 497         assert!(d.is_empty());
 498     }
 499 }
 500
 501 #[test]
 502 fn test_from_iter() {
 503     let v = vec![1, 2, 3, 4, 5, 6, 7];
 504     let deq: VecDeque<_> = v.iter().cloned().collect();
 505     let u: Vec<_> = deq.iter().cloned().collect();
 506     assert_eq!(u, v);
 507
 508     let seq = (0..).step_by(2).take(256);
 509     let deq: VecDeque<_> = seq.collect();
 510     for (i, &x) in deq.iter().enumerate() {
 511         assert_eq!(2 * i, x);
 512     }
 513     assert_eq!(deq.len(), 256);
 514 }
 515
 516 #[test]
 517 fn test_clone() {
 518     let mut d = VecDeque::new();
 519     d.push_front(17);
 520     d.push_front(42);
 521     d.push_back(137);
 522     d.push_back(137);
 523     assert_eq!(d.len(), 4);
 524     let mut e = d.clone();
 525     assert_eq!(e.len(), 4);
 526     while !d.is_empty() {
 527         assert_eq!(d.pop_back(), e.pop_back());
 528     }
 529     assert_eq!(d.len(), 0);
 530     assert_eq!(e.len(), 0);
 531 }
 532
 533 #[test]
 534 fn test_eq() {
 535     let mut d = VecDeque::new();
 536     assert!(d == VecDeque::with_capacity(0));
 537     d.push_front(137);
 538     d.push_front(17);
 539     d.push_front(42);
 540     d.push_back(137);
 541     let mut e = VecDeque::with_capacity(0);
 542     e.push_back(42);
 543     e.push_back(17);
 544     e.push_back(137);
 545     e.push_back(137);
 546     assert!(&e == &d);
 547     e.pop_back();
 548     e.push_back(0);
 549     assert!(e != d);
 550     e.clear();
 551     assert!(e == VecDeque::new());
 552 }
 553
 554 #[test]
 555 fn test_partial_eq_array() {
 556     let d = VecDeque::<char>::new();
 557     assert!(d == []);
 558
 559     let mut d = VecDeque::new();
 560     d.push_front('a');
 561     assert!(d == ['a']);
 562
 563     let mut d = VecDeque::new();
 564     d.push_back('a');
 565     assert!(d == ['a']);
 566
 567     let mut d = VecDeque::new();
 568     d.push_back('a');
 569     d.push_back('b');
 570     assert!(d == ['a', 'b']);
 571 }
 572
 573 #[test]
 574 fn test_hash() {
 575     let mut x = VecDeque::new();
 576     let mut y = VecDeque::new();
 577
 578     x.push_back(1);
 579     x.push_back(2);
 580     x.push_back(3);
 581
 582     y.push_back(0);
 583     y.push_back(1);
 584     y.pop_front();
 585     y.push_back(2);
 586     y.push_back(3);
 587
 588     assert!(hash(&x) == hash(&y));
 589 }
 590
 591 #[test]
 592 fn test_hash_after_rotation() {
 593     // test that two deques hash equal even if elements are laid out differently
 594     let len = 28;
 595     let mut ring: VecDeque<i32> = (0..len as i32).collect();
 596     let orig = ring.clone();
 597     for _ in 0..ring.capacity() {
 598         // shift values 1 step to the right by pop, sub one, push
 599         ring.pop_front();
 600         for elt in &mut ring {
 601             *elt -= 1;
 602         }
 603         ring.push_back(len - 1);
 604         assert_eq!(hash(&orig), hash(&ring));
 605         assert_eq!(orig, ring);
 606         assert_eq!(ring, orig);
 607     }
 608 }
 609
 610 #[test]
 611 fn test_eq_after_rotation() {
 612     // test that two deques are equal even if elements are laid out differently
 613     let len = 28;
 614     let mut ring: VecDeque<i32> = (0..len as i32).collect();
 615     let mut shifted = ring.clone();
 616     for _ in 0..10 {
 617         // shift values 1 step to the right by pop, sub one, push
 618         ring.pop_front();
 619         for elt in &mut ring {
 620             *elt -= 1;
 621         }
 622         ring.push_back(len - 1);
 623     }
 624
 625     // try every shift
 626     for _ in 0..shifted.capacity() {
 627         shifted.pop_front();
 628         for elt in &mut shifted {
 629             *elt -= 1;
 630         }
 631         shifted.push_back(len - 1);
 632         assert_eq!(shifted, ring);
 633         assert_eq!(ring, shifted);
 634     }
 635 }
 636
 637 #[test]
 638 fn test_ord() {
 639     let x = VecDeque::new();
 640     let mut y = VecDeque::new();
 641     y.push_back(1);
 642     y.push_back(2);
 643     y.push_back(3);
 644     assert!(x < y);
 645     assert!(y > x);
 646     assert!(x <= x);
 647     assert!(x >= x);
 648 }
 649
 650 #[test]
 651 fn test_show() {
 652     let ringbuf: VecDeque<_> = (0..10).collect();
 653     assert_eq!(format!("{:?}", ringbuf), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
 654
 655     let ringbuf: VecDeque<_> = vec!["just", "one", "test", "more"]
 656         .iter()
 657         .cloned()
 658         .collect();
 659     assert_eq!(format!("{:?}", ringbuf),
 660                "[\"just\", \"one\", \"test\", \"more\"]");
 661 }
 662
 663 #[test]
 664 fn test_drop() {
 665     static mut DROPS: i32 = 0;
 666     struct Elem;
 667     impl Drop for Elem {
 668         fn drop(&mut self) {
 669             unsafe {
 670                 DROPS += 1;
 671             }
 672         }
 673     }
 674
 675     let mut ring = VecDeque::new();
 676     ring.push_back(Elem);
 677     ring.push_front(Elem);
 678     ring.push_back(Elem);
 679     ring.push_front(Elem);
 680     drop(ring);
 681
 682     assert_eq!(unsafe { DROPS }, 4);
 683 }
 684
 685 #[test]
 686 fn test_drop_with_pop() {
 687     static mut DROPS: i32 = 0;
 688     struct Elem;
 689     impl Drop for Elem {
 690         fn drop(&mut self) {
 691             unsafe {
 692                 DROPS += 1;
 693             }
 694         }
 695     }
 696
 697     let mut ring = VecDeque::new();
 698     ring.push_back(Elem);
 699     ring.push_front(Elem);
 700     ring.push_back(Elem);
 701     ring.push_front(Elem);
 702
 703     drop(ring.pop_back());
 704     drop(ring.pop_front());
 705     assert_eq!(unsafe { DROPS }, 2);
 706
 707     drop(ring);
 708     assert_eq!(unsafe { DROPS }, 4);
 709 }
 710
 711 #[test]
 712 fn test_drop_clear() {
 713     static mut DROPS: i32 = 0;
 714     struct Elem;
 715     impl Drop for Elem {
 716         fn drop(&mut self) {
 717             unsafe {
 718                 DROPS += 1;
 719             }
 720         }
 721     }
 722
 723     let mut ring = VecDeque::new();
 724     ring.push_back(Elem);
 725     ring.push_front(Elem);
 726     ring.push_back(Elem);
 727     ring.push_front(Elem);
 728     ring.clear();
 729     assert_eq!(unsafe { DROPS }, 4);
 730
 731     drop(ring);
 732     assert_eq!(unsafe { DROPS }, 4);
 733 }
 734
 735 #[test]
 736 fn test_reserve_grow() {
 737     // test growth path A
 738     // [T o o H] -> [T o o H . . . . ]
 739     let mut ring = VecDeque::with_capacity(4);
 740     for i in 0..3 {
 741         ring.push_back(i);
 742     }
 743     ring.reserve(7);
 744     for i in 0..3 {
 745         assert_eq!(ring.pop_front(), Some(i));
 746     }
 747
 748     // test growth path B
 749     // [H T o o] -> [. T o o H . . . ]
 750     let mut ring = VecDeque::with_capacity(4);
 751     for i in 0..1 {
 752         ring.push_back(i);
 753         assert_eq!(ring.pop_front(), Some(i));
 754     }
 755     for i in 0..3 {
 756         ring.push_back(i);
 757     }
 758     ring.reserve(7);
 759     for i in 0..3 {
 760         assert_eq!(ring.pop_front(), Some(i));
 761     }
 762
 763     // test growth path C
 764     // [o o H T] -> [o o H . . . . T ]
 765     let mut ring = VecDeque::with_capacity(4);
 766     for i in 0..3 {
 767         ring.push_back(i);
 768         assert_eq!(ring.pop_front(), Some(i));
 769     }
 770     for i in 0..3 {
 771         ring.push_back(i);
 772     }
 773     ring.reserve(7);
 774     for i in 0..3 {
 775         assert_eq!(ring.pop_front(), Some(i));
 776     }
 777 }
 778
 779 #[test]
 780 fn test_get() {
 781     let mut ring = VecDeque::new();
 782     ring.push_back(0);
 783     assert_eq!(ring.get(0), Some(&0));
 784     assert_eq!(ring.get(1), None);
 785
 786     ring.push_back(1);
 787     assert_eq!(ring.get(0), Some(&0));
 788     assert_eq!(ring.get(1), Some(&1));
 789     assert_eq!(ring.get(2), None);
 790
 791     ring.push_back(2);
 792     assert_eq!(ring.get(0), Some(&0));
 793     assert_eq!(ring.get(1), Some(&1));
 794     assert_eq!(ring.get(2), Some(&2));
 795     assert_eq!(ring.get(3), None);
 796
 797     assert_eq!(ring.pop_front(), Some(0));
 798     assert_eq!(ring.get(0), Some(&1));
 799     assert_eq!(ring.get(1), Some(&2));
 800     assert_eq!(ring.get(2), None);
 801
 802     assert_eq!(ring.pop_front(), Some(1));
 803     assert_eq!(ring.get(0), Some(&2));
 804     assert_eq!(ring.get(1), None);
 805
 806     assert_eq!(ring.pop_front(), Some(2));
 807     assert_eq!(ring.get(0), None);
 808     assert_eq!(ring.get(1), None);
 809 }
 810
 811 #[test]
 812 fn test_get_mut() {
 813     let mut ring = VecDeque::new();
 814     for i in 0..3 {
 815         ring.push_back(i);
 816     }
 817
 818     match ring.get_mut(1) {
 819         Some(x) => *x = -1,
 820         None => (),
 821     };
 822
 823     assert_eq!(ring.get_mut(0), Some(&mut 0));
 824     assert_eq!(ring.get_mut(1), Some(&mut -1));
 825     assert_eq!(ring.get_mut(2), Some(&mut 2));
 826     assert_eq!(ring.get_mut(3), None);
 827
 828     assert_eq!(ring.pop_front(), Some(0));
 829     assert_eq!(ring.get_mut(0), Some(&mut -1));
 830     assert_eq!(ring.get_mut(1), Some(&mut 2));
 831     assert_eq!(ring.get_mut(2), None);
 832 }
 833
 834 #[test]
 835 fn test_front() {
 836     let mut ring = VecDeque::new();
 837     ring.push_back(10);
 838     ring.push_back(20);
 839     assert_eq!(ring.front(), Some(&10));
 840     ring.pop_front();
 841     assert_eq!(ring.front(), Some(&20));
 842     ring.pop_front();
 843     assert_eq!(ring.front(), None);
 844 }
 845
 846 #[test]
 847 fn test_as_slices() {
 848     let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
 849     let cap = ring.capacity() as i32;
 850     let first = cap / 2;
 851     let last = cap - first;
 852     for i in 0..first {
 853         ring.push_back(i);
 854
 855         let (left, right) = ring.as_slices();
 856         let expected: Vec<_> = (0..=i).collect();
 857         assert_eq!(left, &expected[..]);
 858         assert_eq!(right, []);
 859     }
 860
 861     for j in -last..0 {
 862         ring.push_front(j);
 863         let (left, right) = ring.as_slices();
 864         let expected_left: Vec<_> = (-last..=j).rev().collect();
 865         let expected_right: Vec<_> = (0..first).collect();
 866         assert_eq!(left, &expected_left[..]);
 867         assert_eq!(right, &expected_right[..]);
 868     }
 869
 870     assert_eq!(ring.len() as i32, cap);
 871     assert_eq!(ring.capacity() as i32, cap);
 872 }
 873
 874 #[test]
 875 fn test_as_mut_slices() {
 876     let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
 877     let cap = ring.capacity() as i32;
 878     let first = cap / 2;
 879     let last = cap - first;
 880     for i in 0..first {
 881         ring.push_back(i);
 882
 883         let (left, right) = ring.as_mut_slices();
 884         let expected: Vec<_> = (0..=i).collect();
 885         assert_eq!(left, &expected[..]);
 886         assert_eq!(right, []);
 887     }
 888
 889     for j in -last..0 {
 890         ring.push_front(j);
 891         let (left, right) = ring.as_mut_slices();
 892         let expected_left: Vec<_> = (-last..=j).rev().collect();
 893         let expected_right: Vec<_> = (0..first).collect();
 894         assert_eq!(left, &expected_left[..]);
 895         assert_eq!(right, &expected_right[..]);
 896     }
 897
 898     assert_eq!(ring.len() as i32, cap);
 899     assert_eq!(ring.capacity() as i32, cap);
 900 }
 901
 902 #[test]
 903 fn test_append() {
 904     let mut a: VecDeque<_> = vec![1, 2, 3].into_iter().collect();
 905     let mut b: VecDeque<_> = vec![4, 5, 6].into_iter().collect();
 906
 907     // normal append
 908     a.append(&mut b);
 909     assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
 910     #[cfg(not(miri))]
 911     assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
 912
 913     // append nothing to something
 914     a.append(&mut b);
 915     assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
 916     #[cfg(not(miri))]
 917     assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
 918
 919     // append something to nothing
 920     b.append(&mut a);
 921     assert_eq!(b.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
 922     #[cfg(not(miri))]
 923     assert_eq!(a.iter().cloned().collect::<Vec<_>>(), []);
 924 }
 925
 926 #[test]
 927 #[cfg(not(miri))]
 928 fn test_append_permutations() {
 929     fn construct_vec_deque(
 930         push_back: usize,
 931         pop_back: usize,
 932         push_front: usize,
 933         pop_front: usize,
 934     ) -> VecDeque<usize> {
 935         let mut out = VecDeque::new();
 936         for a in 0..push_back {
 937             out.push_back(a);
 938         }
 939         for b in 0..push_front {
 940             out.push_front(push_back + b);
 941         }
 942         for _ in 0..pop_back {
 943             out.pop_back();
 944         }
 945         for _ in 0..pop_front {
 946             out.pop_front();
 947         }
 948         out
 949     }
 950
 951     const MAX: usize = 5;
 952
 953     // Many different permutations of both the `VecDeque` getting appended to
 954     // and the one getting appended are generated to check `append`.
 955     // This ensures all 6 code paths of `append` are tested.
 956     for src_push_back in 0..MAX {
 957         for src_push_front in 0..MAX {
 958             // doesn't pop more values than are pushed
 959             for src_pop_back in 0..(src_push_back + src_push_front) {
 960                 for src_pop_front in 0..(src_push_back + src_push_front - src_pop_back) {
 961
 962                     let src = construct_vec_deque(
 963                         src_push_back,
 964                         src_pop_back,
 965                         src_push_front,
 966                         src_pop_front,
 967                     );
 968
 969                     for dst_push_back in 0..MAX {
 970                         for dst_push_front in 0..MAX {
 971                             for dst_pop_back in 0..(dst_push_back + dst_push_front) {
 972                                 for dst_pop_front
 973                                     in 0..(dst_push_back + dst_push_front - dst_pop_back)
 974                                 {
 975                                     let mut dst = construct_vec_deque(
 976                                         dst_push_back,
 977                                         dst_pop_back,
 978                                         dst_push_front,
 979                                         dst_pop_front,
 980                                     );
 981                                     let mut src = src.clone();
 982
 983                                     // Assert that appending `src` to `dst` gives the same order
 984                                     // of values as iterating over both in sequence.
 985                                     let correct = dst
 986                                         .iter()
 987                                         .chain(src.iter())
 988                                         .cloned()
 989                                         .collect::<Vec<usize>>();
 990                                     dst.append(&mut src);
 991                                     assert_eq!(dst, correct);
 992                                     assert!(src.is_empty());
 993                                 }
 994                             }
 995                         }
 996                     }
 997                 }
 998             }
 999         }
1000     }
1001 }
1002
1003 struct DropCounter<'a> {
1004     count: &'a mut u32,
1005 }
1006
1007 impl Drop for DropCounter<'_> {
1008     fn drop(&mut self) {
1009         *self.count += 1;
1010     }
1011 }
1012
1013 #[test]
1014 fn test_append_double_drop() {
1015     let (mut count_a, mut count_b) = (0, 0);
1016     {
1017         let mut a = VecDeque::new();
1018         let mut b = VecDeque::new();
1019         a.push_back(DropCounter { count: &mut count_a });
1020         b.push_back(DropCounter { count: &mut count_b });
1021
1022         a.append(&mut b);
1023     }
1024     assert_eq!(count_a, 1);
1025     assert_eq!(count_b, 1);
1026 }
1027
1028 #[test]
1029 fn test_retain() {
1030     let mut buf = VecDeque::new();
1031     buf.extend(1..5);
1032     buf.retain(|&x| x % 2 == 0);
1033     let v: Vec<_> = buf.into_iter().collect();
1034     assert_eq!(&v[..], &[2, 4]);
1035 }
1036
1037 #[test]
1038 fn test_extend_ref() {
1039     let mut v = VecDeque::new();
1040     v.push_back(1);
1041     v.extend(&[2, 3, 4]);
1042
1043     assert_eq!(v.len(), 4);
1044     assert_eq!(v[0], 1);
1045     assert_eq!(v[1], 2);
1046     assert_eq!(v[2], 3);
1047     assert_eq!(v[3], 4);
1048
1049     let mut w = VecDeque::new();
1050     w.push_back(5);
1051     w.push_back(6);
1052     v.extend(&w);
1053
1054     assert_eq!(v.len(), 6);
1055     assert_eq!(v[0], 1);
1056     assert_eq!(v[1], 2);
1057     assert_eq!(v[2], 3);
1058     assert_eq!(v[3], 4);
1059     assert_eq!(v[4], 5);
1060     assert_eq!(v[5], 6);
1061 }
1062
1063 #[test]
1064 fn test_contains() {
1065     let mut v = VecDeque::new();
1066     v.extend(&[2, 3, 4]);
1067
1068     assert!(v.contains(&3));
1069     assert!(!v.contains(&1));
1070
1071     v.clear();
1072
1073     assert!(!v.contains(&3));
1074 }
1075
1076 #[allow(dead_code)]
1077 fn assert_covariance() {
1078     fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
1079         d
1080     }
1081 }
1082
1083 #[test]
1084 fn test_is_empty() {
1085     let mut v = VecDeque::<i32>::new();
1086     assert!(v.is_empty());
1087     assert!(v.iter().is_empty());
1088     assert!(v.iter_mut().is_empty());
1089     v.extend(&[2, 3, 4]);
1090     assert!(!v.is_empty());
1091     assert!(!v.iter().is_empty());
1092     assert!(!v.iter_mut().is_empty());
1093     while let Some(_) = v.pop_front() {
1094         assert_eq!(v.is_empty(), v.len() == 0);
1095         assert_eq!(v.iter().is_empty(), v.iter().len() == 0);
1096         assert_eq!(v.iter_mut().is_empty(), v.iter_mut().len() == 0);
1097     }
1098     assert!(v.is_empty());
1099     assert!(v.iter().is_empty());
1100     assert!(v.iter_mut().is_empty());
1101     assert!(v.into_iter().is_empty());
1102 }
1103
1104 #[test]
1105 fn test_reserve_exact_2() {
1106     // This is all the same as test_reserve
1107
1108     let mut v = VecDeque::new();
1109
1110     v.reserve_exact(2);
1111     assert!(v.capacity() >= 2);
1112
1113     for i in 0..16 {
1114         v.push_back(i);
1115     }
1116
1117     assert!(v.capacity() >= 16);
1118     v.reserve_exact(16);
1119     assert!(v.capacity() >= 32);
1120
1121     v.push_back(16);
1122
1123     v.reserve_exact(16);
1124     assert!(v.capacity() >= 48)
1125 }
1126
1127 #[test]
1128 #[cfg(not(miri))]
1129 fn test_try_reserve() {
1130
1131     // These are the interesting cases:
1132     // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM)
1133     // * > isize::MAX should always fail
1134     //    * On 16/32-bit should CapacityOverflow
1135     //    * On 64-bit should OOM
1136     // * overflow may trigger when adding `len` to `cap` (in number of elements)
1137     // * overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes)
1138
1139     const MAX_CAP: usize = (isize::MAX as usize + 1) / 2 - 1;
1140     const MAX_USIZE: usize = usize::MAX;
1141
1142     // On 16/32-bit, we check that allocations don't exceed isize::MAX,
1143     // on 64-bit, we assume the OS will give an OOM for such a ridiculous size.
1144     // Any platform that succeeds for these requests is technically broken with
1145     // ptr::offset because LLVM is the worst.
1146     let guards_against_isize = size_of::<usize>() < 8;
1147
1148     {
1149         // Note: basic stuff is checked by test_reserve
1150         let mut empty_bytes: VecDeque<u8> = VecDeque::new();
1151
1152         // Check isize::MAX doesn't count as an overflow
1153         if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP) {
1154             panic!("isize::MAX shouldn't trigger an overflow!");
1155         }
1156         // Play it again, frank! (just to be sure)
1157         if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP) {
1158             panic!("isize::MAX shouldn't trigger an overflow!");
1159         }
1160
1161         if guards_against_isize {
1162             // Check isize::MAX + 1 does count as overflow
1163             if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP + 1) {
1164             } else { panic!("isize::MAX + 1 should trigger an overflow!") }
1165
1166             // Check usize::MAX does count as overflow
1167             if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_USIZE) {
1168             } else { panic!("usize::MAX should trigger an overflow!") }
1169         } else {
1170             // Check isize::MAX is an OOM
1171             // VecDeque starts with capacity 7, always adds 1 to the capacity
1172             // and also rounds the number to next power of 2 so this is the
1173             // furthest we can go without triggering CapacityOverflow
1174             if let Err(AllocErr) = empty_bytes.try_reserve(MAX_CAP) {
1175             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1176         }
1177     }
1178
1179
1180     {
1181         // Same basic idea, but with non-zero len
1182         let mut ten_bytes: VecDeque<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1183
1184         if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10) {
1185             panic!("isize::MAX shouldn't trigger an overflow!");
1186         }
1187         if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10) {
1188             panic!("isize::MAX shouldn't trigger an overflow!");
1189         }
1190         if guards_against_isize {
1191             if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 9) {
1192             } else { panic!("isize::MAX + 1 should trigger an overflow!"); }
1193         } else {
1194             if let Err(AllocErr) = ten_bytes.try_reserve(MAX_CAP - 9) {
1195             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1196         }
1197         // Should always overflow in the add-to-len
1198         if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_USIZE) {
1199         } else { panic!("usize::MAX should trigger an overflow!") }
1200     }
1201
1202
1203     {
1204         // Same basic idea, but with interesting type size
1205         let mut ten_u32s: VecDeque<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1206
1207         if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP/4 - 10) {
1208             panic!("isize::MAX shouldn't trigger an overflow!");
1209         }
1210         if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP/4 - 10) {
1211             panic!("isize::MAX shouldn't trigger an overflow!");
1212         }
1213         if guards_against_isize {
1214             if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP/4 - 9) {
1215             } else { panic!("isize::MAX + 1 should trigger an overflow!"); }
1216         } else {
1217             if let Err(AllocErr) = ten_u32s.try_reserve(MAX_CAP/4 - 9) {
1218             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1219         }
1220         // Should fail in the mul-by-size
1221         if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_USIZE - 20) {
1222         } else {
1223             panic!("usize::MAX should trigger an overflow!");
1224         }
1225     }
1226
1227 }
1228
1229 #[test]
1230 #[cfg(not(miri))]
1231 fn test_try_reserve_exact() {
1232
1233     // This is exactly the same as test_try_reserve with the method changed.
1234     // See that test for comments.
1235
1236     const MAX_CAP: usize = (isize::MAX as usize + 1) / 2 - 1;
1237     const MAX_USIZE: usize = usize::MAX;
1238
1239     let guards_against_isize = size_of::<usize>() < 8;
1240
1241     {
1242         let mut empty_bytes: VecDeque<u8> = VecDeque::new();
1243
1244         if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP) {
1245             panic!("isize::MAX shouldn't trigger an overflow!");
1246         }
1247         if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP) {
1248             panic!("isize::MAX shouldn't trigger an overflow!");
1249         }
1250
1251         if guards_against_isize {
1252             if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP + 1) {
1253             } else { panic!("isize::MAX + 1 should trigger an overflow!") }
1254
1255             if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_USIZE) {
1256             } else { panic!("usize::MAX should trigger an overflow!") }
1257         } else {
1258             // Check isize::MAX is an OOM
1259             // VecDeque starts with capacity 7, always adds 1 to the capacity
1260             // and also rounds the number to next power of 2 so this is the
1261             // furthest we can go without triggering CapacityOverflow
1262             if let Err(AllocErr) = empty_bytes.try_reserve_exact(MAX_CAP) {
1263             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1264         }
1265     }
1266
1267
1268     {
1269         let mut ten_bytes: VecDeque<u8> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1270
1271         if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10) {
1272             panic!("isize::MAX shouldn't trigger an overflow!");
1273         }
1274         if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 10) {
1275             panic!("isize::MAX shouldn't trigger an overflow!");
1276         }
1277         if guards_against_isize {
1278             if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_CAP - 9) {
1279             } else { panic!("isize::MAX + 1 should trigger an overflow!"); }
1280         } else {
1281             if let Err(AllocErr) = ten_bytes.try_reserve_exact(MAX_CAP - 9) {
1282             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1283         }
1284         if let Err(CapacityOverflow) = ten_bytes.try_reserve_exact(MAX_USIZE) {
1285         } else { panic!("usize::MAX should trigger an overflow!") }
1286     }
1287
1288
1289     {
1290         let mut ten_u32s: VecDeque<u32> = vec![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1291
1292         if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 10) {
1293             panic!("isize::MAX shouldn't trigger an overflow!");
1294         }
1295         if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 10) {
1296             panic!("isize::MAX shouldn't trigger an overflow!");
1297         }
1298         if guards_against_isize {
1299             if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 9) {
1300             } else { panic!("isize::MAX + 1 should trigger an overflow!"); }
1301         } else {
1302             if let Err(AllocErr) = ten_u32s.try_reserve_exact(MAX_CAP/4 - 9) {
1303             } else { panic!("isize::MAX + 1 should trigger an OOM!") }
1304         }
1305         if let Err(CapacityOverflow) = ten_u32s.try_reserve_exact(MAX_USIZE - 20) {
1306         } else { panic!("usize::MAX should trigger an overflow!") }
1307     }
1308
1309 }
1310
1311 #[test]
1312 fn test_rotate_nop() {
1313     let mut v: VecDeque<_> = (0..10).collect();
1314     assert_unchanged(&v);
1315
1316     v.rotate_left(0);
1317     assert_unchanged(&v);
1318
1319     v.rotate_left(10);
1320     assert_unchanged(&v);
1321
1322     v.rotate_right(0);
1323     assert_unchanged(&v);
1324
1325     v.rotate_right(10);
1326     assert_unchanged(&v);
1327
1328     v.rotate_left(3);
1329     v.rotate_right(3);
1330     assert_unchanged(&v);
1331
1332     v.rotate_right(3);
1333     v.rotate_left(3);
1334     assert_unchanged(&v);
1335
1336     v.rotate_left(6);
1337     v.rotate_right(6);
1338     assert_unchanged(&v);
1339
1340     v.rotate_right(6);
1341     v.rotate_left(6);
1342     assert_unchanged(&v);
1343
1344     v.rotate_left(3);
1345     v.rotate_left(7);
1346     assert_unchanged(&v);
1347
1348     v.rotate_right(4);
1349     v.rotate_right(6);
1350     assert_unchanged(&v);
1351
1352     v.rotate_left(1);
1353     v.rotate_left(2);
1354     v.rotate_left(3);
1355     v.rotate_left(4);
1356     assert_unchanged(&v);
1357
1358     v.rotate_right(1);
1359     v.rotate_right(2);
1360     v.rotate_right(3);
1361     v.rotate_right(4);
1362     assert_unchanged(&v);
1363
1364     fn assert_unchanged(v: &VecDeque<i32>) {
1365         assert_eq!(v, &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1366     }
1367 }
1368
1369 #[test]
1370 fn test_rotate_left_parts() {
1371     let mut v: VecDeque<_> = (1..=7).collect();
1372     v.rotate_left(2);
1373     assert_eq!(v.as_slices(), (&[3, 4, 5, 6, 7, 1][..], &[2][..]));
1374     v.rotate_left(2);
1375     assert_eq!(v.as_slices(), (&[5, 6, 7, 1][..], &[2, 3, 4][..]));
1376     v.rotate_left(2);
1377     assert_eq!(v.as_slices(), (&[7, 1][..], &[2, 3, 4, 5, 6][..]));
1378     v.rotate_left(2);
1379     assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7, 1][..], &[][..]));
1380     v.rotate_left(2);
1381     assert_eq!(v.as_slices(), (&[4, 5, 6, 7, 1, 2][..], &[3][..]));
1382     v.rotate_left(2);
1383     assert_eq!(v.as_slices(), (&[6, 7, 1, 2][..], &[3, 4, 5][..]));
1384     v.rotate_left(2);
1385     assert_eq!(v.as_slices(), (&[1, 2][..], &[3, 4, 5, 6, 7][..]));
1386 }
1387
1388 #[test]
1389 fn test_rotate_right_parts() {
1390     let mut v: VecDeque<_> = (1..=7).collect();
1391     v.rotate_right(2);
1392     assert_eq!(v.as_slices(), (&[6, 7][..], &[1, 2, 3, 4, 5][..]));
1393     v.rotate_right(2);
1394     assert_eq!(v.as_slices(), (&[4, 5, 6, 7][..], &[1, 2, 3][..]));
1395     v.rotate_right(2);
1396     assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7][..], &[1][..]));
1397     v.rotate_right(2);
1398     assert_eq!(v.as_slices(), (&[7, 1, 2, 3, 4, 5, 6][..], &[][..]));
1399     v.rotate_right(2);
1400     assert_eq!(v.as_slices(), (&[5, 6][..], &[7, 1, 2, 3, 4][..]));
1401     v.rotate_right(2);
1402     assert_eq!(v.as_slices(), (&[3, 4, 5, 6][..], &[7, 1, 2][..]));
1403     v.rotate_right(2);
1404     assert_eq!(v.as_slices(), (&[1, 2, 3, 4, 5, 6][..], &[7][..]));
1405 }
1406
1407 #[test]
1408 fn test_rotate_left_random() {
1409     let shifts = [
1410         6, 1, 0, 11, 12, 1, 11, 7, 9, 3, 6, 1,
1411         4, 0, 5, 1, 3, 1, 12, 8, 3, 1, 11, 11,
1412         9, 4, 12, 3, 12, 9, 11, 1, 7, 9, 7, 2,
1413     ];
1414     let n = 12;
1415     let mut v: VecDeque<_> = (0..n).collect();
1416     let mut total_shift = 0;
1417     for shift in shifts.iter().cloned() {
1418         v.rotate_left(shift);
1419         total_shift += shift;
1420         for i in 0..n {
1421             assert_eq!(v[i], (i + total_shift) % n);
1422         }
1423     }
1424 }
1425
1426 #[test]
1427 fn test_rotate_right_random() {
1428     let shifts = [
1429         6, 1, 0, 11, 12, 1, 11, 7, 9, 3, 6, 1,
1430         4, 0, 5, 1, 3, 1, 12, 8, 3, 1, 11, 11,
1431         9, 4, 12, 3, 12, 9, 11, 1, 7, 9, 7, 2,
1432     ];
1433     let n = 12;
1434     let mut v: VecDeque<_> = (0..n).collect();
1435     let mut total_shift = 0;
1436     for shift in shifts.iter().cloned() {
1437         v.rotate_right(shift);
1438         total_shift += shift;
1439         for i in 0..n {
1440             assert_eq!(v[(i + total_shift) % n], i);
1441         }
1442     }
1443 }
1444
1445 #[test]
1446 fn test_try_fold_empty() {
1447     assert_eq!(Some(0), VecDeque::<u32>::new().iter().try_fold(0, |_, _| None));
1448 }
1449
1450 #[test]
1451 fn test_try_fold_none() {
1452     let v: VecDeque<u32> = (0..12).collect();
1453     assert_eq!(None, v.into_iter().try_fold(0, |a, b|
1454         if b < 11 { Some(a + b) } else { None }));
1455 }
1456
1457 #[test]
1458 fn test_try_fold_ok() {
1459     let v: VecDeque<u32> = (0..12).collect();
1460     assert_eq!(Ok::<_, ()>(66), v.into_iter().try_fold(0, |a, b| Ok(a + b)));
1461 }
1462
1463 #[test]
1464 fn test_try_fold_unit() {
1465     let v: VecDeque<()> = std::iter::repeat(()).take(42).collect();
1466     assert_eq!(Some(()), v.into_iter().try_fold((), |(), ()| Some(())));
1467 }
1468
1469 #[test]
1470 fn test_try_fold_rotated() {
1471     let mut v: VecDeque<_> = (0..12).collect();
1472     for n in 0..10 {
1473         if n & 1 == 0 {
1474             v.rotate_left(n);
1475         } else {
1476             v.rotate_right(n);
1477         }
1478         assert_eq!(Ok::<_, ()>(66), v.iter().try_fold(0, |a, b| Ok(a + b)));
1479     }
1480 }