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}
;
29 use core
::hash
::{Hash, Hasher}
;
32 use alloc
::raw_vec
::RawVec
;
34 use super::range
::RangeArgument
;
36 const INITIAL_CAPACITY
: usize = 7; // 2^3 - 1
37 const MINIMUM_CAPACITY
: usize = 1; // 2 - 1
38 #[cfg(target_pointer_width = "32")]
39 const MAXIMUM_ZST_CAPACITY
: usize = 1 << (32 - 1); // Largest possible power of two
40 #[cfg(target_pointer_width = "64")]
41 const MAXIMUM_ZST_CAPACITY
: usize = 1 << (64 - 1); // Largest possible power of two
43 /// `VecDeque` is a growable ring buffer, which can be used as a double-ended
44 /// queue efficiently.
46 /// The "default" usage of this type as a queue is to use `push_back` to add to
47 /// the queue, and `pop_front` to remove from the queue. `extend` and `append`
48 /// push onto the back in this manner, and iterating over `VecDeque` goes front
50 #[stable(feature = "rust1", since = "1.0.0")]
51 pub struct VecDeque
<T
> {
52 // tail and head are pointers into the buffer. Tail always points
53 // to the first element that could be read, Head always points
54 // to where data should be written.
55 // If tail == head the buffer is empty. The length of the ringbuffer
56 // is defined as the distance between the two.
62 #[stable(feature = "rust1", since = "1.0.0")]
63 impl<T
: Clone
> Clone
for VecDeque
<T
> {
64 fn clone(&self) -> VecDeque
<T
> {
65 self.iter().cloned().collect()
69 #[stable(feature = "rust1", since = "1.0.0")]
70 impl<T
> Drop
for VecDeque
<T
> {
71 #[unsafe_destructor_blind_to_params]
73 let (front
, back
) = self.as_mut_slices();
76 ptr
::drop_in_place(front
);
77 ptr
::drop_in_place(back
);
79 // RawVec handles deallocation
83 #[stable(feature = "rust1", since = "1.0.0")]
84 impl<T
> Default
for VecDeque
<T
> {
86 fn default() -> VecDeque
<T
> {
92 /// Marginally more convenient
94 fn ptr(&self) -> *mut T
{
98 /// Marginally more convenient
100 fn cap(&self) -> usize {
101 if mem
::size_of
::<T
>() == 0 {
102 // For zero sized types, we are always at maximum capacity
109 /// Turn ptr into a slice
111 unsafe fn buffer_as_slice(&self) -> &[T
] {
112 slice
::from_raw_parts(self.ptr(), self.cap())
115 /// Turn ptr into a mut slice
117 unsafe fn buffer_as_mut_slice(&mut self) -> &mut [T
] {
118 slice
::from_raw_parts_mut(self.ptr(), self.cap())
121 /// Moves an element out of the buffer
123 unsafe fn buffer_read(&mut self, off
: usize) -> T
{
124 ptr
::read(self.ptr().offset(off
as isize))
127 /// Writes an element into the buffer, moving it.
129 unsafe fn buffer_write(&mut self, off
: usize, value
: T
) {
130 ptr
::write(self.ptr().offset(off
as isize), value
);
133 /// Returns true if and only if the buffer is at capacity
135 fn is_full(&self) -> bool
{
136 self.cap() - self.len() == 1
139 /// Returns the index in the underlying buffer for a given logical element
142 fn wrap_index(&self, idx
: usize) -> usize {
143 wrap_index(idx
, self.cap())
146 /// Returns the index in the underlying buffer for a given logical element
149 fn wrap_add(&self, idx
: usize, addend
: usize) -> usize {
150 wrap_index(idx
.wrapping_add(addend
), self.cap())
153 /// Returns the index in the underlying buffer for a given logical element
154 /// index - subtrahend.
156 fn wrap_sub(&self, idx
: usize, subtrahend
: usize) -> usize {
157 wrap_index(idx
.wrapping_sub(subtrahend
), self.cap())
160 /// Copies a contiguous block of memory len long from src to dst
162 unsafe fn copy(&self, dst
: usize, src
: usize, len
: usize) {
163 debug_assert
!(dst
+ len
<= self.cap(),
164 "cpy dst={} src={} len={} cap={}",
169 debug_assert
!(src
+ len
<= self.cap(),
170 "cpy dst={} src={} len={} cap={}",
175 ptr
::copy(self.ptr().offset(src
as isize),
176 self.ptr().offset(dst
as isize),
180 /// Copies a contiguous block of memory len long from src to dst
182 unsafe fn copy_nonoverlapping(&self, dst
: usize, src
: usize, len
: usize) {
183 debug_assert
!(dst
+ len
<= self.cap(),
184 "cno dst={} src={} len={} cap={}",
189 debug_assert
!(src
+ len
<= self.cap(),
190 "cno dst={} src={} len={} cap={}",
195 ptr
::copy_nonoverlapping(self.ptr().offset(src
as isize),
196 self.ptr().offset(dst
as isize),
200 /// Copies a potentially wrapping block of memory len long from src to dest.
201 /// (abs(dst - src) + len) must be no larger than cap() (There must be at
202 /// most one continuous overlapping region between src and dest).
203 unsafe fn wrap_copy(&self, dst
: usize, src
: usize, len
: usize) {
205 fn diff(a
: usize, b
: usize) -> usize {
212 debug_assert
!(cmp
::min(diff(dst
, src
), self.cap() - diff(dst
, src
)) + len
<= self.cap(),
213 "wrc dst={} src={} len={} cap={}",
219 if src
== dst
|| len
== 0 {
223 let dst_after_src
= self.wrap_sub(dst
, src
) < len
;
225 let src_pre_wrap_len
= self.cap() - src
;
226 let dst_pre_wrap_len
= self.cap() - dst
;
227 let src_wraps
= src_pre_wrap_len
< len
;
228 let dst_wraps
= dst_pre_wrap_len
< len
;
230 match (dst_after_src
, src_wraps
, dst_wraps
) {
231 (_
, false, false) => {
232 // src doesn't wrap, dst doesn't wrap
235 // 1 [_ _ A A B B C C _]
236 // 2 [_ _ A A A A B B _]
239 self.copy(dst
, src
, len
);
241 (false, false, true) => {
242 // dst before src, src doesn't wrap, dst wraps
245 // 1 [A A B B _ _ _ C C]
246 // 2 [A A B B _ _ _ A A]
247 // 3 [B B B B _ _ _ A A]
250 self.copy(dst
, src
, dst_pre_wrap_len
);
251 self.copy(0, src
+ dst_pre_wrap_len
, len
- dst_pre_wrap_len
);
253 (true, false, true) => {
254 // src before dst, src doesn't wrap, dst wraps
257 // 1 [C C _ _ _ A A B B]
258 // 2 [B B _ _ _ A A B B]
259 // 3 [B B _ _ _ A A A A]
262 self.copy(0, src
+ dst_pre_wrap_len
, len
- dst_pre_wrap_len
);
263 self.copy(dst
, src
, dst_pre_wrap_len
);
265 (false, true, false) => {
266 // dst before src, src wraps, dst doesn't wrap
269 // 1 [C C _ _ _ A A B B]
270 // 2 [C C _ _ _ B B B B]
271 // 3 [C C _ _ _ B B C C]
274 self.copy(dst
, src
, src_pre_wrap_len
);
275 self.copy(dst
+ src_pre_wrap_len
, 0, len
- src_pre_wrap_len
);
277 (true, true, false) => {
278 // src before dst, src wraps, dst doesn't wrap
281 // 1 [A A B B _ _ _ C C]
282 // 2 [A A A A _ _ _ C C]
283 // 3 [C C A A _ _ _ C C]
286 self.copy(dst
+ src_pre_wrap_len
, 0, len
- src_pre_wrap_len
);
287 self.copy(dst
, src
, src_pre_wrap_len
);
289 (false, true, true) => {
290 // dst before src, src wraps, dst wraps
293 // 1 [A B C D _ E F G H]
294 // 2 [A B C D _ E G H H]
295 // 3 [A B C D _ E G H A]
296 // 4 [B C C D _ E G H A]
299 debug_assert
!(dst_pre_wrap_len
> src_pre_wrap_len
);
300 let delta
= dst_pre_wrap_len
- src_pre_wrap_len
;
301 self.copy(dst
, src
, src_pre_wrap_len
);
302 self.copy(dst
+ src_pre_wrap_len
, 0, delta
);
303 self.copy(0, delta
, len
- dst_pre_wrap_len
);
305 (true, true, true) => {
306 // src before dst, src wraps, dst wraps
309 // 1 [A B C D _ E F G H]
310 // 2 [A A B D _ E F G H]
311 // 3 [H A B D _ E F G H]
312 // 4 [H A B D _ E F F G]
315 debug_assert
!(src_pre_wrap_len
> dst_pre_wrap_len
);
316 let delta
= src_pre_wrap_len
- dst_pre_wrap_len
;
317 self.copy(delta
, 0, len
- src_pre_wrap_len
);
318 self.copy(0, self.cap() - delta
, delta
);
319 self.copy(dst
, src
, dst_pre_wrap_len
);
324 /// Frobs the head and tail sections around to handle the fact that we
325 /// just reallocated. Unsafe because it trusts old_cap.
327 unsafe fn handle_cap_increase(&mut self, old_cap
: usize) {
328 let new_cap
= self.cap();
330 // Move the shortest contiguous section of the ring buffer
332 // [o o o o o o o . ]
334 // A [o o o o o o o . . . . . . . . . ]
336 // [o o . o o o o o ]
338 // B [. . . o o o o o o o . . . . . . ]
340 // [o o o o o . o o ]
342 // C [o o o o o . . . . . . . . . o o ]
344 if self.tail
<= self.head
{
347 } else if self.head
< old_cap
- self.tail
{
349 self.copy_nonoverlapping(old_cap
, 0, self.head
);
350 self.head
+= old_cap
;
351 debug_assert
!(self.head
> self.tail
);
354 let new_tail
= new_cap
- (old_cap
- self.tail
);
355 self.copy_nonoverlapping(new_tail
, self.tail
, old_cap
- self.tail
);
356 self.tail
= new_tail
;
357 debug_assert
!(self.head
< self.tail
);
359 debug_assert
!(self.head
< self.cap());
360 debug_assert
!(self.tail
< self.cap());
361 debug_assert
!(self.cap().count_ones() == 1);
365 impl<T
> VecDeque
<T
> {
366 /// Creates an empty `VecDeque`.
367 #[stable(feature = "rust1", since = "1.0.0")]
368 pub fn new() -> VecDeque
<T
> {
369 VecDeque
::with_capacity(INITIAL_CAPACITY
)
372 /// Creates an empty `VecDeque` with space for at least `n` elements.
373 #[stable(feature = "rust1", since = "1.0.0")]
374 pub fn with_capacity(n
: usize) -> VecDeque
<T
> {
375 // +1 since the ringbuffer always leaves one space empty
376 let cap
= cmp
::max(n
+ 1, MINIMUM_CAPACITY
+ 1).next_power_of_two();
377 assert
!(cap
> n
, "capacity overflow");
382 buf
: RawVec
::with_capacity(cap
),
386 /// Retrieves an element in the `VecDeque` by index.
391 /// use std::collections::VecDeque;
393 /// let mut buf = VecDeque::new();
394 /// buf.push_back(3);
395 /// buf.push_back(4);
396 /// buf.push_back(5);
397 /// assert_eq!(buf.get(1), Some(&4));
399 #[stable(feature = "rust1", since = "1.0.0")]
400 pub fn get(&self, index
: usize) -> Option
<&T
> {
401 if index
< self.len() {
402 let idx
= self.wrap_add(self.tail
, index
);
403 unsafe { Some(&*self.ptr().offset(idx as isize)) }
409 /// Retrieves an element in the `VecDeque` mutably by index.
414 /// use std::collections::VecDeque;
416 /// let mut buf = VecDeque::new();
417 /// buf.push_back(3);
418 /// buf.push_back(4);
419 /// buf.push_back(5);
420 /// if let Some(elem) = buf.get_mut(1) {
424 /// assert_eq!(buf[1], 7);
426 #[stable(feature = "rust1", since = "1.0.0")]
427 pub fn get_mut(&mut self, index
: usize) -> Option
<&mut T
> {
428 if index
< self.len() {
429 let idx
= self.wrap_add(self.tail
, index
);
430 unsafe { Some(&mut *self.ptr().offset(idx as isize)) }
436 /// Swaps elements at indices `i` and `j`.
438 /// `i` and `j` may be equal.
440 /// Fails if there is no element with either index.
445 /// use std::collections::VecDeque;
447 /// let mut buf = VecDeque::new();
448 /// buf.push_back(3);
449 /// buf.push_back(4);
450 /// buf.push_back(5);
452 /// assert_eq!(buf[0], 5);
453 /// assert_eq!(buf[2], 3);
455 #[stable(feature = "rust1", since = "1.0.0")]
456 pub fn swap(&mut self, i
: usize, j
: usize) {
457 assert
!(i
< self.len());
458 assert
!(j
< self.len());
459 let ri
= self.wrap_add(self.tail
, i
);
460 let rj
= self.wrap_add(self.tail
, j
);
462 ptr
::swap(self.ptr().offset(ri
as isize),
463 self.ptr().offset(rj
as isize))
467 /// Returns the number of elements the `VecDeque` can hold without
473 /// use std::collections::VecDeque;
475 /// let buf: VecDeque<i32> = VecDeque::with_capacity(10);
476 /// assert!(buf.capacity() >= 10);
479 #[stable(feature = "rust1", since = "1.0.0")]
480 pub fn capacity(&self) -> usize {
484 /// Reserves the minimum capacity for exactly `additional` more elements to be inserted in the
485 /// given `VecDeque`. Does nothing if the capacity is already sufficient.
487 /// Note that the allocator may give the collection more space than it requests. Therefore
488 /// capacity can not be relied upon to be precisely minimal. Prefer `reserve` if future
489 /// insertions are expected.
493 /// Panics if the new capacity overflows `usize`.
498 /// use std::collections::VecDeque;
500 /// let mut buf: VecDeque<i32> = vec![1].into_iter().collect();
501 /// buf.reserve_exact(10);
502 /// assert!(buf.capacity() >= 11);
504 #[stable(feature = "rust1", since = "1.0.0")]
505 pub fn reserve_exact(&mut self, additional
: usize) {
506 self.reserve(additional
);
509 /// Reserves capacity for at least `additional` more elements to be inserted in the given
510 /// `VecDeque`. The collection may reserve more space to avoid frequent reallocations.
514 /// Panics if the new capacity overflows `usize`.
519 /// use std::collections::VecDeque;
521 /// let mut buf: VecDeque<i32> = vec![1].into_iter().collect();
523 /// assert!(buf.capacity() >= 11);
525 #[stable(feature = "rust1", since = "1.0.0")]
526 pub fn reserve(&mut self, additional
: usize) {
527 let old_cap
= self.cap();
528 let used_cap
= self.len() + 1;
529 let new_cap
= used_cap
.checked_add(additional
)
530 .and_then(|needed_cap
| needed_cap
.checked_next_power_of_two())
531 .expect("capacity overflow");
533 if new_cap
> self.capacity() {
534 self.buf
.reserve_exact(used_cap
, new_cap
- used_cap
);
536 self.handle_cap_increase(old_cap
);
541 /// Shrinks the capacity of the `VecDeque` as much as possible.
543 /// It will drop down as close as possible to the length but the allocator may still inform the
544 /// `VecDeque` that there is space for a few more elements.
549 /// use std::collections::VecDeque;
551 /// let mut buf = VecDeque::with_capacity(15);
552 /// buf.extend(0..4);
553 /// assert_eq!(buf.capacity(), 15);
554 /// buf.shrink_to_fit();
555 /// assert!(buf.capacity() >= 4);
557 #[stable(feature = "deque_extras_15", since = "1.5.0")]
558 pub fn shrink_to_fit(&mut self) {
559 // +1 since the ringbuffer always leaves one space empty
560 // len + 1 can't overflow for an existing, well-formed ringbuffer.
561 let target_cap
= cmp
::max(self.len() + 1, MINIMUM_CAPACITY
+ 1).next_power_of_two();
562 if target_cap
< self.cap() {
563 // There are three cases of interest:
564 // All elements are out of desired bounds
565 // Elements are contiguous, and head is out of desired bounds
566 // Elements are discontiguous, and tail is out of desired bounds
568 // At all other times, element positions are unaffected.
570 // Indicates that elements at the head should be moved.
571 let head_outside
= self.head
== 0 || self.head
>= target_cap
;
572 // Move elements from out of desired bounds (positions after target_cap)
573 if self.tail
>= target_cap
&& head_outside
{
575 // [. . . . . . . . o o o o o o o . ]
577 // [o o o o o o o . ]
579 self.copy_nonoverlapping(0, self.tail
, self.len());
581 self.head
= self.len();
583 } else if self.tail
!= 0 && self.tail
< target_cap
&& head_outside
{
585 // [. . . o o o o o o o . . . . . . ]
587 // [o o . o o o o o ]
588 let len
= self.wrap_sub(self.head
, target_cap
);
590 self.copy_nonoverlapping(0, target_cap
, len
);
593 debug_assert
!(self.head
< self.tail
);
594 } else if self.tail
>= target_cap
{
596 // [o o o o o . . . . . . . . . o o ]
598 // [o o o o o . o o ]
599 debug_assert
!(self.wrap_sub(self.head
, 1) < target_cap
);
600 let len
= self.cap() - self.tail
;
601 let new_tail
= target_cap
- len
;
603 self.copy_nonoverlapping(new_tail
, self.tail
, len
);
605 self.tail
= new_tail
;
606 debug_assert
!(self.head
< self.tail
);
609 self.buf
.shrink_to_fit(target_cap
);
611 debug_assert
!(self.head
< self.cap());
612 debug_assert
!(self.tail
< self.cap());
613 debug_assert
!(self.cap().count_ones() == 1);
617 /// Shortens a `VecDeque`, dropping excess elements from the back.
619 /// If `len` is greater than the `VecDeque`'s current length, this has no
625 /// #![feature(deque_extras)]
627 /// use std::collections::VecDeque;
629 /// let mut buf = VecDeque::new();
630 /// buf.push_back(5);
631 /// buf.push_back(10);
632 /// buf.push_back(15);
634 /// assert_eq!(buf.len(), 1);
635 /// assert_eq!(Some(&5), buf.get(0));
637 #[unstable(feature = "deque_extras",
638 reason
= "matches collection reform specification; waiting on panic semantics",
640 pub fn truncate(&mut self, len
: usize) {
641 for _
in len
..self.len() {
646 /// Returns a front-to-back iterator.
651 /// use std::collections::VecDeque;
653 /// let mut buf = VecDeque::new();
654 /// buf.push_back(5);
655 /// buf.push_back(3);
656 /// buf.push_back(4);
657 /// let b: &[_] = &[&5, &3, &4];
658 /// let c: Vec<&i32> = buf.iter().collect();
659 /// assert_eq!(&c[..], b);
661 #[stable(feature = "rust1", since = "1.0.0")]
662 pub fn iter(&self) -> Iter
<T
> {
666 ring
: unsafe { self.buffer_as_slice() }
,
670 /// Returns a front-to-back iterator that returns mutable references.
675 /// use std::collections::VecDeque;
677 /// let mut buf = VecDeque::new();
678 /// buf.push_back(5);
679 /// buf.push_back(3);
680 /// buf.push_back(4);
681 /// for num in buf.iter_mut() {
684 /// let b: &[_] = &[&mut 3, &mut 1, &mut 2];
685 /// assert_eq!(&buf.iter_mut().collect::<Vec<&mut i32>>()[..], b);
687 #[stable(feature = "rust1", since = "1.0.0")]
688 pub fn iter_mut(&mut self) -> IterMut
<T
> {
692 ring
: unsafe { self.buffer_as_mut_slice() }
,
696 /// Returns a pair of slices which contain, in order, the contents of the
699 #[stable(feature = "deque_extras_15", since = "1.5.0")]
700 pub fn as_slices(&self) -> (&[T
], &[T
]) {
702 let contiguous
= self.is_contiguous();
703 let buf
= self.buffer_as_slice();
705 let (empty
, buf
) = buf
.split_at(0);
706 (&buf
[self.tail
..self.head
], empty
)
708 let (mid
, right
) = buf
.split_at(self.tail
);
709 let (left
, _
) = mid
.split_at(self.head
);
715 /// Returns a pair of slices which contain, in order, the contents of the
718 #[stable(feature = "deque_extras_15", since = "1.5.0")]
719 pub fn as_mut_slices(&mut self) -> (&mut [T
], &mut [T
]) {
721 let contiguous
= self.is_contiguous();
722 let head
= self.head
;
723 let tail
= self.tail
;
724 let buf
= self.buffer_as_mut_slice();
727 let (empty
, buf
) = buf
.split_at_mut(0);
728 (&mut buf
[tail
..head
], empty
)
730 let (mid
, right
) = buf
.split_at_mut(tail
);
731 let (left
, _
) = mid
.split_at_mut(head
);
738 /// Returns the number of elements in the `VecDeque`.
743 /// use std::collections::VecDeque;
745 /// let mut v = VecDeque::new();
746 /// assert_eq!(v.len(), 0);
748 /// assert_eq!(v.len(), 1);
750 #[stable(feature = "rust1", since = "1.0.0")]
751 pub fn len(&self) -> usize {
752 count(self.tail
, self.head
, self.cap())
755 /// Returns true if the buffer contains no elements
760 /// use std::collections::VecDeque;
762 /// let mut v = VecDeque::new();
763 /// assert!(v.is_empty());
765 /// assert!(!v.is_empty());
767 #[stable(feature = "rust1", since = "1.0.0")]
768 pub fn is_empty(&self) -> bool
{
772 /// Create a draining iterator that removes the specified range in the
773 /// `VecDeque` and yields the removed items.
775 /// Note 1: The element range is removed even if the iterator is not
776 /// consumed until the end.
778 /// Note 2: It is unspecified how many elements are removed from the deque,
779 /// if the `Drain` value is not dropped, but the borrow it holds expires
780 /// (eg. due to mem::forget).
784 /// Panics if the starting point is greater than the end point or if
785 /// the end point is greater than the length of the vector.
790 /// use std::collections::VecDeque;
792 /// let mut v: VecDeque<_> = vec![1, 2, 3].into_iter().collect();
793 /// assert_eq!(vec![3].into_iter().collect::<VecDeque<_>>(), v.drain(2..).collect());
794 /// assert_eq!(vec![1, 2].into_iter().collect::<VecDeque<_>>(), v);
796 /// // A full range clears all contents
798 /// assert!(v.is_empty());
801 #[stable(feature = "drain", since = "1.6.0")]
802 pub fn drain
<R
>(&mut self, range
: R
) -> Drain
<T
>
803 where R
: RangeArgument
<usize>
807 // When the Drain is first created, the source deque is shortened to
808 // make sure no uninitialized or moved-from elements are accessible at
809 // all if the Drain's destructor never gets to run.
811 // Drain will ptr::read out the values to remove.
812 // When finished, the remaining data will be copied back to cover the hole,
813 // and the head/tail values will be restored correctly.
815 let len
= self.len();
816 let start
= *range
.start().unwrap_or(&0);
817 let end
= *range
.end().unwrap_or(&len
);
818 assert
!(start
<= end
, "drain lower bound was too large");
819 assert
!(end
<= len
, "drain upper bound was too large");
821 // The deque's elements are parted into three segments:
822 // * self.tail -> drain_tail
823 // * drain_tail -> drain_head
824 // * drain_head -> self.head
826 // T = self.tail; H = self.head; t = drain_tail; h = drain_head
828 // We store drain_tail as self.head, and drain_head and self.head as
829 // after_tail and after_head respectively on the Drain. This also
830 // truncates the effective array such that if the Drain is leaked, we
831 // have forgotten about the potentially moved values after the start of
835 // [. . . o o x x o o . . .]
837 let drain_tail
= self.wrap_add(self.tail
, start
);
838 let drain_head
= self.wrap_add(self.tail
, end
);
839 let head
= self.head
;
841 // "forget" about the values after the start of the drain until after
842 // the drain is complete and the Drain destructor is run.
843 self.head
= drain_tail
;
846 deque
: self as *mut _
,
847 after_tail
: drain_head
,
852 ring
: unsafe { self.buffer_as_mut_slice() }
,
857 /// Clears the buffer, removing all values.
862 /// use std::collections::VecDeque;
864 /// let mut v = VecDeque::new();
867 /// assert!(v.is_empty());
869 #[stable(feature = "rust1", since = "1.0.0")]
871 pub fn clear(&mut self) {
875 /// Provides a reference to the front element, or `None` if the sequence is
881 /// use std::collections::VecDeque;
883 /// let mut d = VecDeque::new();
884 /// assert_eq!(d.front(), None);
888 /// assert_eq!(d.front(), Some(&1));
890 #[stable(feature = "rust1", since = "1.0.0")]
891 pub fn front(&self) -> Option
<&T
> {
892 if !self.is_empty() {
899 /// Provides a mutable reference to the front element, or `None` if the
900 /// sequence is empty.
905 /// use std::collections::VecDeque;
907 /// let mut d = VecDeque::new();
908 /// assert_eq!(d.front_mut(), None);
912 /// match d.front_mut() {
913 /// Some(x) => *x = 9,
916 /// assert_eq!(d.front(), Some(&9));
918 #[stable(feature = "rust1", since = "1.0.0")]
919 pub fn front_mut(&mut self) -> Option
<&mut T
> {
920 if !self.is_empty() {
927 /// Provides a reference to the back element, or `None` if the sequence is
933 /// use std::collections::VecDeque;
935 /// let mut d = VecDeque::new();
936 /// assert_eq!(d.back(), None);
940 /// assert_eq!(d.back(), Some(&2));
942 #[stable(feature = "rust1", since = "1.0.0")]
943 pub fn back(&self) -> Option
<&T
> {
944 if !self.is_empty() {
945 Some(&self[self.len() - 1])
951 /// Provides a mutable reference to the back element, or `None` if the
952 /// sequence is empty.
957 /// use std::collections::VecDeque;
959 /// let mut d = VecDeque::new();
960 /// assert_eq!(d.back(), None);
964 /// match d.back_mut() {
965 /// Some(x) => *x = 9,
968 /// assert_eq!(d.back(), Some(&9));
970 #[stable(feature = "rust1", since = "1.0.0")]
971 pub fn back_mut(&mut self) -> Option
<&mut T
> {
972 let len
= self.len();
973 if !self.is_empty() {
974 Some(&mut self[len
- 1])
980 /// Removes the first element and returns it, or `None` if the sequence is
986 /// use std::collections::VecDeque;
988 /// let mut d = VecDeque::new();
992 /// assert_eq!(d.pop_front(), Some(1));
993 /// assert_eq!(d.pop_front(), Some(2));
994 /// assert_eq!(d.pop_front(), None);
996 #[stable(feature = "rust1", since = "1.0.0")]
997 pub fn pop_front(&mut self) -> Option
<T
> {
1001 let tail
= self.tail
;
1002 self.tail
= self.wrap_add(self.tail
, 1);
1003 unsafe { Some(self.buffer_read(tail)) }
1007 /// Inserts an element first in the sequence.
1012 /// use std::collections::VecDeque;
1014 /// let mut d = VecDeque::new();
1015 /// d.push_front(1);
1016 /// d.push_front(2);
1017 /// assert_eq!(d.front(), Some(&2));
1019 #[stable(feature = "rust1", since = "1.0.0")]
1020 pub fn push_front(&mut self, value
: T
) {
1022 let old_cap
= self.cap();
1025 self.handle_cap_increase(old_cap
);
1027 debug_assert
!(!self.is_full());
1030 self.tail
= self.wrap_sub(self.tail
, 1);
1031 let tail
= self.tail
;
1033 self.buffer_write(tail
, value
);
1037 /// Appends an element to the back of a buffer
1042 /// use std::collections::VecDeque;
1044 /// let mut buf = VecDeque::new();
1045 /// buf.push_back(1);
1046 /// buf.push_back(3);
1047 /// assert_eq!(3, *buf.back().unwrap());
1049 #[stable(feature = "rust1", since = "1.0.0")]
1050 pub fn push_back(&mut self, value
: T
) {
1052 let old_cap
= self.cap();
1055 self.handle_cap_increase(old_cap
);
1057 debug_assert
!(!self.is_full());
1060 let head
= self.head
;
1061 self.head
= self.wrap_add(self.head
, 1);
1062 unsafe { self.buffer_write(head, value) }
1065 /// Removes the last element from a buffer and returns it, or `None` if
1071 /// use std::collections::VecDeque;
1073 /// let mut buf = VecDeque::new();
1074 /// assert_eq!(buf.pop_back(), None);
1075 /// buf.push_back(1);
1076 /// buf.push_back(3);
1077 /// assert_eq!(buf.pop_back(), Some(3));
1079 #[stable(feature = "rust1", since = "1.0.0")]
1080 pub fn pop_back(&mut self) -> Option
<T
> {
1081 if self.is_empty() {
1084 self.head
= self.wrap_sub(self.head
, 1);
1085 let head
= self.head
;
1086 unsafe { Some(self.buffer_read(head)) }
1091 fn is_contiguous(&self) -> bool
{
1092 self.tail
<= self.head
1095 /// Removes an element from anywhere in the `VecDeque` and returns it, replacing it with the
1098 /// This does not preserve ordering, but is O(1).
1100 /// Returns `None` if `index` is out of bounds.
1105 /// use std::collections::VecDeque;
1107 /// let mut buf = VecDeque::new();
1108 /// assert_eq!(buf.swap_remove_back(0), None);
1109 /// buf.push_back(1);
1110 /// buf.push_back(2);
1111 /// buf.push_back(3);
1113 /// assert_eq!(buf.swap_remove_back(0), Some(1));
1114 /// assert_eq!(buf.len(), 2);
1115 /// assert_eq!(buf[0], 3);
1116 /// assert_eq!(buf[1], 2);
1118 #[stable(feature = "deque_extras_15", since = "1.5.0")]
1119 pub fn swap_remove_back(&mut self, index
: usize) -> Option
<T
> {
1120 let length
= self.len();
1121 if length
> 0 && index
< length
- 1 {
1122 self.swap(index
, length
- 1);
1123 } else if index
>= length
{
1129 /// Removes an element from anywhere in the `VecDeque` and returns it,
1130 /// replacing it with the first element.
1132 /// This does not preserve ordering, but is O(1).
1134 /// Returns `None` if `index` is out of bounds.
1139 /// use std::collections::VecDeque;
1141 /// let mut buf = VecDeque::new();
1142 /// assert_eq!(buf.swap_remove_front(0), None);
1143 /// buf.push_back(1);
1144 /// buf.push_back(2);
1145 /// buf.push_back(3);
1147 /// assert_eq!(buf.swap_remove_front(2), Some(3));
1148 /// assert_eq!(buf.len(), 2);
1149 /// assert_eq!(buf[0], 2);
1150 /// assert_eq!(buf[1], 1);
1152 #[stable(feature = "deque_extras_15", since = "1.5.0")]
1153 pub fn swap_remove_front(&mut self, index
: usize) -> Option
<T
> {
1154 let length
= self.len();
1155 if length
> 0 && index
< length
&& index
!= 0 {
1156 self.swap(index
, 0);
1157 } else if index
>= length
{
1163 /// Inserts an element at `index` within the `VecDeque`. Whichever
1164 /// end is closer to the insertion point will be moved to make room,
1165 /// and all the affected elements will be moved to new positions.
1169 /// Panics if `index` is greater than `VecDeque`'s length
1173 /// use std::collections::VecDeque;
1175 /// let mut buf = VecDeque::new();
1176 /// buf.push_back(10);
1177 /// buf.push_back(12);
1178 /// buf.insert(1, 11);
1179 /// assert_eq!(Some(&11), buf.get(1));
1181 #[stable(feature = "deque_extras_15", since = "1.5.0")]
1182 pub fn insert(&mut self, index
: usize, value
: T
) {
1183 assert
!(index
<= self.len(), "index out of bounds");
1185 let old_cap
= self.cap();
1188 self.handle_cap_increase(old_cap
);
1190 debug_assert
!(!self.is_full());
1193 // Move the least number of elements in the ring buffer and insert
1196 // At most len/2 - 1 elements will be moved. O(min(n, n-i))
1198 // There are three main cases:
1199 // Elements are contiguous
1200 // - special case when tail is 0
1201 // Elements are discontiguous and the insert is in the tail section
1202 // Elements are discontiguous and the insert is in the head section
1204 // For each of those there are two more cases:
1205 // Insert is closer to tail
1206 // Insert is closer to head
1208 // Key: H - self.head
1210 // o - Valid element
1211 // I - Insertion element
1212 // A - The element that should be after the insertion point
1213 // M - Indicates element was moved
1215 let idx
= self.wrap_add(self.tail
, index
);
1217 let distance_to_tail
= index
;
1218 let distance_to_head
= self.len() - index
;
1220 let contiguous
= self.is_contiguous();
1223 distance_to_tail
<= distance_to_head
,
1225 (true, true, _
) if index
== 0 => {
1230 // [A o o o o o o . . . . . . . . .]
1233 // [A o o o o o o o . . . . . I]
1236 self.tail
= self.wrap_sub(self.tail
, 1);
1238 (true, true, _
) => {
1240 // contiguous, insert closer to tail:
1243 // [. . . o o A o o o o . . . . . .]
1246 // [. . o o I A o o o o . . . . . .]
1249 // contiguous, insert closer to tail and tail is 0:
1253 // [o o A o o o o . . . . . . . . .]
1256 // [o I A o o o o o . . . . . . . o]
1259 let new_tail
= self.wrap_sub(self.tail
, 1);
1261 self.copy(new_tail
, self.tail
, 1);
1262 // Already moved the tail, so we only copy `index - 1` elements.
1263 self.copy(self.tail
, self.tail
+ 1, index
- 1);
1265 self.tail
= new_tail
;
1268 (true, false, _
) => {
1270 // contiguous, insert closer to head:
1273 // [. . . o o o o A o o . . . . . .]
1276 // [. . . o o o o I A o o . . . . .]
1279 self.copy(idx
+ 1, idx
, self.head
- idx
);
1280 self.head
= self.wrap_add(self.head
, 1);
1283 (false, true, true) => {
1285 // discontiguous, insert closer to tail, tail section:
1288 // [o o o o o o . . . . . o o A o o]
1291 // [o o o o o o . . . . o o I A o o]
1294 self.copy(self.tail
- 1, self.tail
, index
);
1298 (false, false, true) => {
1300 // discontiguous, insert closer to head, tail section:
1303 // [o o . . . . . . . o o o o o A o]
1306 // [o o o . . . . . . o o o o o I A]
1309 // copy elements up to new head
1310 self.copy(1, 0, self.head
);
1312 // copy last element into empty spot at bottom of buffer
1313 self.copy(0, self.cap() - 1, 1);
1315 // move elements from idx to end forward not including ^ element
1316 self.copy(idx
+ 1, idx
, self.cap() - 1 - idx
);
1321 (false, true, false) if idx
== 0 => {
1323 // discontiguous, insert is closer to tail, head section,
1324 // and is at index zero in the internal buffer:
1327 // [A o o o o o o o o o . . . o o o]
1330 // [A o o o o o o o o o . . o o o I]
1333 // copy elements up to new tail
1334 self.copy(self.tail
- 1, self.tail
, self.cap() - self.tail
);
1336 // copy last element into empty spot at bottom of buffer
1337 self.copy(self.cap() - 1, 0, 1);
1342 (false, true, false) => {
1344 // discontiguous, insert closer to tail, head section:
1347 // [o o o A o o o o o o . . . o o o]
1350 // [o o I A o o o o o o . . o o o o]
1353 // copy elements up to new tail
1354 self.copy(self.tail
- 1, self.tail
, self.cap() - self.tail
);
1356 // copy last element into empty spot at bottom of buffer
1357 self.copy(self.cap() - 1, 0, 1);
1359 // move elements from idx-1 to end forward not including ^ element
1360 self.copy(0, 1, idx
- 1);
1365 (false, false, false) => {
1367 // discontiguous, insert closer to head, head section:
1370 // [o o o o A o o . . . . . . o o o]
1373 // [o o o o I A o o . . . . . o o o]
1376 self.copy(idx
+ 1, idx
, self.head
- idx
);
1382 // tail might've been changed so we need to recalculate
1383 let new_idx
= self.wrap_add(self.tail
, index
);
1385 self.buffer_write(new_idx
, value
);
1389 /// Removes and returns the element at `index` from the `VecDeque`.
1390 /// Whichever end is closer to the removal point will be moved to make
1391 /// room, and all the affected elements will be moved to new positions.
1392 /// Returns `None` if `index` is out of bounds.
1396 /// use std::collections::VecDeque;
1398 /// let mut buf = VecDeque::new();
1399 /// buf.push_back(1);
1400 /// buf.push_back(2);
1401 /// buf.push_back(3);
1403 /// assert_eq!(buf.remove(1), Some(2));
1404 /// assert_eq!(buf.get(1), Some(&3));
1406 #[stable(feature = "rust1", since = "1.0.0")]
1407 pub fn remove(&mut self, index
: usize) -> Option
<T
> {
1408 if self.is_empty() || self.len() <= index
{
1412 // There are three main cases:
1413 // Elements are contiguous
1414 // Elements are discontiguous and the removal is in the tail section
1415 // Elements are discontiguous and the removal is in the head section
1416 // - special case when elements are technically contiguous,
1417 // but self.head = 0
1419 // For each of those there are two more cases:
1420 // Insert is closer to tail
1421 // Insert is closer to head
1423 // Key: H - self.head
1425 // o - Valid element
1426 // x - Element marked for removal
1427 // R - Indicates element that is being removed
1428 // M - Indicates element was moved
1430 let idx
= self.wrap_add(self.tail
, index
);
1432 let elem
= unsafe { Some(self.buffer_read(idx)) }
;
1434 let distance_to_tail
= index
;
1435 let distance_to_head
= self.len() - index
;
1437 let contiguous
= self.is_contiguous();
1440 distance_to_tail
<= distance_to_head
,
1442 (true, true, _
) => {
1444 // contiguous, remove closer to tail:
1447 // [. . . o o x o o o o . . . . . .]
1450 // [. . . . o o o o o o . . . . . .]
1453 self.copy(self.tail
+ 1, self.tail
, index
);
1457 (true, false, _
) => {
1459 // contiguous, remove closer to head:
1462 // [. . . o o o o x o o . . . . . .]
1465 // [. . . o o o o o o . . . . . . .]
1468 self.copy(idx
, idx
+ 1, self.head
- idx
- 1);
1472 (false, true, true) => {
1474 // discontiguous, remove closer to tail, tail section:
1477 // [o o o o o o . . . . . o o x o o]
1480 // [o o o o o o . . . . . . o o o o]
1483 self.copy(self.tail
+ 1, self.tail
, index
);
1484 self.tail
= self.wrap_add(self.tail
, 1);
1487 (false, false, false) => {
1489 // discontiguous, remove closer to head, head section:
1492 // [o o o o x o o . . . . . . o o o]
1495 // [o o o o o o . . . . . . . o o o]
1498 self.copy(idx
, idx
+ 1, self.head
- idx
- 1);
1502 (false, false, true) => {
1504 // discontiguous, remove closer to head, tail section:
1507 // [o o o . . . . . . o o o o o x o]
1510 // [o o . . . . . . . o o o o o o o]
1513 // or quasi-discontiguous, remove next to head, tail section:
1516 // [. . . . . . . . . o o o o o x o]
1519 // [. . . . . . . . . o o o o o o .]
1522 // draw in elements in the tail section
1523 self.copy(idx
, idx
+ 1, self.cap() - idx
- 1);
1525 // Prevents underflow.
1527 // copy first element into empty spot
1528 self.copy(self.cap() - 1, 0, 1);
1530 // move elements in the head section backwards
1531 self.copy(0, 1, self.head
- 1);
1534 self.head
= self.wrap_sub(self.head
, 1);
1537 (false, true, false) => {
1539 // discontiguous, remove closer to tail, head section:
1542 // [o o x o o o o o o o . . . o o o]
1545 // [o o o o o o o o o o . . . . o o]
1548 // draw in elements up to idx
1549 self.copy(1, 0, idx
);
1551 // copy last element into empty spot
1552 self.copy(0, self.cap() - 1, 1);
1554 // move elements from tail to end forward, excluding the last one
1555 self.copy(self.tail
+ 1, self.tail
, self.cap() - self.tail
- 1);
1557 self.tail
= self.wrap_add(self.tail
, 1);
1565 /// Splits the collection into two at the given index.
1567 /// Returns a newly allocated `Self`. `self` contains elements `[0, at)`,
1568 /// and the returned `Self` contains elements `[at, len)`.
1570 /// Note that the capacity of `self` does not change.
1574 /// Panics if `at > len`
1579 /// use std::collections::VecDeque;
1581 /// let mut buf: VecDeque<_> = vec![1,2,3].into_iter().collect();
1582 /// let buf2 = buf.split_off(1);
1583 /// // buf = [1], buf2 = [2, 3]
1584 /// assert_eq!(buf.len(), 1);
1585 /// assert_eq!(buf2.len(), 2);
1588 #[stable(feature = "split_off", since = "1.4.0")]
1589 pub fn split_off(&mut self, at
: usize) -> Self {
1590 let len
= self.len();
1591 assert
!(at
<= len
, "`at` out of bounds");
1593 let other_len
= len
- at
;
1594 let mut other
= VecDeque
::with_capacity(other_len
);
1597 let (first_half
, second_half
) = self.as_slices();
1599 let first_len
= first_half
.len();
1600 let second_len
= second_half
.len();
1602 // `at` lies in the first half.
1603 let amount_in_first
= first_len
- at
;
1605 ptr
::copy_nonoverlapping(first_half
.as_ptr().offset(at
as isize),
1609 // just take all of the second half.
1610 ptr
::copy_nonoverlapping(second_half
.as_ptr(),
1611 other
.ptr().offset(amount_in_first
as isize),
1614 // `at` lies in the second half, need to factor in the elements we skipped
1615 // in the first half.
1616 let offset
= at
- first_len
;
1617 let amount_in_second
= second_len
- offset
;
1618 ptr
::copy_nonoverlapping(second_half
.as_ptr().offset(offset
as isize),
1624 // Cleanup where the ends of the buffers are
1625 self.head
= self.wrap_sub(self.head
, other_len
);
1626 other
.head
= other
.wrap_index(other_len
);
1631 /// Moves all the elements of `other` into `Self`, leaving `other` empty.
1635 /// Panics if the new number of elements in self overflows a `usize`.
1640 /// use std::collections::VecDeque;
1642 /// let mut buf: VecDeque<_> = vec![1, 2, 3].into_iter().collect();
1643 /// let mut buf2: VecDeque<_> = vec![4, 5, 6].into_iter().collect();
1644 /// buf.append(&mut buf2);
1645 /// assert_eq!(buf.len(), 6);
1646 /// assert_eq!(buf2.len(), 0);
1649 #[stable(feature = "append", since = "1.4.0")]
1650 pub fn append(&mut self, other
: &mut Self) {
1652 self.extend(other
.drain(..));
1655 /// Retains only the elements specified by the predicate.
1657 /// In other words, remove all elements `e` such that `f(&e)` returns false.
1658 /// This method operates in place and preserves the order of the retained
1664 /// use std::collections::VecDeque;
1666 /// let mut buf = VecDeque::new();
1667 /// buf.extend(1..5);
1668 /// buf.retain(|&x| x%2 == 0);
1670 /// let v: Vec<_> = buf.into_iter().collect();
1671 /// assert_eq!(&v[..], &[2, 4]);
1673 #[stable(feature = "vec_deque_retain", since = "1.4.0")]
1674 pub fn retain
<F
>(&mut self, mut f
: F
)
1675 where F
: FnMut(&T
) -> bool
1677 let len
= self.len();
1683 self.swap(i
- del
, i
);
1687 self.truncate(len
- del
);
1692 impl<T
: Clone
> VecDeque
<T
> {
1693 /// Modifies the `VecDeque` in-place so that `len()` is equal to new_len,
1694 /// either by removing excess elements or by appending copies of a value to the back.
1699 /// #![feature(deque_extras)]
1701 /// use std::collections::VecDeque;
1703 /// let mut buf = VecDeque::new();
1704 /// buf.push_back(5);
1705 /// buf.push_back(10);
1706 /// buf.push_back(15);
1707 /// buf.resize(2, 0);
1708 /// buf.resize(6, 20);
1709 /// for (a, b) in [5, 10, 20, 20, 20, 20].iter().zip(&buf) {
1710 /// assert_eq!(a, b);
1713 #[unstable(feature = "deque_extras",
1714 reason
= "matches collection reform specification; waiting on panic semantics",
1716 pub fn resize(&mut self, new_len
: usize, value
: T
) {
1717 let len
= self.len();
1720 self.extend(repeat(value
).take(new_len
- len
))
1722 self.truncate(new_len
);
1727 /// Returns the index in the underlying buffer for a given logical element index.
1729 fn wrap_index(index
: usize, size
: usize) -> usize {
1730 // size is always a power of 2
1731 debug_assert
!(size
.is_power_of_two());
1735 /// Calculate the number of elements left to be read in the buffer
1737 fn count(tail
: usize, head
: usize, size
: usize) -> usize {
1738 // size is always a power of 2
1739 (head
.wrapping_sub(tail
)) & (size
- 1)
1742 /// `VecDeque` iterator.
1743 #[stable(feature = "rust1", since = "1.0.0")]
1744 pub struct Iter
<'a
, T
: 'a
> {
1750 // FIXME(#19839) Remove in favor of `#[derive(Clone)]`
1751 #[stable(feature = "rust1", since = "1.0.0")]
1752 impl<'a
, T
> Clone
for Iter
<'a
, T
> {
1753 fn clone(&self) -> Iter
<'a
, T
> {
1762 #[stable(feature = "rust1", since = "1.0.0")]
1763 impl<'a
, T
> Iterator
for Iter
<'a
, T
> {
1767 fn next(&mut self) -> Option
<&'a T
> {
1768 if self.tail
== self.head
{
1771 let tail
= self.tail
;
1772 self.tail
= wrap_index(self.tail
.wrapping_add(1), self.ring
.len());
1773 unsafe { Some(self.ring.get_unchecked(tail)) }
1777 fn size_hint(&self) -> (usize, Option
<usize>) {
1778 let len
= count(self.tail
, self.head
, self.ring
.len());
1783 #[stable(feature = "rust1", since = "1.0.0")]
1784 impl<'a
, T
> DoubleEndedIterator
for Iter
<'a
, T
> {
1786 fn next_back(&mut self) -> Option
<&'a T
> {
1787 if self.tail
== self.head
{
1790 self.head
= wrap_index(self.head
.wrapping_sub(1), self.ring
.len());
1791 unsafe { Some(self.ring.get_unchecked(self.head)) }
1795 #[stable(feature = "rust1", since = "1.0.0")]
1796 impl<'a
, T
> ExactSizeIterator
for Iter
<'a
, T
> {}
1798 /// `VecDeque` mutable iterator.
1799 #[stable(feature = "rust1", since = "1.0.0")]
1800 pub struct IterMut
<'a
, T
: 'a
> {
1806 #[stable(feature = "rust1", since = "1.0.0")]
1807 impl<'a
, T
> Iterator
for IterMut
<'a
, T
> {
1808 type Item
= &'a
mut T
;
1811 fn next(&mut self) -> Option
<&'a
mut T
> {
1812 if self.tail
== self.head
{
1815 let tail
= self.tail
;
1816 self.tail
= wrap_index(self.tail
.wrapping_add(1), self.ring
.len());
1819 let elem
= self.ring
.get_unchecked_mut(tail
);
1820 Some(&mut *(elem
as *mut _
))
1825 fn size_hint(&self) -> (usize, Option
<usize>) {
1826 let len
= count(self.tail
, self.head
, self.ring
.len());
1831 #[stable(feature = "rust1", since = "1.0.0")]
1832 impl<'a
, T
> DoubleEndedIterator
for IterMut
<'a
, T
> {
1834 fn next_back(&mut self) -> Option
<&'a
mut T
> {
1835 if self.tail
== self.head
{
1838 self.head
= wrap_index(self.head
.wrapping_sub(1), self.ring
.len());
1841 let elem
= self.ring
.get_unchecked_mut(self.head
);
1842 Some(&mut *(elem
as *mut _
))
1847 #[stable(feature = "rust1", since = "1.0.0")]
1848 impl<'a
, T
> ExactSizeIterator
for IterMut
<'a
, T
> {}
1850 /// A by-value VecDeque iterator
1852 #[stable(feature = "rust1", since = "1.0.0")]
1853 pub struct IntoIter
<T
> {
1857 #[stable(feature = "rust1", since = "1.0.0")]
1858 impl<T
> Iterator
for IntoIter
<T
> {
1862 fn next(&mut self) -> Option
<T
> {
1863 self.inner
.pop_front()
1867 fn size_hint(&self) -> (usize, Option
<usize>) {
1868 let len
= self.inner
.len();
1873 #[stable(feature = "rust1", since = "1.0.0")]
1874 impl<T
> DoubleEndedIterator
for IntoIter
<T
> {
1876 fn next_back(&mut self) -> Option
<T
> {
1877 self.inner
.pop_back()
1881 #[stable(feature = "rust1", since = "1.0.0")]
1882 impl<T
> ExactSizeIterator
for IntoIter
<T
> {}
1884 /// A draining VecDeque iterator
1885 #[stable(feature = "drain", since = "1.6.0")]
1886 pub struct Drain
<'a
, T
: 'a
> {
1890 deque
: *mut VecDeque
<T
>,
1893 #[stable(feature = "drain", since = "1.6.0")]
1894 unsafe impl<'a
, T
: Sync
> Sync
for Drain
<'a
, T
> {}
1895 #[stable(feature = "drain", since = "1.6.0")]
1896 unsafe impl<'a
, T
: Send
> Send
for Drain
<'a
, T
> {}
1898 #[stable(feature = "rust1", since = "1.0.0")]
1899 impl<'a
, T
: 'a
> Drop
for Drain
<'a
, T
> {
1900 fn drop(&mut self) {
1901 for _
in self.by_ref() {}
1903 let source_deque
= unsafe { &mut *self.deque }
;
1905 // T = source_deque_tail; H = source_deque_head; t = drain_tail; h = drain_head
1908 // [. . . o o x x o o . . .]
1910 let orig_tail
= source_deque
.tail
;
1911 let drain_tail
= source_deque
.head
;
1912 let drain_head
= self.after_tail
;
1913 let orig_head
= self.after_head
;
1915 let tail_len
= count(orig_tail
, drain_tail
, source_deque
.cap());
1916 let head_len
= count(drain_head
, orig_head
, source_deque
.cap());
1918 // Restore the original head value
1919 source_deque
.head
= orig_head
;
1921 match (tail_len
, head_len
) {
1923 source_deque
.head
= 0;
1924 source_deque
.tail
= 0;
1927 source_deque
.tail
= drain_head
;
1930 source_deque
.head
= drain_tail
;
1934 if tail_len
<= head_len
{
1935 source_deque
.tail
= source_deque
.wrap_sub(drain_head
, tail_len
);
1936 source_deque
.wrap_copy(source_deque
.tail
, orig_tail
, tail_len
);
1938 source_deque
.head
= source_deque
.wrap_add(drain_tail
, head_len
);
1939 source_deque
.wrap_copy(drain_tail
, drain_head
, head_len
);
1947 #[stable(feature = "rust1", since = "1.0.0")]
1948 impl<'a
, T
: 'a
> Iterator
for Drain
<'a
, T
> {
1952 fn next(&mut self) -> Option
<T
> {
1953 self.iter
.next().map(|elt
| unsafe { ptr::read(elt) }
)
1957 fn size_hint(&self) -> (usize, Option
<usize>) {
1958 self.iter
.size_hint()
1962 #[stable(feature = "rust1", since = "1.0.0")]
1963 impl<'a
, T
: 'a
> DoubleEndedIterator
for Drain
<'a
, T
> {
1965 fn next_back(&mut self) -> Option
<T
> {
1966 self.iter
.next_back().map(|elt
| unsafe { ptr::read(elt) }
)
1970 #[stable(feature = "rust1", since = "1.0.0")]
1971 impl<'a
, T
: 'a
> ExactSizeIterator
for Drain
<'a
, T
> {}
1973 #[stable(feature = "rust1", since = "1.0.0")]
1974 impl<A
: PartialEq
> PartialEq
for VecDeque
<A
> {
1975 fn eq(&self, other
: &VecDeque
<A
>) -> bool
{
1976 if self.len() != other
.len() {
1979 let (sa
, sb
) = self.as_slices();
1980 let (oa
, ob
) = other
.as_slices();
1981 if sa
.len() == oa
.len() {
1982 sa
== oa
&& sb
== ob
1983 } else if sa
.len() < oa
.len() {
1984 // Always divisible in three sections, for example:
1985 // self: [a b c|d e f]
1986 // other: [0 1 2 3|4 5]
1987 // front = 3, mid = 1,
1988 // [a b c] == [0 1 2] && [d] == [3] && [e f] == [4 5]
1989 let front
= sa
.len();
1990 let mid
= oa
.len() - front
;
1992 let (oa_front
, oa_mid
) = oa
.split_at(front
);
1993 let (sb_mid
, sb_back
) = sb
.split_at(mid
);
1994 debug_assert_eq
!(sa
.len(), oa_front
.len());
1995 debug_assert_eq
!(sb_mid
.len(), oa_mid
.len());
1996 debug_assert_eq
!(sb_back
.len(), ob
.len());
1997 sa
== oa_front
&& sb_mid
== oa_mid
&& sb_back
== ob
1999 let front
= oa
.len();
2000 let mid
= sa
.len() - front
;
2002 let (sa_front
, sa_mid
) = sa
.split_at(front
);
2003 let (ob_mid
, ob_back
) = ob
.split_at(mid
);
2004 debug_assert_eq
!(sa_front
.len(), oa
.len());
2005 debug_assert_eq
!(sa_mid
.len(), ob_mid
.len());
2006 debug_assert_eq
!(sb
.len(), ob_back
.len());
2007 sa_front
== oa
&& sa_mid
== ob_mid
&& sb
== ob_back
2012 #[stable(feature = "rust1", since = "1.0.0")]
2013 impl<A
: Eq
> Eq
for VecDeque
<A
> {}
2015 #[stable(feature = "rust1", since = "1.0.0")]
2016 impl<A
: PartialOrd
> PartialOrd
for VecDeque
<A
> {
2017 fn partial_cmp(&self, other
: &VecDeque
<A
>) -> Option
<Ordering
> {
2018 self.iter().partial_cmp(other
.iter())
2022 #[stable(feature = "rust1", since = "1.0.0")]
2023 impl<A
: Ord
> Ord
for VecDeque
<A
> {
2025 fn cmp(&self, other
: &VecDeque
<A
>) -> Ordering
{
2026 self.iter().cmp(other
.iter())
2030 #[stable(feature = "rust1", since = "1.0.0")]
2031 impl<A
: Hash
> Hash
for VecDeque
<A
> {
2032 fn hash
<H
: Hasher
>(&self, state
: &mut H
) {
2033 self.len().hash(state
);
2034 let (a
, b
) = self.as_slices();
2035 Hash
::hash_slice(a
, state
);
2036 Hash
::hash_slice(b
, state
);
2040 #[stable(feature = "rust1", since = "1.0.0")]
2041 impl<A
> Index
<usize> for VecDeque
<A
> {
2045 fn index(&self, index
: usize) -> &A
{
2046 self.get(index
).expect("Out of bounds access")
2050 #[stable(feature = "rust1", since = "1.0.0")]
2051 impl<A
> IndexMut
<usize> for VecDeque
<A
> {
2053 fn index_mut(&mut self, index
: usize) -> &mut A
{
2054 self.get_mut(index
).expect("Out of bounds access")
2058 #[stable(feature = "rust1", since = "1.0.0")]
2059 impl<A
> FromIterator
<A
> for VecDeque
<A
> {
2060 fn from_iter
<T
: IntoIterator
<Item
= A
>>(iter
: T
) -> VecDeque
<A
> {
2061 let iterator
= iter
.into_iter();
2062 let (lower
, _
) = iterator
.size_hint();
2063 let mut deq
= VecDeque
::with_capacity(lower
);
2064 deq
.extend(iterator
);
2069 #[stable(feature = "rust1", since = "1.0.0")]
2070 impl<T
> IntoIterator
for VecDeque
<T
> {
2072 type IntoIter
= IntoIter
<T
>;
2074 /// Consumes the list into a front-to-back iterator yielding elements by
2076 fn into_iter(self) -> IntoIter
<T
> {
2077 IntoIter { inner: self }
2081 #[stable(feature = "rust1", since = "1.0.0")]
2082 impl<'a
, T
> IntoIterator
for &'a VecDeque
<T
> {
2084 type IntoIter
= Iter
<'a
, T
>;
2086 fn into_iter(self) -> Iter
<'a
, T
> {
2091 #[stable(feature = "rust1", since = "1.0.0")]
2092 impl<'a
, T
> IntoIterator
for &'a
mut VecDeque
<T
> {
2093 type Item
= &'a
mut T
;
2094 type IntoIter
= IterMut
<'a
, T
>;
2096 fn into_iter(mut self) -> IterMut
<'a
, T
> {
2101 #[stable(feature = "rust1", since = "1.0.0")]
2102 impl<A
> Extend
<A
> for VecDeque
<A
> {
2103 fn extend
<T
: IntoIterator
<Item
= A
>>(&mut self, iter
: T
) {
2105 self.push_back(elt
);
2110 #[stable(feature = "extend_ref", since = "1.2.0")]
2111 impl<'a
, T
: 'a
+ Copy
> Extend
<&'a T
> for VecDeque
<T
> {
2112 fn extend
<I
: IntoIterator
<Item
= &'a T
>>(&mut self, iter
: I
) {
2113 self.extend(iter
.into_iter().cloned());
2117 #[stable(feature = "rust1", since = "1.0.0")]
2118 impl<T
: fmt
::Debug
> fmt
::Debug
for VecDeque
<T
> {
2119 fn fmt(&self, f
: &mut fmt
::Formatter
) -> fmt
::Result
{
2120 f
.debug_list().entries(self).finish()
2126 use core
::iter
::Iterator
;
2127 use core
::option
::Option
::Some
;
2131 use super::VecDeque
;
2134 fn bench_push_back_100(b
: &mut test
::Bencher
) {
2135 let mut deq
= VecDeque
::with_capacity(101);
2146 fn bench_push_front_100(b
: &mut test
::Bencher
) {
2147 let mut deq
= VecDeque
::with_capacity(101);
2158 fn bench_pop_back_100(b
: &mut test
::Bencher
) {
2159 let mut deq
= VecDeque
::<i32>::with_capacity(101);
2164 while !deq
.is_empty() {
2165 test
::black_box(deq
.pop_back());
2171 fn bench_pop_front_100(b
: &mut test
::Bencher
) {
2172 let mut deq
= VecDeque
::<i32>::with_capacity(101);
2177 while !deq
.is_empty() {
2178 test
::black_box(deq
.pop_front());
2184 fn test_swap_front_back_remove() {
2185 fn test(back
: bool
) {
2186 // This test checks that every single combination of tail position and length is tested.
2187 // Capacity 15 should be large enough to cover every case.
2188 let mut tester
= VecDeque
::with_capacity(15);
2189 let usable_cap
= tester
.capacity();
2190 let final_len
= usable_cap
/ 2;
2192 for len
in 0..final_len
{
2193 let expected
= if back
{
2196 (0..len
).rev().collect()
2198 for tail_pos
in 0..usable_cap
{
2199 tester
.tail
= tail_pos
;
2200 tester
.head
= tail_pos
;
2202 for i
in 0..len
* 2 {
2203 tester
.push_front(i
);
2206 assert_eq
!(tester
.swap_remove_back(i
), Some(len
* 2 - 1 - i
));
2209 for i
in 0..len
* 2 {
2210 tester
.push_back(i
);
2213 let idx
= tester
.len() - 1 - i
;
2214 assert_eq
!(tester
.swap_remove_front(idx
), Some(len
* 2 - 1 - i
));
2217 assert
!(tester
.tail
< tester
.cap());
2218 assert
!(tester
.head
< tester
.cap());
2219 assert_eq
!(tester
, expected
);
2229 // This test checks that every single combination of tail position, length, and
2230 // insertion position is tested. Capacity 15 should be large enough to cover every case.
2232 let mut tester
= VecDeque
::with_capacity(15);
2233 // can't guarantee we got 15, so have to get what we got.
2234 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2235 // this test isn't covering what it wants to
2236 let cap
= tester
.capacity();
2239 // len is the length *after* insertion
2241 // 0, 1, 2, .., len - 1
2242 let expected
= (0..).take(len
).collect();
2243 for tail_pos
in 0..cap
{
2244 for to_insert
in 0..len
{
2245 tester
.tail
= tail_pos
;
2246 tester
.head
= tail_pos
;
2249 tester
.push_back(i
);
2252 tester
.insert(to_insert
, to_insert
);
2253 assert
!(tester
.tail
< tester
.cap());
2254 assert
!(tester
.head
< tester
.cap());
2255 assert_eq
!(tester
, expected
);
2263 // This test checks that every single combination of tail position, length, and
2264 // removal position is tested. Capacity 15 should be large enough to cover every case.
2266 let mut tester
= VecDeque
::with_capacity(15);
2267 // can't guarantee we got 15, so have to get what we got.
2268 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2269 // this test isn't covering what it wants to
2270 let cap
= tester
.capacity();
2272 // len is the length *after* removal
2273 for len
in 0..cap
- 1 {
2274 // 0, 1, 2, .., len - 1
2275 let expected
= (0..).take(len
).collect();
2276 for tail_pos
in 0..cap
{
2277 for to_remove
in 0..len
+ 1 {
2278 tester
.tail
= tail_pos
;
2279 tester
.head
= tail_pos
;
2282 tester
.push_back(1234);
2284 tester
.push_back(i
);
2286 if to_remove
== len
{
2287 tester
.push_back(1234);
2289 tester
.remove(to_remove
);
2290 assert
!(tester
.tail
< tester
.cap());
2291 assert
!(tester
.head
< tester
.cap());
2292 assert_eq
!(tester
, expected
);
2300 let mut tester
: VecDeque
<usize> = VecDeque
::with_capacity(7);
2302 let cap
= tester
.capacity();
2303 for len
in 0..cap
+ 1 {
2304 for tail
in 0..cap
+ 1 {
2305 for drain_start
in 0..len
+ 1 {
2306 for drain_end
in drain_start
..len
+ 1 {
2310 tester
.push_back(i
);
2313 // Check that we drain the correct values
2314 let drained
: VecDeque
<_
> = tester
.drain(drain_start
..drain_end
).collect();
2315 let drained_expected
: VecDeque
<_
> = (drain_start
..drain_end
).collect();
2316 assert_eq
!(drained
, drained_expected
);
2318 // We shouldn't have changed the capacity or made the
2319 // head or tail out of bounds
2320 assert_eq
!(tester
.capacity(), cap
);
2321 assert
!(tester
.tail
< tester
.cap());
2322 assert
!(tester
.head
< tester
.cap());
2324 // We should see the correct values in the VecDeque
2325 let expected
: VecDeque
<_
> = (0..drain_start
)
2326 .chain(drain_end
..len
)
2328 assert_eq
!(expected
, tester
);
2336 fn test_shrink_to_fit() {
2337 // This test checks that every single combination of head and tail position,
2338 // is tested. Capacity 15 should be large enough to cover every case.
2340 let mut tester
= VecDeque
::with_capacity(15);
2341 // can't guarantee we got 15, so have to get what we got.
2342 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2343 // this test isn't covering what it wants to
2344 let cap
= tester
.capacity();
2346 let max_cap
= tester
.capacity();
2348 for len
in 0..cap
+ 1 {
2349 // 0, 1, 2, .., len - 1
2350 let expected
= (0..).take(len
).collect();
2351 for tail_pos
in 0..max_cap
+ 1 {
2352 tester
.tail
= tail_pos
;
2353 tester
.head
= tail_pos
;
2356 tester
.push_back(i
);
2358 tester
.shrink_to_fit();
2359 assert
!(tester
.capacity() <= cap
);
2360 assert
!(tester
.tail
< tester
.cap());
2361 assert
!(tester
.head
< tester
.cap());
2362 assert_eq
!(tester
, expected
);
2368 fn test_split_off() {
2369 // This test checks that every single combination of tail position, length, and
2370 // split position is tested. Capacity 15 should be large enough to cover every case.
2372 let mut tester
= VecDeque
::with_capacity(15);
2373 // can't guarantee we got 15, so have to get what we got.
2374 // 15 would be great, but we will definitely get 2^k - 1, for k >= 4, or else
2375 // this test isn't covering what it wants to
2376 let cap
= tester
.capacity();
2378 // len is the length *before* splitting
2380 // index to split at
2381 for at
in 0..len
+ 1 {
2382 // 0, 1, 2, .., at - 1 (may be empty)
2383 let expected_self
= (0..).take(at
).collect();
2384 // at, at + 1, .., len - 1 (may be empty)
2385 let expected_other
= (at
..).take(len
- at
).collect();
2387 for tail_pos
in 0..cap
{
2388 tester
.tail
= tail_pos
;
2389 tester
.head
= tail_pos
;
2391 tester
.push_back(i
);
2393 let result
= tester
.split_off(at
);
2394 assert
!(tester
.tail
< tester
.cap());
2395 assert
!(tester
.head
< tester
.cap());
2396 assert
!(result
.tail
< result
.cap());
2397 assert
!(result
.head
< result
.cap());
2398 assert_eq
!(tester
, expected_self
);
2399 assert_eq
!(result
, expected_other
);