src/liballoc/tests/vec_deque.rs

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