alloc/collections/vec_deque/
into_iter.rs1use 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#[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 #[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: 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 unsafe { ptr::read(elem) }
113 })
114 .try_fold(init, &mut f)?;
115
116 tail.iter()
117 .map(|elem| {
118 guard.consumed += 1;
119 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 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 return Ok(unsafe { raw_arr.transpose().assume_init() });
155 }
156
157 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 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 Ok(unsafe { raw_arr.transpose().assume_init() })
170 } else {
171 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 self.inner.head = WrappedIndex::zero();
178 self.inner.len = 0;
179 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: 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 unsafe { ptr::read(elem) }
233 })
234 .try_rfold(init, &mut f)?;
235
236 head.iter()
237 .map(|elem| {
238 guard.consumed += 1;
239 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> {}