1 use core
::iter
::TrustedLen
;
6 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
7 fn bench_push_back_100(b
: &mut test
::Bencher
) {
8 let mut deq
= VecDeque
::with_capacity(101);
19 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
20 fn bench_push_front_100(b
: &mut test
::Bencher
) {
21 let mut deq
= VecDeque
::with_capacity(101);
32 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
33 fn bench_pop_back_100(b
: &mut test
::Bencher
) {
34 let mut deq
= VecDeque
::<i32>::with_capacity(101);
39 while !deq
.is_empty() {
40 test
::black_box(deq
.pop_back());
46 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
47 fn bench_retain_whole_10000(b
: &mut test
::Bencher
) {
48 let v
= (1..100000).collect
::<VecDeque
<u32>>();
51 let mut v
= v
.clone();
57 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
58 fn bench_retain_odd_10000(b
: &mut test
::Bencher
) {
59 let v
= (1..100000).collect
::<VecDeque
<u32>>();
62 let mut v
= v
.clone();
63 v
.retain(|x
| x
& 1 == 0)
68 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
69 fn bench_retain_half_10000(b
: &mut test
::Bencher
) {
70 let v
= (1..100000).collect
::<VecDeque
<u32>>();
73 let mut v
= v
.clone();
74 v
.retain(|x
| *x
> 50000)
79 #[cfg_attr(miri, ignore)] // isolated Miri does not support benchmarks
80 fn bench_pop_front_100(b
: &mut test
::Bencher
) {
81 let mut deq
= VecDeque
::<i32>::with_capacity(101);
86 while !deq
.is_empty() {
87 test
::black_box(deq
.pop_front());
93 fn test_swap_front_back_remove() {
95 // This test checks that every single combination of tail position and length is tested.
96 // Capacity 15 should be large enough to cover every case.
97 let mut tester
= VecDeque
::with_capacity(15);
98 let usable_cap
= tester
.capacity();
99 let final_len
= usable_cap
/ 2;
101 for len
in 0..final_len
{
102 let expected
: VecDeque
<_
> =
103 if back { (0..len).collect() }
else { (0..len).rev().collect() }
;
104 for tail_pos
in 0..usable_cap
{
105 tester
.tail
= tail_pos
;
106 tester
.head
= tail_pos
;
108 for i
in 0..len
* 2 {
109 tester
.push_front(i
);
112 assert_eq
!(tester
.swap_remove_back(i
), Some(len
* 2 - 1 - i
));
115 for i
in 0..len
* 2 {
119 let idx
= tester
.len() - 1 - i
;
120 assert_eq
!(tester
.swap_remove_front(idx
), Some(len
* 2 - 1 - i
));
123 assert
!(tester
.tail
< tester
.cap());
124 assert
!(tester
.head
< tester
.cap());
125 assert_eq
!(tester
, expected
);
135 // This test checks that every single combination of tail position, length, and
136 // insertion position is tested. Capacity 15 should be large enough to cover every case.
138 let mut tester
= VecDeque
::with_capacity(15);
139 // can't guarantee we got 15, so have to get what we got.
140 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
141 // this test isn't covering what it wants to
142 let cap
= tester
.capacity();
144 // len is the length *after* insertion
145 let minlen
= if cfg
!(miri
) { cap - 1 }
else { 1 }
; // Miri is too slow
146 for len
in minlen
..cap
{
147 // 0, 1, 2, .., len - 1
148 let expected
= (0..).take(len
).collect
::<VecDeque
<_
>>();
149 for tail_pos
in 0..cap
{
150 for to_insert
in 0..len
{
151 tester
.tail
= tail_pos
;
152 tester
.head
= tail_pos
;
158 tester
.insert(to_insert
, to_insert
);
159 assert
!(tester
.tail
< tester
.cap());
160 assert
!(tester
.head
< tester
.cap());
161 assert_eq
!(tester
, expected
);
169 let mut tester
= VecDeque
::new();
174 assert_eq
!(tester
.len(), 3);
176 assert_eq
!(tester
.get(1), Some(&2));
177 assert_eq
!(tester
.get(2), Some(&3));
178 assert_eq
!(tester
.get(0), Some(&1));
179 assert_eq
!(tester
.get(3), None
);
183 assert_eq
!(tester
.len(), 2);
184 assert_eq
!(tester
.get(0), Some(&2));
185 assert_eq
!(tester
.get(1), Some(&3));
186 assert_eq
!(tester
.get(2), None
);
191 let mut tester
= VecDeque
::new();
196 assert_eq
!(tester
.len(), 3);
198 if let Some(elem
) = tester
.get_mut(0) {
199 assert_eq
!(*elem
, 1);
203 if let Some(elem
) = tester
.get_mut(2) {
204 assert_eq
!(*elem
, 3);
208 assert_eq
!(tester
.get(0), Some(&10));
209 assert_eq
!(tester
.get(2), Some(&30));
210 assert_eq
!(tester
.get_mut(3), None
);
214 assert_eq
!(tester
.len(), 2);
215 assert_eq
!(tester
.get(0), Some(&10));
216 assert_eq
!(tester
.get(1), Some(&2));
217 assert_eq
!(tester
.get(2), None
);
222 let mut tester
= VecDeque
::new();
227 assert_eq
!(tester
, [1, 2, 3]);
230 assert_eq
!(tester
, [1, 2, 3]);
232 assert_eq
!(tester
, [2, 1, 3]);
234 assert_eq
!(tester
, [2, 3, 1]);
236 assert_eq
!(tester
, [2, 1, 3]);
238 assert_eq
!(tester
, [3, 1, 2]);
240 assert_eq
!(tester
, [3, 1, 2]);
244 #[should_panic = "assertion failed: j < self.len()"]
245 fn test_swap_panic() {
246 let mut tester
= VecDeque
::new();
254 fn test_reserve_exact() {
255 let mut tester
: VecDeque
<i32> = VecDeque
::with_capacity(1);
256 assert
!(tester
.capacity() == 1);
257 tester
.reserve_exact(50);
258 assert
!(tester
.capacity() >= 51);
259 tester
.reserve_exact(40);
260 assert
!(tester
.capacity() >= 51);
261 tester
.reserve_exact(200);
262 assert
!(tester
.capacity() >= 200);
266 #[should_panic = "capacity overflow"]
267 fn test_reserve_exact_panic() {
268 let mut tester
: VecDeque
<i32> = VecDeque
::new();
269 tester
.reserve_exact(usize::MAX
);
273 fn test_try_reserve_exact() {
274 let mut tester
: VecDeque
<i32> = VecDeque
::with_capacity(1);
275 assert
!(tester
.capacity() == 1);
276 assert_eq
!(tester
.try_reserve_exact(100), Ok(()));
277 assert
!(tester
.capacity() >= 100);
278 assert_eq
!(tester
.try_reserve_exact(50), Ok(()));
279 assert
!(tester
.capacity() >= 100);
280 assert_eq
!(tester
.try_reserve_exact(200), Ok(()));
281 assert
!(tester
.capacity() >= 200);
282 assert_eq
!(tester
.try_reserve_exact(0), Ok(()));
283 assert
!(tester
.capacity() >= 200);
284 assert
!(tester
.try_reserve_exact(usize::MAX
).is_err());
288 fn test_try_reserve() {
289 let mut tester
: VecDeque
<i32> = VecDeque
::with_capacity(1);
290 assert
!(tester
.capacity() == 1);
291 assert_eq
!(tester
.try_reserve(100), Ok(()));
292 assert
!(tester
.capacity() >= 100);
293 assert_eq
!(tester
.try_reserve(50), Ok(()));
294 assert
!(tester
.capacity() >= 100);
295 assert_eq
!(tester
.try_reserve(200), Ok(()));
296 assert
!(tester
.capacity() >= 200);
297 assert_eq
!(tester
.try_reserve(0), Ok(()));
298 assert
!(tester
.capacity() >= 200);
299 assert
!(tester
.try_reserve(usize::MAX
).is_err());
304 let mut tester
= VecDeque
::new();
309 assert
!(tester
.contains(&1));
310 assert
!(tester
.contains(&3));
311 assert
!(!tester
.contains(&0));
312 assert
!(!tester
.contains(&4));
314 assert
!(!tester
.contains(&1));
315 assert
!(tester
.contains(&2));
316 assert
!(tester
.contains(&3));
320 fn test_rotate_left_right() {
321 let mut tester
: VecDeque
<_
> = (1..=10).collect();
323 assert_eq
!(tester
.len(), 10);
325 tester
.rotate_left(0);
326 assert_eq
!(tester
, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
328 tester
.rotate_right(0);
329 assert_eq
!(tester
, [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
331 tester
.rotate_left(3);
332 assert_eq
!(tester
, [4, 5, 6, 7, 8, 9, 10, 1, 2, 3]);
334 tester
.rotate_right(5);
335 assert_eq
!(tester
, [9, 10, 1, 2, 3, 4, 5, 6, 7, 8]);
337 tester
.rotate_left(tester
.len());
338 assert_eq
!(tester
, [9, 10, 1, 2, 3, 4, 5, 6, 7, 8]);
340 tester
.rotate_right(tester
.len());
341 assert_eq
!(tester
, [9, 10, 1, 2, 3, 4, 5, 6, 7, 8]);
343 tester
.rotate_left(1);
344 assert_eq
!(tester
, [10, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
348 #[should_panic = "assertion failed: mid <= self.len()"]
349 fn test_rotate_left_panic() {
350 let mut tester
: VecDeque
<_
> = (1..=10).collect();
351 tester
.rotate_left(tester
.len() + 1);
355 #[should_panic = "assertion failed: k <= self.len()"]
356 fn test_rotate_right_panic() {
357 let mut tester
: VecDeque
<_
> = (1..=10).collect();
358 tester
.rotate_right(tester
.len() + 1);
362 fn test_binary_search() {
363 // If the givin VecDeque is not sorted, the returned result is unspecified and meaningless,
364 // as this method performs a binary search.
366 let tester
: VecDeque
<_
> = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
368 assert_eq
!(tester
.binary_search(&0), Ok(0));
369 assert_eq
!(tester
.binary_search(&5), Ok(5));
370 assert_eq
!(tester
.binary_search(&55), Ok(10));
371 assert_eq
!(tester
.binary_search(&4), Err(5));
372 assert_eq
!(tester
.binary_search(&-1), Err(0));
373 assert
!(matches
!(tester
.binary_search(&1), Ok(1..=2)));
375 let tester
: VecDeque
<_
> = [1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3].into();
376 assert_eq
!(tester
.binary_search(&1), Ok(0));
377 assert
!(matches
!(tester
.binary_search(&2), Ok(1..=4)));
378 assert
!(matches
!(tester
.binary_search(&3), Ok(5..=13)));
379 assert_eq
!(tester
.binary_search(&-2), Err(0));
380 assert_eq
!(tester
.binary_search(&0), Err(0));
381 assert_eq
!(tester
.binary_search(&4), Err(14));
382 assert_eq
!(tester
.binary_search(&5), Err(14));
386 fn test_binary_search_by() {
387 // If the givin VecDeque is not sorted, the returned result is unspecified and meaningless,
388 // as this method performs a binary search.
390 let tester
: VecDeque
<_
> = [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55].into();
392 assert_eq
!(tester
.binary_search_by(|x
| x
.cmp(&0)), Ok(0));
393 assert_eq
!(tester
.binary_search_by(|x
| x
.cmp(&5)), Ok(5));
394 assert_eq
!(tester
.binary_search_by(|x
| x
.cmp(&55)), Ok(10));
395 assert_eq
!(tester
.binary_search_by(|x
| x
.cmp(&4)), Err(5));
396 assert_eq
!(tester
.binary_search_by(|x
| x
.cmp(&-1)), Err(0));
397 assert
!(matches
!(tester
.binary_search_by(|x
| x
.cmp(&1)), Ok(1..=2)));
401 fn test_binary_search_key() {
402 // If the givin VecDeque is not sorted, the returned result is unspecified and meaningless,
403 // as this method performs a binary search.
405 let tester
: VecDeque
<_
> = [
422 assert_eq
!(tester
.binary_search_by_key(&-1, |&(a
, _b
)| a
), Ok(0));
423 assert_eq
!(tester
.binary_search_by_key(&8, |&(a
, _b
)| a
), Ok(4));
424 assert_eq
!(tester
.binary_search_by_key(&25, |&(a
, _b
)| a
), Ok(8));
425 assert_eq
!(tester
.binary_search_by_key(&54, |&(a
, _b
)| a
), Ok(12));
426 assert_eq
!(tester
.binary_search_by_key(&-2, |&(a
, _b
)| a
), Err(0));
427 assert_eq
!(tester
.binary_search_by_key(&1, |&(a
, _b
)| a
), Err(1));
428 assert_eq
!(tester
.binary_search_by_key(&4, |&(a
, _b
)| a
), Err(2));
429 assert_eq
!(tester
.binary_search_by_key(&13, |&(a
, _b
)| a
), Err(6));
430 assert_eq
!(tester
.binary_search_by_key(&55, |&(a
, _b
)| a
), Err(13));
431 assert_eq
!(tester
.binary_search_by_key(&100, |&(a
, _b
)| a
), Err(13));
433 let tester
: VecDeque
<_
> = [
450 assert_eq
!(tester
.binary_search_by_key(&0, |&(_a
, b
)| b
), Ok(0));
451 assert
!(matches
!(tester
.binary_search_by_key(&1, |&(_a
, b
)| b
), Ok(1..=4)));
452 assert_eq
!(tester
.binary_search_by_key(&8, |&(_a
, b
)| b
), Ok(8));
453 assert_eq
!(tester
.binary_search_by_key(&13, |&(_a
, b
)| b
), Ok(9));
454 assert_eq
!(tester
.binary_search_by_key(&55, |&(_a
, b
)| b
), Ok(12));
455 assert_eq
!(tester
.binary_search_by_key(&-1, |&(_a
, b
)| b
), Err(0));
456 assert_eq
!(tester
.binary_search_by_key(&4, |&(_a
, b
)| b
), Err(7));
457 assert_eq
!(tester
.binary_search_by_key(&56, |&(_a
, b
)| b
), Err(13));
458 assert_eq
!(tester
.binary_search_by_key(&100, |&(_a
, b
)| b
), Err(13));
462 fn make_contiguous_big_tail() {
463 let mut tester
= VecDeque
::with_capacity(15);
470 tester
.push_front(i
);
474 assert_eq
!(tester
.capacity(), 15);
475 assert_eq
!((&[9, 8, 7, 6, 5, 4, 3] as &[_
], &[0, 1, 2] as &[_
]), tester
.as_slices());
477 let expected_start
= tester
.head
;
478 tester
.make_contiguous();
479 assert_eq
!(tester
.tail
, expected_start
);
480 assert_eq
!((&[9, 8, 7, 6, 5, 4, 3, 0, 1, 2] as &[_
], &[] as &[_
]), tester
.as_slices());
484 fn make_contiguous_big_head() {
485 let mut tester
= VecDeque
::with_capacity(15);
492 tester
.push_front(i
);
496 let expected_start
= 0;
497 tester
.make_contiguous();
498 assert_eq
!(tester
.tail
, expected_start
);
499 assert_eq
!((&[9, 8, 0, 1, 2, 3, 4, 5, 6, 7] as &[_
], &[] as &[_
]), tester
.as_slices());
503 fn make_contiguous_small_free() {
504 let mut tester
= VecDeque
::with_capacity(15);
506 for i
in 'A'
as u8..'I'
as u8 {
507 tester
.push_back(i
as char);
510 for i
in 'I'
as u8..'N'
as u8 {
511 tester
.push_front(i
as char);
515 let expected_start
= 0;
516 tester
.make_contiguous();
517 assert_eq
!(tester
.tail
, expected_start
);
519 (&['M'
, 'L'
, 'K'
, 'J'
, 'I'
, 'A'
, 'B'
, 'C'
, 'D'
, 'E'
, 'F'
, 'G'
, 'H'
] as &[_
], &[] as &[_
]),
524 for i
in 'I'
as u8..'N'
as u8 {
525 tester
.push_back(i
as char);
528 for i
in 'A'
as u8..'I'
as u8 {
529 tester
.push_front(i
as char);
533 let expected_start
= 0;
534 tester
.make_contiguous();
535 assert_eq
!(tester
.tail
, expected_start
);
537 (&['H'
, 'G'
, 'F'
, 'E'
, 'D'
, 'C'
, 'B'
, 'A'
, 'I'
, 'J'
, 'K'
, 'L'
, 'M'
] as &[_
], &[] as &[_
]),
543 fn make_contiguous_head_to_end() {
544 let mut dq
= VecDeque
::with_capacity(3);
548 dq
.make_contiguous();
549 let expected_tail
= 0;
550 let expected_head
= 3;
551 assert_eq
!(expected_tail
, dq
.tail
);
552 assert_eq
!(expected_head
, dq
.head
);
553 assert_eq
!((&['A'
, 'B'
, 'C'
] as &[_
], &[] as &[_
]), dq
.as_slices());
557 fn make_contiguous_head_to_end_2() {
558 // Another test case for #79808, taken from #80293.
560 let mut dq
= VecDeque
::from_iter(0..6);
566 dq
.make_contiguous();
567 let collected
: Vec
<_
> = dq
.iter().copied().collect();
568 assert_eq
!(dq
.as_slices(), (&collected
[..], &[] as &[_
]));
573 // This test checks that every single combination of tail position, length, and
574 // removal position is tested. Capacity 15 should be large enough to cover every case.
576 let mut tester
= VecDeque
::with_capacity(15);
577 // can't guarantee we got 15, so have to get what we got.
578 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
579 // this test isn't covering what it wants to
580 let cap
= tester
.capacity();
582 // len is the length *after* removal
583 let minlen
= if cfg
!(miri
) { cap - 2 }
else { 0 }
; // Miri is too slow
584 for len
in minlen
..cap
- 1 {
585 // 0, 1, 2, .., len - 1
586 let expected
= (0..).take(len
).collect
::<VecDeque
<_
>>();
587 for tail_pos
in 0..cap
{
588 for to_remove
in 0..=len
{
589 tester
.tail
= tail_pos
;
590 tester
.head
= tail_pos
;
593 tester
.push_back(1234);
597 if to_remove
== len
{
598 tester
.push_back(1234);
600 tester
.remove(to_remove
);
601 assert
!(tester
.tail
< tester
.cap());
602 assert
!(tester
.head
< tester
.cap());
603 assert_eq
!(tester
, expected
);
611 let mut tester
: VecDeque
<usize> = VecDeque
::with_capacity(7);
613 let cap
= tester
.capacity();
614 let minlen
= if cfg
!(miri
) { cap - 1 }
else { 0 }
; // Miri is too slow
615 for len
in minlen
..=cap
{
616 for tail
in 0..=cap
{
617 for start
in 0..=len
{
618 for end
in start
..=len
{
625 // Check that we iterate over the correct values
626 let range
: VecDeque
<_
> = tester
.range(start
..end
).copied().collect();
627 let expected
: VecDeque
<_
> = (start
..end
).collect();
628 assert_eq
!(range
, expected
);
636 fn test_range_mut() {
637 let mut tester
: VecDeque
<usize> = VecDeque
::with_capacity(7);
639 let cap
= tester
.capacity();
641 for tail
in 0..=cap
{
642 for start
in 0..=len
{
643 for end
in start
..=len
{
650 let head_was
= tester
.head
;
651 let tail_was
= tester
.tail
;
653 // Check that we iterate over the correct values
654 let range
: VecDeque
<_
> = tester
.range_mut(start
..end
).map(|v
| *v
).collect();
655 let expected
: VecDeque
<_
> = (start
..end
).collect();
656 assert_eq
!(range
, expected
);
658 // We shouldn't have changed the capacity or made the
659 // head or tail out of bounds
660 assert_eq
!(tester
.capacity(), cap
);
661 assert_eq
!(tester
.tail
, tail_was
);
662 assert_eq
!(tester
.head
, head_was
);
671 let mut tester
: VecDeque
<usize> = VecDeque
::with_capacity(7);
673 let cap
= tester
.capacity();
675 for tail
in 0..=cap
{
676 for drain_start
in 0..=len
{
677 for drain_end
in drain_start
..=len
{
684 // Check that we drain the correct values
685 let drained
: VecDeque
<_
> = tester
.drain(drain_start
..drain_end
).collect();
686 let drained_expected
: VecDeque
<_
> = (drain_start
..drain_end
).collect();
687 assert_eq
!(drained
, drained_expected
);
689 // We shouldn't have changed the capacity or made the
690 // head or tail out of bounds
691 assert_eq
!(tester
.capacity(), cap
);
692 assert
!(tester
.tail
< tester
.cap());
693 assert
!(tester
.head
< tester
.cap());
695 // We should see the correct values in the VecDeque
696 let expected
: VecDeque
<_
> = (0..drain_start
).chain(drain_end
..len
).collect();
697 assert_eq
!(expected
, tester
);
705 fn test_shrink_to_fit() {
706 // This test checks that every single combination of head and tail position,
707 // is tested. Capacity 15 should be large enough to cover every case.
709 let mut tester
= VecDeque
::with_capacity(15);
710 // can't guarantee we got 15, so have to get what we got.
711 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
712 // this test isn't covering what it wants to
713 let cap
= tester
.capacity();
715 let max_cap
= tester
.capacity();
718 // 0, 1, 2, .., len - 1
719 let expected
= (0..).take(len
).collect
::<VecDeque
<_
>>();
720 for tail_pos
in 0..=max_cap
{
721 tester
.tail
= tail_pos
;
722 tester
.head
= tail_pos
;
727 tester
.shrink_to_fit();
728 assert
!(tester
.capacity() <= cap
);
729 assert
!(tester
.tail
< tester
.cap());
730 assert
!(tester
.head
< tester
.cap());
731 assert_eq
!(tester
, expected
);
737 fn test_split_off() {
738 // This test checks that every single combination of tail position, length, and
739 // split position is tested. Capacity 15 should be large enough to cover every case.
741 let mut tester
= VecDeque
::with_capacity(15);
742 // can't guarantee we got 15, so have to get what we got.
743 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
744 // this test isn't covering what it wants to
745 let cap
= tester
.capacity();
747 // len is the length *before* splitting
748 let minlen
= if cfg
!(miri
) { cap - 1 }
else { 0 }
; // Miri is too slow
749 for len
in minlen
..cap
{
752 // 0, 1, 2, .., at - 1 (may be empty)
753 let expected_self
= (0..).take(at
).collect
::<VecDeque
<_
>>();
754 // at, at + 1, .., len - 1 (may be empty)
755 let expected_other
= (at
..).take(len
- at
).collect
::<VecDeque
<_
>>();
757 for tail_pos
in 0..cap
{
758 tester
.tail
= tail_pos
;
759 tester
.head
= tail_pos
;
763 let result
= tester
.split_off(at
);
764 assert
!(tester
.tail
< tester
.cap());
765 assert
!(tester
.head
< tester
.cap());
766 assert
!(result
.tail
< result
.cap());
767 assert
!(result
.head
< result
.cap());
768 assert_eq
!(tester
, expected_self
);
769 assert_eq
!(result
, expected_other
);
780 let mut vec
= Vec
::with_capacity(cap
);
783 let vd
= VecDeque
::from(vec
.clone());
784 assert
!(vd
.cap().is_power_of_two());
785 assert_eq
!(vd
.len(), vec
.len());
786 assert
!(vd
.into_iter().eq(vec
));
790 let vec
= Vec
::from([(); MAXIMUM_ZST_CAPACITY
- 1]);
791 let vd
= VecDeque
::from(vec
.clone());
792 assert
!(vd
.cap().is_power_of_two());
793 assert_eq
!(vd
.len(), vec
.len());
797 fn test_extend_basic() {
798 test_extend_impl(false);
802 fn test_extend_trusted_len() {
803 test_extend_impl(true);
806 fn test_extend_impl(trusted_len
: bool
) {
807 struct VecDequeTester
{
808 test
: VecDeque
<usize>,
809 expected
: VecDeque
<usize>,
813 impl VecDequeTester
{
814 fn new(trusted_len
: bool
) -> Self {
815 Self { test: VecDeque::new(), expected: VecDeque::new(), trusted_len }
818 fn test_extend
<I
>(&mut self, iter
: I
)
820 I
: Iterator
<Item
= usize> + TrustedLen
+ Clone
,
822 struct BasicIterator
<I
>(I
);
823 impl<I
> Iterator
for BasicIterator
<I
>
825 I
: Iterator
<Item
= usize>,
829 fn next(&mut self) -> Option
<Self::Item
> {
834 if self.trusted_len
{
835 self.test
.extend(iter
.clone());
837 self.test
.extend(BasicIterator(iter
.clone()));
841 self.expected
.push_back(item
)
844 assert_eq
!(self.test
, self.expected
);
845 let (a1
, b1
) = self.test
.as_slices();
846 let (a2
, b2
) = self.expected
.as_slices();
851 fn drain
<R
: RangeBounds
<usize> + Clone
>(&mut self, range
: R
) {
852 self.test
.drain(range
.clone());
853 self.expected
.drain(range
);
855 assert_eq
!(self.test
, self.expected
);
858 fn clear(&mut self) {
860 self.expected
.clear();
863 fn remaining_capacity(&self) -> usize {
864 self.test
.capacity() - self.test
.len()
868 let mut tester
= VecDequeTester
::new(trusted_len
);
871 tester
.test_extend(0..tester
.remaining_capacity() - 1);
874 tester
.test_extend(1024..2048);
879 tester
.test_extend(0..tester
.remaining_capacity() - 1);
883 tester
.test_extend(4096..8196);
888 tester
.test_extend(0..32);
892 #[should_panic = "capacity overflow"]
893 fn test_from_vec_zst_overflow() {
895 let vec
= Vec
::from([(); MAXIMUM_ZST_CAPACITY
]);
896 let vd
= VecDeque
::from(vec
.clone()); // no room for +1
897 assert
!(vd
.cap().is_power_of_two());
898 assert_eq
!(vd
.len(), vec
.len());
902 fn test_from_array() {
903 fn test
<const N
: usize>() {
904 let mut array
: [usize; N
] = [0; N
];
910 let deq
: VecDeque
<_
> = array
.into();
913 assert_eq
!(deq
[i
], i
);
916 assert
!(deq
.cap().is_power_of_two());
917 assert_eq
!(deq
.len(), N
);
925 let array
= [(); MAXIMUM_ZST_CAPACITY
- 1];
926 let deq
= VecDeque
::from(array
);
927 assert
!(deq
.cap().is_power_of_two());
928 assert_eq
!(deq
.len(), MAXIMUM_ZST_CAPACITY
- 1);
932 fn test_vec_from_vecdeque() {
935 fn create_vec_and_test_convert(capacity
: usize, offset
: usize, len
: usize) {
936 let mut vd
= VecDeque
::with_capacity(capacity
);
943 let vec
: Vec
<_
> = Vec
::from(vd
.clone());
944 assert_eq
!(vec
.len(), vd
.len());
945 assert
!(vec
.into_iter().eq(vd
));
949 let max_pwr
= if cfg
!(miri
) { 5 }
else { 7 }
;
951 for cap_pwr
in 0..max_pwr
{
952 // Make capacity as a (2^x)-1, so that the ring size is 2^x
953 let cap
= (2i32.pow(cap_pwr
) - 1) as usize;
955 // In these cases there is enough free space to solve it with copies
956 for len
in 0..((cap
+ 1) / 2) {
957 // Test contiguous cases
958 for offset
in 0..(cap
- len
) {
959 create_vec_and_test_convert(cap
, offset
, len
)
962 // Test cases where block at end of buffer is bigger than block at start
963 for offset
in (cap
- len
)..(cap
- (len
/ 2)) {
964 create_vec_and_test_convert(cap
, offset
, len
)
967 // Test cases where block at start of buffer is bigger than block at end
968 for offset
in (cap
- (len
/ 2))..cap
{
969 create_vec_and_test_convert(cap
, offset
, len
)
973 // Now there's not (necessarily) space to straighten the ring with simple copies,
974 // the ring will use swapping when:
975 // (cap + 1 - offset) > (cap + 1 - len) && (len - (cap + 1 - offset)) > (cap + 1 - len))
976 // right block size > free space && left block size > free space
977 for len
in ((cap
+ 1) / 2)..cap
{
978 // Test contiguous cases
979 for offset
in 0..(cap
- len
) {
980 create_vec_and_test_convert(cap
, offset
, len
)
983 // Test cases where block at end of buffer is bigger than block at start
984 for offset
in (cap
- len
)..(cap
- (len
/ 2)) {
985 create_vec_and_test_convert(cap
, offset
, len
)
988 // Test cases where block at start of buffer is bigger than block at end
989 for offset
in (cap
- (len
/ 2))..cap
{
990 create_vec_and_test_convert(cap
, offset
, len
)
997 fn test_clone_from() {
1000 let limit
= if cfg
!(miri
) { 4 }
else { 8 }
; // Miri is too slow
1001 for pfv
in 0..limit
{
1002 for pfu
in 0..limit
{
1003 for longer
in 0..2 {
1004 let (vr
, ur
) = if longer
== 0 { (&m, &n) }
else { (&n, &m) }
;
1005 let mut v
= VecDeque
::from(vr
.clone());
1009 let mut u
= VecDeque
::from(ur
.clone());
1021 fn test_vec_deque_truncate_drop() {
1022 static mut DROPS
: u32 = 0;
1025 impl Drop
for Elem
{
1026 fn drop(&mut self) {
1033 let v
= vec
![Elem(1), Elem(2), Elem(3), Elem(4), Elem(5)];
1034 for push_front
in 0..=v
.len() {
1036 let mut tester
= VecDeque
::with_capacity(5);
1037 for (index
, elem
) in v
.into_iter().enumerate() {
1038 if index
< push_front
{
1039 tester
.push_front(elem
);
1041 tester
.push_back(elem
);
1044 assert_eq
!(unsafe { DROPS }
, 0);
1046 assert_eq
!(unsafe { DROPS }
, 2);
1048 assert_eq
!(unsafe { DROPS }
, 5);
1057 use crate::boxed
::Box
;
1059 let mut dst
= VecDeque
::new();
1060 dst
.push_front(Box
::new(1));
1061 dst
.push_front(Box
::new(2));
1062 assert_eq
!(*dst
.pop_back().unwrap(), 1);
1064 let mut src
= VecDeque
::new();
1065 src
.push_front(Box
::new(2));
1066 dst
.append(&mut src
);
1075 use core
::num
::Wrapping
;
1077 // This is a valid, albeit rather bad hash function implementation.
1078 struct SimpleHasher(Wrapping
<u64>);
1080 impl Hasher
for SimpleHasher
{
1081 fn finish(&self) -> u64 {
1085 fn write(&mut self, bytes
: &[u8]) {
1086 // This particular implementation hashes value 24 in addition to bytes.
1087 // Such an implementation is valid as Hasher only guarantees equivalence
1088 // for the exact same set of calls to its methods.
1089 for &v
in iter
::once(&24).chain(bytes
) {
1090 self.0 = Wrapping(31) * self.0 + Wrapping(u64::from(v
));
1095 fn hash_code(value
: impl Hash
) -> u64 {
1096 let mut hasher
= SimpleHasher(Wrapping(1));
1097 value
.hash(&mut hasher
);
1101 // This creates two deques for which values returned by as_slices
1103 let vda
: VecDeque
<u8> = (0..10).collect();
1104 let mut vdb
= VecDeque
::with_capacity(10);
1106 (0..5).rev().for_each(|elem
| vdb
.push_front(elem
));
1107 assert_ne
!(vda
.as_slices(), vdb
.as_slices());
1108 assert_eq
!(vda
, vdb
);
1109 assert_eq
!(hash_code(vda
), hash_code(vdb
));