library/alloc/tests/vec_deque.rs

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