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