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 //! VecDeque is a double-ended queue, which is implemented with the help of a
12 //! growing ring buffer.
14 //! This queue has `O(1)` amortized inserts and removals from both ends of the
15 //! container. It also has `O(1)` indexing like a vector. The contained elements
16 //! are not required to be copyable, and the queue will be sendable if the
17 //! contained type is sendable.
19 #![stable(feature = "rust1", since = "1.0.0")]
21 use core
::cmp
::Ordering
;
23 use core
::iter
::{repeat, FromIterator}
;
25 use core
::ops
::{Index, IndexMut}
;
30 use core
::hash
::{Hash, Hasher}
;
33 use alloc
::raw_vec
::RawVec
;
35 const INITIAL_CAPACITY
: usize = 7; // 2^3 - 1
36 const MINIMUM_CAPACITY
: usize = 1; // 2 - 1
37 const MAXIMUM_ZST_CAPACITY
: usize = 1 << (usize::BITS
- 1); // Largest possible power of two
39 /// `VecDeque` is a growable ring buffer, which can be used as a
40 /// double-ended queue efficiently.
42 /// The "default" usage of this type as a queue is to use `push_back` to add to the queue, and
43 /// `pop_front` to remove from the queue. `extend` and `append` push onto the back in this manner,
44 /// and iterating over `VecDeque` goes front to back.
45 #[stable(feature = "rust1", since = "1.0.0")]
46 pub struct VecDeque
<T
> {
47 // tail and head are pointers into the buffer. Tail always points
48 // to the first element that could be read, Head always points
49 // to where data should be written.
50 // If tail == head the buffer is empty. The length of the ringbuffer
51 // is defined as the distance between the two.
58 #[stable(feature = "rust1", since = "1.0.0")]
59 impl<T
: Clone
> Clone
for VecDeque
<T
> {
60 fn clone(&self) -> VecDeque
<T
> {
61 self.iter().cloned().collect()
65 #[stable(feature = "rust1", since = "1.0.0")]
66 impl<T
> Drop
for VecDeque
<T
> {
69 // RawVec handles deallocation
73 #[stable(feature = "rust1", since = "1.0.0")]
74 impl<T
> Default
for VecDeque
<T
> {
76 fn default() -> VecDeque
<T
> { VecDeque::new() }
80 /// Marginally more convenient
82 fn ptr(&self) -> *mut T
{
86 /// Marginally more convenient
88 fn cap(&self) -> usize {
89 if mem
::size_of
::<T
>() == 0 {
90 // For zero sized types, we are always at maximum capacity
97 /// Turn ptr into a slice
99 unsafe fn buffer_as_slice(&self) -> &[T
] {
100 slice
::from_raw_parts(self.ptr(), self.cap())
103 /// Turn ptr into a mut slice
105 unsafe fn buffer_as_mut_slice(&mut self) -> &mut [T
] {
106 slice
::from_raw_parts_mut(self.ptr(), self.cap())
109 /// Moves an element out of the buffer
111 unsafe fn buffer_read(&mut self, off
: usize) -> T
{
112 ptr
::read(self.ptr().offset(off
as isize))
115 /// Writes an element into the buffer, moving it.
117 unsafe fn buffer_write(&mut self, off
: usize, value
: T
) {
118 ptr
::write(self.ptr().offset(off
as isize), value
);
121 /// Returns true if and only if the buffer is at capacity
123 fn is_full(&self) -> bool { self.cap() - self.len() == 1 }
125 /// Returns the index in the underlying buffer for a given logical element
128 fn wrap_index(&self, idx
: usize) -> usize { wrap_index(idx, self.cap()) }
130 /// Returns the index in the underlying buffer for a given logical element
133 fn wrap_add(&self, idx
: usize, addend
: usize) -> usize {
134 wrap_index(idx
.wrapping_add(addend
), self.cap())
137 /// Returns the index in the underlying buffer for a given logical element
138 /// index - subtrahend.
140 fn wrap_sub(&self, idx
: usize, subtrahend
: usize) -> usize {
141 wrap_index(idx
.wrapping_sub(subtrahend
), self.cap())
144 /// Copies a contiguous block of memory len long from src to dst
146 unsafe fn copy(&self, dst
: usize, src
: usize, len
: usize) {
147 debug_assert
!(dst
+ len
<= self.cap(), "dst={} src={} len={} cap={}", dst
, src
, len
,
149 debug_assert
!(src
+ len
<= self.cap(), "dst={} src={} len={} cap={}", dst
, src
, len
,
152 self.ptr().offset(src
as isize),
153 self.ptr().offset(dst
as isize),
157 /// Copies a contiguous block of memory len long from src to dst
159 unsafe fn copy_nonoverlapping(&self, dst
: usize, src
: usize, len
: usize) {
160 debug_assert
!(dst
+ len
<= self.cap(), "dst={} src={} len={} cap={}", dst
, src
, len
,
162 debug_assert
!(src
+ len
<= self.cap(), "dst={} src={} len={} cap={}", dst
, src
, len
,
164 ptr
::copy_nonoverlapping(
165 self.ptr().offset(src
as isize),
166 self.ptr().offset(dst
as isize),
170 /// Frobs the head and tail sections around to handle the fact that we
171 /// just reallocated. Unsafe because it trusts old_cap.
173 unsafe fn handle_cap_increase(&mut self, old_cap
: usize) {
174 let new_cap
= self.cap();
176 // Move the shortest contiguous section of the ring buffer
178 // [o o o o o o o . ]
180 // A [o o o o o o o . . . . . . . . . ]
182 // [o o . o o o o o ]
184 // B [. . . o o o o o o o . . . . . . ]
186 // [o o o o o . o o ]
188 // C [o o o o o . . . . . . . . . o o ]
190 if self.tail
<= self.head
{ // A
192 } else if self.head
< old_cap
- self.tail
{ // B
193 self.copy_nonoverlapping(old_cap
, 0, self.head
);
194 self.head
+= old_cap
;
195 debug_assert
!(self.head
> self.tail
);
197 let new_tail
= new_cap
- (old_cap
- self.tail
);
198 self.copy_nonoverlapping(new_tail
, self.tail
, old_cap
- self.tail
);
199 self.tail
= new_tail
;
200 debug_assert
!(self.head
< self.tail
);
202 debug_assert
!(self.head
< self.cap());
203 debug_assert
!(self.tail
< self.cap());
204 debug_assert
!(self.cap().count_ones() == 1);
208 impl<T
> VecDeque
<T
> {
209 /// Creates an empty `VecDeque`.
210 #[stable(feature = "rust1", since = "1.0.0")]
211 pub fn new() -> VecDeque
<T
> {
212 VecDeque
::with_capacity(INITIAL_CAPACITY
)
215 /// Creates an empty `VecDeque` with space for at least `n` elements.
216 #[stable(feature = "rust1", since = "1.0.0")]
217 pub fn with_capacity(n
: usize) -> VecDeque
<T
> {
218 // +1 since the ringbuffer always leaves one space empty
219 let cap
= cmp
::max(n
+ 1, MINIMUM_CAPACITY
+ 1).next_power_of_two();
220 assert
!(cap
> n
, "capacity overflow");
225 buf
: RawVec
::with_capacity(cap
),
229 /// Retrieves an element in the `VecDeque` by index.
234 /// use std::collections::VecDeque;
236 /// let mut buf = VecDeque::new();
237 /// buf.push_back(3);
238 /// buf.push_back(4);
239 /// buf.push_back(5);
240 /// assert_eq!(buf.get(1), Some(&4));
242 #[stable(feature = "rust1", since = "1.0.0")]
243 pub fn get(&self, index
: usize) -> Option
<&T
> {
244 if index
< self.len() {
245 let idx
= self.wrap_add(self.tail
, index
);
246 unsafe { Some(&*self.ptr().offset(idx as isize)) }
252 /// Retrieves an element in the `VecDeque` mutably by index.
257 /// use std::collections::VecDeque;
259 /// let mut buf = VecDeque::new();
260 /// buf.push_back(3);
261 /// buf.push_back(4);
262 /// buf.push_back(5);
263 /// if let Some(elem) = buf.get_mut(1) {
267 /// assert_eq!(buf[1], 7);
269 #[stable(feature = "rust1", since = "1.0.0")]
270 pub fn get_mut(&mut self, index
: usize) -> Option
<&mut T
> {
271 if index
< self.len() {
272 let idx
= self.wrap_add(self.tail
, index
);
273 unsafe { Some(&mut *self.ptr().offset(idx as isize)) }
279 /// Swaps elements at indices `i` and `j`.
281 /// `i` and `j` may be equal.
283 /// Fails if there is no element with either index.
288 /// use std::collections::VecDeque;
290 /// let mut buf = VecDeque::new();
291 /// buf.push_back(3);
292 /// buf.push_back(4);
293 /// buf.push_back(5);
295 /// assert_eq!(buf[0], 5);
296 /// assert_eq!(buf[2], 3);
298 #[stable(feature = "rust1", since = "1.0.0")]
299 pub fn swap(&mut self, i
: usize, j
: usize) {
300 assert
!(i
< self.len());
301 assert
!(j
< self.len());
302 let ri
= self.wrap_add(self.tail
, i
);
303 let rj
= self.wrap_add(self.tail
, j
);
305 ptr
::swap(self.ptr().offset(ri
as isize), self.ptr().offset(rj
as isize))
309 /// Returns the number of elements the `VecDeque` can hold without
315 /// use std::collections::VecDeque;
317 /// let buf: VecDeque<i32> = VecDeque::with_capacity(10);
318 /// assert!(buf.capacity() >= 10);
321 #[stable(feature = "rust1", since = "1.0.0")]
322 pub fn capacity(&self) -> usize { self.cap() - 1 }
324 /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the
325 /// given `VecDeque`. Does nothing if the capacity is already sufficient.
327 /// Note that the allocator may give the collection more space than it requests. Therefore
328 /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
329 /// insertions are expected.
333 /// Panics if the new capacity overflows `usize`.
338 /// use std::collections::VecDeque;
340 /// let mut buf: VecDeque<i32> = vec![1].into_iter().collect();
341 /// buf.reserve_exact(10);
342 /// assert!(buf.capacity() >= 11);
344 #[stable(feature = "rust1", since = "1.0.0")]
345 pub fn reserve_exact(&mut self, additional
: usize) {
346 self.reserve(additional
);
349 /// Reserves capacity for at least `additional` more elements to be inserted in the given
350 /// `VecDeque`. The collection may reserve more space to avoid frequent reallocations.
354 /// Panics if the new capacity overflows `usize`.
359 /// use std::collections::VecDeque;
361 /// let mut buf: VecDeque<i32> = vec![1].into_iter().collect();
363 /// assert!(buf.capacity() >= 11);
365 #[stable(feature = "rust1", since = "1.0.0")]
366 pub fn reserve(&mut self, additional
: usize) {
367 let old_cap
= self.cap();
368 let used_cap
= self.len() + 1;
369 let new_cap
= used_cap
370 .checked_add(additional
)
371 .and_then(|needed_cap
| needed_cap
.checked_next_power_of_two())
372 .expect("capacity overflow");
374 if new_cap
> self.capacity() {
375 self.buf
.reserve_exact(used_cap
, new_cap
- used_cap
);
376 unsafe { self.handle_cap_increase(old_cap); }
380 /// Shrinks the capacity of the `VecDeque` as much as possible.
382 /// It will drop down as close as possible to the length but the allocator may still inform the
383 /// `VecDeque` that there is space for a few more elements.
388 /// #![feature(deque_extras)]
390 /// use std::collections::VecDeque;
392 /// let mut buf = VecDeque::with_capacity(15);
393 /// buf.extend(0..4);
394 /// assert_eq!(buf.capacity(), 15);
395 /// buf.shrink_to_fit();
396 /// assert!(buf.capacity() >= 4);
398 #[unstable(feature = "deque_extras",
399 reason
= "needs to be audited",
401 pub fn shrink_to_fit(&mut self) {
402 // +1 since the ringbuffer always leaves one space empty
403 // len + 1 can't overflow for an existing, well-formed ringbuffer.
404 let target_cap
= cmp
::max(self.len() + 1, MINIMUM_CAPACITY
+ 1).next_power_of_two();
405 if target_cap
< self.cap() {
406 // There are three cases of interest:
407 // All elements are out of desired bounds
408 // Elements are contiguous, and head is out of desired bounds
409 // Elements are discontiguous, and tail is out of desired bounds
411 // At all other times, element positions are unaffected.
413 // Indicates that elements at the head should be moved.
414 let head_outside
= self.head
== 0 || self.head
>= target_cap
;
415 // Move elements from out of desired bounds (positions after target_cap)
416 if self.tail
>= target_cap
&& head_outside
{
418 // [. . . . . . . . o o o o o o o . ]
420 // [o o o o o o o . ]
422 self.copy_nonoverlapping(0, self.tail
, self.len());
424 self.head
= self.len();
426 } else if self.tail
!= 0 && self.tail
< target_cap
&& head_outside
{
428 // [. . . o o o o o o o . . . . . . ]
430 // [o o . o o o o o ]
431 let len
= self.wrap_sub(self.head
, target_cap
);
433 self.copy_nonoverlapping(0, target_cap
, len
);
436 debug_assert
!(self.head
< self.tail
);
437 } else if self.tail
>= target_cap
{
439 // [o o o o o . . . . . . . . . o o ]
441 // [o o o o o . o o ]
442 debug_assert
!(self.wrap_sub(self.head
, 1) < target_cap
);
443 let len
= self.cap() - self.tail
;
444 let new_tail
= target_cap
- len
;
446 self.copy_nonoverlapping(new_tail
, self.tail
, len
);
448 self.tail
= new_tail
;
449 debug_assert
!(self.head
< self.tail
);
452 self.buf
.shrink_to_fit(target_cap
);
454 debug_assert
!(self.head
< self.cap());
455 debug_assert
!(self.tail
< self.cap());
456 debug_assert
!(self.cap().count_ones() == 1);
460 /// Shortens a `VecDeque`, dropping excess elements from the back.
462 /// If `len` is greater than the `VecDeque`'s current length, this has no
468 /// #![feature(deque_extras)]
470 /// use std::collections::VecDeque;
472 /// let mut buf = VecDeque::new();
473 /// buf.push_back(5);
474 /// buf.push_back(10);
475 /// buf.push_back(15);
477 /// assert_eq!(buf.len(), 1);
478 /// assert_eq!(Some(&5), buf.get(0));
480 #[unstable(feature = "deque_extras",
481 reason
= "matches collection reform specification; waiting on panic semantics",
483 pub fn truncate(&mut self, len
: usize) {
484 for _
in len
..self.len() {
489 /// Returns a front-to-back iterator.
494 /// use std::collections::VecDeque;
496 /// let mut buf = VecDeque::new();
497 /// buf.push_back(5);
498 /// buf.push_back(3);
499 /// buf.push_back(4);
500 /// let b: &[_] = &[&5, &3, &4];
501 /// let c: Vec<&i32> = buf.iter().collect();
502 /// assert_eq!(&c[..], b);
504 #[stable(feature = "rust1", since = "1.0.0")]
505 pub fn iter(&self) -> Iter
<T
> {
509 ring
: unsafe { self.buffer_as_slice() }
513 /// Returns a front-to-back iterator that returns mutable references.
518 /// use std::collections::VecDeque;
520 /// let mut buf = VecDeque::new();
521 /// buf.push_back(5);
522 /// buf.push_back(3);
523 /// buf.push_back(4);
524 /// for num in buf.iter_mut() {
527 /// let b: &[_] = &[&mut 3, &mut 1, &mut 2];
528 /// assert_eq!(&buf.iter_mut().collect::<Vec<&mut i32>>()[..], b);
530 #[stable(feature = "rust1", since = "1.0.0")]
531 pub fn iter_mut(&mut self) -> IterMut
<T
> {
535 ring
: unsafe { self.buffer_as_mut_slice() }
,
539 /// Returns a pair of slices which contain, in order, the contents of the
542 #[unstable(feature = "deque_extras",
543 reason
= "matches collection reform specification, waiting for dust to settle",
545 pub fn as_slices(&self) -> (&[T
], &[T
]) {
547 let contiguous
= self.is_contiguous();
548 let buf
= self.buffer_as_slice();
550 let (empty
, buf
) = buf
.split_at(0);
551 (&buf
[self.tail
..self.head
], empty
)
553 let (mid
, right
) = buf
.split_at(self.tail
);
554 let (left
, _
) = mid
.split_at(self.head
);
560 /// Returns a pair of slices which contain, in order, the contents of the
563 #[unstable(feature = "deque_extras",
564 reason
= "matches collection reform specification, waiting for dust to settle",
566 pub fn as_mut_slices(&mut self) -> (&mut [T
], &mut [T
]) {
568 let contiguous
= self.is_contiguous();
569 let head
= self.head
;
570 let tail
= self.tail
;
571 let buf
= self.buffer_as_mut_slice();
574 let (empty
, buf
) = buf
.split_at_mut(0);
575 (&mut buf
[tail
.. head
], empty
)
577 let (mid
, right
) = buf
.split_at_mut(tail
);
578 let (left
, _
) = mid
.split_at_mut(head
);
585 /// Returns the number of elements in the `VecDeque`.
590 /// use std::collections::VecDeque;
592 /// let mut v = VecDeque::new();
593 /// assert_eq!(v.len(), 0);
595 /// assert_eq!(v.len(), 1);
597 #[stable(feature = "rust1", since = "1.0.0")]
598 pub fn len(&self) -> usize { count(self.tail, self.head, self.cap()) }
600 /// Returns true if the buffer contains no elements
605 /// use std::collections::VecDeque;
607 /// let mut v = VecDeque::new();
608 /// assert!(v.is_empty());
610 /// assert!(!v.is_empty());
612 #[stable(feature = "rust1", since = "1.0.0")]
613 pub fn is_empty(&self) -> bool { self.len() == 0 }
615 /// Creates a draining iterator that clears the `VecDeque` and iterates over
616 /// the removed items from start to end.
621 /// #![feature(drain)]
623 /// use std::collections::VecDeque;
625 /// let mut v = VecDeque::new();
627 /// assert_eq!(v.drain().next(), Some(1));
628 /// assert!(v.is_empty());
631 #[unstable(feature = "drain",
632 reason
= "matches collection reform specification, waiting for dust to settle",
634 pub fn drain(&mut self) -> Drain
<T
> {
640 /// Clears the buffer, removing all values.
645 /// use std::collections::VecDeque;
647 /// let mut v = VecDeque::new();
650 /// assert!(v.is_empty());
652 #[stable(feature = "rust1", since = "1.0.0")]
654 pub fn clear(&mut self) {
658 /// Provides a reference to the front element, or `None` if the sequence is
664 /// use std::collections::VecDeque;
666 /// let mut d = VecDeque::new();
667 /// assert_eq!(d.front(), None);
671 /// assert_eq!(d.front(), Some(&1));
673 #[stable(feature = "rust1", since = "1.0.0")]
674 pub fn front(&self) -> Option
<&T
> {
675 if !self.is_empty() { Some(&self[0]) }
else { None }
678 /// Provides a mutable reference to the front element, or `None` if the
679 /// sequence is empty.
684 /// use std::collections::VecDeque;
686 /// let mut d = VecDeque::new();
687 /// assert_eq!(d.front_mut(), None);
691 /// match d.front_mut() {
692 /// Some(x) => *x = 9,
695 /// assert_eq!(d.front(), Some(&9));
697 #[stable(feature = "rust1", since = "1.0.0")]
698 pub fn front_mut(&mut self) -> Option
<&mut T
> {
699 if !self.is_empty() { Some(&mut self[0]) }
else { None }
702 /// Provides a reference to the back element, or `None` if the sequence is
708 /// use std::collections::VecDeque;
710 /// let mut d = VecDeque::new();
711 /// assert_eq!(d.back(), None);
715 /// assert_eq!(d.back(), Some(&2));
717 #[stable(feature = "rust1", since = "1.0.0")]
718 pub fn back(&self) -> Option
<&T
> {
719 if !self.is_empty() { Some(&self[self.len() - 1]) }
else { None }
722 /// Provides a mutable reference to the back element, or `None` if the
723 /// sequence is empty.
728 /// use std::collections::VecDeque;
730 /// let mut d = VecDeque::new();
731 /// assert_eq!(d.back(), None);
735 /// match d.back_mut() {
736 /// Some(x) => *x = 9,
739 /// assert_eq!(d.back(), Some(&9));
741 #[stable(feature = "rust1", since = "1.0.0")]
742 pub fn back_mut(&mut self) -> Option
<&mut T
> {
743 let len
= self.len();
744 if !self.is_empty() { Some(&mut self[len - 1]) }
else { None }
747 /// Removes the first element and returns it, or `None` if the sequence is
753 /// use std::collections::VecDeque;
755 /// let mut d = VecDeque::new();
759 /// assert_eq!(d.pop_front(), Some(1));
760 /// assert_eq!(d.pop_front(), Some(2));
761 /// assert_eq!(d.pop_front(), None);
763 #[stable(feature = "rust1", since = "1.0.0")]
764 pub fn pop_front(&mut self) -> Option
<T
> {
768 let tail
= self.tail
;
769 self.tail
= self.wrap_add(self.tail
, 1);
770 unsafe { Some(self.buffer_read(tail)) }
774 /// Inserts an element first in the sequence.
779 /// use std::collections::VecDeque;
781 /// let mut d = VecDeque::new();
784 /// assert_eq!(d.front(), Some(&2));
786 #[stable(feature = "rust1", since = "1.0.0")]
787 pub fn push_front(&mut self, value
: T
) {
789 let old_cap
= self.cap();
791 unsafe { self.handle_cap_increase(old_cap); }
792 debug_assert
!(!self.is_full());
795 self.tail
= self.wrap_sub(self.tail
, 1);
796 let tail
= self.tail
;
797 unsafe { self.buffer_write(tail, value); }
800 /// Appends an element to the back of a buffer
805 /// use std::collections::VecDeque;
807 /// let mut buf = VecDeque::new();
808 /// buf.push_back(1);
809 /// buf.push_back(3);
810 /// assert_eq!(3, *buf.back().unwrap());
812 #[stable(feature = "rust1", since = "1.0.0")]
813 pub fn push_back(&mut self, value
: T
) {
815 let old_cap
= self.cap();
817 unsafe { self.handle_cap_increase(old_cap); }
818 debug_assert
!(!self.is_full());
821 let head
= self.head
;
822 self.head
= self.wrap_add(self.head
, 1);
823 unsafe { self.buffer_write(head, value) }
826 /// Removes the last element from a buffer and returns it, or `None` if
832 /// use std::collections::VecDeque;
834 /// let mut buf = VecDeque::new();
835 /// assert_eq!(buf.pop_back(), None);
836 /// buf.push_back(1);
837 /// buf.push_back(3);
838 /// assert_eq!(buf.pop_back(), Some(3));
840 #[stable(feature = "rust1", since = "1.0.0")]
841 pub fn pop_back(&mut self) -> Option
<T
> {
845 self.head
= self.wrap_sub(self.head
, 1);
846 let head
= self.head
;
847 unsafe { Some(self.buffer_read(head)) }
852 fn is_contiguous(&self) -> bool
{
853 self.tail
<= self.head
856 /// Removes an element from anywhere in the `VecDeque` and returns it, replacing it with the
859 /// This does not preserve ordering, but is O(1).
861 /// Returns `None` if `index` is out of bounds.
866 /// #![feature(deque_extras)]
868 /// use std::collections::VecDeque;
870 /// let mut buf = VecDeque::new();
871 /// assert_eq!(buf.swap_back_remove(0), None);
872 /// buf.push_back(1);
873 /// buf.push_back(2);
874 /// buf.push_back(3);
876 /// assert_eq!(buf.swap_back_remove(0), Some(1));
877 /// assert_eq!(buf.len(), 2);
878 /// assert_eq!(buf[0], 3);
879 /// assert_eq!(buf[1], 2);
881 #[unstable(feature = "deque_extras",
882 reason
= "the naming of this function may be altered",
884 pub fn swap_back_remove(&mut self, index
: usize) -> Option
<T
> {
885 let length
= self.len();
886 if length
> 0 && index
< length
- 1 {
887 self.swap(index
, length
- 1);
888 } else if index
>= length
{
894 /// Removes an element from anywhere in the `VecDeque` and returns it,
895 /// replacing it with the first element.
897 /// This does not preserve ordering, but is O(1).
899 /// Returns `None` if `index` is out of bounds.
904 /// #![feature(deque_extras)]
906 /// use std::collections::VecDeque;
908 /// let mut buf = VecDeque::new();
909 /// assert_eq!(buf.swap_front_remove(0), None);
910 /// buf.push_back(1);
911 /// buf.push_back(2);
912 /// buf.push_back(3);
914 /// assert_eq!(buf.swap_front_remove(2), Some(3));
915 /// assert_eq!(buf.len(), 2);
916 /// assert_eq!(buf[0], 2);
917 /// assert_eq!(buf[1], 1);
919 #[unstable(feature = "deque_extras",
920 reason
= "the naming of this function may be altered",
922 pub fn swap_front_remove(&mut self, index
: usize) -> Option
<T
> {
923 let length
= self.len();
924 if length
> 0 && index
< length
&& index
!= 0 {
926 } else if index
>= length
{
932 /// Inserts an element at `index` within the `VecDeque`. Whichever
933 /// end is closer to the insertion point will be moved to make room,
934 /// and all the affected elements will be moved to new positions.
938 /// Panics if `index` is greater than `VecDeque`'s length
942 /// #![feature(deque_extras)]
944 /// use std::collections::VecDeque;
946 /// let mut buf = VecDeque::new();
947 /// buf.push_back(10);
948 /// buf.push_back(12);
949 /// buf.insert(1, 11);
950 /// assert_eq!(Some(&11), buf.get(1));
952 #[unstable(feature = "deque_extras",
953 reason
= "needs to be audited",
955 pub fn insert(&mut self, index
: usize, value
: T
) {
956 assert
!(index
<= self.len(), "index out of bounds");
958 let old_cap
= self.cap();
960 unsafe { self.handle_cap_increase(old_cap); }
961 debug_assert
!(!self.is_full());
964 // Move the least number of elements in the ring buffer and insert
967 // At most len/2 - 1 elements will be moved. O(min(n, n-i))
969 // There are three main cases:
970 // Elements are contiguous
971 // - special case when tail is 0
972 // Elements are discontiguous and the insert is in the tail section
973 // Elements are discontiguous and the insert is in the head section
975 // For each of those there are two more cases:
976 // Insert is closer to tail
977 // Insert is closer to head
979 // Key: H - self.head
982 // I - Insertion element
983 // A - The element that should be after the insertion point
984 // M - Indicates element was moved
986 let idx
= self.wrap_add(self.tail
, index
);
988 let distance_to_tail
= index
;
989 let distance_to_head
= self.len() - index
;
991 let contiguous
= self.is_contiguous();
993 match (contiguous
, distance_to_tail
<= distance_to_head
, idx
>= self.tail
) {
994 (true, true, _
) if index
== 0 => {
999 // [A o o o o o o . . . . . . . . .]
1002 // [A o o o o o o o . . . . . I]
1005 self.tail
= self.wrap_sub(self.tail
, 1);
1007 (true, true, _
) => unsafe {
1008 // contiguous, insert closer to tail:
1011 // [. . . o o A o o o o . . . . . .]
1014 // [. . o o I A o o o o . . . . . .]
1017 // contiguous, insert closer to tail and tail is 0:
1021 // [o o A o o o o . . . . . . . . .]
1024 // [o I A o o o o o . . . . . . . o]
1027 let new_tail
= self.wrap_sub(self.tail
, 1);
1029 self.copy(new_tail
, self.tail
, 1);
1030 // Already moved the tail, so we only copy `index - 1` elements.
1031 self.copy(self.tail
, self.tail
+ 1, index
- 1);
1033 self.tail
= new_tail
;
1035 (true, false, _
) => unsafe {
1036 // contiguous, insert closer to head:
1039 // [. . . o o o o A o o . . . . . .]
1042 // [. . . o o o o I A o o . . . . .]
1045 self.copy(idx
+ 1, idx
, self.head
- idx
);
1046 self.head
= self.wrap_add(self.head
, 1);
1048 (false, true, true) => unsafe {
1049 // discontiguous, insert closer to tail, tail section:
1052 // [o o o o o o . . . . . o o A o o]
1055 // [o o o o o o . . . . o o I A o o]
1058 self.copy(self.tail
- 1, self.tail
, index
);
1061 (false, false, true) => unsafe {
1062 // discontiguous, insert closer to head, tail section:
1065 // [o o . . . . . . . o o o o o A o]
1068 // [o o o . . . . . . o o o o o I A]
1071 // copy elements up to new head
1072 self.copy(1, 0, self.head
);
1074 // copy last element into empty spot at bottom of buffer
1075 self.copy(0, self.cap() - 1, 1);
1077 // move elements from idx to end forward not including ^ element
1078 self.copy(idx
+ 1, idx
, self.cap() - 1 - idx
);
1082 (false, true, false) if idx
== 0 => unsafe {
1083 // discontiguous, insert is closer to tail, head section,
1084 // and is at index zero in the internal buffer:
1087 // [A o o o o o o o o o . . . o o o]
1090 // [A o o o o o o o o o . . o o o I]
1093 // copy elements up to new tail
1094 self.copy(self.tail
- 1, self.tail
, self.cap() - self.tail
);
1096 // copy last element into empty spot at bottom of buffer
1097 self.copy(self.cap() - 1, 0, 1);
1101 (false, true, false) => unsafe {
1102 // discontiguous, insert closer to tail, head section:
1105 // [o o o A o o o o o o . . . o o o]
1108 // [o o I A o o o o o o . . o o o o]
1111 // copy elements up to new tail
1112 self.copy(self.tail
- 1, self.tail
, self.cap() - self.tail
);
1114 // copy last element into empty spot at bottom of buffer
1115 self.copy(self.cap() - 1, 0, 1);
1117 // move elements from idx-1 to end forward not including ^ element
1118 self.copy(0, 1, idx
- 1);
1122 (false, false, false) => unsafe {
1123 // discontiguous, insert closer to head, head section:
1126 // [o o o o A o o . . . . . . o o o]
1129 // [o o o o I A o o . . . . . o o o]
1132 self.copy(idx
+ 1, idx
, self.head
- idx
);
1137 // tail might've been changed so we need to recalculate
1138 let new_idx
= self.wrap_add(self.tail
, index
);
1140 self.buffer_write(new_idx
, value
);
1144 /// Removes and returns the element at `index` from the `VecDeque`.
1145 /// Whichever end is closer to the removal point will be moved to make
1146 /// room, and all the affected elements will be moved to new positions.
1147 /// Returns `None` if `index` is out of bounds.
1151 /// use std::collections::VecDeque;
1153 /// let mut buf = VecDeque::new();
1154 /// buf.push_back(1);
1155 /// buf.push_back(2);
1156 /// buf.push_back(3);
1158 /// assert_eq!(buf.remove(1), Some(2));
1159 /// assert_eq!(buf.get(1), Some(&3));
1161 #[stable(feature = "rust1", since = "1.0.0")]
1162 pub fn remove(&mut self, index
: usize) -> Option
<T
> {
1163 if self.is_empty() || self.len() <= index
{
1167 // There are three main cases:
1168 // Elements are contiguous
1169 // Elements are discontiguous and the removal is in the tail section
1170 // Elements are discontiguous and the removal is in the head section
1171 // - special case when elements are technically contiguous,
1172 // but self.head = 0
1174 // For each of those there are two more cases:
1175 // Insert is closer to tail
1176 // Insert is closer to head
1178 // Key: H - self.head
1180 // o - Valid element
1181 // x - Element marked for removal
1182 // R - Indicates element that is being removed
1183 // M - Indicates element was moved
1185 let idx
= self.wrap_add(self.tail
, index
);
1188 Some(self.buffer_read(idx
))
1191 let distance_to_tail
= index
;
1192 let distance_to_head
= self.len() - index
;
1194 let contiguous
= self.is_contiguous();
1196 match (contiguous
, distance_to_tail
<= distance_to_head
, idx
>= self.tail
) {
1197 (true, true, _
) => unsafe {
1198 // contiguous, remove closer to tail:
1201 // [. . . o o x o o o o . . . . . .]
1204 // [. . . . o o o o o o . . . . . .]
1207 self.copy(self.tail
+ 1, self.tail
, index
);
1210 (true, false, _
) => unsafe {
1211 // contiguous, remove closer to head:
1214 // [. . . o o o o x o o . . . . . .]
1217 // [. . . o o o o o o . . . . . . .]
1220 self.copy(idx
, idx
+ 1, self.head
- idx
- 1);
1223 (false, true, true) => unsafe {
1224 // discontiguous, remove closer to tail, tail section:
1227 // [o o o o o o . . . . . o o x o o]
1230 // [o o o o o o . . . . . . o o o o]
1233 self.copy(self.tail
+ 1, self.tail
, index
);
1234 self.tail
= self.wrap_add(self.tail
, 1);
1236 (false, false, false) => unsafe {
1237 // discontiguous, remove closer to head, head section:
1240 // [o o o o x o o . . . . . . o o o]
1243 // [o o o o o o . . . . . . . o o o]
1246 self.copy(idx
, idx
+ 1, self.head
- idx
- 1);
1249 (false, false, true) => unsafe {
1250 // discontiguous, remove closer to head, tail section:
1253 // [o o o . . . . . . o o o o o x o]
1256 // [o o . . . . . . . o o o o o o o]
1259 // or quasi-discontiguous, remove next to head, tail section:
1262 // [. . . . . . . . . o o o o o x o]
1265 // [. . . . . . . . . o o o o o o .]
1268 // draw in elements in the tail section
1269 self.copy(idx
, idx
+ 1, self.cap() - idx
- 1);
1271 // Prevents underflow.
1273 // copy first element into empty spot
1274 self.copy(self.cap() - 1, 0, 1);
1276 // move elements in the head section backwards
1277 self.copy(0, 1, self.head
- 1);
1280 self.head
= self.wrap_sub(self.head
, 1);
1282 (false, true, false) => unsafe {
1283 // discontiguous, remove closer to tail, head section:
1286 // [o o x o o o o o o o . . . o o o]
1289 // [o o o o o o o o o o . . . . o o]
1292 // draw in elements up to idx
1293 self.copy(1, 0, idx
);
1295 // copy last element into empty spot
1296 self.copy(0, self.cap() - 1, 1);
1298 // move elements from tail to end forward, excluding the last one
1299 self.copy(self.tail
+ 1, self.tail
, self.cap() - self.tail
- 1);
1301 self.tail
= self.wrap_add(self.tail
, 1);
1308 /// Splits the collection into two at the given index.
1310 /// Returns a newly allocated `Self`. `self` contains elements `[0, at)`,
1311 /// and the returned `Self` contains elements `[at, len)`.
1313 /// Note that the capacity of `self` does not change.
1317 /// Panics if `at > len`
1322 /// #![feature(split_off)]
1324 /// use std::collections::VecDeque;
1326 /// let mut buf: VecDeque<_> = vec![1,2,3].into_iter().collect();
1327 /// let buf2 = buf.split_off(1);
1328 /// // buf = [1], buf2 = [2, 3]
1329 /// assert_eq!(buf.len(), 1);
1330 /// assert_eq!(buf2.len(), 2);
1333 #[stable(feature = "split_off", since = "1.4.0")]
1334 pub fn split_off(&mut self, at
: usize) -> Self {
1335 let len
= self.len();
1336 assert
!(at
<= len
, "`at` out of bounds");
1338 let other_len
= len
- at
;
1339 let mut other
= VecDeque
::with_capacity(other_len
);
1342 let (first_half
, second_half
) = self.as_slices();
1344 let first_len
= first_half
.len();
1345 let second_len
= second_half
.len();
1347 // `at` lies in the first half.
1348 let amount_in_first
= first_len
- at
;
1350 ptr
::copy_nonoverlapping(first_half
.as_ptr().offset(at
as isize),
1354 // just take all of the second half.
1355 ptr
::copy_nonoverlapping(second_half
.as_ptr(),
1356 other
.ptr().offset(amount_in_first
as isize),
1359 // `at` lies in the second half, need to factor in the elements we skipped
1360 // in the first half.
1361 let offset
= at
- first_len
;
1362 let amount_in_second
= second_len
- offset
;
1363 ptr
::copy_nonoverlapping(second_half
.as_ptr().offset(offset
as isize),
1369 // Cleanup where the ends of the buffers are
1370 self.head
= self.wrap_sub(self.head
, other_len
);
1371 other
.head
= other
.wrap_index(other_len
);
1376 /// Moves all the elements of `other` into `Self`, leaving `other` empty.
1380 /// Panics if the new number of elements in self overflows a `usize`.
1385 /// use std::collections::VecDeque;
1387 /// let mut buf: VecDeque<_> = vec![1, 2, 3].into_iter().collect();
1388 /// let mut buf2: VecDeque<_> = vec![4, 5, 6].into_iter().collect();
1389 /// buf.append(&mut buf2);
1390 /// assert_eq!(buf.len(), 6);
1391 /// assert_eq!(buf2.len(), 0);
1394 #[stable(feature = "append", since = "1.4.0")]
1395 pub fn append(&mut self, other
: &mut Self) {
1397 self.extend(other
.drain());
1400 /// Retains only the elements specified by the predicate.
1402 /// In other words, remove all elements `e` such that `f(&e)` returns false.
1403 /// This method operates in place and preserves the order of the retained
1409 /// #![feature(vec_deque_retain)]
1411 /// use std::collections::VecDeque;
1413 /// let mut buf = VecDeque::new();
1414 /// buf.extend(1..5);
1415 /// buf.retain(|&x| x%2 == 0);
1417 /// let v: Vec<_> = buf.into_iter().collect();
1418 /// assert_eq!(&v[..], &[2, 4]);
1420 #[stable(feature = "vec_deque_retain", since = "1.4.0")]
1421 pub fn retain
<F
>(&mut self, mut f
: F
) where F
: FnMut(&T
) -> bool
{
1422 let len
= self.len();
1428 self.swap(i
-del
, i
);
1432 self.truncate(len
- del
);
1437 impl<T
: Clone
> VecDeque
<T
> {
1438 /// Modifies the `VecDeque` in-place so that `len()` is equal to new_len,
1439 /// either by removing excess elements or by appending copies of a value to the back.
1444 /// #![feature(deque_extras)]
1446 /// use std::collections::VecDeque;
1448 /// let mut buf = VecDeque::new();
1449 /// buf.push_back(5);
1450 /// buf.push_back(10);
1451 /// buf.push_back(15);
1452 /// buf.resize(2, 0);
1453 /// buf.resize(6, 20);
1454 /// for (a, b) in [5, 10, 20, 20, 20, 20].iter().zip(&buf) {
1455 /// assert_eq!(a, b);
1458 #[unstable(feature = "deque_extras",
1459 reason
= "matches collection reform specification; waiting on panic semantics",
1461 pub fn resize(&mut self, new_len
: usize, value
: T
) {
1462 let len
= self.len();
1465 self.extend(repeat(value
).take(new_len
- len
))
1467 self.truncate(new_len
);
1472 /// Returns the index in the underlying buffer for a given logical element index.
1474 fn wrap_index(index
: usize, size
: usize) -> usize {
1475 // size is always a power of 2
1476 debug_assert
!(size
.is_power_of_two());
1480 /// Calculate the number of elements left to be read in the buffer
1482 fn count(tail
: usize, head
: usize, size
: usize) -> usize {
1483 // size is always a power of 2
1484 (head
.wrapping_sub(tail
)) & (size
- 1)
1487 /// `VecDeque` iterator.
1488 #[stable(feature = "rust1", since = "1.0.0")]
1489 pub struct Iter
<'a
, T
:'a
> {
1495 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1496 impl<'a
, T
> Clone
for Iter
<'a
, T
> {
1497 fn clone(&self) -> Iter
<'a
, T
> {
1506 #[stable(feature = "rust1", since = "1.0.0")]
1507 impl<'a
, T
> Iterator
for Iter
<'a
, T
> {
1511 fn next(&mut self) -> Option
<&'a T
> {
1512 if self.tail
== self.head
{
1515 let tail
= self.tail
;
1516 self.tail
= wrap_index(self.tail
.wrapping_add(1), self.ring
.len());
1517 unsafe { Some(self.ring.get_unchecked(tail)) }
1521 fn size_hint(&self) -> (usize, Option
<usize>) {
1522 let len
= count(self.tail
, self.head
, self.ring
.len());
1527 #[stable(feature = "rust1", since = "1.0.0")]
1528 impl<'a
, T
> DoubleEndedIterator
for Iter
<'a
, T
> {
1530 fn next_back(&mut self) -> Option
<&'a T
> {
1531 if self.tail
== self.head
{
1534 self.head
= wrap_index(self.head
.wrapping_sub(1), self.ring
.len());
1535 unsafe { Some(self.ring.get_unchecked(self.head)) }
1539 #[stable(feature = "rust1", since = "1.0.0")]
1540 impl<'a
, T
> ExactSizeIterator
for Iter
<'a
, T
> {}
1542 /// `VecDeque` mutable iterator.
1543 #[stable(feature = "rust1", since = "1.0.0")]
1544 pub struct IterMut
<'a
, T
:'a
> {
1550 #[stable(feature = "rust1", since = "1.0.0")]
1551 impl<'a
, T
> Iterator
for IterMut
<'a
, T
> {
1552 type Item
= &'a
mut T
;
1555 fn next(&mut self) -> Option
<&'a
mut T
> {
1556 if self.tail
== self.head
{
1559 let tail
= self.tail
;
1560 self.tail
= wrap_index(self.tail
.wrapping_add(1), self.ring
.len());
1563 let elem
= self.ring
.get_unchecked_mut(tail
);
1564 Some(&mut *(elem
as *mut _
))
1569 fn size_hint(&self) -> (usize, Option
<usize>) {
1570 let len
= count(self.tail
, self.head
, self.ring
.len());
1575 #[stable(feature = "rust1", since = "1.0.0")]
1576 impl<'a
, T
> DoubleEndedIterator
for IterMut
<'a
, T
> {
1578 fn next_back(&mut self) -> Option
<&'a
mut T
> {
1579 if self.tail
== self.head
{
1582 self.head
= wrap_index(self.head
.wrapping_sub(1), self.ring
.len());
1585 let elem
= self.ring
.get_unchecked_mut(self.head
);
1586 Some(&mut *(elem
as *mut _
))
1591 #[stable(feature = "rust1", since = "1.0.0")]
1592 impl<'a
, T
> ExactSizeIterator
for IterMut
<'a
, T
> {}
1594 /// A by-value VecDeque iterator
1596 #[stable(feature = "rust1", since = "1.0.0")]
1597 pub struct IntoIter
<T
> {
1601 #[stable(feature = "rust1", since = "1.0.0")]
1602 impl<T
> Iterator
for IntoIter
<T
> {
1606 fn next(&mut self) -> Option
<T
> {
1607 self.inner
.pop_front()
1611 fn size_hint(&self) -> (usize, Option
<usize>) {
1612 let len
= self.inner
.len();
1617 #[stable(feature = "rust1", since = "1.0.0")]
1618 impl<T
> DoubleEndedIterator
for IntoIter
<T
> {
1620 fn next_back(&mut self) -> Option
<T
> {
1621 self.inner
.pop_back()
1625 #[stable(feature = "rust1", since = "1.0.0")]
1626 impl<T
> ExactSizeIterator
for IntoIter
<T
> {}
1628 /// A draining VecDeque iterator
1629 #[unstable(feature = "drain",
1630 reason
= "matches collection reform specification, waiting for dust to settle",
1632 pub struct Drain
<'a
, T
: 'a
> {
1633 inner
: &'a
mut VecDeque
<T
>,
1636 #[stable(feature = "rust1", since = "1.0.0")]
1637 impl<'a
, T
: 'a
> Drop
for Drain
<'a
, T
> {
1638 fn drop(&mut self) {
1639 for _
in self.by_ref() {}
1640 self.inner
.head
= 0;
1641 self.inner
.tail
= 0;
1645 #[stable(feature = "rust1", since = "1.0.0")]
1646 impl<'a
, T
: 'a
> Iterator
for Drain
<'a
, T
> {
1650 fn next(&mut self) -> Option
<T
> {
1651 self.inner
.pop_front()
1655 fn size_hint(&self) -> (usize, Option
<usize>) {
1656 let len
= self.inner
.len();
1661 #[stable(feature = "rust1", since = "1.0.0")]
1662 impl<'a
, T
: 'a
> DoubleEndedIterator
for Drain
<'a
, T
> {
1664 fn next_back(&mut self) -> Option
<T
> {
1665 self.inner
.pop_back()
1669 #[stable(feature = "rust1", since = "1.0.0")]
1670 impl<'a
, T
: 'a
> ExactSizeIterator
for Drain
<'a
, T
> {}
1672 #[stable(feature = "rust1", since = "1.0.0")]
1673 impl<A
: PartialEq
> PartialEq
for VecDeque
<A
> {
1674 fn eq(&self, other
: &VecDeque
<A
>) -> bool
{
1675 self.len() == other
.len() &&
1676 self.iter().zip(other
).all(|(a
, b
)| a
.eq(b
))
1680 #[stable(feature = "rust1", since = "1.0.0")]
1681 impl<A
: Eq
> Eq
for VecDeque
<A
> {}
1683 #[stable(feature = "rust1", since = "1.0.0")]
1684 impl<A
: PartialOrd
> PartialOrd
for VecDeque
<A
> {
1685 fn partial_cmp(&self, other
: &VecDeque
<A
>) -> Option
<Ordering
> {
1686 self.iter().partial_cmp(other
.iter())
1690 #[stable(feature = "rust1", since = "1.0.0")]
1691 impl<A
: Ord
> Ord
for VecDeque
<A
> {
1693 fn cmp(&self, other
: &VecDeque
<A
>) -> Ordering
{
1694 self.iter().cmp(other
.iter())
1698 #[stable(feature = "rust1", since = "1.0.0")]
1699 impl<A
: Hash
> Hash
for VecDeque
<A
> {
1700 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
1701 self.len().hash(state
);
1708 #[stable(feature = "rust1", since = "1.0.0")]
1709 impl<A
> Index
<usize> for VecDeque
<A
> {
1713 fn index(&self, index
: usize) -> &A
{
1714 self.get(index
).expect("Out of bounds access")
1718 #[stable(feature = "rust1", since = "1.0.0")]
1719 impl<A
> IndexMut
<usize> for VecDeque
<A
> {
1721 fn index_mut(&mut self, index
: usize) -> &mut A
{
1722 self.get_mut(index
).expect("Out of bounds access")
1726 #[stable(feature = "rust1", since = "1.0.0")]
1727 impl<A
> FromIterator
<A
> for VecDeque
<A
> {
1728 fn from_iter
<T
: IntoIterator
<Item
=A
>>(iterable
: T
) -> VecDeque
<A
> {
1729 let iterator
= iterable
.into_iter();
1730 let (lower
, _
) = iterator
.size_hint();
1731 let mut deq
= VecDeque
::with_capacity(lower
);
1732 deq
.extend(iterator
);
1737 #[stable(feature = "rust1", since = "1.0.0")]
1738 impl<T
> IntoIterator
for VecDeque
<T
> {
1740 type IntoIter
= IntoIter
<T
>;
1742 /// Consumes the list into a front-to-back iterator yielding elements by
1744 fn into_iter(self) -> IntoIter
<T
> {
1751 #[stable(feature = "rust1", since = "1.0.0")]
1752 impl<'a
, T
> IntoIterator
for &'a VecDeque
<T
> {
1754 type IntoIter
= Iter
<'a
, T
>;
1756 fn into_iter(self) -> Iter
<'a
, T
> {
1761 #[stable(feature = "rust1", since = "1.0.0")]
1762 impl<'a
, T
> IntoIterator
for &'a
mut VecDeque
<T
> {
1763 type Item
= &'a
mut T
;
1764 type IntoIter
= IterMut
<'a
, T
>;
1766 fn into_iter(mut self) -> IterMut
<'a
, T
> {
1771 #[stable(feature = "rust1", since = "1.0.0")]
1772 impl<A
> Extend
<A
> for VecDeque
<A
> {
1773 fn extend
<T
: IntoIterator
<Item
=A
>>(&mut self, iter
: T
) {
1775 self.push_back(elt
);
1780 #[stable(feature = "extend_ref", since = "1.2.0")]
1781 impl<'a
, T
: 'a
+ Copy
> Extend
<&'a T
> for VecDeque
<T
> {
1782 fn extend
<I
: IntoIterator
<Item
=&'a T
>>(&mut self, iter
: I
) {
1783 self.extend(iter
.into_iter().cloned());
1787 #[stable(feature = "rust1", since = "1.0.0")]
1788 impl<T
: fmt
::Debug
> fmt
::Debug
for VecDeque
<T
> {
1789 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
1790 try
!(write
!(f
, "["));
1792 for (i
, e
) in self.iter().enumerate() {
1793 if i
!= 0 { try!(write!(f, ", ")); }
1794 try
!(write
!(f
, "{:?}", *e
));
1803 use core
::iter
::Iterator
;
1804 use core
::option
::Option
::Some
;
1808 use super::VecDeque
;
1811 fn bench_push_back_100(b
: &mut test
::Bencher
) {
1812 let mut deq
= VecDeque
::with_capacity(101);
1823 fn bench_push_front_100(b
: &mut test
::Bencher
) {
1824 let mut deq
= VecDeque
::with_capacity(101);
1835 fn bench_pop_back_100(b
: &mut test
::Bencher
) {
1836 let mut deq
= VecDeque
::<i32>::with_capacity(101);
1841 while !deq
.is_empty() {
1842 test
::black_box(deq
.pop_back());
1848 fn bench_pop_front_100(b
: &mut test
::Bencher
) {
1849 let mut deq
= VecDeque
::<i32>::with_capacity(101);
1854 while !deq
.is_empty() {
1855 test
::black_box(deq
.pop_front());
1861 fn test_swap_front_back_remove() {
1862 fn test(back
: bool
) {
1863 // This test checks that every single combination of tail position and length is tested.
1864 // Capacity 15 should be large enough to cover every case.
1865 let mut tester
= VecDeque
::with_capacity(15);
1866 let usable_cap
= tester
.capacity();
1867 let final_len
= usable_cap
/ 2;
1869 for len
in 0..final_len
{
1870 let expected
= if back
{
1873 (0..len
).rev().collect()
1875 for tail_pos
in 0..usable_cap
{
1876 tester
.tail
= tail_pos
;
1877 tester
.head
= tail_pos
;
1879 for i
in 0..len
* 2 {
1880 tester
.push_front(i
);
1883 assert_eq
!(tester
.swap_back_remove(i
), Some(len
* 2 - 1 - i
));
1886 for i
in 0..len
* 2 {
1887 tester
.push_back(i
);
1890 let idx
= tester
.len() - 1 - i
;
1891 assert_eq
!(tester
.swap_front_remove(idx
), Some(len
* 2 - 1 - i
));
1894 assert
!(tester
.tail
< tester
.cap());
1895 assert
!(tester
.head
< tester
.cap());
1896 assert_eq
!(tester
, expected
);
1906 // This test checks that every single combination of tail position, length, and
1907 // insertion position is tested. Capacity 15 should be large enough to cover every case.
1909 let mut tester
= VecDeque
::with_capacity(15);
1910 // can't guarantee we got 15, so have to get what we got.
1911 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
1912 // this test isn't covering what it wants to
1913 let cap
= tester
.capacity();
1916 // len is the length *after* insertion
1918 // 0, 1, 2, .., len - 1
1919 let expected
= (0..).take(len
).collect();
1920 for tail_pos
in 0..cap
{
1921 for to_insert
in 0..len
{
1922 tester
.tail
= tail_pos
;
1923 tester
.head
= tail_pos
;
1926 tester
.push_back(i
);
1929 tester
.insert(to_insert
, to_insert
);
1930 assert
!(tester
.tail
< tester
.cap());
1931 assert
!(tester
.head
< tester
.cap());
1932 assert_eq
!(tester
, expected
);
1940 // This test checks that every single combination of tail position, length, and
1941 // removal position is tested. Capacity 15 should be large enough to cover every case.
1943 let mut tester
= VecDeque
::with_capacity(15);
1944 // can't guarantee we got 15, so have to get what we got.
1945 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
1946 // this test isn't covering what it wants to
1947 let cap
= tester
.capacity();
1949 // len is the length *after* removal
1950 for len
in 0..cap
- 1 {
1951 // 0, 1, 2, .., len - 1
1952 let expected
= (0..).take(len
).collect();
1953 for tail_pos
in 0..cap
{
1954 for to_remove
in 0..len
+ 1 {
1955 tester
.tail
= tail_pos
;
1956 tester
.head
= tail_pos
;
1959 tester
.push_back(1234);
1961 tester
.push_back(i
);
1963 if to_remove
== len
{
1964 tester
.push_back(1234);
1966 tester
.remove(to_remove
);
1967 assert
!(tester
.tail
< tester
.cap());
1968 assert
!(tester
.head
< tester
.cap());
1969 assert_eq
!(tester
, expected
);
1976 fn test_shrink_to_fit() {
1977 // This test checks that every single combination of head and tail position,
1978 // is tested. Capacity 15 should be large enough to cover every case.
1980 let mut tester
= VecDeque
::with_capacity(15);
1981 // can't guarantee we got 15, so have to get what we got.
1982 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
1983 // this test isn't covering what it wants to
1984 let cap
= tester
.capacity();
1986 let max_cap
= tester
.capacity();
1988 for len
in 0..cap
+ 1 {
1989 // 0, 1, 2, .., len - 1
1990 let expected
= (0..).take(len
).collect();
1991 for tail_pos
in 0..max_cap
+ 1 {
1992 tester
.tail
= tail_pos
;
1993 tester
.head
= tail_pos
;
1996 tester
.push_back(i
);
1998 tester
.shrink_to_fit();
1999 assert
!(tester
.capacity() <= cap
);
2000 assert
!(tester
.tail
< tester
.cap());
2001 assert
!(tester
.head
< tester
.cap());
2002 assert_eq
!(tester
, expected
);
2008 fn test_split_off() {
2009 // This test checks that every single combination of tail position, length, and
2010 // split position is tested. Capacity 15 should be large enough to cover every case.
2012 let mut tester
= VecDeque
::with_capacity(15);
2013 // can't guarantee we got 15, so have to get what we got.
2014 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2015 // this test isn't covering what it wants to
2016 let cap
= tester
.capacity();
2018 // len is the length *before* splitting
2020 // index to split at
2021 for at
in 0..len
+ 1 {
2022 // 0, 1, 2, .., at - 1 (may be empty)
2023 let expected_self
= (0..).take(at
).collect();
2024 // at, at + 1, .., len - 1 (may be empty)
2025 let expected_other
= (at
..).take(len
- at
).collect();
2027 for tail_pos
in 0..cap
{
2028 tester
.tail
= tail_pos
;
2029 tester
.head
= tail_pos
;
2031 tester
.push_back(i
);
2033 let result
= tester
.split_off(at
);
2034 assert
!(tester
.tail
< tester
.cap());
2035 assert
!(tester
.head
< tester
.cap());
2036 assert
!(result
.tail
< result
.cap());
2037 assert
!(result
.head
< result
.cap());
2038 assert_eq
!(tester
, expected_self
);
2039 assert_eq
!(result
, expected_other
);
2046 fn test_zst_push() {
2052 // Test that for all possible sequences of push_front / push_back,
2053 // we end up with a deque of the correct size
2056 let mut tester
= VecDeque
::with_capacity(len
);
2057 assert_eq
!(tester
.len(), 0);
2058 assert
!(tester
.capacity() >= len
);
2059 for case
in 0..(1 << len
) {
2060 assert_eq
!(tester
.len(), 0);
2062 if case
& (1 << bit
) != 0 {
2063 tester
.push_front(Zst
);
2065 tester
.push_back(Zst
);
2068 assert_eq
!(tester
.len(), len
);
2069 assert_eq
!(tester
.iter().count(), len
);