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         assert_eq!(d.drain(..).collect::<Vec<_>>(), [8, 7, 6, 0, 1, 2, 3, 4]);
 469         assert!(d.is_empty());
 470     }
 471
 472     // partially used
 473     {
 474         let mut d: VecDeque<_> = VecDeque::new();
 475         for i in 0..5 {
 476             d.push_back(i);
 477         }
 478         for i in 6..9 {
 479             d.push_front(i);
 480         }
 481
 482         {
 483             let mut it = d.drain(..);
 484             assert_eq!(it.size_hint(), (8, Some(8)));
 485             assert_eq!(it.next(), Some(8));
 486             assert_eq!(it.size_hint(), (7, Some(7)));
 487             assert_eq!(it.next_back(), Some(4));
 488             assert_eq!(it.size_hint(), (6, Some(6)));
 489             assert_eq!(it.next(), Some(7));
 490             assert_eq!(it.size_hint(), (5, Some(5)));
 491         }
 492         assert!(d.is_empty());
 493     }
 494 }
 495
 496 #[test]
 497 fn test_from_iter() {
 498     let v = vec![1, 2, 3, 4, 5, 6, 7];
 499     let deq: VecDeque<_> = v.iter().cloned().collect();
 500     let u: Vec<_> = deq.iter().cloned().collect();
 501     assert_eq!(u, v);
 502
 503     let seq = (0..).step_by(2).take(256);
 504     let deq: VecDeque<_> = seq.collect();
 505     for (i, &x) in deq.iter().enumerate() {
 506         assert_eq!(2 * i, x);
 507     }
 508     assert_eq!(deq.len(), 256);
 509 }
 510
 511 #[test]
 512 fn test_clone() {
 513     let mut d = VecDeque::new();
 514     d.push_front(17);
 515     d.push_front(42);
 516     d.push_back(137);
 517     d.push_back(137);
 518     assert_eq!(d.len(), 4);
 519     let mut e = d.clone();
 520     assert_eq!(e.len(), 4);
 521     while !d.is_empty() {
 522         assert_eq!(d.pop_back(), e.pop_back());
 523     }
 524     assert_eq!(d.len(), 0);
 525     assert_eq!(e.len(), 0);
 526 }
 527
 528 #[test]
 529 fn test_eq() {
 530     let mut d = VecDeque::new();
 531     assert!(d == VecDeque::with_capacity(0));
 532     d.push_front(137);
 533     d.push_front(17);
 534     d.push_front(42);
 535     d.push_back(137);
 536     let mut e = VecDeque::with_capacity(0);
 537     e.push_back(42);
 538     e.push_back(17);
 539     e.push_back(137);
 540     e.push_back(137);
 541     assert!(&e == &d);
 542     e.pop_back();
 543     e.push_back(0);
 544     assert!(e != d);
 545     e.clear();
 546     assert!(e == VecDeque::new());
 547 }
 548
 549 #[test]
 550 fn test_partial_eq_array() {
 551     let d = VecDeque::<char>::new();
 552     assert!(d == []);
 553
 554     let mut d = VecDeque::new();
 555     d.push_front('a');
 556     assert!(d == ['a']);
 557
 558     let mut d = VecDeque::new();
 559     d.push_back('a');
 560     assert!(d == ['a']);
 561
 562     let mut d = VecDeque::new();
 563     d.push_back('a');
 564     d.push_back('b');
 565     assert!(d == ['a', 'b']);
 566 }
 567
 568 #[test]
 569 fn test_hash() {
 570     let mut x = VecDeque::new();
 571     let mut y = VecDeque::new();
 572
 573     x.push_back(1);
 574     x.push_back(2);
 575     x.push_back(3);
 576
 577     y.push_back(0);
 578     y.push_back(1);
 579     y.pop_front();
 580     y.push_back(2);
 581     y.push_back(3);
 582
 583     assert!(hash(&x) == hash(&y));
 584 }
 585
 586 #[test]
 587 fn test_hash_after_rotation() {
 588     // test that two deques hash equal even if elements are laid out differently
 589     let len = 28;
 590     let mut ring: VecDeque<i32> = (0..len as i32).collect();
 591     let orig = ring.clone();
 592     for _ in 0..ring.capacity() {
 593         // shift values 1 step to the right by pop, sub one, push
 594         ring.pop_front();
 595         for elt in &mut ring {
 596             *elt -= 1;
 597         }
 598         ring.push_back(len - 1);
 599         assert_eq!(hash(&orig), hash(&ring));
 600         assert_eq!(orig, ring);
 601         assert_eq!(ring, orig);
 602     }
 603 }
 604
 605 #[test]
 606 fn test_eq_after_rotation() {
 607     // test that two deques are equal even if elements are laid out differently
 608     let len = 28;
 609     let mut ring: VecDeque<i32> = (0..len as i32).collect();
 610     let mut shifted = ring.clone();
 611     for _ in 0..10 {
 612         // shift values 1 step to the right by pop, sub one, push
 613         ring.pop_front();
 614         for elt in &mut ring {
 615             *elt -= 1;
 616         }
 617         ring.push_back(len - 1);
 618     }
 619
 620     // try every shift
 621     for _ in 0..shifted.capacity() {
 622         shifted.pop_front();
 623         for elt in &mut shifted {
 624             *elt -= 1;
 625         }
 626         shifted.push_back(len - 1);
 627         assert_eq!(shifted, ring);
 628         assert_eq!(ring, shifted);
 629     }
 630 }
 631
 632 #[test]
 633 fn test_ord() {
 634     let x = VecDeque::new();
 635     let mut y = VecDeque::new();
 636     y.push_back(1);
 637     y.push_back(2);
 638     y.push_back(3);
 639     assert!(x < y);
 640     assert!(y > x);
 641     assert!(x <= x);
 642     assert!(x >= x);
 643 }
 644
 645 #[test]
 646 fn test_show() {
 647     let ringbuf: VecDeque<_> = (0..10).collect();
 648     assert_eq!(format!("{ringbuf:?}"), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
 649
 650     let ringbuf: VecDeque<_> = vec!["just", "one", "test", "more"].iter().cloned().collect();
 651     assert_eq!(format!("{ringbuf:?}"), "[\"just\", \"one\", \"test\", \"more\"]");
 652 }
 653
 654 #[test]
 655 fn test_drop() {
 656     static mut DROPS: i32 = 0;
 657     struct Elem;
 658     impl Drop for Elem {
 659         fn drop(&mut self) {
 660             unsafe {
 661                 DROPS += 1;
 662             }
 663         }
 664     }
 665
 666     let mut ring = VecDeque::new();
 667     ring.push_back(Elem);
 668     ring.push_front(Elem);
 669     ring.push_back(Elem);
 670     ring.push_front(Elem);
 671     drop(ring);
 672
 673     assert_eq!(unsafe { DROPS }, 4);
 674 }
 675
 676 #[test]
 677 fn test_drop_with_pop() {
 678     static mut DROPS: i32 = 0;
 679     struct Elem;
 680     impl Drop for Elem {
 681         fn drop(&mut self) {
 682             unsafe {
 683                 DROPS += 1;
 684             }
 685         }
 686     }
 687
 688     let mut ring = VecDeque::new();
 689     ring.push_back(Elem);
 690     ring.push_front(Elem);
 691     ring.push_back(Elem);
 692     ring.push_front(Elem);
 693
 694     drop(ring.pop_back());
 695     drop(ring.pop_front());
 696     assert_eq!(unsafe { DROPS }, 2);
 697
 698     drop(ring);
 699     assert_eq!(unsafe { DROPS }, 4);
 700 }
 701
 702 #[test]
 703 fn test_drop_clear() {
 704     static mut DROPS: i32 = 0;
 705     struct Elem;
 706     impl Drop for Elem {
 707         fn drop(&mut self) {
 708             unsafe {
 709                 DROPS += 1;
 710             }
 711         }
 712     }
 713
 714     let mut ring = VecDeque::new();
 715     ring.push_back(Elem);
 716     ring.push_front(Elem);
 717     ring.push_back(Elem);
 718     ring.push_front(Elem);
 719     ring.clear();
 720     assert_eq!(unsafe { DROPS }, 4);
 721
 722     drop(ring);
 723     assert_eq!(unsafe { DROPS }, 4);
 724 }
 725
 726 #[test]
 727 fn test_drop_panic() {
 728     static mut DROPS: i32 = 0;
 729
 730     struct D(bool);
 731
 732     impl Drop for D {
 733         fn drop(&mut self) {
 734             unsafe {
 735                 DROPS += 1;
 736             }
 737
 738             if self.0 {
 739                 panic!("panic in `drop`");
 740             }
 741         }
 742     }
 743
 744     let mut q = VecDeque::new();
 745     q.push_back(D(false));
 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_front(D(false));
 751     q.push_front(D(false));
 752     q.push_front(D(true));
 753
 754     catch_unwind(move || drop(q)).ok();
 755
 756     assert_eq!(unsafe { DROPS }, 8);
 757 }
 758
 759 #[test]
 760 fn test_reserve_grow() {
 761     // test growth path A
 762     // [T o o H] -> [T o o H . . . . ]
 763     let mut ring = VecDeque::with_capacity(4);
 764     for i in 0..3 {
 765         ring.push_back(i);
 766     }
 767     ring.reserve(7);
 768     for i in 0..3 {
 769         assert_eq!(ring.pop_front(), Some(i));
 770     }
 771
 772     // test growth path B
 773     // [H T o o] -> [. T o o H . . . ]
 774     let mut ring = VecDeque::with_capacity(4);
 775     for i in 0..1 {
 776         ring.push_back(i);
 777         assert_eq!(ring.pop_front(), Some(i));
 778     }
 779     for i in 0..3 {
 780         ring.push_back(i);
 781     }
 782     ring.reserve(7);
 783     for i in 0..3 {
 784         assert_eq!(ring.pop_front(), Some(i));
 785     }
 786
 787     // test growth path C
 788     // [o o H T] -> [o o H . . . . T ]
 789     let mut ring = VecDeque::with_capacity(4);
 790     for i in 0..3 {
 791         ring.push_back(i);
 792         assert_eq!(ring.pop_front(), Some(i));
 793     }
 794     for i in 0..3 {
 795         ring.push_back(i);
 796     }
 797     ring.reserve(7);
 798     for i in 0..3 {
 799         assert_eq!(ring.pop_front(), Some(i));
 800     }
 801 }
 802
 803 #[test]
 804 fn test_get() {
 805     let mut ring = VecDeque::new();
 806     ring.push_back(0);
 807     assert_eq!(ring.get(0), Some(&0));
 808     assert_eq!(ring.get(1), None);
 809
 810     ring.push_back(1);
 811     assert_eq!(ring.get(0), Some(&0));
 812     assert_eq!(ring.get(1), Some(&1));
 813     assert_eq!(ring.get(2), None);
 814
 815     ring.push_back(2);
 816     assert_eq!(ring.get(0), Some(&0));
 817     assert_eq!(ring.get(1), Some(&1));
 818     assert_eq!(ring.get(2), Some(&2));
 819     assert_eq!(ring.get(3), None);
 820
 821     assert_eq!(ring.pop_front(), Some(0));
 822     assert_eq!(ring.get(0), Some(&1));
 823     assert_eq!(ring.get(1), Some(&2));
 824     assert_eq!(ring.get(2), None);
 825
 826     assert_eq!(ring.pop_front(), Some(1));
 827     assert_eq!(ring.get(0), Some(&2));
 828     assert_eq!(ring.get(1), None);
 829
 830     assert_eq!(ring.pop_front(), Some(2));
 831     assert_eq!(ring.get(0), None);
 832     assert_eq!(ring.get(1), None);
 833 }
 834
 835 #[test]
 836 fn test_get_mut() {
 837     let mut ring = VecDeque::new();
 838     for i in 0..3 {
 839         ring.push_back(i);
 840     }
 841
 842     match ring.get_mut(1) {
 843         Some(x) => *x = -1,
 844         None => (),
 845     };
 846
 847     assert_eq!(ring.get_mut(0), Some(&mut 0));
 848     assert_eq!(ring.get_mut(1), Some(&mut -1));
 849     assert_eq!(ring.get_mut(2), Some(&mut 2));
 850     assert_eq!(ring.get_mut(3), None);
 851
 852     assert_eq!(ring.pop_front(), Some(0));
 853     assert_eq!(ring.get_mut(0), Some(&mut -1));
 854     assert_eq!(ring.get_mut(1), Some(&mut 2));
 855     assert_eq!(ring.get_mut(2), None);
 856 }
 857
 858 #[test]
 859 fn test_front() {
 860     let mut ring = VecDeque::new();
 861     ring.push_back(10);
 862     ring.push_back(20);
 863     assert_eq!(ring.front(), Some(&10));
 864     ring.pop_front();
 865     assert_eq!(ring.front(), Some(&20));
 866     ring.pop_front();
 867     assert_eq!(ring.front(), None);
 868 }
 869
 870 #[test]
 871 fn test_as_slices() {
 872     let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
 873     let cap = ring.capacity() as i32;
 874     let first = cap / 2;
 875     let last = cap - first;
 876     for i in 0..first {
 877         ring.push_back(i);
 878
 879         let (left, right) = ring.as_slices();
 880         let expected: Vec<_> = (0..=i).collect();
 881         assert_eq!(left, &expected[..]);
 882         assert_eq!(right, []);
 883     }
 884
 885     for j in -last..0 {
 886         ring.push_front(j);
 887         let (left, right) = ring.as_slices();
 888         let expected_left: Vec<_> = (-last..=j).rev().collect();
 889         let expected_right: Vec<_> = (0..first).collect();
 890         assert_eq!(left, &expected_left[..]);
 891         assert_eq!(right, &expected_right[..]);
 892     }
 893
 894     assert_eq!(ring.len() as i32, cap);
 895     assert_eq!(ring.capacity() as i32, cap);
 896 }
 897
 898 #[test]
 899 fn test_as_mut_slices() {
 900     let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
 901     let cap = ring.capacity() as i32;
 902     let first = cap / 2;
 903     let last = cap - first;
 904     for i in 0..first {
 905         ring.push_back(i);
 906
 907         let (left, right) = ring.as_mut_slices();
 908         let expected: Vec<_> = (0..=i).collect();
 909         assert_eq!(left, &expected[..]);
 910         assert_eq!(right, []);
 911     }
 912
 913     for j in -last..0 {
 914         ring.push_front(j);
 915         let (left, right) = ring.as_mut_slices();
 916         let expected_left: Vec<_> = (-last..=j).rev().collect();
 917         let expected_right: Vec<_> = (0..first).collect();
 918         assert_eq!(left, &expected_left[..]);
 919         assert_eq!(right, &expected_right[..]);
 920     }
 921
 922     assert_eq!(ring.len() as i32, cap);
 923     assert_eq!(ring.capacity() as i32, cap);
 924 }
 925
 926 #[test]
 927 fn test_append() {
 928     let mut a: VecDeque<_> = [1, 2, 3].into_iter().collect();
 929     let mut b: VecDeque<_> = [4, 5, 6].into_iter().collect();
 930
 931     // normal append
 932     a.append(&mut b);
 933     assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
 934     assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
 935
 936     // append nothing to something
 937     a.append(&mut b);
 938     assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
 939     assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
 940
 941     // append something to nothing
 942     b.append(&mut a);
 943     assert_eq!(b.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
 944     assert_eq!(a.iter().cloned().collect::<Vec<_>>(), []);
 945 }
 946
 947 #[test]
 948 fn test_append_permutations() {
 949     fn construct_vec_deque(
 950         push_back: usize,
 951         pop_back: usize,
 952         push_front: usize,
 953         pop_front: usize,
 954     ) -> VecDeque<usize> {
 955         let mut out = VecDeque::new();
 956         for a in 0..push_back {
 957             out.push_back(a);
 958         }
 959         for b in 0..push_front {
 960             out.push_front(push_back + b);
 961         }
 962         for _ in 0..pop_back {
 963             out.pop_back();
 964         }
 965         for _ in 0..pop_front {
 966             out.pop_front();
 967         }
 968         out
 969     }
 970
 971     // Miri is too slow
 972     let max = if cfg!(miri) { 3 } else { 5 };
 973
 974     // Many different permutations of both the `VecDeque` getting appended to
 975     // and the one getting appended are generated to check `append`.
 976     // This ensures all 6 code paths of `append` are tested.
 977     for src_push_back in 0..max {
 978         for src_push_front in 0..max {
 979             // doesn't pop more values than are pushed
 980             for src_pop_back in 0..(src_push_back + src_push_front) {
 981                 for src_pop_front in 0..(src_push_back + src_push_front - src_pop_back) {
 982                     let src = construct_vec_deque(
 983                         src_push_back,
 984                         src_pop_back,
 985                         src_push_front,
 986                         src_pop_front,
 987                     );
 988
 989                     for dst_push_back in 0..max {
 990                         for dst_push_front in 0..max {
 991                             for dst_pop_back in 0..(dst_push_back + dst_push_front) {
 992                                 for dst_pop_front in
 993                                     0..(dst_push_back + dst_push_front - dst_pop_back)
 994                                 {
 995                                     let mut dst = construct_vec_deque(
 996                                         dst_push_back,
 997                                         dst_pop_back,
 998                                         dst_push_front,
 999                                         dst_pop_front,
1000                                     );
1001                                     let mut src = src.clone();
1002
1003                                     // Assert that appending `src` to `dst` gives the same order
1004                                     // of values as iterating over both in sequence.
1005                                     let correct = dst
1006                                         .iter()
1007                                         .chain(src.iter())
1008                                         .cloned()
1009                                         .collect::<Vec<usize>>();
1010                                     dst.append(&mut src);
1011                                     assert_eq!(dst, correct);
1012                                     assert!(src.is_empty());
1013                                 }
1014                             }
1015                         }
1016                     }
1017                 }
1018             }
1019         }
1020     }
1021 }
1022
1023 struct DropCounter<'a> {
1024     count: &'a mut u32,
1025 }
1026
1027 impl Drop for DropCounter<'_> {
1028     fn drop(&mut self) {
1029         *self.count += 1;
1030     }
1031 }
1032
1033 #[test]
1034 fn test_append_double_drop() {
1035     let (mut count_a, mut count_b) = (0, 0);
1036     {
1037         let mut a = VecDeque::new();
1038         let mut b = VecDeque::new();
1039         a.push_back(DropCounter { count: &mut count_a });
1040         b.push_back(DropCounter { count: &mut count_b });
1041
1042         a.append(&mut b);
1043     }
1044     assert_eq!(count_a, 1);
1045     assert_eq!(count_b, 1);
1046 }
1047
1048 #[test]
1049 fn test_retain() {
1050     let mut buf = VecDeque::new();
1051     buf.extend(1..5);
1052     buf.retain(|&x| x % 2 == 0);
1053     let v: Vec<_> = buf.into_iter().collect();
1054     assert_eq!(&v[..], &[2, 4]);
1055 }
1056
1057 #[test]
1058 fn test_extend_ref() {
1059     let mut v = VecDeque::new();
1060     v.push_back(1);
1061     v.extend(&[2, 3, 4]);
1062
1063     assert_eq!(v.len(), 4);
1064     assert_eq!(v[0], 1);
1065     assert_eq!(v[1], 2);
1066     assert_eq!(v[2], 3);
1067     assert_eq!(v[3], 4);
1068
1069     let mut w = VecDeque::new();
1070     w.push_back(5);
1071     w.push_back(6);
1072     v.extend(&w);
1073
1074     assert_eq!(v.len(), 6);
1075     assert_eq!(v[0], 1);
1076     assert_eq!(v[1], 2);
1077     assert_eq!(v[2], 3);
1078     assert_eq!(v[3], 4);
1079     assert_eq!(v[4], 5);
1080     assert_eq!(v[5], 6);
1081 }
1082
1083 #[test]
1084 fn test_contains() {
1085     let mut v = VecDeque::new();
1086     v.extend(&[2, 3, 4]);
1087
1088     assert!(v.contains(&3));
1089     assert!(!v.contains(&1));
1090
1091     v.clear();
1092
1093     assert!(!v.contains(&3));
1094 }
1095
1096 #[allow(dead_code)]
1097 fn assert_covariance() {
1098     fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
1099         d
1100     }
1101 }
1102
1103 #[test]
1104 fn test_is_empty() {
1105     let mut v = VecDeque::<i32>::new();
1106     assert!(v.is_empty());
1107     assert!(v.iter().is_empty());
1108     assert!(v.iter_mut().is_empty());
1109     v.extend(&[2, 3, 4]);
1110     assert!(!v.is_empty());
1111     assert!(!v.iter().is_empty());
1112     assert!(!v.iter_mut().is_empty());
1113     while let Some(_) = v.pop_front() {
1114         assert_eq!(v.is_empty(), v.len() == 0);
1115         assert_eq!(v.iter().is_empty(), v.iter().len() == 0);
1116         assert_eq!(v.iter_mut().is_empty(), v.iter_mut().len() == 0);
1117     }
1118     assert!(v.is_empty());
1119     assert!(v.iter().is_empty());
1120     assert!(v.iter_mut().is_empty());
1121     assert!(v.into_iter().is_empty());
1122 }
1123
1124 #[test]
1125 fn test_reserve_exact_2() {
1126     // This is all the same as test_reserve
1127
1128     let mut v = VecDeque::new();
1129
1130     v.reserve_exact(2);
1131     assert!(v.capacity() >= 2);
1132
1133     for i in 0..16 {
1134         v.push_back(i);
1135     }
1136
1137     assert!(v.capacity() >= 16);
1138     v.reserve_exact(16);
1139     assert!(v.capacity() >= 32);
1140
1141     v.push_back(16);
1142
1143     v.reserve_exact(16);
1144     assert!(v.capacity() >= 33)
1145 }
1146
1147 #[test]
1148 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1149 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1150 fn test_try_reserve() {
1151     // These are the interesting cases:
1152     // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM)
1153     // * > isize::MAX should always fail
1154     //    * On 16/32-bit should CapacityOverflow
1155     //    * On 64-bit should OOM
1156     // * overflow may trigger when adding `len` to `cap` (in number of elements)
1157     // * overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes)
1158
1159     const MAX_CAP: usize = isize::MAX as usize;
1160     const MAX_USIZE: usize = usize::MAX;
1161
1162     {
1163         // Note: basic stuff is checked by test_reserve
1164         let mut empty_bytes: VecDeque<u8> = VecDeque::new();
1165
1166         // Check isize::MAX doesn't count as an overflow
1167         if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) {
1168             panic!("isize::MAX shouldn't trigger an overflow!");
1169         }
1170         // Play it again, frank! (just to be sure)
1171         if let Err(CapacityOverflow) = empty_bytes.try_reserve(MAX_CAP).map_err(|e| e.kind()) {
1172             panic!("isize::MAX shouldn't trigger an overflow!");
1173         }
1174
1175         // Check isize::MAX + 1 does count as overflow
1176         assert_matches!(
1177             empty_bytes.try_reserve(MAX_CAP + 1).map_err(|e| e.kind()),
1178             Err(CapacityOverflow),
1179             "isize::MAX + 1 should trigger an overflow!"
1180         );
1181
1182         // Check usize::MAX does count as overflow
1183         assert_matches!(
1184             empty_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1185             Err(CapacityOverflow),
1186             "usize::MAX should trigger an overflow!"
1187         );
1188     }
1189
1190     {
1191         // Same basic idea, but with non-zero len
1192         let mut ten_bytes: VecDeque<u8> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1193
1194         if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) {
1195             panic!("isize::MAX shouldn't trigger an overflow!");
1196         }
1197         if let Err(CapacityOverflow) = ten_bytes.try_reserve(MAX_CAP - 10).map_err(|e| e.kind()) {
1198             panic!("isize::MAX shouldn't trigger an overflow!");
1199         }
1200
1201         assert_matches!(
1202             ten_bytes.try_reserve(MAX_CAP - 9).map_err(|e| e.kind()),
1203             Err(CapacityOverflow),
1204             "isize::MAX + 1 should trigger an overflow!"
1205         );
1206
1207         // Should always overflow in the add-to-len
1208         assert_matches!(
1209             ten_bytes.try_reserve(MAX_USIZE).map_err(|e| e.kind()),
1210             Err(CapacityOverflow),
1211             "usize::MAX should trigger an overflow!"
1212         );
1213     }
1214
1215     {
1216         // Same basic idea, but with interesting type size
1217         let mut ten_u32s: VecDeque<u32> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1218
1219         if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1220         {
1221             panic!("isize::MAX shouldn't trigger an overflow!");
1222         }
1223         if let Err(CapacityOverflow) = ten_u32s.try_reserve(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1224         {
1225             panic!("isize::MAX shouldn't trigger an overflow!");
1226         }
1227
1228         assert_matches!(
1229             ten_u32s.try_reserve(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1230             Err(CapacityOverflow),
1231             "isize::MAX + 1 should trigger an overflow!"
1232         );
1233
1234         // Should fail in the mul-by-size
1235         assert_matches!(
1236             ten_u32s.try_reserve(MAX_USIZE - 20).map_err(|e| e.kind()),
1237             Err(CapacityOverflow),
1238             "usize::MAX should trigger an overflow!"
1239         );
1240     }
1241 }
1242
1243 #[test]
1244 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1245 #[cfg_attr(target_os = "android", ignore)] // Android used in CI has a broken dlmalloc
1246 fn test_try_reserve_exact() {
1247     // This is exactly the same as test_try_reserve with the method changed.
1248     // See that test for comments.
1249
1250     const MAX_CAP: usize = isize::MAX as usize;
1251     const MAX_USIZE: usize = usize::MAX;
1252
1253     {
1254         let mut empty_bytes: VecDeque<u8> = VecDeque::new();
1255
1256         if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1257         {
1258             panic!("isize::MAX shouldn't trigger an overflow!");
1259         }
1260         if let Err(CapacityOverflow) = empty_bytes.try_reserve_exact(MAX_CAP).map_err(|e| e.kind())
1261         {
1262             panic!("isize::MAX shouldn't trigger an overflow!");
1263         }
1264
1265         assert_matches!(
1266             empty_bytes.try_reserve_exact(MAX_CAP + 1).map_err(|e| e.kind()),
1267             Err(CapacityOverflow),
1268             "isize::MAX + 1 should trigger an overflow!"
1269         );
1270
1271         assert_matches!(
1272             empty_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1273             Err(CapacityOverflow),
1274             "usize::MAX should trigger an overflow!"
1275         );
1276     }
1277
1278     {
1279         let mut ten_bytes: VecDeque<u8> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1280
1281         if let Err(CapacityOverflow) =
1282             ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1283         {
1284             panic!("isize::MAX shouldn't trigger an overflow!");
1285         }
1286         if let Err(CapacityOverflow) =
1287             ten_bytes.try_reserve_exact(MAX_CAP - 10).map_err(|e| e.kind())
1288         {
1289             panic!("isize::MAX shouldn't trigger an overflow!");
1290         }
1291
1292         assert_matches!(
1293             ten_bytes.try_reserve_exact(MAX_CAP - 9).map_err(|e| e.kind()),
1294             Err(CapacityOverflow),
1295             "isize::MAX + 1 should trigger an overflow!"
1296         );
1297
1298         assert_matches!(
1299             ten_bytes.try_reserve_exact(MAX_USIZE).map_err(|e| e.kind()),
1300             Err(CapacityOverflow),
1301             "usize::MAX should trigger an overflow!"
1302         );
1303     }
1304
1305     {
1306         let mut ten_u32s: VecDeque<u32> = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1307
1308         if let Err(CapacityOverflow) =
1309             ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1310         {
1311             panic!("isize::MAX shouldn't trigger an overflow!");
1312         }
1313         if let Err(CapacityOverflow) =
1314             ten_u32s.try_reserve_exact(MAX_CAP / 4 - 10).map_err(|e| e.kind())
1315         {
1316             panic!("isize::MAX shouldn't trigger an overflow!");
1317         }
1318
1319         assert_matches!(
1320             ten_u32s.try_reserve_exact(MAX_CAP / 4 - 9).map_err(|e| e.kind()),
1321             Err(CapacityOverflow),
1322             "isize::MAX + 1 should trigger an overflow!"
1323         );
1324
1325         assert_matches!(
1326             ten_u32s.try_reserve_exact(MAX_USIZE - 20).map_err(|e| e.kind()),
1327             Err(CapacityOverflow),
1328             "usize::MAX should trigger an overflow!"
1329         );
1330     }
1331 }
1332
1333 #[test]
1334 fn test_rotate_nop() {
1335     let mut v: VecDeque<_> = (0..10).collect();
1336     assert_unchanged(&v);
1337
1338     v.rotate_left(0);
1339     assert_unchanged(&v);
1340
1341     v.rotate_left(10);
1342     assert_unchanged(&v);
1343
1344     v.rotate_right(0);
1345     assert_unchanged(&v);
1346
1347     v.rotate_right(10);
1348     assert_unchanged(&v);
1349
1350     v.rotate_left(3);
1351     v.rotate_right(3);
1352     assert_unchanged(&v);
1353
1354     v.rotate_right(3);
1355     v.rotate_left(3);
1356     assert_unchanged(&v);
1357
1358     v.rotate_left(6);
1359     v.rotate_right(6);
1360     assert_unchanged(&v);
1361
1362     v.rotate_right(6);
1363     v.rotate_left(6);
1364     assert_unchanged(&v);
1365
1366     v.rotate_left(3);
1367     v.rotate_left(7);
1368     assert_unchanged(&v);
1369
1370     v.rotate_right(4);
1371     v.rotate_right(6);
1372     assert_unchanged(&v);
1373
1374     v.rotate_left(1);
1375     v.rotate_left(2);
1376     v.rotate_left(3);
1377     v.rotate_left(4);
1378     assert_unchanged(&v);
1379
1380     v.rotate_right(1);
1381     v.rotate_right(2);
1382     v.rotate_right(3);
1383     v.rotate_right(4);
1384     assert_unchanged(&v);
1385
1386     fn assert_unchanged(v: &VecDeque<i32>) {
1387         assert_eq!(v, &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1388     }
1389 }
1390
1391 #[test]
1392 fn test_rotate_left_parts() {
1393     let mut v: VecDeque<_> = VecDeque::with_capacity(8);
1394     v.extend(1..=7);
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<_> = VecDeque::with_capacity(8);
1414     v.extend(1..=7);
1415     v.rotate_right(2);
1416     assert_eq!(v.as_slices(), (&[6, 7][..], &[1, 2, 3, 4, 5][..]));
1417     v.rotate_right(2);
1418     assert_eq!(v.as_slices(), (&[4, 5, 6, 7][..], &[1, 2, 3][..]));
1419     v.rotate_right(2);
1420     assert_eq!(v.as_slices(), (&[2, 3, 4, 5, 6, 7][..], &[1][..]));
1421     v.rotate_right(2);
1422     assert_eq!(v.as_slices(), (&[7, 1, 2, 3, 4, 5, 6][..], &[][..]));
1423     v.rotate_right(2);
1424     assert_eq!(v.as_slices(), (&[5, 6][..], &[7, 1, 2, 3, 4][..]));
1425     v.rotate_right(2);
1426     assert_eq!(v.as_slices(), (&[3, 4, 5, 6][..], &[7, 1, 2][..]));
1427     v.rotate_right(2);
1428     assert_eq!(v.as_slices(), (&[1, 2, 3, 4, 5, 6][..], &[7][..]));
1429 }
1430
1431 #[test]
1432 fn test_rotate_left_random() {
1433     let shifts = [
1434         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,
1435         12, 9, 11, 1, 7, 9, 7, 2,
1436     ];
1437     let n = 12;
1438     let mut v: VecDeque<_> = (0..n).collect();
1439     let mut total_shift = 0;
1440     for shift in shifts.iter().cloned() {
1441         v.rotate_left(shift);
1442         total_shift += shift;
1443         for i in 0..n {
1444             assert_eq!(v[i], (i + total_shift) % n);
1445         }
1446     }
1447 }
1448
1449 #[test]
1450 fn test_rotate_right_random() {
1451     let shifts = [
1452         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,
1453         12, 9, 11, 1, 7, 9, 7, 2,
1454     ];
1455     let n = 12;
1456     let mut v: VecDeque<_> = (0..n).collect();
1457     let mut total_shift = 0;
1458     for shift in shifts.iter().cloned() {
1459         v.rotate_right(shift);
1460         total_shift += shift;
1461         for i in 0..n {
1462             assert_eq!(v[(i + total_shift) % n], i);
1463         }
1464     }
1465 }
1466
1467 #[test]
1468 fn test_try_fold_empty() {
1469     assert_eq!(Some(0), VecDeque::<u32>::new().iter().try_fold(0, |_, _| None));
1470 }
1471
1472 #[test]
1473 fn test_try_fold_none() {
1474     let v: VecDeque<u32> = (0..12).collect();
1475     assert_eq!(None, v.into_iter().try_fold(0, |a, b| if b < 11 { Some(a + b) } else { None }));
1476 }
1477
1478 #[test]
1479 fn test_try_fold_ok() {
1480     let v: VecDeque<u32> = (0..12).collect();
1481     assert_eq!(Ok::<_, ()>(66), v.into_iter().try_fold(0, |a, b| Ok(a + b)));
1482 }
1483
1484 #[test]
1485 fn test_try_fold_unit() {
1486     let v: VecDeque<()> = std::iter::repeat(()).take(42).collect();
1487     assert_eq!(Some(()), v.into_iter().try_fold((), |(), ()| Some(())));
1488 }
1489
1490 #[test]
1491 fn test_try_fold_unit_none() {
1492     let v: std::collections::VecDeque<()> = [(); 10].iter().cloned().collect();
1493     let mut iter = v.into_iter();
1494     assert!(iter.try_fold((), |_, _| None).is_none());
1495     assert_eq!(iter.len(), 9);
1496 }
1497
1498 #[test]
1499 fn test_try_fold_rotated() {
1500     let mut v: VecDeque<_> = (0..12).collect();
1501     for n in 0..10 {
1502         if n & 1 == 0 {
1503             v.rotate_left(n);
1504         } else {
1505             v.rotate_right(n);
1506         }
1507         assert_eq!(Ok::<_, ()>(66), v.iter().try_fold(0, |a, b| Ok(a + b)));
1508     }
1509 }
1510
1511 #[test]
1512 fn test_try_fold_moves_iter() {
1513     let v: VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect();
1514     let mut iter = v.into_iter();
1515     assert_eq!(iter.try_fold(0_i8, |acc, &x| acc.checked_add(x)), None);
1516     assert_eq!(iter.next(), Some(&60));
1517 }
1518
1519 #[test]
1520 fn test_try_fold_exhaust_wrap() {
1521     let mut v = VecDeque::with_capacity(7);
1522     v.push_back(1);
1523     v.push_back(1);
1524     v.push_back(1);
1525     v.pop_front();
1526     v.pop_front();
1527     let mut iter = v.iter();
1528     let _ = iter.try_fold(0, |_, _| Some(1));
1529     assert!(iter.is_empty());
1530 }
1531
1532 #[test]
1533 fn test_try_fold_wraparound() {
1534     let mut v = VecDeque::with_capacity(8);
1535     v.push_back(7);
1536     v.push_back(8);
1537     v.push_back(9);
1538     v.push_front(2);
1539     v.push_front(1);
1540     let mut iter = v.iter();
1541     let _ = iter.find(|&&x| x == 2);
1542     assert_eq!(Some(&7), iter.next());
1543 }
1544
1545 #[test]
1546 fn test_try_rfold_rotated() {
1547     let mut v: VecDeque<_> = (0..12).collect();
1548     for n in 0..10 {
1549         if n & 1 == 0 {
1550             v.rotate_left(n);
1551         } else {
1552             v.rotate_right(n);
1553         }
1554         assert_eq!(Ok::<_, ()>(66), v.iter().try_rfold(0, |a, b| Ok(a + b)));
1555     }
1556 }
1557
1558 #[test]
1559 fn test_try_rfold_moves_iter() {
1560     let v: VecDeque<_> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect();
1561     let mut iter = v.into_iter();
1562     assert_eq!(iter.try_rfold(0_i8, |acc, &x| acc.checked_add(x)), None);
1563     assert_eq!(iter.next_back(), Some(&70));
1564 }
1565
1566 #[test]
1567 fn truncate_leak() {
1568     static mut DROPS: i32 = 0;
1569
1570     struct D(bool);
1571
1572     impl Drop for D {
1573         fn drop(&mut self) {
1574             unsafe {
1575                 DROPS += 1;
1576             }
1577
1578             if self.0 {
1579                 panic!("panic in `drop`");
1580             }
1581         }
1582     }
1583
1584     let mut q = VecDeque::new();
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_back(D(false));
1590     q.push_front(D(true));
1591     q.push_front(D(false));
1592     q.push_front(D(false));
1593
1594     catch_unwind(AssertUnwindSafe(|| q.truncate(1))).ok();
1595
1596     assert_eq!(unsafe { DROPS }, 7);
1597 }
1598
1599 #[test]
1600 fn test_drain_leak() {
1601     static mut DROPS: i32 = 0;
1602
1603     #[derive(Debug, PartialEq)]
1604     struct D(u32, bool);
1605
1606     impl Drop for D {
1607         fn drop(&mut self) {
1608             unsafe {
1609                 DROPS += 1;
1610             }
1611
1612             if self.1 {
1613                 panic!("panic in `drop`");
1614             }
1615         }
1616     }
1617
1618     let mut v = VecDeque::new();
1619     v.push_back(D(4, false));
1620     v.push_back(D(5, false));
1621     v.push_back(D(6, false));
1622     v.push_front(D(3, false));
1623     v.push_front(D(2, true));
1624     v.push_front(D(1, false));
1625     v.push_front(D(0, false));
1626
1627     catch_unwind(AssertUnwindSafe(|| {
1628         v.drain(1..=4);
1629     }))
1630     .ok();
1631
1632     assert_eq!(unsafe { DROPS }, 4);
1633     assert_eq!(v.len(), 3);
1634     drop(v);
1635     assert_eq!(unsafe { DROPS }, 7);
1636 }
1637
1638 #[test]
1639 fn test_binary_search() {
1640     // Contiguous (front only) search:
1641     let deque: VecDeque<_> = vec![1, 2, 3, 5, 6].into();
1642     assert!(deque.as_slices().1.is_empty());
1643     assert_eq!(deque.binary_search(&3), Ok(2));
1644     assert_eq!(deque.binary_search(&4), Err(3));
1645
1646     // Split search (both front & back non-empty):
1647     let mut deque: VecDeque<_> = vec![5, 6].into();
1648     deque.push_front(3);
1649     deque.push_front(2);
1650     deque.push_front(1);
1651     deque.push_back(10);
1652     assert!(!deque.as_slices().0.is_empty());
1653     assert!(!deque.as_slices().1.is_empty());
1654     assert_eq!(deque.binary_search(&0), Err(0));
1655     assert_eq!(deque.binary_search(&1), Ok(0));
1656     assert_eq!(deque.binary_search(&5), Ok(3));
1657     assert_eq!(deque.binary_search(&7), Err(5));
1658     assert_eq!(deque.binary_search(&20), Err(6));
1659 }
1660
1661 #[test]
1662 fn test_binary_search_by() {
1663     let deque: VecDeque<_> = vec![(1,), (2,), (3,), (5,), (6,)].into();
1664
1665     assert_eq!(deque.binary_search_by(|&(v,)| v.cmp(&3)), Ok(2));
1666     assert_eq!(deque.binary_search_by(|&(v,)| v.cmp(&4)), Err(3));
1667 }
1668
1669 #[test]
1670 fn test_binary_search_by_key() {
1671     let deque: VecDeque<_> = vec![(1,), (2,), (3,), (5,), (6,)].into();
1672
1673     assert_eq!(deque.binary_search_by_key(&3, |&(v,)| v), Ok(2));
1674     assert_eq!(deque.binary_search_by_key(&4, |&(v,)| v), Err(3));
1675 }
1676
1677 #[test]
1678 fn test_partition_point() {
1679     // Contiguous (front only) search:
1680     let deque: VecDeque<_> = vec![1, 2, 3, 5, 6].into();
1681     assert!(deque.as_slices().1.is_empty());
1682     assert_eq!(deque.partition_point(|&v| v <= 3), 3);
1683
1684     // Split search (both front & back non-empty):
1685     let mut deque: VecDeque<_> = vec![5, 6].into();
1686     deque.push_front(3);
1687     deque.push_front(2);
1688     deque.push_front(1);
1689     deque.push_back(10);
1690     assert!(!deque.as_slices().0.is_empty());
1691     assert!(!deque.as_slices().1.is_empty());
1692     assert_eq!(deque.partition_point(|&v| v <= 5), 4);
1693 }
1694
1695 #[test]
1696 fn test_zero_sized_push() {
1697     const N: usize = 8;
1698
1699     // Zero sized type
1700     struct Zst;
1701
1702     // Test that for all possible sequences of push_front / push_back,
1703     // we end up with a deque of the correct size
1704
1705     for len in 0..N {
1706         let mut tester = VecDeque::with_capacity(len);
1707         assert_eq!(tester.len(), 0);
1708         assert!(tester.capacity() >= len);
1709         for case in 0..(1 << len) {
1710             assert_eq!(tester.len(), 0);
1711             for bit in 0..len {
1712                 if case & (1 << bit) != 0 {
1713                     tester.push_front(Zst);
1714                 } else {
1715                     tester.push_back(Zst);
1716                 }
1717             }
1718             assert_eq!(tester.len(), len);
1719             assert_eq!(tester.iter().count(), len);
1720             tester.clear();
1721         }
1722     }
1723 }
1724
1725 #[test]
1726 fn test_from_zero_sized_vec() {
1727     let v = vec![(); 100];
1728     let queue = VecDeque::from(v);
1729     assert_eq!(queue.len(), 100);
1730 }
1731
1732 #[test]
1733 fn test_resize_keeps_reserved_space_from_item() {
1734     let v = Vec::<i32>::with_capacity(1234);
1735     let mut d = VecDeque::new();
1736     d.resize(1, v);
1737     assert_eq!(d[0].capacity(), 1234);
1738 }
1739
1740 #[test]
1741 fn test_collect_from_into_iter_keeps_allocation() {
1742     let mut v = Vec::with_capacity(13);
1743     v.extend(0..7);
1744     check(v.as_ptr(), v.last().unwrap(), v.into_iter());
1745
1746     let mut v = VecDeque::with_capacity(13);
1747     v.extend(0..7);
1748     check(&v[0], &v[v.len() - 1], v.into_iter());
1749
1750     fn check(buf: *const i32, last: *const i32, mut it: impl Iterator<Item = i32>) {
1751         assert_eq!(it.next(), Some(0));
1752         assert_eq!(it.next(), Some(1));
1753
1754         let mut v: VecDeque<i32> = it.collect();
1755         assert_eq!(v.capacity(), 13);
1756         assert_eq!(v.as_slices().0.as_ptr(), buf.wrapping_add(2));
1757         assert_eq!(&v[v.len() - 1] as *const _, last);
1758
1759         assert_eq!(v.as_slices(), ([2, 3, 4, 5, 6].as_slice(), [].as_slice()));
1760         v.push_front(7);
1761         assert_eq!(v.as_slices(), ([7, 2, 3, 4, 5, 6].as_slice(), [].as_slice()));
1762         v.push_front(8);
1763         assert_eq!(v.as_slices(), ([8, 7, 2, 3, 4, 5, 6].as_slice(), [].as_slice()));
1764
1765         // Now that we've adding thing in place of the two that we removed from
1766         // the front of the iterator, we're back to matching the buffer pointer.
1767         assert_eq!(v.as_slices().0.as_ptr(), buf);
1768         assert_eq!(&v[v.len() - 1] as *const _, last);
1769
1770         v.push_front(9);
1771         assert_eq!(v.as_slices(), ([9].as_slice(), [8, 7, 2, 3, 4, 5, 6].as_slice()));
1772         assert_eq!(v.capacity(), 13);
1773     }
1774 }