1use core::iter::{FusedIterator, TrustedLen, TrustedRandomAccess, TrustedRandomAccessNoCoerce};
2use core::num::NonZero;
3use core::ops::Try;
4use 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")]
13pub struct Iter<'a, T: 'a> {
14 i1: slice::Iter<'a, T>,
15 i2: slice::Iter<'a, T>,
16}
17
18impl<'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")]
25impl<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")]
33impl<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")]
40impl<'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")]
114impl<'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")]
160impl<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")]
171impl<T> FusedIterator for Iter<'_, T> {}
172
173#[unstable(feature = "trusted_len", issue = "37572")]
174unsafe impl<T> TrustedLen for Iter<'_, T> {}
175
176#[doc(hidden)]
177#[unstable(feature = "trusted_random_access", issue = "none")]
178unsafe impl<T> TrustedRandomAccess for Iter<'_, T> {}
179
180#[doc(hidden)]
181#[unstable(feature = "trusted_random_access", issue = "none")]
182unsafe impl<T> TrustedRandomAccessNoCoerce for Iter<'_, T> {
183 const MAY_HAVE_SIDE_EFFECT: bool = false;
184}
185