src/liballoc/tests/vec_deque.rs

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