src/liballoc/tests/vec_deque.rs

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