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.
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.
11 use std
::collections
::VecDeque
;
17 use self::Taggypar
::*;
21 let mut d
= VecDeque
::new();
22 assert_eq
!(d
.len(), 0);
26 assert_eq
!(d
.len(), 3);
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));
34 assert_eq
!(i
, Some(137));
36 assert_eq
!(i
, Some(137));
38 assert_eq
!(i
, Some(17));
39 assert_eq
!(d
.len(), 0);
41 assert_eq
!(d
.len(), 1);
43 assert_eq
!(d
.len(), 2);
45 assert_eq
!(d
.len(), 3);
47 assert_eq
!(d
.len(), 4);
55 fn test_parameterized
<T
:Clone
+ PartialEq
+ Debug
>(a
: T
, b
: T
, c
: T
, d
: T
) {
56 let mut deq
= VecDeque
::new();
57 assert_eq
!(deq
.len(), 0);
58 deq
.push_front(a
.clone());
59 deq
.push_front(b
.clone());
60 deq
.push_back(c
.clone());
61 assert_eq
!(deq
.len(), 3);
62 deq
.push_back(d
.clone());
63 assert_eq
!(deq
.len(), 4);
64 assert_eq
!((*deq
.front().unwrap()).clone(), b
.clone());
65 assert_eq
!((*deq
.back().unwrap()).clone(), d
.clone());
66 assert_eq
!(deq
.pop_front().unwrap(), b
.clone());
67 assert_eq
!(deq
.pop_back().unwrap(), d
.clone());
68 assert_eq
!(deq
.pop_back().unwrap(), c
.clone());
69 assert_eq
!(deq
.pop_back().unwrap(), a
.clone());
70 assert_eq
!(deq
.len(), 0);
71 deq
.push_back(c
.clone());
72 assert_eq
!(deq
.len(), 1);
73 deq
.push_front(b
.clone());
74 assert_eq
!(deq
.len(), 2);
75 deq
.push_back(d
.clone());
76 assert_eq
!(deq
.len(), 3);
77 deq
.push_front(a
.clone());
78 assert_eq
!(deq
.len(), 4);
79 assert_eq
!(deq
[0].clone(), a
.clone());
80 assert_eq
!(deq
[1].clone(), b
.clone());
81 assert_eq
!(deq
[2].clone(), c
.clone());
82 assert_eq
!(deq
[3].clone(), d
.clone());
86 fn test_push_front_grow() {
87 let mut deq
= VecDeque
::new();
91 assert_eq
!(deq
.len(), 66);
94 assert_eq
!(deq
[i
], 65 - i
);
97 let mut deq
= VecDeque
::new();
103 assert_eq
!(deq
[i
], i
);
109 let mut deq
= VecDeque
::new();
113 assert_eq
!(deq
[1], 2);
118 fn test_index_out_of_bounds() {
119 let mut deq
= VecDeque
::new();
127 fn bench_new(b
: &mut test
::Bencher
) {
129 let ring
: VecDeque
<i32> = VecDeque
::new();
130 test
::black_box(ring
);
135 fn bench_grow_1025(b
: &mut test
::Bencher
) {
137 let mut deq
= VecDeque
::new();
141 test
::black_box(deq
);
146 fn bench_iter_1000(b
: &mut test
::Bencher
) {
147 let ring
: VecDeque
<_
> = (0..1000).collect();
154 test
::black_box(sum
);
159 fn bench_mut_iter_1000(b
: &mut test
::Bencher
) {
160 let mut ring
: VecDeque
<_
> = (0..1000).collect();
167 test
::black_box(sum
);
171 #[derive(Clone, PartialEq, Debug)]
175 Three(i32, i32, i32),
178 #[derive(Clone, PartialEq, Debug)]
185 #[derive(Clone, PartialEq, Debug)]
193 fn test_param_int() {
194 test_parameterized
::<i32>(5, 72, 64, 175);
198 fn test_param_taggy() {
199 test_parameterized
::<Taggy
>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
203 fn test_param_taggypar() {
204 test_parameterized
::<Taggypar
<i32>>(Onepar
::<i32>(1),
206 Threepar
::<i32>(1, 2, 3),
207 Twopar
::<i32>(17, 42));
211 fn test_param_reccy() {
212 let reccy1
= RecCy { x: 1, y: 2, t: One(1) }
;
213 let reccy2
= RecCy { x: 345, y: 2, t: Two(1, 2) }
;
214 let reccy3
= RecCy { x: 1, y: 777, t: Three(1, 2, 3) }
;
215 let reccy4
= RecCy { x: 19, y: 252, t: Two(17, 42) }
;
216 test_parameterized
::<RecCy
>(reccy1
, reccy2
, reccy3
, reccy4
);
220 fn test_with_capacity() {
221 let mut d
= VecDeque
::with_capacity(0);
223 assert_eq
!(d
.len(), 1);
224 let mut d
= VecDeque
::with_capacity(50);
226 assert_eq
!(d
.len(), 1);
230 fn test_with_capacity_non_power_two() {
231 let mut d3
= VecDeque
::with_capacity(3);
236 assert_eq
!(d3
.pop_front(), Some(1));
238 assert_eq
!(d3
.front(), None
);
245 assert_eq
!(d3
.pop_front(), Some(3));
247 // Pushing the lo past half way point to trigger
248 // the 'B' scenario for growth
255 // There used to be a bug here about how the
256 // VecDeque made growth assumptions about the
257 // underlying Vec which didn't hold and lead
259 // (Vec grows to next power of two)
260 //good- [9, 12, 15, X, X, X, X, |6]
261 //bug- [15, 12, X, X, X, |6, X, X]
262 assert_eq
!(d3
.pop_front(), Some(6));
264 // Which leads us to the following state which
265 // would be a failure case.
266 //bug- [15, 12, X, X, X, X, |X, X]
267 assert_eq
!(d3
.front(), Some(&9));
271 fn test_reserve_exact() {
272 let mut d
= VecDeque
::new();
275 assert
!(d
.capacity() >= 51);
280 let mut d
= VecDeque
::new();
283 assert
!(d
.capacity() >= 51);
288 let mut d
: VecDeque
<_
> = (0..5).collect();
291 assert_eq
!(d
.iter().cloned().collect
::<Vec
<_
>>(), [4, 2, 3, 1]);
296 let mut d
= VecDeque
::new();
297 assert_eq
!(d
.iter().next(), None
);
298 assert_eq
!(d
.iter().size_hint(), (0, Some(0)));
304 let b
: &[_
] = &[&0,&1,&2,&3,&4];
305 assert_eq
!(d
.iter().collect
::<Vec
<_
>>(), b
);
312 let b
: &[_
] = &[&8,&7,&6,&0,&1,&2,&3,&4];
313 assert_eq
!(d
.iter().collect
::<Vec
<_
>>(), b
);
316 let mut it
= d
.iter();
317 let mut len
= d
.len();
321 _
=> { len -= 1; assert_eq!(it.size_hint(), (len, Some(len))) }
328 let mut d
= VecDeque
::new();
329 assert_eq
!(d
.iter().rev().next(), None
);
335 let b
: &[_
] = &[&4,&3,&2,&1,&0];
336 assert_eq
!(d
.iter().rev().collect
::<Vec
<_
>>(), b
);
342 let b
: &[_
] = &[&4,&3,&2,&1,&0,&6,&7,&8];
343 assert_eq
!(d
.iter().rev().collect
::<Vec
<_
>>(), b
);
347 fn test_mut_rev_iter_wrap() {
348 let mut d
= VecDeque
::with_capacity(3);
349 assert
!(d
.iter_mut().rev().next().is_none());
354 assert_eq
!(d
.pop_front(), Some(1));
357 assert_eq
!(d
.iter_mut().rev().map(|x
| *x
).collect
::<Vec
<_
>>(),
363 let mut d
= VecDeque
::new();
364 assert
!(d
.iter_mut().next().is_none());
370 for (i
, elt
) in d
.iter_mut().enumerate() {
371 assert_eq
!(*elt
, 2 - i
);
376 let mut it
= d
.iter_mut();
377 assert_eq
!(*it
.next().unwrap(), 0);
378 assert_eq
!(*it
.next().unwrap(), 1);
379 assert_eq
!(*it
.next().unwrap(), 2);
380 assert
!(it
.next().is_none());
385 fn test_mut_rev_iter() {
386 let mut d
= VecDeque
::new();
387 assert
!(d
.iter_mut().rev().next().is_none());
393 for (i
, elt
) in d
.iter_mut().rev().enumerate() {
399 let mut it
= d
.iter_mut().rev();
400 assert_eq
!(*it
.next().unwrap(), 0);
401 assert_eq
!(*it
.next().unwrap(), 1);
402 assert_eq
!(*it
.next().unwrap(), 2);
403 assert
!(it
.next().is_none());
408 fn test_into_iter() {
412 let d
: VecDeque
<i32> = VecDeque
::new();
413 let mut iter
= d
.into_iter();
415 assert_eq
!(iter
.size_hint(), (0, Some(0)));
416 assert_eq
!(iter
.next(), None
);
417 assert_eq
!(iter
.size_hint(), (0, Some(0)));
422 let mut d
= VecDeque
::new();
427 let b
= vec
![0,1,2,3,4];
428 assert_eq
!(d
.into_iter().collect
::<Vec
<_
>>(), b
);
433 let mut d
= VecDeque
::new();
441 let b
= vec
![8,7,6,0,1,2,3,4];
442 assert_eq
!(d
.into_iter().collect
::<Vec
<_
>>(), b
);
447 let mut d
= VecDeque
::new();
455 let mut it
= d
.into_iter();
456 assert_eq
!(it
.size_hint(), (8, Some(8)));
457 assert_eq
!(it
.next(), Some(8));
458 assert_eq
!(it
.size_hint(), (7, Some(7)));
459 assert_eq
!(it
.next_back(), Some(4));
460 assert_eq
!(it
.size_hint(), (6, Some(6)));
461 assert_eq
!(it
.next(), Some(7));
462 assert_eq
!(it
.size_hint(), (5, Some(5)));
471 let mut d
: VecDeque
<i32> = VecDeque
::new();
474 let mut iter
= d
.drain(..);
476 assert_eq
!(iter
.size_hint(), (0, Some(0)));
477 assert_eq
!(iter
.next(), None
);
478 assert_eq
!(iter
.size_hint(), (0, Some(0)));
481 assert
!(d
.is_empty());
486 let mut d
= VecDeque
::new();
491 assert_eq
!(d
.drain(..).collect
::<Vec
<_
>>(), [0, 1, 2, 3, 4]);
492 assert
!(d
.is_empty());
497 let mut d
= VecDeque
::new();
505 assert_eq
!(d
.drain(..).collect
::<Vec
<_
>>(), [8,7,6,0,1,2,3,4]);
506 assert
!(d
.is_empty());
511 let mut d
: VecDeque
<_
> = VecDeque
::new();
520 let mut it
= d
.drain(..);
521 assert_eq
!(it
.size_hint(), (8, Some(8)));
522 assert_eq
!(it
.next(), Some(8));
523 assert_eq
!(it
.size_hint(), (7, Some(7)));
524 assert_eq
!(it
.next_back(), Some(4));
525 assert_eq
!(it
.size_hint(), (6, Some(6)));
526 assert_eq
!(it
.next(), Some(7));
527 assert_eq
!(it
.size_hint(), (5, Some(5)));
529 assert
!(d
.is_empty());
534 fn test_from_iter() {
535 let v
= vec
!(1,2,3,4,5,6,7);
536 let deq
: VecDeque
<_
> = v
.iter().cloned().collect();
537 let u
: Vec
<_
> = deq
.iter().cloned().collect();
540 let seq
= (0..).step_by(2).take(256);
541 let deq
: VecDeque
<_
> = seq
.collect();
542 for (i
, &x
) in deq
.iter().enumerate() {
545 assert_eq
!(deq
.len(), 256);
550 let mut d
= VecDeque
::new();
555 assert_eq
!(d
.len(), 4);
556 let mut e
= d
.clone();
557 assert_eq
!(e
.len(), 4);
558 while !d
.is_empty() {
559 assert_eq
!(d
.pop_back(), e
.pop_back());
561 assert_eq
!(d
.len(), 0);
562 assert_eq
!(e
.len(), 0);
567 let mut d
= VecDeque
::new();
568 assert
!(d
== VecDeque
::with_capacity(0));
573 let mut e
= VecDeque
::with_capacity(0);
583 assert
!(e
== VecDeque
::new());
588 let mut x
= VecDeque
::new();
589 let mut y
= VecDeque
::new();
601 assert
!(::hash(&x
) == ::hash(&y
));
605 fn test_hash_after_rotation() {
606 // test that two deques hash equal even if elements are laid out differently
608 let mut ring
: VecDeque
<i32> = (0..len
as i32).collect();
609 let orig
= ring
.clone();
610 for _
in 0..ring
.capacity() {
611 // shift values 1 step to the right by pop, sub one, push
613 for elt
in &mut ring
{
616 ring
.push_back(len
- 1);
617 assert_eq
!(::hash(&orig
), ::hash(&ring
));
618 assert_eq
!(orig
, ring
);
619 assert_eq
!(ring
, orig
);
624 fn test_eq_after_rotation() {
625 // test that two deques are equal even if elements are laid out differently
627 let mut ring
: VecDeque
<i32> = (0..len
as i32).collect();
628 let mut shifted
= ring
.clone();
630 // shift values 1 step to the right by pop, sub one, push
632 for elt
in &mut ring
{
635 ring
.push_back(len
- 1);
639 for _
in 0..shifted
.capacity() {
641 for elt
in &mut shifted
{
644 shifted
.push_back(len
- 1);
645 assert_eq
!(shifted
, ring
);
646 assert_eq
!(ring
, shifted
);
652 let x
= VecDeque
::new();
653 let mut y
= VecDeque
::new();
665 let ringbuf
: VecDeque
<_
> = (0..10).collect();
666 assert_eq
!(format
!("{:?}", ringbuf
), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
668 let ringbuf
: VecDeque
<_
> = vec
!["just", "one", "test", "more"].iter()
671 assert_eq
!(format
!("{:?}", ringbuf
), "[\"just\", \"one\", \"test\", \"more\"]");
676 static mut drops
: i32 = 0;
680 unsafe { drops += 1; }
684 let mut ring
= VecDeque
::new();
685 ring
.push_back(Elem
);
686 ring
.push_front(Elem
);
687 ring
.push_back(Elem
);
688 ring
.push_front(Elem
);
691 assert_eq
!(unsafe {drops}
, 4);
695 fn test_drop_with_pop() {
696 static mut drops
: i32 = 0;
700 unsafe { drops += 1; }
704 let mut ring
= VecDeque
::new();
705 ring
.push_back(Elem
);
706 ring
.push_front(Elem
);
707 ring
.push_back(Elem
);
708 ring
.push_front(Elem
);
710 drop(ring
.pop_back());
711 drop(ring
.pop_front());
712 assert_eq
!(unsafe {drops}
, 2);
715 assert_eq
!(unsafe {drops}
, 4);
719 fn test_drop_clear() {
720 static mut drops
: i32 = 0;
724 unsafe { drops += 1; }
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
);
734 assert_eq
!(unsafe {drops}
, 4);
737 assert_eq
!(unsafe {drops}
, 4);
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);
750 assert_eq
!(ring
.pop_front(), Some(i
));
753 // test growth path B
754 // [H T o o] -> [. T o o H . . . ]
755 let mut ring
= VecDeque
::with_capacity(4);
758 assert_eq
!(ring
.pop_front(), Some(i
));
765 assert_eq
!(ring
.pop_front(), Some(i
));
768 // test growth path C
769 // [o o H T] -> [o o H . . . . T ]
770 let mut ring
= VecDeque
::with_capacity(4);
773 assert_eq
!(ring
.pop_front(), Some(i
));
780 assert_eq
!(ring
.pop_front(), Some(i
));
786 let mut ring
= VecDeque
::new();
788 assert_eq
!(ring
.get(0), Some(&0));
789 assert_eq
!(ring
.get(1), None
);
792 assert_eq
!(ring
.get(0), Some(&0));
793 assert_eq
!(ring
.get(1), Some(&1));
794 assert_eq
!(ring
.get(2), None
);
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
);
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
);
807 assert_eq
!(ring
.pop_front(), Some(1));
808 assert_eq
!(ring
.get(0), Some(&2));
809 assert_eq
!(ring
.get(1), None
);
811 assert_eq
!(ring
.pop_front(), Some(2));
812 assert_eq
!(ring
.get(0), None
);
813 assert_eq
!(ring
.get(1), None
);
818 let mut ring
= VecDeque
::new();
823 match ring
.get_mut(1) {
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
);
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
);
841 let mut ring
= VecDeque
::new();
844 assert_eq
!(ring
.front(), Some(&10));
846 assert_eq
!(ring
.front(), Some(&20));
848 assert_eq
!(ring
.front(), None
);
852 fn test_as_slices() {
853 let mut ring
: VecDeque
<i32> = VecDeque
::with_capacity(127);
854 let cap
= ring
.capacity() as i32;
856 let last
= cap
- first
;
860 let (left
, right
) = ring
.as_slices();
861 let expected
: Vec
<_
> = (0..i
+1).collect();
862 assert_eq
!(left
, &expected
[..]);
863 assert_eq
!(right
, []);
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
[..]);
875 assert_eq
!(ring
.len() as i32, cap
);
876 assert_eq
!(ring
.capacity() as i32, cap
);
880 fn test_as_mut_slices() {
881 let mut ring
: VecDeque
<i32> = VecDeque
::with_capacity(127);
882 let cap
= ring
.capacity() as i32;
884 let last
= cap
- first
;
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
, []);
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
[..]);
903 assert_eq
!(ring
.len() as i32, cap
);
904 assert_eq
!(ring
.capacity() as i32, cap
);
909 let mut a
: VecDeque
<_
> = vec
![1, 2, 3].into_iter().collect();
910 let mut b
: VecDeque
<_
> = vec
![4, 5, 6].into_iter().collect();
914 assert_eq
!(a
.iter().cloned().collect
::<Vec
<_
>>(), [1, 2, 3, 4, 5, 6]);
915 assert_eq
!(b
.iter().cloned().collect
::<Vec
<_
>>(), []);
917 // append nothing to something
919 assert_eq
!(a
.iter().cloned().collect
::<Vec
<_
>>(), [1, 2, 3, 4, 5, 6]);
920 assert_eq
!(b
.iter().cloned().collect
::<Vec
<_
>>(), []);
922 // append something to nothing
924 assert_eq
!(b
.iter().cloned().collect
::<Vec
<_
>>(), [1, 2, 3, 4, 5, 6]);
925 assert_eq
!(a
.iter().cloned().collect
::<Vec
<_
>>(), []);
930 let mut buf
= VecDeque
::new();
932 buf
.retain(|&x
| x
% 2 == 0);
933 let v
: Vec
<_
> = buf
.into_iter().collect();
934 assert_eq
!(&v
[..], &[2, 4]);
938 fn test_extend_ref() {
939 let mut v
= VecDeque
::new();
941 v
.extend(&[2, 3, 4]);
943 assert_eq
!(v
.len(), 4);
949 let mut w
= VecDeque
::new();
954 assert_eq
!(v
.len(), 6);