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