1 use std
::collections
::TryReserveError
::*;
2 use std
::collections
::{vec_deque::Drain, VecDeque}
;
5 use std
::panic
::catch_unwind
;
6 use std
::{isize, usize}
;
15 let mut d
= VecDeque
::new();
16 assert_eq
!(d
.len(), 0);
20 assert_eq
!(d
.len(), 3);
22 assert_eq
!(d
.len(), 4);
23 assert_eq
!(*d
.front().unwrap(), 42);
24 assert_eq
!(*d
.back().unwrap(), 137);
25 let mut i
= d
.pop_front();
26 assert_eq
!(i
, Some(42));
28 assert_eq
!(i
, Some(137));
30 assert_eq
!(i
, Some(137));
32 assert_eq
!(i
, Some(17));
33 assert_eq
!(d
.len(), 0);
35 assert_eq
!(d
.len(), 1);
37 assert_eq
!(d
.len(), 2);
39 assert_eq
!(d
.len(), 3);
41 assert_eq
!(d
.len(), 4);
48 fn test_parameterized
<T
: Clone
+ PartialEq
+ Debug
>(a
: T
, b
: T
, c
: T
, d
: T
) {
49 let mut deq
= VecDeque
::new();
50 assert_eq
!(deq
.len(), 0);
51 deq
.push_front(a
.clone());
52 deq
.push_front(b
.clone());
53 deq
.push_back(c
.clone());
54 assert_eq
!(deq
.len(), 3);
55 deq
.push_back(d
.clone());
56 assert_eq
!(deq
.len(), 4);
57 assert_eq
!((*deq
.front().unwrap()).clone(), b
.clone());
58 assert_eq
!((*deq
.back().unwrap()).clone(), d
.clone());
59 assert_eq
!(deq
.pop_front().unwrap(), b
.clone());
60 assert_eq
!(deq
.pop_back().unwrap(), d
.clone());
61 assert_eq
!(deq
.pop_back().unwrap(), c
.clone());
62 assert_eq
!(deq
.pop_back().unwrap(), a
.clone());
63 assert_eq
!(deq
.len(), 0);
64 deq
.push_back(c
.clone());
65 assert_eq
!(deq
.len(), 1);
66 deq
.push_front(b
.clone());
67 assert_eq
!(deq
.len(), 2);
68 deq
.push_back(d
.clone());
69 assert_eq
!(deq
.len(), 3);
70 deq
.push_front(a
.clone());
71 assert_eq
!(deq
.len(), 4);
72 assert_eq
!(deq
[0].clone(), a
.clone());
73 assert_eq
!(deq
[1].clone(), b
.clone());
74 assert_eq
!(deq
[2].clone(), c
.clone());
75 assert_eq
!(deq
[3].clone(), d
.clone());
79 fn test_push_front_grow() {
80 let mut deq
= VecDeque
::new();
84 assert_eq
!(deq
.len(), 66);
87 assert_eq
!(deq
[i
], 65 - i
);
90 let mut deq
= VecDeque
::new();
96 assert_eq
!(deq
[i
], i
);
102 let mut deq
= VecDeque
::new();
106 assert_eq
!(deq
[1], 2);
111 fn test_index_out_of_bounds() {
112 let mut deq
= VecDeque
::new();
119 #[derive(Clone, PartialEq, Debug)]
123 Three(i32, i32, i32),
126 #[derive(Clone, PartialEq, Debug)]
133 #[derive(Clone, PartialEq, Debug)]
141 fn test_param_int() {
142 test_parameterized
::<i32>(5, 72, 64, 175);
146 fn test_param_taggy() {
147 test_parameterized
::<Taggy
>(One(1), Two(1, 2), Three(1, 2, 3), Two(17, 42));
151 fn test_param_taggypar() {
152 test_parameterized
::<Taggypar
<i32>>(
155 Threepar
::<i32>(1, 2, 3),
156 Twopar
::<i32>(17, 42),
161 fn test_param_reccy() {
162 let reccy1
= RecCy { x: 1, y: 2, t: One(1) }
;
163 let reccy2
= RecCy { x: 345, y: 2, t: Two(1, 2) }
;
164 let reccy3
= RecCy { x: 1, y: 777, t: Three(1, 2, 3) }
;
165 let reccy4
= RecCy { x: 19, y: 252, t: Two(17, 42) }
;
166 test_parameterized
::<RecCy
>(reccy1
, reccy2
, reccy3
, reccy4
);
170 fn test_with_capacity() {
171 let mut d
= VecDeque
::with_capacity(0);
173 assert_eq
!(d
.len(), 1);
174 let mut d
= VecDeque
::with_capacity(50);
176 assert_eq
!(d
.len(), 1);
180 fn test_with_capacity_non_power_two() {
181 let mut d3
= VecDeque
::with_capacity(3);
186 assert_eq
!(d3
.pop_front(), Some(1));
188 assert_eq
!(d3
.front(), None
);
195 assert_eq
!(d3
.pop_front(), Some(3));
197 // Pushing the lo past half way point to trigger
198 // the 'B' scenario for growth
205 // There used to be a bug here about how the
206 // VecDeque made growth assumptions about the
207 // underlying Vec which didn't hold and lead
209 // (Vec grows to next power of two)
210 // good- [9, 12, 15, X, X, X, X, |6]
211 // bug- [15, 12, X, X, X, |6, X, X]
212 assert_eq
!(d3
.pop_front(), Some(6));
214 // Which leads us to the following state which
215 // would be a failure case.
216 // bug- [15, 12, X, X, X, X, |X, X]
217 assert_eq
!(d3
.front(), Some(&9));
221 fn test_reserve_exact() {
222 let mut d
= VecDeque
::new();
225 assert
!(d
.capacity() >= 51);
230 let mut d
= VecDeque
::new();
233 assert
!(d
.capacity() >= 51);
238 let mut d
: VecDeque
<_
> = (0..5).collect();
241 assert_eq
!(d
.iter().cloned().collect
::<Vec
<_
>>(), [4, 2, 3, 1]);
246 let mut d
= VecDeque
::new();
247 assert_eq
!(d
.iter().next(), None
);
248 assert_eq
!(d
.iter().size_hint(), (0, Some(0)));
254 let b
: &[_
] = &[&0, &1, &2, &3, &4];
255 assert_eq
!(d
.iter().collect
::<Vec
<_
>>(), b
);
262 let b
: &[_
] = &[&8, &7, &6, &0, &1, &2, &3, &4];
263 assert_eq
!(d
.iter().collect
::<Vec
<_
>>(), b
);
266 let mut it
= d
.iter();
267 let mut len
= d
.len();
273 assert_eq
!(it
.size_hint(), (len
, Some(len
)))
281 let mut d
= VecDeque
::new();
282 assert_eq
!(d
.iter().rev().next(), None
);
288 let b
: &[_
] = &[&4, &3, &2, &1, &0];
289 assert_eq
!(d
.iter().rev().collect
::<Vec
<_
>>(), b
);
295 let b
: &[_
] = &[&4, &3, &2, &1, &0, &6, &7, &8];
296 assert_eq
!(d
.iter().rev().collect
::<Vec
<_
>>(), b
);
300 fn test_mut_rev_iter_wrap() {
301 let mut d
= VecDeque
::with_capacity(3);
302 assert
!(d
.iter_mut().rev().next().is_none());
307 assert_eq
!(d
.pop_front(), Some(1));
310 assert_eq
!(d
.iter_mut().rev().map(|x
| *x
).collect
::<Vec
<_
>>(), vec
![4, 3, 2]);
315 let mut d
= VecDeque
::new();
316 assert
!(d
.iter_mut().next().is_none());
322 for (i
, elt
) in d
.iter_mut().enumerate() {
323 assert_eq
!(*elt
, 2 - i
);
328 let mut it
= d
.iter_mut();
329 assert_eq
!(*it
.next().unwrap(), 0);
330 assert_eq
!(*it
.next().unwrap(), 1);
331 assert_eq
!(*it
.next().unwrap(), 2);
332 assert
!(it
.next().is_none());
337 fn test_mut_rev_iter() {
338 let mut d
= VecDeque
::new();
339 assert
!(d
.iter_mut().rev().next().is_none());
345 for (i
, elt
) in d
.iter_mut().rev().enumerate() {
351 let mut it
= d
.iter_mut().rev();
352 assert_eq
!(*it
.next().unwrap(), 0);
353 assert_eq
!(*it
.next().unwrap(), 1);
354 assert_eq
!(*it
.next().unwrap(), 2);
355 assert
!(it
.next().is_none());
360 fn test_into_iter() {
363 let d
: VecDeque
<i32> = VecDeque
::new();
364 let mut iter
= d
.into_iter();
366 assert_eq
!(iter
.size_hint(), (0, Some(0)));
367 assert_eq
!(iter
.next(), None
);
368 assert_eq
!(iter
.size_hint(), (0, Some(0)));
373 let mut d
= VecDeque
::new();
378 let b
= vec
![0, 1, 2, 3, 4];
379 assert_eq
!(d
.into_iter().collect
::<Vec
<_
>>(), b
);
384 let mut d
= VecDeque
::new();
392 let b
= vec
![8, 7, 6, 0, 1, 2, 3, 4];
393 assert_eq
!(d
.into_iter().collect
::<Vec
<_
>>(), b
);
398 let mut d
= VecDeque
::new();
406 let mut it
= d
.into_iter();
407 assert_eq
!(it
.size_hint(), (8, Some(8)));
408 assert_eq
!(it
.next(), Some(8));
409 assert_eq
!(it
.size_hint(), (7, Some(7)));
410 assert_eq
!(it
.next_back(), Some(4));
411 assert_eq
!(it
.size_hint(), (6, Some(6)));
412 assert_eq
!(it
.next(), Some(7));
413 assert_eq
!(it
.size_hint(), (5, Some(5)));
421 let mut d
: VecDeque
<i32> = VecDeque
::new();
424 let mut iter
= d
.drain(..);
426 assert_eq
!(iter
.size_hint(), (0, Some(0)));
427 assert_eq
!(iter
.next(), None
);
428 assert_eq
!(iter
.size_hint(), (0, Some(0)));
431 assert
!(d
.is_empty());
436 let mut d
= VecDeque
::new();
441 assert_eq
!(d
.drain(..).collect
::<Vec
<_
>>(), [0, 1, 2, 3, 4]);
442 assert
!(d
.is_empty());
447 let mut d
= VecDeque
::new();
455 assert_eq
!(d
.drain(..).collect
::<Vec
<_
>>(), [8, 7, 6, 0, 1, 2, 3, 4]);
456 assert
!(d
.is_empty());
461 let mut d
: VecDeque
<_
> = VecDeque
::new();
470 let mut it
= d
.drain(..);
471 assert_eq
!(it
.size_hint(), (8, Some(8)));
472 assert_eq
!(it
.next(), Some(8));
473 assert_eq
!(it
.size_hint(), (7, Some(7)));
474 assert_eq
!(it
.next_back(), Some(4));
475 assert_eq
!(it
.size_hint(), (6, Some(6)));
476 assert_eq
!(it
.next(), Some(7));
477 assert_eq
!(it
.size_hint(), (5, Some(5)));
479 assert
!(d
.is_empty());
484 fn test_from_iter() {
485 let v
= vec
![1, 2, 3, 4, 5, 6, 7];
486 let deq
: VecDeque
<_
> = v
.iter().cloned().collect();
487 let u
: Vec
<_
> = deq
.iter().cloned().collect();
490 let seq
= (0..).step_by(2).take(256);
491 let deq
: VecDeque
<_
> = seq
.collect();
492 for (i
, &x
) in deq
.iter().enumerate() {
493 assert_eq
!(2 * i
, x
);
495 assert_eq
!(deq
.len(), 256);
500 let mut d
= VecDeque
::new();
505 assert_eq
!(d
.len(), 4);
506 let mut e
= d
.clone();
507 assert_eq
!(e
.len(), 4);
508 while !d
.is_empty() {
509 assert_eq
!(d
.pop_back(), e
.pop_back());
511 assert_eq
!(d
.len(), 0);
512 assert_eq
!(e
.len(), 0);
517 let mut d
= VecDeque
::new();
518 assert
!(d
== VecDeque
::with_capacity(0));
523 let mut e
= VecDeque
::with_capacity(0);
533 assert
!(e
== VecDeque
::new());
537 fn test_partial_eq_array() {
538 let d
= VecDeque
::<char>::new();
541 let mut d
= VecDeque
::new();
545 let mut d
= VecDeque
::new();
549 let mut d
= VecDeque
::new();
552 assert
!(d
== ['a'
, 'b'
]);
557 let mut x
= VecDeque
::new();
558 let mut y
= VecDeque
::new();
570 assert
!(hash(&x
) == hash(&y
));
574 fn test_hash_after_rotation() {
575 // test that two deques hash equal even if elements are laid out differently
577 let mut ring
: VecDeque
<i32> = (0..len
as i32).collect();
578 let orig
= ring
.clone();
579 for _
in 0..ring
.capacity() {
580 // shift values 1 step to the right by pop, sub one, push
582 for elt
in &mut ring
{
585 ring
.push_back(len
- 1);
586 assert_eq
!(hash(&orig
), hash(&ring
));
587 assert_eq
!(orig
, ring
);
588 assert_eq
!(ring
, orig
);
593 fn test_eq_after_rotation() {
594 // test that two deques are equal even if elements are laid out differently
596 let mut ring
: VecDeque
<i32> = (0..len
as i32).collect();
597 let mut shifted
= ring
.clone();
599 // shift values 1 step to the right by pop, sub one, push
601 for elt
in &mut ring
{
604 ring
.push_back(len
- 1);
608 for _
in 0..shifted
.capacity() {
610 for elt
in &mut shifted
{
613 shifted
.push_back(len
- 1);
614 assert_eq
!(shifted
, ring
);
615 assert_eq
!(ring
, shifted
);
621 let x
= VecDeque
::new();
622 let mut y
= VecDeque
::new();
634 let ringbuf
: VecDeque
<_
> = (0..10).collect();
635 assert_eq
!(format
!("{:?}", ringbuf
), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]");
637 let ringbuf
: VecDeque
<_
> = vec
!["just", "one", "test", "more"].iter().cloned().collect();
638 assert_eq
!(format
!("{:?}", ringbuf
), "[\"just\", \"one\", \"test\", \"more\"]");
643 static mut DROPS
: i32 = 0;
653 let mut ring
= VecDeque
::new();
654 ring
.push_back(Elem
);
655 ring
.push_front(Elem
);
656 ring
.push_back(Elem
);
657 ring
.push_front(Elem
);
660 assert_eq
!(unsafe { DROPS }
, 4);
664 fn test_drop_with_pop() {
665 static mut DROPS
: i32 = 0;
675 let mut ring
= VecDeque
::new();
676 ring
.push_back(Elem
);
677 ring
.push_front(Elem
);
678 ring
.push_back(Elem
);
679 ring
.push_front(Elem
);
681 drop(ring
.pop_back());
682 drop(ring
.pop_front());
683 assert_eq
!(unsafe { DROPS }
, 2);
686 assert_eq
!(unsafe { DROPS }
, 4);
690 fn test_drop_clear() {
691 static mut DROPS
: i32 = 0;
701 let mut ring
= VecDeque
::new();
702 ring
.push_back(Elem
);
703 ring
.push_front(Elem
);
704 ring
.push_back(Elem
);
705 ring
.push_front(Elem
);
707 assert_eq
!(unsafe { DROPS }
, 4);
710 assert_eq
!(unsafe { DROPS }
, 4);
714 fn test_drop_panic() {
715 static mut DROPS
: i32 = 0;
726 panic
!("panic in `drop`");
731 let mut q
= VecDeque
::new();
732 q
.push_back(D(false));
733 q
.push_back(D(false));
734 q
.push_back(D(false));
735 q
.push_back(D(false));
736 q
.push_back(D(false));
737 q
.push_front(D(false));
738 q
.push_front(D(false));
739 q
.push_front(D(true));
741 catch_unwind(move || drop(q
)).ok();
743 assert_eq
!(unsafe { DROPS }
, 8);
747 fn test_reserve_grow() {
748 // test growth path A
749 // [T o o H] -> [T o o H . . . . ]
750 let mut ring
= VecDeque
::with_capacity(4);
756 assert_eq
!(ring
.pop_front(), Some(i
));
759 // test growth path B
760 // [H T o o] -> [. T o o H . . . ]
761 let mut ring
= VecDeque
::with_capacity(4);
764 assert_eq
!(ring
.pop_front(), Some(i
));
771 assert_eq
!(ring
.pop_front(), Some(i
));
774 // test growth path C
775 // [o o H T] -> [o o H . . . . T ]
776 let mut ring
= VecDeque
::with_capacity(4);
779 assert_eq
!(ring
.pop_front(), Some(i
));
786 assert_eq
!(ring
.pop_front(), Some(i
));
792 let mut ring
= VecDeque
::new();
794 assert_eq
!(ring
.get(0), Some(&0));
795 assert_eq
!(ring
.get(1), None
);
798 assert_eq
!(ring
.get(0), Some(&0));
799 assert_eq
!(ring
.get(1), Some(&1));
800 assert_eq
!(ring
.get(2), None
);
803 assert_eq
!(ring
.get(0), Some(&0));
804 assert_eq
!(ring
.get(1), Some(&1));
805 assert_eq
!(ring
.get(2), Some(&2));
806 assert_eq
!(ring
.get(3), None
);
808 assert_eq
!(ring
.pop_front(), Some(0));
809 assert_eq
!(ring
.get(0), Some(&1));
810 assert_eq
!(ring
.get(1), Some(&2));
811 assert_eq
!(ring
.get(2), None
);
813 assert_eq
!(ring
.pop_front(), Some(1));
814 assert_eq
!(ring
.get(0), Some(&2));
815 assert_eq
!(ring
.get(1), None
);
817 assert_eq
!(ring
.pop_front(), Some(2));
818 assert_eq
!(ring
.get(0), None
);
819 assert_eq
!(ring
.get(1), None
);
824 let mut ring
= VecDeque
::new();
829 match ring
.get_mut(1) {
834 assert_eq
!(ring
.get_mut(0), Some(&mut 0));
835 assert_eq
!(ring
.get_mut(1), Some(&mut -1));
836 assert_eq
!(ring
.get_mut(2), Some(&mut 2));
837 assert_eq
!(ring
.get_mut(3), None
);
839 assert_eq
!(ring
.pop_front(), Some(0));
840 assert_eq
!(ring
.get_mut(0), Some(&mut -1));
841 assert_eq
!(ring
.get_mut(1), Some(&mut 2));
842 assert_eq
!(ring
.get_mut(2), None
);
847 let mut ring
= VecDeque
::new();
850 assert_eq
!(ring
.front(), Some(&10));
852 assert_eq
!(ring
.front(), Some(&20));
854 assert_eq
!(ring
.front(), None
);
858 fn test_as_slices() {
859 let mut ring
: VecDeque
<i32> = VecDeque
::with_capacity(127);
860 let cap
= ring
.capacity() as i32;
862 let last
= cap
- first
;
866 let (left
, right
) = ring
.as_slices();
867 let expected
: Vec
<_
> = (0..=i
).collect();
868 assert_eq
!(left
, &expected
[..]);
869 assert_eq
!(right
, []);
874 let (left
, right
) = ring
.as_slices();
875 let expected_left
: Vec
<_
> = (-last
..=j
).rev().collect();
876 let expected_right
: Vec
<_
> = (0..first
).collect();
877 assert_eq
!(left
, &expected_left
[..]);
878 assert_eq
!(right
, &expected_right
[..]);
881 assert_eq
!(ring
.len() as i32, cap
);
882 assert_eq
!(ring
.capacity() as i32, cap
);
886 fn test_as_mut_slices() {
887 let mut ring
: VecDeque
<i32> = VecDeque
::with_capacity(127);
888 let cap
= ring
.capacity() as i32;
890 let last
= cap
- first
;
894 let (left
, right
) = ring
.as_mut_slices();
895 let expected
: Vec
<_
> = (0..=i
).collect();
896 assert_eq
!(left
, &expected
[..]);
897 assert_eq
!(right
, []);
902 let (left
, right
) = ring
.as_mut_slices();
903 let expected_left
: Vec
<_
> = (-last
..=j
).rev().collect();
904 let expected_right
: Vec
<_
> = (0..first
).collect();
905 assert_eq
!(left
, &expected_left
[..]);
906 assert_eq
!(right
, &expected_right
[..]);
909 assert_eq
!(ring
.len() as i32, cap
);
910 assert_eq
!(ring
.capacity() as i32, cap
);
915 let mut a
: VecDeque
<_
> = vec
![1, 2, 3].into_iter().collect();
916 let mut b
: VecDeque
<_
> = vec
![4, 5, 6].into_iter().collect();
920 assert_eq
!(a
.iter().cloned().collect
::<Vec
<_
>>(), [1, 2, 3, 4, 5, 6]);
921 assert_eq
!(b
.iter().cloned().collect
::<Vec
<_
>>(), []);
923 // append nothing to something
925 assert_eq
!(a
.iter().cloned().collect
::<Vec
<_
>>(), [1, 2, 3, 4, 5, 6]);
926 assert_eq
!(b
.iter().cloned().collect
::<Vec
<_
>>(), []);
928 // append something to nothing
930 assert_eq
!(b
.iter().cloned().collect
::<Vec
<_
>>(), [1, 2, 3, 4, 5, 6]);
931 assert_eq
!(a
.iter().cloned().collect
::<Vec
<_
>>(), []);
935 fn test_append_permutations() {
936 fn construct_vec_deque(
941 ) -> VecDeque
<usize> {
942 let mut out
= VecDeque
::new();
943 for a
in 0..push_back
{
946 for b
in 0..push_front
{
947 out
.push_front(push_back
+ b
);
949 for _
in 0..pop_back
{
952 for _
in 0..pop_front
{
958 #[cfg(not(miri))] // Miri is too slow
959 const MAX
: usize = 5;
961 const MAX
: usize = 3;
963 // Many different permutations of both the `VecDeque` getting appended to
964 // and the one getting appended are generated to check `append`.
965 // This ensures all 6 code paths of `append` are tested.
966 for src_push_back
in 0..MAX
{
967 for src_push_front
in 0..MAX
{
968 // doesn't pop more values than are pushed
969 for src_pop_back
in 0..(src_push_back
+ src_push_front
) {
970 for src_pop_front
in 0..(src_push_back
+ src_push_front
- src_pop_back
) {
971 let src
= construct_vec_deque(
978 for dst_push_back
in 0..MAX
{
979 for dst_push_front
in 0..MAX
{
980 for dst_pop_back
in 0..(dst_push_back
+ dst_push_front
) {
982 0..(dst_push_back
+ dst_push_front
- dst_pop_back
)
984 let mut dst
= construct_vec_deque(
990 let mut src
= src
.clone();
992 // Assert that appending `src` to `dst` gives the same order
993 // of values as iterating over both in sequence.
998 .collect
::<Vec
<usize>>();
999 dst
.append(&mut src
);
1000 assert_eq
!(dst
, correct
);
1001 assert
!(src
.is_empty());
1012 struct DropCounter
<'a
> {
1016 impl Drop
for DropCounter
<'_
> {
1017 fn drop(&mut self) {
1023 fn test_append_double_drop() {
1024 let (mut count_a
, mut count_b
) = (0, 0);
1026 let mut a
= VecDeque
::new();
1027 let mut b
= VecDeque
::new();
1028 a
.push_back(DropCounter { count: &mut count_a }
);
1029 b
.push_back(DropCounter { count: &mut count_b }
);
1033 assert_eq
!(count_a
, 1);
1034 assert_eq
!(count_b
, 1);
1039 let mut buf
= VecDeque
::new();
1041 buf
.retain(|&x
| x
% 2 == 0);
1042 let v
: Vec
<_
> = buf
.into_iter().collect();
1043 assert_eq
!(&v
[..], &[2, 4]);
1047 fn test_extend_ref() {
1048 let mut v
= VecDeque
::new();
1050 v
.extend(&[2, 3, 4]);
1052 assert_eq
!(v
.len(), 4);
1053 assert_eq
!(v
[0], 1);
1054 assert_eq
!(v
[1], 2);
1055 assert_eq
!(v
[2], 3);
1056 assert_eq
!(v
[3], 4);
1058 let mut w
= VecDeque
::new();
1063 assert_eq
!(v
.len(), 6);
1064 assert_eq
!(v
[0], 1);
1065 assert_eq
!(v
[1], 2);
1066 assert_eq
!(v
[2], 3);
1067 assert_eq
!(v
[3], 4);
1068 assert_eq
!(v
[4], 5);
1069 assert_eq
!(v
[5], 6);
1073 fn test_contains() {
1074 let mut v
= VecDeque
::new();
1075 v
.extend(&[2, 3, 4]);
1077 assert
!(v
.contains(&3));
1078 assert
!(!v
.contains(&1));
1082 assert
!(!v
.contains(&3));
1086 fn assert_covariance() {
1087 fn drain
<'new
>(d
: Drain
<'
static, &'
static str>) -> Drain
<'new
, &'new
str> {
1093 fn test_is_empty() {
1094 let mut v
= VecDeque
::<i32>::new();
1095 assert
!(v
.is_empty());
1096 assert
!(v
.iter().is_empty());
1097 assert
!(v
.iter_mut().is_empty());
1098 v
.extend(&[2, 3, 4]);
1099 assert
!(!v
.is_empty());
1100 assert
!(!v
.iter().is_empty());
1101 assert
!(!v
.iter_mut().is_empty());
1102 while let Some(_
) = v
.pop_front() {
1103 assert_eq
!(v
.is_empty(), v
.len() == 0);
1104 assert_eq
!(v
.iter().is_empty(), v
.iter().len() == 0);
1105 assert_eq
!(v
.iter_mut().is_empty(), v
.iter_mut().len() == 0);
1107 assert
!(v
.is_empty());
1108 assert
!(v
.iter().is_empty());
1109 assert
!(v
.iter_mut().is_empty());
1110 assert
!(v
.into_iter().is_empty());
1114 fn test_reserve_exact_2() {
1115 // This is all the same as test_reserve
1117 let mut v
= VecDeque
::new();
1120 assert
!(v
.capacity() >= 2);
1126 assert
!(v
.capacity() >= 16);
1127 v
.reserve_exact(16);
1128 assert
!(v
.capacity() >= 32);
1132 v
.reserve_exact(16);
1133 assert
!(v
.capacity() >= 48)
1137 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1138 fn test_try_reserve() {
1139 // These are the interesting cases:
1140 // * exactly isize::MAX should never trigger a CapacityOverflow (can be OOM)
1141 // * > isize::MAX should always fail
1142 // * On 16/32-bit should CapacityOverflow
1143 // * On 64-bit should OOM
1144 // * overflow may trigger when adding `len` to `cap` (in number of elements)
1145 // * overflow may trigger when multiplying `new_cap` by size_of::<T> (to get bytes)
1147 const MAX_CAP
: usize = (isize::MAX
as usize + 1) / 2 - 1;
1148 const MAX_USIZE
: usize = usize::MAX
;
1150 // On 16/32-bit, we check that allocations don't exceed isize::MAX,
1151 // on 64-bit, we assume the OS will give an OOM for such a ridiculous size.
1152 // Any platform that succeeds for these requests is technically broken with
1153 // ptr::offset because LLVM is the worst.
1154 let guards_against_isize
= size_of
::<usize>() < 8;
1157 // Note: basic stuff is checked by test_reserve
1158 let mut empty_bytes
: VecDeque
<u8> = VecDeque
::new();
1160 // Check isize::MAX doesn't count as an overflow
1161 if let Err(CapacityOverflow
) = empty_bytes
.try_reserve(MAX_CAP
) {
1162 panic
!("isize::MAX shouldn't trigger an overflow!");
1164 // Play it again, frank! (just to be sure)
1165 if let Err(CapacityOverflow
) = empty_bytes
.try_reserve(MAX_CAP
) {
1166 panic
!("isize::MAX shouldn't trigger an overflow!");
1169 if guards_against_isize
{
1170 // Check isize::MAX + 1 does count as overflow
1171 if let Err(CapacityOverflow
) = empty_bytes
.try_reserve(MAX_CAP
+ 1) {
1173 panic
!("isize::MAX + 1 should trigger an overflow!")
1176 // Check usize::MAX does count as overflow
1177 if let Err(CapacityOverflow
) = empty_bytes
.try_reserve(MAX_USIZE
) {
1179 panic
!("usize::MAX should trigger an overflow!")
1182 // Check isize::MAX is an OOM
1183 // VecDeque starts with capacity 7, always adds 1 to the capacity
1184 // and also rounds the number to next power of 2 so this is the
1185 // furthest we can go without triggering CapacityOverflow
1186 if let Err(AllocError { .. }
) = empty_bytes
.try_reserve(MAX_CAP
) {
1188 panic
!("isize::MAX + 1 should trigger an OOM!")
1194 // Same basic idea, but with non-zero len
1195 let mut ten_bytes
: VecDeque
<u8> = vec
![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1197 if let Err(CapacityOverflow
) = ten_bytes
.try_reserve(MAX_CAP
- 10) {
1198 panic
!("isize::MAX shouldn't trigger an overflow!");
1200 if let Err(CapacityOverflow
) = ten_bytes
.try_reserve(MAX_CAP
- 10) {
1201 panic
!("isize::MAX shouldn't trigger an overflow!");
1203 if guards_against_isize
{
1204 if let Err(CapacityOverflow
) = ten_bytes
.try_reserve(MAX_CAP
- 9) {
1206 panic
!("isize::MAX + 1 should trigger an overflow!");
1209 if let Err(AllocError { .. }
) = ten_bytes
.try_reserve(MAX_CAP
- 9) {
1211 panic
!("isize::MAX + 1 should trigger an OOM!")
1214 // Should always overflow in the add-to-len
1215 if let Err(CapacityOverflow
) = ten_bytes
.try_reserve(MAX_USIZE
) {
1217 panic
!("usize::MAX should trigger an overflow!")
1222 // Same basic idea, but with interesting type size
1223 let mut ten_u32s
: VecDeque
<u32> = vec
![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1225 if let Err(CapacityOverflow
) = ten_u32s
.try_reserve(MAX_CAP
/ 4 - 10) {
1226 panic
!("isize::MAX shouldn't trigger an overflow!");
1228 if let Err(CapacityOverflow
) = ten_u32s
.try_reserve(MAX_CAP
/ 4 - 10) {
1229 panic
!("isize::MAX shouldn't trigger an overflow!");
1231 if guards_against_isize
{
1232 if let Err(CapacityOverflow
) = ten_u32s
.try_reserve(MAX_CAP
/ 4 - 9) {
1234 panic
!("isize::MAX + 1 should trigger an overflow!");
1237 if let Err(AllocError { .. }
) = ten_u32s
.try_reserve(MAX_CAP
/ 4 - 9) {
1239 panic
!("isize::MAX + 1 should trigger an OOM!")
1242 // Should fail in the mul-by-size
1243 if let Err(CapacityOverflow
) = ten_u32s
.try_reserve(MAX_USIZE
- 20) {
1245 panic
!("usize::MAX should trigger an overflow!");
1251 #[cfg_attr(miri, ignore)] // Miri does not support signalling OOM
1252 fn test_try_reserve_exact() {
1253 // This is exactly the same as test_try_reserve with the method changed.
1254 // See that test for comments.
1256 const MAX_CAP
: usize = (isize::MAX
as usize + 1) / 2 - 1;
1257 const MAX_USIZE
: usize = usize::MAX
;
1259 let guards_against_isize
= size_of
::<usize>() < 8;
1262 let mut empty_bytes
: VecDeque
<u8> = VecDeque
::new();
1264 if let Err(CapacityOverflow
) = empty_bytes
.try_reserve_exact(MAX_CAP
) {
1265 panic
!("isize::MAX shouldn't trigger an overflow!");
1267 if let Err(CapacityOverflow
) = empty_bytes
.try_reserve_exact(MAX_CAP
) {
1268 panic
!("isize::MAX shouldn't trigger an overflow!");
1271 if guards_against_isize
{
1272 if let Err(CapacityOverflow
) = empty_bytes
.try_reserve_exact(MAX_CAP
+ 1) {
1274 panic
!("isize::MAX + 1 should trigger an overflow!")
1277 if let Err(CapacityOverflow
) = empty_bytes
.try_reserve_exact(MAX_USIZE
) {
1279 panic
!("usize::MAX should trigger an overflow!")
1282 // Check isize::MAX is an OOM
1283 // VecDeque starts with capacity 7, always adds 1 to the capacity
1284 // and also rounds the number to next power of 2 so this is the
1285 // furthest we can go without triggering CapacityOverflow
1286 if let Err(AllocError { .. }
) = empty_bytes
.try_reserve_exact(MAX_CAP
) {
1288 panic
!("isize::MAX + 1 should trigger an OOM!")
1294 let mut ten_bytes
: VecDeque
<u8> = vec
![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1296 if let Err(CapacityOverflow
) = ten_bytes
.try_reserve_exact(MAX_CAP
- 10) {
1297 panic
!("isize::MAX shouldn't trigger an overflow!");
1299 if let Err(CapacityOverflow
) = ten_bytes
.try_reserve_exact(MAX_CAP
- 10) {
1300 panic
!("isize::MAX shouldn't trigger an overflow!");
1302 if guards_against_isize
{
1303 if let Err(CapacityOverflow
) = ten_bytes
.try_reserve_exact(MAX_CAP
- 9) {
1305 panic
!("isize::MAX + 1 should trigger an overflow!");
1308 if let Err(AllocError { .. }
) = ten_bytes
.try_reserve_exact(MAX_CAP
- 9) {
1310 panic
!("isize::MAX + 1 should trigger an OOM!")
1313 if let Err(CapacityOverflow
) = ten_bytes
.try_reserve_exact(MAX_USIZE
) {
1315 panic
!("usize::MAX should trigger an overflow!")
1320 let mut ten_u32s
: VecDeque
<u32> = vec
![1, 2, 3, 4, 5, 6, 7, 8, 9, 10].into_iter().collect();
1322 if let Err(CapacityOverflow
) = ten_u32s
.try_reserve_exact(MAX_CAP
/ 4 - 10) {
1323 panic
!("isize::MAX shouldn't trigger an overflow!");
1325 if let Err(CapacityOverflow
) = ten_u32s
.try_reserve_exact(MAX_CAP
/ 4 - 10) {
1326 panic
!("isize::MAX shouldn't trigger an overflow!");
1328 if guards_against_isize
{
1329 if let Err(CapacityOverflow
) = ten_u32s
.try_reserve_exact(MAX_CAP
/ 4 - 9) {
1331 panic
!("isize::MAX + 1 should trigger an overflow!");
1334 if let Err(AllocError { .. }
) = ten_u32s
.try_reserve_exact(MAX_CAP
/ 4 - 9) {
1336 panic
!("isize::MAX + 1 should trigger an OOM!")
1339 if let Err(CapacityOverflow
) = ten_u32s
.try_reserve_exact(MAX_USIZE
- 20) {
1341 panic
!("usize::MAX should trigger an overflow!")
1347 fn test_rotate_nop() {
1348 let mut v
: VecDeque
<_
> = (0..10).collect();
1349 assert_unchanged(&v
);
1352 assert_unchanged(&v
);
1355 assert_unchanged(&v
);
1358 assert_unchanged(&v
);
1361 assert_unchanged(&v
);
1365 assert_unchanged(&v
);
1369 assert_unchanged(&v
);
1373 assert_unchanged(&v
);
1377 assert_unchanged(&v
);
1381 assert_unchanged(&v
);
1385 assert_unchanged(&v
);
1391 assert_unchanged(&v
);
1397 assert_unchanged(&v
);
1399 fn assert_unchanged(v
: &VecDeque
<i32>) {
1400 assert_eq
!(v
, &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
1405 fn test_rotate_left_parts() {
1406 let mut v
: VecDeque
<_
> = (1..=7).collect();
1408 assert_eq
!(v
.as_slices(), (&[3, 4, 5, 6, 7, 1][..], &[2][..]));
1410 assert_eq
!(v
.as_slices(), (&[5, 6, 7, 1][..], &[2, 3, 4][..]));
1412 assert_eq
!(v
.as_slices(), (&[7, 1][..], &[2, 3, 4, 5, 6][..]));
1414 assert_eq
!(v
.as_slices(), (&[2, 3, 4, 5, 6, 7, 1][..], &[][..]));
1416 assert_eq
!(v
.as_slices(), (&[4, 5, 6, 7, 1, 2][..], &[3][..]));
1418 assert_eq
!(v
.as_slices(), (&[6, 7, 1, 2][..], &[3, 4, 5][..]));
1420 assert_eq
!(v
.as_slices(), (&[1, 2][..], &[3, 4, 5, 6, 7][..]));
1424 fn test_rotate_right_parts() {
1425 let mut v
: VecDeque
<_
> = (1..=7).collect();
1427 assert_eq
!(v
.as_slices(), (&[6, 7][..], &[1, 2, 3, 4, 5][..]));
1429 assert_eq
!(v
.as_slices(), (&[4, 5, 6, 7][..], &[1, 2, 3][..]));
1431 assert_eq
!(v
.as_slices(), (&[2, 3, 4, 5, 6, 7][..], &[1][..]));
1433 assert_eq
!(v
.as_slices(), (&[7, 1, 2, 3, 4, 5, 6][..], &[][..]));
1435 assert_eq
!(v
.as_slices(), (&[5, 6][..], &[7, 1, 2, 3, 4][..]));
1437 assert_eq
!(v
.as_slices(), (&[3, 4, 5, 6][..], &[7, 1, 2][..]));
1439 assert_eq
!(v
.as_slices(), (&[1, 2, 3, 4, 5, 6][..], &[7][..]));
1443 fn test_rotate_left_random() {
1445 6, 1, 0, 11, 12, 1, 11, 7, 9, 3, 6, 1, 4, 0, 5, 1, 3, 1, 12, 8, 3, 1, 11, 11, 9, 4, 12, 3,
1446 12, 9, 11, 1, 7, 9, 7, 2,
1449 let mut v
: VecDeque
<_
> = (0..n
).collect();
1450 let mut total_shift
= 0;
1451 for shift
in shifts
.iter().cloned() {
1452 v
.rotate_left(shift
);
1453 total_shift
+= shift
;
1455 assert_eq
!(v
[i
], (i
+ total_shift
) % n
);
1461 fn test_rotate_right_random() {
1463 6, 1, 0, 11, 12, 1, 11, 7, 9, 3, 6, 1, 4, 0, 5, 1, 3, 1, 12, 8, 3, 1, 11, 11, 9, 4, 12, 3,
1464 12, 9, 11, 1, 7, 9, 7, 2,
1467 let mut v
: VecDeque
<_
> = (0..n
).collect();
1468 let mut total_shift
= 0;
1469 for shift
in shifts
.iter().cloned() {
1470 v
.rotate_right(shift
);
1471 total_shift
+= shift
;
1473 assert_eq
!(v
[(i
+ total_shift
) % n
], i
);
1479 fn test_try_fold_empty() {
1480 assert_eq
!(Some(0), VecDeque
::<u32>::new().iter().try_fold(0, |_
, _
| None
));
1484 fn test_try_fold_none() {
1485 let v
: VecDeque
<u32> = (0..12).collect();
1486 assert_eq
!(None
, v
.into_iter().try_fold(0, |a
, b
| if b
< 11 { Some(a + b) }
else { None }
));
1490 fn test_try_fold_ok() {
1491 let v
: VecDeque
<u32> = (0..12).collect();
1492 assert_eq
!(Ok
::<_
, ()>(66), v
.into_iter().try_fold(0, |a
, b
| Ok(a
+ b
)));
1496 fn test_try_fold_unit() {
1497 let v
: VecDeque
<()> = std
::iter
::repeat(()).take(42).collect();
1498 assert_eq
!(Some(()), v
.into_iter().try_fold((), |(), ()| Some(())));
1502 fn test_try_fold_unit_none() {
1503 let v
: std
::collections
::VecDeque
<()> = [(); 10].iter().cloned().collect();
1504 let mut iter
= v
.into_iter();
1505 assert
!(iter
.try_fold((), |_
, _
| None
).is_none());
1506 assert_eq
!(iter
.len(), 9);
1510 fn test_try_fold_rotated() {
1511 let mut v
: VecDeque
<_
> = (0..12).collect();
1518 assert_eq
!(Ok
::<_
, ()>(66), v
.iter().try_fold(0, |a
, b
| Ok(a
+ b
)));
1523 fn test_try_fold_moves_iter() {
1524 let v
: VecDeque
<_
> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect();
1525 let mut iter
= v
.into_iter();
1526 assert_eq
!(iter
.try_fold(0_i8, |acc
, &x
| acc
.checked_add(x
)), None
);
1527 assert_eq
!(iter
.next(), Some(&60));
1531 fn test_try_fold_exhaust_wrap() {
1532 let mut v
= VecDeque
::with_capacity(7);
1538 let mut iter
= v
.iter();
1539 let _
= iter
.try_fold(0, |_
, _
| Some(1));
1540 assert
!(iter
.is_empty());
1544 fn test_try_fold_wraparound() {
1545 let mut v
= VecDeque
::with_capacity(8);
1551 let mut iter
= v
.iter();
1552 let _
= iter
.find(|&&x
| x
== 2);
1553 assert_eq
!(Some(&7), iter
.next());
1557 fn test_try_rfold_rotated() {
1558 let mut v
: VecDeque
<_
> = (0..12).collect();
1565 assert_eq
!(Ok
::<_
, ()>(66), v
.iter().try_rfold(0, |a
, b
| Ok(a
+ b
)));
1570 fn test_try_rfold_moves_iter() {
1571 let v
: VecDeque
<_
> = [10, 20, 30, 40, 100, 60, 70, 80, 90].iter().collect();
1572 let mut iter
= v
.into_iter();
1573 assert_eq
!(iter
.try_rfold(0_i8, |acc
, &x
| acc
.checked_add(x
)), None
);
1574 assert_eq
!(iter
.next_back(), Some(&70));