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