1 | use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce}; |
2 | use core::num::NonZero; |
3 | use core::ops::Try; |
4 | use core::{fmt, mem, slice}; |
5 | |
6 | /// An iterator over the elements of a `VecDeque`. |
7 | /// |
8 | /// This `struct` is created by the [`iter`] method on [`super::VecDeque`]. See its |
9 | /// documentation for more. |
10 | /// |
11 | /// [`iter`]: super::VecDeque::iter |
12 | #[stable (feature = "rust1" , since = "1.0.0" )] |
13 | pub struct Iter<'a, T: 'a> { |
14 | i1: slice::Iter<'a, T>, |
15 | i2: slice::Iter<'a, T>, |
16 | } |
17 | |
18 | impl<'a, T> Iter<'a, T> { |
19 | pub(super) fn new(i1: slice::Iter<'a, T>, i2: slice::Iter<'a, T>) -> Self { |
20 | Self { i1, i2 } |
21 | } |
22 | |
23 | /// Views the underlying data as a pair of subslices of the original data. |
24 | /// |
25 | /// The slices contain, in order, the contents of the deque not yet yielded |
26 | /// by the iterator. |
27 | /// |
28 | /// This has the same lifetime as the original `VecDeque`, and so the |
29 | /// iterator can continue to be used while this exists. |
30 | /// |
31 | /// # Examples |
32 | /// |
33 | /// ``` |
34 | /// #![feature(vec_deque_iter_as_slices)] |
35 | /// |
36 | /// use std::collections::VecDeque; |
37 | /// |
38 | /// let mut deque = VecDeque::new(); |
39 | /// deque.push_back(0); |
40 | /// deque.push_back(1); |
41 | /// deque.push_back(2); |
42 | /// deque.push_front(10); |
43 | /// deque.push_front(9); |
44 | /// deque.push_front(8); |
45 | /// |
46 | /// let mut iter = deque.iter(); |
47 | /// iter.next(); |
48 | /// iter.next_back(); |
49 | /// |
50 | /// assert_eq!(iter.as_slices(), (&[9, 10][..], &[0, 1][..])); |
51 | /// ``` |
52 | #[unstable (feature = "vec_deque_iter_as_slices" , issue = "123947" )] |
53 | pub fn as_slices(&self) -> (&'a [T], &'a [T]) { |
54 | (self.i1.as_slice(), self.i2.as_slice()) |
55 | } |
56 | } |
57 | |
58 | #[stable (feature = "collection_debug" , since = "1.17.0" )] |
59 | impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { |
60 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
61 | f.debug_tuple(name:"Iter" ).field(&self.i1.as_slice()).field(&self.i2.as_slice()).finish() |
62 | } |
63 | } |
64 | |
65 | #[stable (feature = "default_iters_sequel" , since = "1.82.0" )] |
66 | impl<T> Default for Iter<'_, T> { |
67 | /// Creates an empty `vec_deque::Iter`. |
68 | /// |
69 | /// ``` |
70 | /// # use std::collections::vec_deque; |
71 | /// let iter: vec_deque::Iter<'_, u8> = Default::default(); |
72 | /// assert_eq!(iter.len(), 0); |
73 | /// ``` |
74 | fn default() -> Self { |
75 | Iter { i1: Default::default(), i2: Default::default() } |
76 | } |
77 | } |
78 | |
79 | // FIXME(#26925) Remove in favor of `#[derive(Clone)]` |
80 | #[stable (feature = "rust1" , since = "1.0.0" )] |
81 | impl<T> Clone for Iter<'_, T> { |
82 | fn clone(&self) -> Self { |
83 | Iter { i1: self.i1.clone(), i2: self.i2.clone() } |
84 | } |
85 | } |
86 | |
87 | #[stable (feature = "rust1" , since = "1.0.0" )] |
88 | impl<'a, T> Iterator for Iter<'a, T> { |
89 | type Item = &'a T; |
90 | |
91 | #[inline ] |
92 | fn next(&mut self) -> Option<&'a T> { |
93 | match self.i1.next() { |
94 | Some(val) => Some(val), |
95 | None => { |
96 | // most of the time, the iterator will either always |
97 | // call next(), or always call next_back(). By swapping |
98 | // the iterators once the first one is empty, we ensure |
99 | // that the first branch is taken as often as possible, |
100 | // without sacrificing correctness, as i1 is empty anyways |
101 | mem::swap(&mut self.i1, &mut self.i2); |
102 | self.i1.next() |
103 | } |
104 | } |
105 | } |
106 | |
107 | fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> { |
108 | let remaining = self.i1.advance_by(n); |
109 | match remaining { |
110 | Ok(()) => Ok(()), |
111 | Err(n) => { |
112 | mem::swap(&mut self.i1, &mut self.i2); |
113 | self.i1.advance_by(n.get()) |
114 | } |
115 | } |
116 | } |
117 | |
118 | #[inline ] |
119 | fn size_hint(&self) -> (usize, Option<usize>) { |
120 | let len = self.len(); |
121 | (len, Some(len)) |
122 | } |
123 | |
124 | fn fold<Acc, F>(self, accum: Acc, mut f: F) -> Acc |
125 | where |
126 | F: FnMut(Acc, Self::Item) -> Acc, |
127 | { |
128 | let accum = self.i1.fold(accum, &mut f); |
129 | self.i2.fold(accum, &mut f) |
130 | } |
131 | |
132 | fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R |
133 | where |
134 | F: FnMut(B, Self::Item) -> R, |
135 | R: Try<Output = B>, |
136 | { |
137 | let acc = self.i1.try_fold(init, &mut f)?; |
138 | self.i2.try_fold(acc, &mut f) |
139 | } |
140 | |
141 | #[inline ] |
142 | fn last(mut self) -> Option<&'a T> { |
143 | self.next_back() |
144 | } |
145 | |
146 | #[inline ] |
147 | unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item { |
148 | // Safety: The TrustedRandomAccess contract requires that callers only pass an index |
149 | // that is in bounds. |
150 | unsafe { |
151 | let i1_len = self.i1.len(); |
152 | if idx < i1_len { |
153 | self.i1.__iterator_get_unchecked(idx) |
154 | } else { |
155 | self.i2.__iterator_get_unchecked(idx - i1_len) |
156 | } |
157 | } |
158 | } |
159 | } |
160 | |
161 | #[stable (feature = "rust1" , since = "1.0.0" )] |
162 | impl<'a, T> DoubleEndedIterator for Iter<'a, T> { |
163 | #[inline ] |
164 | fn next_back(&mut self) -> Option<&'a T> { |
165 | match self.i2.next_back() { |
166 | Some(val) => Some(val), |
167 | None => { |
168 | // most of the time, the iterator will either always |
169 | // call next(), or always call next_back(). By swapping |
170 | // the iterators once the second one is empty, we ensure |
171 | // that the first branch is taken as often as possible, |
172 | // without sacrificing correctness, as i2 is empty anyways |
173 | mem::swap(&mut self.i1, &mut self.i2); |
174 | self.i2.next_back() |
175 | } |
176 | } |
177 | } |
178 | |
179 | fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> { |
180 | match self.i2.advance_back_by(n) { |
181 | Ok(()) => Ok(()), |
182 | Err(n) => { |
183 | mem::swap(&mut self.i1, &mut self.i2); |
184 | self.i2.advance_back_by(n.get()) |
185 | } |
186 | } |
187 | } |
188 | |
189 | fn rfold<Acc, F>(self, accum: Acc, mut f: F) -> Acc |
190 | where |
191 | F: FnMut(Acc, Self::Item) -> Acc, |
192 | { |
193 | let accum = self.i2.rfold(accum, &mut f); |
194 | self.i1.rfold(accum, &mut f) |
195 | } |
196 | |
197 | fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R |
198 | where |
199 | F: FnMut(B, Self::Item) -> R, |
200 | R: Try<Output = B>, |
201 | { |
202 | let acc = self.i2.try_rfold(init, &mut f)?; |
203 | self.i1.try_rfold(acc, &mut f) |
204 | } |
205 | } |
206 | |
207 | #[stable (feature = "rust1" , since = "1.0.0" )] |
208 | impl<T> ExactSizeIterator for Iter<'_, T> { |
209 | fn len(&self) -> usize { |
210 | self.i1.len() + self.i2.len() |
211 | } |
212 | |
213 | fn is_empty(&self) -> bool { |
214 | self.i1.is_empty() && self.i2.is_empty() |
215 | } |
216 | } |
217 | |
218 | #[stable (feature = "fused" , since = "1.26.0" )] |
219 | impl<T> FusedIterator for Iter<'_, T> {} |
220 | |
221 | #[unstable (feature = "trusted_len" , issue = "37572" )] |
222 | unsafe impl<T> TrustedLen for Iter<'_, T> {} |
223 | |
224 | #[doc (hidden)] |
225 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
226 | unsafe impl<T> TrustedRandomAccess for Iter<'_, T> {} |
227 | |
228 | #[doc (hidden)] |
229 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
230 | unsafe impl<T> TrustedRandomAccessNoCoerce for Iter<'_, T> { |
231 | const MAY_HAVE_SIDE_EFFECT: bool = false; |
232 | } |
233 | |