src/libcollections/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
  15 use self::Taggy::*;
  16 use self::Taggypar::*;
  17
  18 #[test]
  19 fn test_simple() {
  20     let mut d = VecDeque::new();
  21     assert_eq!(d.len(), 0);
  22     d.push_front(17);
  23     d.push_front(42);
  24     d.push_back(137);
  25     assert_eq!(d.len(), 3);
  26     d.push_back(137);
  27     assert_eq!(d.len(), 4);
  28     assert_eq!(*d.front().unwrap(), 42);
  29     assert_eq!(*d.back().unwrap(), 137);
  30     let mut i = d.pop_front();
  31     assert_eq!(i, Some(42));
  32     i = d.pop_back();
  33     assert_eq!(i, Some(137));
  34     i = d.pop_back();
  35     assert_eq!(i, Some(137));
  36     i = d.pop_back();
  37     assert_eq!(i, Some(17));
  38     assert_eq!(d.len(), 0);
  39     d.push_back(3);
  40     assert_eq!(d.len(), 1);
  41     d.push_front(2);
  42     assert_eq!(d.len(), 2);
  43     d.push_back(4);
  44     assert_eq!(d.len(), 3);
  45     d.push_front(1);
  46     assert_eq!(d.len(), 4);
  47     assert_eq!(d[0], 1);
  48     assert_eq!(d[1], 2);
  49     assert_eq!(d[2], 3);
  50     assert_eq!(d[3], 4);
  51 }
  52
  53 #[cfg(test)]
  54 fn test_parameterized<T: Clone + PartialEq + Debug>(a: T, b: T, c: T, d: T) {
  55     let mut deq = VecDeque::new();
  56     assert_eq!(deq.len(), 0);
  57     deq.push_front(a.clone());
  58     deq.push_front(b.clone());
  59     deq.push_back(c.clone());
  60     assert_eq!(deq.len(), 3);
  61     deq.push_back(d.clone());
  62     assert_eq!(deq.len(), 4);
  63     assert_eq!((*deq.front().unwrap()).clone(), b.clone());
  64     assert_eq!((*deq.back().unwrap()).clone(), d.clone());
  65     assert_eq!(deq.pop_front().unwrap(), b.clone());
  66     assert_eq!(deq.pop_back().unwrap(), d.clone());
  67     assert_eq!(deq.pop_back().unwrap(), c.clone());
  68     assert_eq!(deq.pop_back().unwrap(), a.clone());
  69     assert_eq!(deq.len(), 0);
  70     deq.push_back(c.clone());
  71     assert_eq!(deq.len(), 1);
  72     deq.push_front(b.clone());
  73     assert_eq!(deq.len(), 2);
  74     deq.push_back(d.clone());
  75     assert_eq!(deq.len(), 3);
  76     deq.push_front(a.clone());
  77     assert_eq!(deq.len(), 4);
  78     assert_eq!(deq[0].clone(), a.clone());
  79     assert_eq!(deq[1].clone(), b.clone());
  80     assert_eq!(deq[2].clone(), c.clone());
  81     assert_eq!(deq[3].clone(), d.clone());
  82 }
  83
  84 #[test]
  85 fn test_push_front_grow() {
  86     let mut deq = VecDeque::new();
  87     for i in 0..66 {
  88         deq.push_front(i);
  89     }
  90     assert_eq!(deq.len(), 66);
  91
  92     for i in 0..66 {
  93         assert_eq!(deq[i], 65 - i);
  94     }
  95
  96     let mut deq = VecDeque::new();
  97     for i in 0..66 {
  98         deq.push_back(i);
  99     }
 100
 101     for i in 0..66 {
 102         assert_eq!(deq[i], i);
 103     }
 104 }
 105
 106 #[test]
 107 fn test_index() {
 108     let mut deq = VecDeque::new();
 109     for i in 1..4 {
 110         deq.push_front(i);
 111     }
 112     assert_eq!(deq[1], 2);
 113 }
 114
 115 #[test]
 116 #[should_panic]
 117 fn test_index_out_of_bounds() {
 118     let mut deq = VecDeque::new();
 119     for i in 1..4 {
 120         deq.push_front(i);
 121     }
 122     deq[3];
 123 }
 124
 125 #[derive(Clone, PartialEq, Debug)]
 126 enum Taggy {
 127     One(i32),
 128     Two(i32, i32),
 129     Three(i32, i32, i32),
 130 }
 131
 132 #[derive(Clone, PartialEq, Debug)]
 133 enum Taggypar<T> {
 134     Onepar(T),
 135     Twopar(T, T),
 136     Threepar(T, T, T),
 137 }
 138
 139 #[derive(Clone, PartialEq, Debug)]
 140 struct RecCy {
 141     x: i32,
 142     y: i32,
 143     t: Taggy,
 144 }
 145
 146 #[test]
 147 fn test_param_int() {
 148     test_parameterized::<i32>(5, 72, 64, 175);
 149 }
 150
 151 #[test]
 152 fn test_param_taggy() {
 153     test_parameterized::<Taggy>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
 154 }
 155
 156 #[test]
 157 fn test_param_taggypar() {
 158     test_parameterized::<Taggypar<i32>>(Onepar::<i32>(1),
 159                                         Twopar::<i32>(1, 2),
 160                                         Threepar::<i32>(1, 2, 3),
 161                                         Twopar::<i32>(17, 42));
 162 }
 163
 164 #[test]
 165 fn test_param_reccy() {
 166     let reccy1 = RecCy {
 167         x: 1,
 168         y: 2,
 169         t: One(1),
 170     };
 171     let reccy2 = RecCy {
 172         x: 345,
 173         y: 2,
 174         t: Two(1, 2),
 175     };
 176     let reccy3 = RecCy {
 177         x: 1,
 178         y: 777,
 179         t: Three(1, 2, 3),
 180     };
 181     let reccy4 = RecCy {
 182         x: 19,
 183         y: 252,
 184         t: Two(17, 42),
 185     };
 186     test_parameterized::<RecCy>(reccy1, reccy2, reccy3, reccy4);
 187 }
 188
 189 #[test]
 190 fn test_with_capacity() {
 191     let mut d = VecDeque::with_capacity(0);
 192     d.push_back(1);
 193     assert_eq!(d.len(), 1);
 194     let mut d = VecDeque::with_capacity(50);
 195     d.push_back(1);
 196     assert_eq!(d.len(), 1);
 197 }
 198
 199 #[test]
 200 fn test_with_capacity_non_power_two() {
 201     let mut d3 = VecDeque::with_capacity(3);
 202     d3.push_back(1);
 203
 204     // X = None, | = lo
 205     // [|1, X, X]
 206     assert_eq!(d3.pop_front(), Some(1));
 207     // [X, |X, X]
 208     assert_eq!(d3.front(), None);
 209
 210     // [X, |3, X]
 211     d3.push_back(3);
 212     // [X, |3, 6]
 213     d3.push_back(6);
 214     // [X, X, |6]
 215     assert_eq!(d3.pop_front(), Some(3));
 216
 217     // Pushing the lo past half way point to trigger
 218     // the 'B' scenario for growth
 219     // [9, X, |6]
 220     d3.push_back(9);
 221     // [9, 12, |6]
 222     d3.push_back(12);
 223
 224     d3.push_back(15);
 225     // There used to be a bug here about how the
 226     // VecDeque made growth assumptions about the
 227     // underlying Vec which didn't hold and lead
 228     // to corruption.
 229     // (Vec grows to next power of two)
 230     // good- [9, 12, 15, X, X, X, X, |6]
 231     // bug-  [15, 12, X, X, X, |6, X, X]
 232     assert_eq!(d3.pop_front(), Some(6));
 233
 234     // Which leads us to the following state which
 235     // would be a failure case.
 236     // bug-  [15, 12, X, X, X, X, |X, X]
 237     assert_eq!(d3.front(), Some(&9));
 238 }
 239
 240 #[test]
 241 fn test_reserve_exact() {
 242     let mut d = VecDeque::new();
 243     d.push_back(0);
 244     d.reserve_exact(50);
 245     assert!(d.capacity() >= 51);
 246 }
 247
 248 #[test]
 249 fn test_reserve() {
 250     let mut d = VecDeque::new();
 251     d.push_back(0);
 252     d.reserve(50);
 253     assert!(d.capacity() >= 51);
 254 }
 255
 256 #[test]
 257 fn test_swap() {
 258     let mut d: VecDeque<_> = (0..5).collect();
 259     d.pop_front();
 260     d.swap(0, 3);
 261     assert_eq!(d.iter().cloned().collect::<Vec<_>>(), [4, 2, 3, 1]);
 262 }
 263
 264 #[test]
 265 fn test_iter() {
 266     let mut d = VecDeque::new();
 267     assert_eq!(d.iter().next(), None);
 268     assert_eq!(d.iter().size_hint(), (0, Some(0)));
 269
 270     for i in 0..5 {
 271         d.push_back(i);
 272     }
 273     {
 274         let b: &[_] = &[&0, &1, &2, &3, &4];
 275         assert_eq!(d.iter().collect::<Vec<_>>(), b);
 276     }
 277
 278     for i in 6..9 {
 279         d.push_front(i);
 280     }
 281     {
 282         let b: &[_] = &[&8, &7, &6, &0, &1, &2, &3, &4];
 283         assert_eq!(d.iter().collect::<Vec<_>>(), b);
 284     }
 285
 286     let mut it = d.iter();
 287     let mut len = d.len();
 288     loop {
 289         match it.next() {
 290             None => break,
 291             _ => {
 292                 len -= 1;
 293                 assert_eq!(it.size_hint(), (len, Some(len)))
 294             }
 295         }
 296     }
 297 }
 298
 299 #[test]
 300 fn test_rev_iter() {
 301     let mut d = VecDeque::new();
 302     assert_eq!(d.iter().rev().next(), None);
 303
 304     for i in 0..5 {
 305         d.push_back(i);
 306     }
 307     {
 308         let b: &[_] = &[&4, &3, &2, &1, &0];
 309         assert_eq!(d.iter().rev().collect::<Vec<_>>(), b);
 310     }
 311
 312     for i in 6..9 {
 313         d.push_front(i);
 314     }
 315     let b: &[_] = &[&4, &3, &2, &1, &0, &6, &7, &8];
 316     assert_eq!(d.iter().rev().collect::<Vec<_>>(), b);
 317 }
 318
 319 #[test]
 320 fn test_mut_rev_iter_wrap() {
 321     let mut d = VecDeque::with_capacity(3);
 322     assert!(d.iter_mut().rev().next().is_none());
 323
 324     d.push_back(1);
 325     d.push_back(2);
 326     d.push_back(3);
 327     assert_eq!(d.pop_front(), Some(1));
 328     d.push_back(4);
 329
 330     assert_eq!(d.iter_mut().rev().map(|x| *x).collect::<Vec<_>>(),
 331                vec![4, 3, 2]);
 332 }
 333
 334 #[test]
 335 fn test_mut_iter() {
 336     let mut d = VecDeque::new();
 337     assert!(d.iter_mut().next().is_none());
 338
 339     for i in 0..3 {
 340         d.push_front(i);
 341     }
 342
 343     for (i, elt) in d.iter_mut().enumerate() {
 344         assert_eq!(*elt, 2 - i);
 345         *elt = i;
 346     }
 347
 348     {
 349         let mut it = d.iter_mut();
 350         assert_eq!(*it.next().unwrap(), 0);
 351         assert_eq!(*it.next().unwrap(), 1);
 352         assert_eq!(*it.next().unwrap(), 2);
 353         assert!(it.next().is_none());
 354     }
 355 }
 356
 357 #[test]
 358 fn test_mut_rev_iter() {
 359     let mut d = VecDeque::new();
 360     assert!(d.iter_mut().rev().next().is_none());
 361
 362     for i in 0..3 {
 363         d.push_front(i);
 364     }
 365
 366     for (i, elt) in d.iter_mut().rev().enumerate() {
 367         assert_eq!(*elt, i);
 368         *elt = i;
 369     }
 370
 371     {
 372         let mut it = d.iter_mut().rev();
 373         assert_eq!(*it.next().unwrap(), 0);
 374         assert_eq!(*it.next().unwrap(), 1);
 375         assert_eq!(*it.next().unwrap(), 2);
 376         assert!(it.next().is_none());
 377     }
 378 }
 379
 380 #[test]
 381 fn test_into_iter() {
 382
 383     // Empty iter
 384     {
 385         let d: VecDeque<i32> = VecDeque::new();
 386         let mut iter = d.into_iter();
 387
 388         assert_eq!(iter.size_hint(), (0, Some(0)));
 389         assert_eq!(iter.next(), None);
 390         assert_eq!(iter.size_hint(), (0, Some(0)));
 391     }
 392
 393     // simple iter
 394     {
 395         let mut d = VecDeque::new();
 396         for i in 0..5 {
 397             d.push_back(i);
 398         }
 399
 400         let b = vec![0, 1, 2, 3, 4];
 401         assert_eq!(d.into_iter().collect::<Vec<_>>(), b);
 402     }
 403
 404     // wrapped iter
 405     {
 406         let mut d = VecDeque::new();
 407         for i in 0..5 {
 408             d.push_back(i);
 409         }
 410         for i in 6..9 {
 411             d.push_front(i);
 412         }
 413
 414         let b = vec![8, 7, 6, 0, 1, 2, 3, 4];
 415         assert_eq!(d.into_iter().collect::<Vec<_>>(), b);
 416     }
 417
 418     // partially used
 419     {
 420         let mut d = VecDeque::new();
 421         for i in 0..5 {
 422             d.push_back(i);
 423         }
 424         for i in 6..9 {
 425             d.push_front(i);
 426         }
 427
 428         let mut it = d.into_iter();
 429         assert_eq!(it.size_hint(), (8, Some(8)));
 430         assert_eq!(it.next(), Some(8));
 431         assert_eq!(it.size_hint(), (7, Some(7)));
 432         assert_eq!(it.next_back(), Some(4));
 433         assert_eq!(it.size_hint(), (6, Some(6)));
 434         assert_eq!(it.next(), Some(7));
 435         assert_eq!(it.size_hint(), (5, Some(5)));
 436     }
 437 }
 438
 439 #[test]
 440 fn test_drain() {
 441
 442     // Empty iter
 443     {
 444         let mut d: VecDeque<i32> = VecDeque::new();
 445
 446         {
 447             let mut iter = d.drain(..);
 448
 449             assert_eq!(iter.size_hint(), (0, Some(0)));
 450             assert_eq!(iter.next(), None);
 451             assert_eq!(iter.size_hint(), (0, Some(0)));
 452         }
 453
 454         assert!(d.is_empty());
 455     }
 456
 457     // simple iter
 458     {
 459         let mut d = VecDeque::new();
 460         for i in 0..5 {
 461             d.push_back(i);
 462         }
 463
 464         assert_eq!(d.drain(..).collect::<Vec<_>>(), [0, 1, 2, 3, 4]);
 465         assert!(d.is_empty());
 466     }
 467
 468     // wrapped iter
 469     {
 470         let mut d = VecDeque::new();
 471         for i in 0..5 {
 472             d.push_back(i);
 473         }
 474         for i in 6..9 {
 475             d.push_front(i);
 476         }
 477
 478         assert_eq!(d.drain(..).collect::<Vec<_>>(), [8, 7, 6, 0, 1, 2, 3, 4]);
 479         assert!(d.is_empty());
 480     }
 481
 482     // partially used
 483     {
 484         let mut d: VecDeque<_> = VecDeque::new();
 485         for i in 0..5 {
 486             d.push_back(i);
 487         }
 488         for i in 6..9 {
 489             d.push_front(i);
 490         }
 491
 492         {
 493             let mut it = d.drain(..);
 494             assert_eq!(it.size_hint(), (8, Some(8)));
 495             assert_eq!(it.next(), Some(8));
 496             assert_eq!(it.size_hint(), (7, Some(7)));
 497             assert_eq!(it.next_back(), Some(4));
 498             assert_eq!(it.size_hint(), (6, Some(6)));
 499             assert_eq!(it.next(), Some(7));
 500             assert_eq!(it.size_hint(), (5, Some(5)));
 501         }
 502         assert!(d.is_empty());
 503     }
 504 }
 505
 506 #[test]
 507 fn test_from_iter() {
 508     let v = vec![1, 2, 3, 4, 5, 6, 7];
 509     let deq: VecDeque<_> = v.iter().cloned().collect();
 510     let u: Vec<_> = deq.iter().cloned().collect();
 511     assert_eq!(u, v);
 512
 513     let seq = (0..).step_by(2).take(256);
 514     let deq: VecDeque<_> = seq.collect();
 515     for (i, &x) in deq.iter().enumerate() {
 516         assert_eq!(2 * i, x);
 517     }
 518     assert_eq!(deq.len(), 256);
 519 }
 520
 521 #[test]
 522 fn test_clone() {
 523     let mut d = VecDeque::new();
 524     d.push_front(17);
 525     d.push_front(42);
 526     d.push_back(137);
 527     d.push_back(137);
 528     assert_eq!(d.len(), 4);
 529     let mut e = d.clone();
 530     assert_eq!(e.len(), 4);
 531     while !d.is_empty() {
 532         assert_eq!(d.pop_back(), e.pop_back());
 533     }
 534     assert_eq!(d.len(), 0);
 535     assert_eq!(e.len(), 0);
 536 }
 537
 538 #[test]
 539 fn test_eq() {
 540     let mut d = VecDeque::new();
 541     assert!(d == VecDeque::with_capacity(0));
 542     d.push_front(137);
 543     d.push_front(17);
 544     d.push_front(42);
 545     d.push_back(137);
 546     let mut e = VecDeque::with_capacity(0);
 547     e.push_back(42);
 548     e.push_back(17);
 549     e.push_back(137);
 550     e.push_back(137);
 551     assert!(&e == &d);
 552     e.pop_back();
 553     e.push_back(0);
 554     assert!(e != d);
 555     e.clear();
 556     assert!(e == VecDeque::new());
 557 }
 558
 559 #[test]
 560 fn test_partial_eq_array() {
 561     let d = VecDeque::<char>::new();
 562     assert!(d == []);
 563
 564     let mut d = VecDeque::new();
 565     d.push_front('a');
 566     assert!(d == ['a']);
 567
 568     let mut d = VecDeque::new();
 569     d.push_back('a');
 570     assert!(d == ['a']);
 571
 572     let mut d = VecDeque::new();
 573     d.push_back('a');
 574     d.push_back('b');
 575     assert!(d == ['a', 'b']);
 576 }
 577
 578 #[test]
 579 fn test_hash() {
 580     let mut x = VecDeque::new();
 581     let mut y = VecDeque::new();
 582
 583     x.push_back(1);
 584     x.push_back(2);
 585     x.push_back(3);
 586
 587     y.push_back(0);
 588     y.push_back(1);
 589     y.pop_front();
 590     y.push_back(2);
 591     y.push_back(3);
 592
 593     assert!(::hash(&x) == ::hash(&y));
 594 }
 595
 596 #[test]
 597 fn test_hash_after_rotation() {
 598     // test that two deques hash equal even if elements are laid out differently
 599     let len = 28;
 600     let mut ring: VecDeque<i32> = (0..len as i32).collect();
 601     let orig = ring.clone();
 602     for _ in 0..ring.capacity() {
 603         // shift values 1 step to the right by pop, sub one, push
 604         ring.pop_front();
 605         for elt in &mut ring {
 606             *elt -= 1;
 607         }
 608         ring.push_back(len - 1);
 609         assert_eq!(::hash(&orig), ::hash(&ring));
 610         assert_eq!(orig, ring);
 611         assert_eq!(ring, orig);
 612     }
 613 }
 614
 615 #[test]
 616 fn test_eq_after_rotation() {
 617     // test that two deques are equal even if elements are laid out differently
 618     let len = 28;
 619     let mut ring: VecDeque<i32> = (0..len as i32).collect();
 620     let mut shifted = ring.clone();
 621     for _ in 0..10 {
 622         // shift values 1 step to the right by pop, sub one, push
 623         ring.pop_front();
 624         for elt in &mut ring {
 625             *elt -= 1;
 626         }
 627         ring.push_back(len - 1);
 628     }
 629
 630     // try every shift
 631     for _ in 0..shifted.capacity() {
 632         shifted.pop_front();
 633         for elt in &mut shifted {
 634             *elt -= 1;
 635         }
 636         shifted.push_back(len - 1);
 637         assert_eq!(shifted, ring);
 638         assert_eq!(ring, shifted);
 639     }
 640 }
 641
 642 #[test]
 643 fn test_ord() {
 644     let x = VecDeque::new();
 645     let mut y = VecDeque::new();
 646     y.push_back(1);
 647     y.push_back(2);
 648     y.push_back(3);
 649     assert!(x < y);
 650     assert!(y > x);
 651     assert!(x <= x);
 652     assert!(x >= x);
 653 }
 654
 655 #[test]
 656 fn test_show() {
 657     let ringbuf: VecDeque<_> = (0..10).collect();
 658     assert_eq!(format!("{:?}", ringbuf), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
 659
 660     let ringbuf: VecDeque<_> = vec!["just", "one", "test", "more"]
 661         .iter()
 662         .cloned()
 663         .collect();
 664     assert_eq!(format!("{:?}", ringbuf),
 665                "[\"just\", \"one\", \"test\", \"more\"]");
 666 }
 667
 668 #[test]
 669 fn test_drop() {
 670     static mut DROPS: i32 = 0;
 671     struct Elem;
 672     impl Drop for Elem {
 673         fn drop(&mut self) {
 674             unsafe {
 675                 DROPS += 1;
 676             }
 677         }
 678     }
 679
 680     let mut ring = VecDeque::new();
 681     ring.push_back(Elem);
 682     ring.push_front(Elem);
 683     ring.push_back(Elem);
 684     ring.push_front(Elem);
 685     drop(ring);
 686
 687     assert_eq!(unsafe { DROPS }, 4);
 688 }
 689
 690 #[test]
 691 fn test_drop_with_pop() {
 692     static mut DROPS: i32 = 0;
 693     struct Elem;
 694     impl Drop for Elem {
 695         fn drop(&mut self) {
 696             unsafe {
 697                 DROPS += 1;
 698             }
 699         }
 700     }
 701
 702     let mut ring = VecDeque::new();
 703     ring.push_back(Elem);
 704     ring.push_front(Elem);
 705     ring.push_back(Elem);
 706     ring.push_front(Elem);
 707
 708     drop(ring.pop_back());
 709     drop(ring.pop_front());
 710     assert_eq!(unsafe { DROPS }, 2);
 711
 712     drop(ring);
 713     assert_eq!(unsafe { DROPS }, 4);
 714 }
 715
 716 #[test]
 717 fn test_drop_clear() {
 718     static mut DROPS: i32 = 0;
 719     struct Elem;
 720     impl Drop for Elem {
 721         fn drop(&mut self) {
 722             unsafe {
 723                 DROPS += 1;
 724             }
 725         }
 726     }
 727
 728     let mut ring = VecDeque::new();
 729     ring.push_back(Elem);
 730     ring.push_front(Elem);
 731     ring.push_back(Elem);
 732     ring.push_front(Elem);
 733     ring.clear();
 734     assert_eq!(unsafe { DROPS }, 4);
 735
 736     drop(ring);
 737     assert_eq!(unsafe { DROPS }, 4);
 738 }
 739
 740 #[test]
 741 fn test_reserve_grow() {
 742     // test growth path A
 743     // [T o o H] -> [T o o H . . . . ]
 744     let mut ring = VecDeque::with_capacity(4);
 745     for i in 0..3 {
 746         ring.push_back(i);
 747     }
 748     ring.reserve(7);
 749     for i in 0..3 {
 750         assert_eq!(ring.pop_front(), Some(i));
 751     }
 752
 753     // test growth path B
 754     // [H T o o] -> [. T o o H . . . ]
 755     let mut ring = VecDeque::with_capacity(4);
 756     for i in 0..1 {
 757         ring.push_back(i);
 758         assert_eq!(ring.pop_front(), Some(i));
 759     }
 760     for i in 0..3 {
 761         ring.push_back(i);
 762     }
 763     ring.reserve(7);
 764     for i in 0..3 {
 765         assert_eq!(ring.pop_front(), Some(i));
 766     }
 767
 768     // test growth path C
 769     // [o o H T] -> [o o H . . . . T ]
 770     let mut ring = VecDeque::with_capacity(4);
 771     for i in 0..3 {
 772         ring.push_back(i);
 773         assert_eq!(ring.pop_front(), Some(i));
 774     }
 775     for i in 0..3 {
 776         ring.push_back(i);
 777     }
 778     ring.reserve(7);
 779     for i in 0..3 {
 780         assert_eq!(ring.pop_front(), Some(i));
 781     }
 782 }
 783
 784 #[test]
 785 fn test_get() {
 786     let mut ring = VecDeque::new();
 787     ring.push_back(0);
 788     assert_eq!(ring.get(0), Some(&0));
 789     assert_eq!(ring.get(1), None);
 790
 791     ring.push_back(1);
 792     assert_eq!(ring.get(0), Some(&0));
 793     assert_eq!(ring.get(1), Some(&1));
 794     assert_eq!(ring.get(2), None);
 795
 796     ring.push_back(2);
 797     assert_eq!(ring.get(0), Some(&0));
 798     assert_eq!(ring.get(1), Some(&1));
 799     assert_eq!(ring.get(2), Some(&2));
 800     assert_eq!(ring.get(3), None);
 801
 802     assert_eq!(ring.pop_front(), Some(0));
 803     assert_eq!(ring.get(0), Some(&1));
 804     assert_eq!(ring.get(1), Some(&2));
 805     assert_eq!(ring.get(2), None);
 806
 807     assert_eq!(ring.pop_front(), Some(1));
 808     assert_eq!(ring.get(0), Some(&2));
 809     assert_eq!(ring.get(1), None);
 810
 811     assert_eq!(ring.pop_front(), Some(2));
 812     assert_eq!(ring.get(0), None);
 813     assert_eq!(ring.get(1), None);
 814 }
 815
 816 #[test]
 817 fn test_get_mut() {
 818     let mut ring = VecDeque::new();
 819     for i in 0..3 {
 820         ring.push_back(i);
 821     }
 822
 823     match ring.get_mut(1) {
 824         Some(x) => *x = -1,
 825         None => (),
 826     };
 827
 828     assert_eq!(ring.get_mut(0), Some(&mut 0));
 829     assert_eq!(ring.get_mut(1), Some(&mut -1));
 830     assert_eq!(ring.get_mut(2), Some(&mut 2));
 831     assert_eq!(ring.get_mut(3), None);
 832
 833     assert_eq!(ring.pop_front(), Some(0));
 834     assert_eq!(ring.get_mut(0), Some(&mut -1));
 835     assert_eq!(ring.get_mut(1), Some(&mut 2));
 836     assert_eq!(ring.get_mut(2), None);
 837 }
 838
 839 #[test]
 840 fn test_front() {
 841     let mut ring = VecDeque::new();
 842     ring.push_back(10);
 843     ring.push_back(20);
 844     assert_eq!(ring.front(), Some(&10));
 845     ring.pop_front();
 846     assert_eq!(ring.front(), Some(&20));
 847     ring.pop_front();
 848     assert_eq!(ring.front(), None);
 849 }
 850
 851 #[test]
 852 fn test_as_slices() {
 853     let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
 854     let cap = ring.capacity() as i32;
 855     let first = cap / 2;
 856     let last = cap - first;
 857     for i in 0..first {
 858         ring.push_back(i);
 859
 860         let (left, right) = ring.as_slices();
 861         let expected: Vec<_> = (0..i + 1).collect();
 862         assert_eq!(left, &expected[..]);
 863         assert_eq!(right, []);
 864     }
 865
 866     for j in -last..0 {
 867         ring.push_front(j);
 868         let (left, right) = ring.as_slices();
 869         let expected_left: Vec<_> = (-last..j + 1).rev().collect();
 870         let expected_right: Vec<_> = (0..first).collect();
 871         assert_eq!(left, &expected_left[..]);
 872         assert_eq!(right, &expected_right[..]);
 873     }
 874
 875     assert_eq!(ring.len() as i32, cap);
 876     assert_eq!(ring.capacity() as i32, cap);
 877 }
 878
 879 #[test]
 880 fn test_as_mut_slices() {
 881     let mut ring: VecDeque<i32> = VecDeque::with_capacity(127);
 882     let cap = ring.capacity() as i32;
 883     let first = cap / 2;
 884     let last = cap - first;
 885     for i in 0..first {
 886         ring.push_back(i);
 887
 888         let (left, right) = ring.as_mut_slices();
 889         let expected: Vec<_> = (0..i + 1).collect();
 890         assert_eq!(left, &expected[..]);
 891         assert_eq!(right, []);
 892     }
 893
 894     for j in -last..0 {
 895         ring.push_front(j);
 896         let (left, right) = ring.as_mut_slices();
 897         let expected_left: Vec<_> = (-last..j + 1).rev().collect();
 898         let expected_right: Vec<_> = (0..first).collect();
 899         assert_eq!(left, &expected_left[..]);
 900         assert_eq!(right, &expected_right[..]);
 901     }
 902
 903     assert_eq!(ring.len() as i32, cap);
 904     assert_eq!(ring.capacity() as i32, cap);
 905 }
 906
 907 #[test]
 908 fn test_append() {
 909     let mut a: VecDeque<_> = vec![1, 2, 3].into_iter().collect();
 910     let mut b: VecDeque<_> = vec![4, 5, 6].into_iter().collect();
 911
 912     // normal append
 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 nothing to something
 918     a.append(&mut b);
 919     assert_eq!(a.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
 920     assert_eq!(b.iter().cloned().collect::<Vec<_>>(), []);
 921
 922     // append something to nothing
 923     b.append(&mut a);
 924     assert_eq!(b.iter().cloned().collect::<Vec<_>>(), [1, 2, 3, 4, 5, 6]);
 925     assert_eq!(a.iter().cloned().collect::<Vec<_>>(), []);
 926 }
 927
 928 #[test]
 929 fn test_retain() {
 930     let mut buf = VecDeque::new();
 931     buf.extend(1..5);
 932     buf.retain(|&x| x % 2 == 0);
 933     let v: Vec<_> = buf.into_iter().collect();
 934     assert_eq!(&v[..], &[2, 4]);
 935 }
 936
 937 #[test]
 938 fn test_extend_ref() {
 939     let mut v = VecDeque::new();
 940     v.push_back(1);
 941     v.extend(&[2, 3, 4]);
 942
 943     assert_eq!(v.len(), 4);
 944     assert_eq!(v[0], 1);
 945     assert_eq!(v[1], 2);
 946     assert_eq!(v[2], 3);
 947     assert_eq!(v[3], 4);
 948
 949     let mut w = VecDeque::new();
 950     w.push_back(5);
 951     w.push_back(6);
 952     v.extend(&w);
 953
 954     assert_eq!(v.len(), 6);
 955     assert_eq!(v[0], 1);
 956     assert_eq!(v[1], 2);
 957     assert_eq!(v[2], 3);
 958     assert_eq!(v[3], 4);
 959     assert_eq!(v[4], 5);
 960     assert_eq!(v[5], 6);
 961 }
 962
 963 #[test]
 964 fn test_contains() {
 965     let mut v = VecDeque::new();
 966     v.extend(&[2, 3, 4]);
 967
 968     assert!(v.contains(&3));
 969     assert!(!v.contains(&1));
 970
 971     v.clear();
 972
 973     assert!(!v.contains(&3));
 974 }
 975
 976 #[allow(dead_code)]
 977 fn assert_covariance() {
 978     fn drain<'new>(d: Drain<'static, &'static str>) -> Drain<'new, &'new str> {
 979         d
 980     }
 981 }
 982
 983 #[test]
 984 fn test_is_empty() {
 985     let mut v = VecDeque::<i32>::new();
 986     assert!(v.is_empty());
 987     assert!(v.iter().is_empty());
 988     assert!(v.iter_mut().is_empty());
 989     v.extend(&[2, 3, 4]);
 990     assert!(!v.is_empty());
 991     assert!(!v.iter().is_empty());
 992     assert!(!v.iter_mut().is_empty());
 993     while let Some(_) = v.pop_front() {
 994         assert_eq!(v.is_empty(), v.len() == 0);
 995         assert_eq!(v.iter().is_empty(), v.iter().len() == 0);
 996         assert_eq!(v.iter_mut().is_empty(), v.iter_mut().len() == 0);
 997     }
 998     assert!(v.is_empty());
 999     assert!(v.iter().is_empty());
1000     assert!(v.iter_mut().is_empty());
1001     assert!(v.into_iter().is_empty());
1002 }
1003
1004 #[test]
1005 fn test_placement_in() {
1006     let mut buf: VecDeque<isize> = VecDeque::new();
1007     buf.place_back() <- 1;
1008     buf.place_back() <- 2;
1009     assert_eq!(buf, [1,2]);
1010
1011     buf.place_front() <- 3;
1012     buf.place_front() <- 4;
1013     assert_eq!(buf, [4,3,1,2]);
1014
1015     {
1016         let ptr_head = buf.place_front() <- 5;
1017         assert_eq!(*ptr_head, 5);
1018     }
1019     {
1020         let ptr_tail = buf.place_back() <- 6;
1021         assert_eq!(*ptr_tail, 6);
1022     }
1023     assert_eq!(buf, [5,4,3,1,2,6]);
1024 }