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