Skip to main content

alloc/collections/vec_deque/
into_iter.rs

1use core::iter::{FusedIterator, TrustedLen};
2use core::mem::MaybeUninit;
3use core::num::NonZero;
4use core::ops::Try;
5use core::{array, fmt, ptr};
6
7use super::VecDeque;
8use super::index::WrappedIndex;
9use crate::alloc::{Allocator, Global};
10
11/// An owning iterator over the elements of a `VecDeque`.
12///
13/// This `struct` is created by the [`into_iter`] method on [`VecDeque`]
14/// (provided by the [`IntoIterator`] trait). See its documentation for more.
15///
16/// [`into_iter`]: VecDeque::into_iter
17#[derive(Clone)]
18#[stable(feature = "rust1", since = "1.0.0")]
19pub struct IntoIter<
20    T,
21    #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")] A: Allocator = Global,
22> {
23    inner: VecDeque<T, A>,
24}
25
26impl<T, A: Allocator> IntoIter<T, A> {
27    pub(super) fn new(inner: VecDeque<T, A>) -> Self {
28        IntoIter { inner }
29    }
30
31    pub(super) fn into_vecdeque(self) -> VecDeque<T, A> {
32        self.inner
33    }
34
35    /// Returns a reference to the underlying allocator.
36    #[unstable(feature = "allocator_ext", issue = "163177", implied_by = "allocator_api")]
37    #[inline]
38    pub fn allocator(&self) -> &A {
39        self.inner.allocator()
40    }
41}
42
43#[stable(feature = "collection_debug", since = "1.17.0")]
44impl<T: fmt::Debug, A: Allocator> fmt::Debug for IntoIter<T, A> {
45    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
46        f.debug_tuple("IntoIter").field(&self.inner).finish()
47    }
48}
49
50#[stable(feature = "rust1", since = "1.0.0")]
51impl<T, A: Allocator> Iterator for IntoIter<T, A> {
52    type Item = T;
53
54    #[inline]
55    fn next(&mut self) -> Option<T> {
56        self.inner.pop_front()
57    }
58
59    #[inline]
60    fn size_hint(&self) -> (usize, Option<usize>) {
61        let len = self.inner.len();
62        (len, Some(len))
63    }
64
65    #[inline]
66    fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
67        let len = self.inner.len;
68        let rem = if len < n {
69            self.inner.clear();
70            n - len
71        } else {
72            self.inner.drain(..n);
73            0
74        };
75        NonZero::new(rem).map_or(Ok(()), Err)
76    }
77
78    #[inline]
79    fn count(self) -> usize {
80        self.inner.len
81    }
82
83    fn try_fold<B, F, R>(&mut self, mut init: B, mut f: F) -> R
84    where
85        F: FnMut(B, Self::Item) -> R,
86        R: Try<Output = B>,
87    {
88        struct Guard<'a, T, A: Allocator> {
89            deque: &'a mut VecDeque<T, A>,
90            // `consumed <= deque.len` always holds.
91            consumed: usize,
92        }
93
94        impl<'a, T, A: Allocator> Drop for Guard<'a, T, A> {
95            fn drop(&mut self) {
96                self.deque.len -= self.consumed;
97                self.deque.head = self.deque.to_wrapped_index(self.consumed);
98            }
99        }
100
101        let mut guard = Guard { deque: &mut self.inner, consumed: 0 };
102
103        let (head, tail) = guard.deque.as_slices();
104
105        init = head
106            .iter()
107            .map(|elem| {
108                guard.consumed += 1;
109                // SAFETY: Because we incremented `guard.consumed`, the
110                // deque effectively forgot the element, so we can take
111                // ownership
112                unsafe { ptr::read(elem) }
113            })
114            .try_fold(init, &mut f)?;
115
116        tail.iter()
117            .map(|elem| {
118                guard.consumed += 1;
119                // SAFETY: Same as above.
120                unsafe { ptr::read(elem) }
121            })
122            .try_fold(init, &mut f)
123    }
124
125    #[inline]
126    fn fold<B, F>(mut self, init: B, mut f: F) -> B
127    where
128        F: FnMut(B, Self::Item) -> B,
129    {
130        match self.try_fold(init, |b, item| Ok::<B, !>(f(b, item))) {
131            Ok(b) => b,
132        }
133    }
134
135    #[inline]
136    fn last(mut self) -> Option<Self::Item> {
137        self.inner.pop_back()
138    }
139
140    fn next_chunk<const N: usize>(
141        &mut self,
142    ) -> Result<[Self::Item; N], array::IntoIter<Self::Item, N>> {
143        let mut raw_arr = [const { MaybeUninit::uninit() }; N];
144        let raw_arr_ptr = raw_arr.as_mut_ptr().cast();
145        let (head, tail) = self.inner.as_slices();
146
147        if head.len() >= N {
148            // SAFETY: By manually adjusting the head and length of the deque, we effectively
149            // make it forget the first `N` elements, so taking ownership of them is safe.
150            unsafe { ptr::copy_nonoverlapping(head.as_ptr(), raw_arr_ptr, N) };
151            self.inner.head = self.inner.to_wrapped_index(N);
152            self.inner.len -= N;
153            // SAFETY: We initialized the entire array with items from `head`
154            return Ok(unsafe { raw_arr.transpose().assume_init() });
155        }
156
157        // SAFETY: Same argument as above.
158        unsafe { ptr::copy_nonoverlapping(head.as_ptr(), raw_arr_ptr, head.len()) };
159        let remaining = N - head.len();
160
161        if tail.len() >= remaining {
162            // SAFETY: Same argument as above.
163            unsafe {
164                ptr::copy_nonoverlapping(tail.as_ptr(), raw_arr_ptr.add(head.len()), remaining)
165            };
166            self.inner.head = self.inner.to_wrapped_index(N);
167            self.inner.len -= N;
168            // SAFETY: We initialized the entire array with items from `head` and `tail`
169            Ok(unsafe { raw_arr.transpose().assume_init() })
170        } else {
171            // SAFETY: Same argument as above.
172            unsafe {
173                ptr::copy_nonoverlapping(tail.as_ptr(), raw_arr_ptr.add(head.len()), tail.len())
174            };
175            let init = head.len() + tail.len();
176            // We completely drained all the deques elements.
177            self.inner.head = WrappedIndex::zero();
178            self.inner.len = 0;
179            // SAFETY: We copied all elements from both slices to the beginning of the array, so
180            // the given range is initialized.
181            Err(unsafe { array::IntoIter::new_unchecked(raw_arr, 0..init) })
182        }
183    }
184}
185
186#[stable(feature = "rust1", since = "1.0.0")]
187impl<T, A: Allocator> DoubleEndedIterator for IntoIter<T, A> {
188    #[inline]
189    fn next_back(&mut self) -> Option<T> {
190        self.inner.pop_back()
191    }
192
193    #[inline]
194    fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> {
195        let len = self.inner.len;
196        let rem = if len < n {
197            self.inner.clear();
198            n - len
199        } else {
200            self.inner.truncate(len - n);
201            0
202        };
203        NonZero::new(rem).map_or(Ok(()), Err)
204    }
205
206    fn try_rfold<B, F, R>(&mut self, mut init: B, mut f: F) -> R
207    where
208        F: FnMut(B, Self::Item) -> R,
209        R: Try<Output = B>,
210    {
211        struct Guard<'a, T, A: Allocator> {
212            deque: &'a mut VecDeque<T, A>,
213            // `consumed <= deque.len` always holds.
214            consumed: usize,
215        }
216
217        impl<'a, T, A: Allocator> Drop for Guard<'a, T, A> {
218            fn drop(&mut self) {
219                self.deque.len -= self.consumed;
220            }
221        }
222
223        let mut guard = Guard { deque: &mut self.inner, consumed: 0 };
224
225        let (head, tail) = guard.deque.as_slices();
226
227        init = tail
228            .iter()
229            .map(|elem| {
230                guard.consumed += 1;
231                // SAFETY: See `try_fold`'s safety comment.
232                unsafe { ptr::read(elem) }
233            })
234            .try_rfold(init, &mut f)?;
235
236        head.iter()
237            .map(|elem| {
238                guard.consumed += 1;
239                // SAFETY: Same as above.
240                unsafe { ptr::read(elem) }
241            })
242            .try_rfold(init, &mut f)
243    }
244
245    #[inline]
246    fn rfold<B, F>(mut self, init: B, mut f: F) -> B
247    where
248        F: FnMut(B, Self::Item) -> B,
249    {
250        match self.try_rfold(init, |b, item| Ok::<B, !>(f(b, item))) {
251            Ok(b) => b,
252        }
253    }
254}
255
256#[stable(feature = "rust1", since = "1.0.0")]
257impl<T, A: Allocator> ExactSizeIterator for IntoIter<T, A> {
258    #[inline]
259    fn is_empty(&self) -> bool {
260        self.inner.is_empty()
261    }
262}
263
264#[stable(feature = "fused", since = "1.26.0")]
265impl<T, A: Allocator> FusedIterator for IntoIter<T, A> {}
266
267#[unstable(feature = "trusted_len", issue = "37572")]
268unsafe impl<T, A: Allocator> TrustedLen for IntoIter<T, A> {}