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 | |
24 | #[stable (feature = "collection_debug" , since = "1.17.0" )] |
25 | impl<T: fmt::Debug> fmt::Debug for Iter<'_, T> { |
26 | fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { |
27 | f.debug_tuple(name:"Iter" ).field(&self.i1.as_slice()).field(&self.i2.as_slice()).finish() |
28 | } |
29 | } |
30 | |
31 | // FIXME(#26925) Remove in favor of `#[derive(Clone)]` |
32 | #[stable (feature = "rust1" , since = "1.0.0" )] |
33 | impl<T> Clone for Iter<'_, T> { |
34 | fn clone(&self) -> Self { |
35 | Iter { i1: self.i1.clone(), i2: self.i2.clone() } |
36 | } |
37 | } |
38 | |
39 | #[stable (feature = "rust1" , since = "1.0.0" )] |
40 | impl<'a, T> Iterator for Iter<'a, T> { |
41 | type Item = &'a T; |
42 | |
43 | #[inline ] |
44 | fn next(&mut self) -> Option<&'a T> { |
45 | match self.i1.next() { |
46 | Some(val) => Some(val), |
47 | None => { |
48 | // most of the time, the iterator will either always |
49 | // call next(), or always call next_back(). By swapping |
50 | // the iterators once the first one is empty, we ensure |
51 | // that the first branch is taken as often as possible, |
52 | // without sacrificing correctness, as i1 is empty anyways |
53 | mem::swap(&mut self.i1, &mut self.i2); |
54 | self.i1.next() |
55 | } |
56 | } |
57 | } |
58 | |
59 | fn advance_by(&mut self, n: usize) -> Result<(), NonZero<usize>> { |
60 | let remaining = self.i1.advance_by(n); |
61 | match remaining { |
62 | Ok(()) => return Ok(()), |
63 | Err(n) => { |
64 | mem::swap(&mut self.i1, &mut self.i2); |
65 | self.i1.advance_by(n.get()) |
66 | } |
67 | } |
68 | } |
69 | |
70 | #[inline ] |
71 | fn size_hint(&self) -> (usize, Option<usize>) { |
72 | let len = self.len(); |
73 | (len, Some(len)) |
74 | } |
75 | |
76 | fn fold<Acc, F>(self, accum: Acc, mut f: F) -> Acc |
77 | where |
78 | F: FnMut(Acc, Self::Item) -> Acc, |
79 | { |
80 | let accum = self.i1.fold(accum, &mut f); |
81 | self.i2.fold(accum, &mut f) |
82 | } |
83 | |
84 | fn try_fold<B, F, R>(&mut self, init: B, mut f: F) -> R |
85 | where |
86 | F: FnMut(B, Self::Item) -> R, |
87 | R: Try<Output = B>, |
88 | { |
89 | let acc = self.i1.try_fold(init, &mut f)?; |
90 | self.i2.try_fold(acc, &mut f) |
91 | } |
92 | |
93 | #[inline ] |
94 | fn last(mut self) -> Option<&'a T> { |
95 | self.next_back() |
96 | } |
97 | |
98 | #[inline ] |
99 | unsafe fn __iterator_get_unchecked(&mut self, idx: usize) -> Self::Item { |
100 | // Safety: The TrustedRandomAccess contract requires that callers only pass an index |
101 | // that is in bounds. |
102 | unsafe { |
103 | let i1_len = self.i1.len(); |
104 | if idx < i1_len { |
105 | self.i1.__iterator_get_unchecked(idx) |
106 | } else { |
107 | self.i2.__iterator_get_unchecked(idx - i1_len) |
108 | } |
109 | } |
110 | } |
111 | } |
112 | |
113 | #[stable (feature = "rust1" , since = "1.0.0" )] |
114 | impl<'a, T> DoubleEndedIterator for Iter<'a, T> { |
115 | #[inline ] |
116 | fn next_back(&mut self) -> Option<&'a T> { |
117 | match self.i2.next_back() { |
118 | Some(val) => Some(val), |
119 | None => { |
120 | // most of the time, the iterator will either always |
121 | // call next(), or always call next_back(). By swapping |
122 | // the iterators once the second one is empty, we ensure |
123 | // that the first branch is taken as often as possible, |
124 | // without sacrificing correctness, as i2 is empty anyways |
125 | mem::swap(&mut self.i1, &mut self.i2); |
126 | self.i2.next_back() |
127 | } |
128 | } |
129 | } |
130 | |
131 | fn advance_back_by(&mut self, n: usize) -> Result<(), NonZero<usize>> { |
132 | match self.i2.advance_back_by(n) { |
133 | Ok(()) => return Ok(()), |
134 | Err(n) => { |
135 | mem::swap(&mut self.i1, &mut self.i2); |
136 | self.i2.advance_back_by(n.get()) |
137 | } |
138 | } |
139 | } |
140 | |
141 | fn rfold<Acc, F>(self, accum: Acc, mut f: F) -> Acc |
142 | where |
143 | F: FnMut(Acc, Self::Item) -> Acc, |
144 | { |
145 | let accum = self.i2.rfold(accum, &mut f); |
146 | self.i1.rfold(accum, &mut f) |
147 | } |
148 | |
149 | fn try_rfold<B, F, R>(&mut self, init: B, mut f: F) -> R |
150 | where |
151 | F: FnMut(B, Self::Item) -> R, |
152 | R: Try<Output = B>, |
153 | { |
154 | let acc = self.i2.try_rfold(init, &mut f)?; |
155 | self.i1.try_rfold(acc, &mut f) |
156 | } |
157 | } |
158 | |
159 | #[stable (feature = "rust1" , since = "1.0.0" )] |
160 | impl<T> ExactSizeIterator for Iter<'_, T> { |
161 | fn len(&self) -> usize { |
162 | self.i1.len() + self.i2.len() |
163 | } |
164 | |
165 | fn is_empty(&self) -> bool { |
166 | self.i1.is_empty() && self.i2.is_empty() |
167 | } |
168 | } |
169 | |
170 | #[stable (feature = "fused" , since = "1.26.0" )] |
171 | impl<T> FusedIterator for Iter<'_, T> {} |
172 | |
173 | #[unstable (feature = "trusted_len" , issue = "37572" )] |
174 | unsafe impl<T> TrustedLen for Iter<'_, T> {} |
175 | |
176 | #[doc (hidden)] |
177 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
178 | unsafe impl<T> TrustedRandomAccess for Iter<'_, T> {} |
179 | |
180 | #[doc (hidden)] |
181 | #[unstable (feature = "trusted_random_access" , issue = "none" )] |
182 | unsafe impl<T> TrustedRandomAccessNoCoerce for Iter<'_, T> { |
183 | const MAY_HAVE_SIDE_EFFECT: bool = false; |
184 | } |
185 | |