1use crate::{chunk::Chunk, *};
2use std::{collections::*, iter::*, ptr};
3
4#[derive(Clone)]
5pub struct Iter<'a, T: Sized> {
6 size: usize,
7 chunk_iter: vec_deque::Iter<'a, *mut Chunk<T>>,
8 front_chunk: *const Chunk<T>,
9 front_elem: *const T,
10 back_chunk: *const Chunk<T>,
11 back_elem: *const T,
12}
13
14pub struct IterMut<'a, T: Sized> {
15 size: usize,
16 chunk_iter: vec_deque::IterMut<'a, *mut Chunk<T>>,
17 front_chunk: *mut Chunk<T>,
18 front_elem: *mut T,
19 back_chunk: *mut Chunk<T>,
20 back_elem: *mut T,
21}
22
23pub struct IntoIter<T: Sized>(PinnedDeque<T>);
24
25impl<'a, T> Iterator for Iter<'a, T>
26where
27 T: Sized,
28{
29 type Item = &'a T;
30
31 fn next(&mut self) -> Option<Self::Item> {
32 if self.size == 0 {
33 None
34 } else {
35 self.size -= 1;
36 let res = unsafe { &*self.front_elem };
37 self.front_elem = self.front_elem.wrapping_add(1);
38 if self.front_elem > unsafe { &*self.front_chunk }.back() {
39 self.front_chunk = if let Some(chunk) = self.chunk_iter.next() {
40 *chunk as *const Chunk<T>
41 } else {
42 self.back_chunk
43 };
44 self.front_elem = unsafe {
45 let front_chunk: &Chunk<T> = &*self.front_chunk;
46 front_chunk.front()
47 }
48 }
49 Some(res)
50 }
51 }
52
53 fn size_hint(&self) -> (usize, Option<usize>) {
54 (self.size, Some(self.size))
55 }
56}
57
58impl<'a, T> Iterator for IterMut<'a, T>
59where
60 T: Sized,
61{
62 type Item = &'a mut T;
63
64 fn next(&mut self) -> Option<Self::Item> {
65 if self.size == 0 {
66 None
67 } else {
68 self.size -= 1;
69 let res = unsafe { &mut *self.front_elem };
70
71 self.front_elem = self.front_elem.wrapping_add(1);
72 if self.front_elem > unsafe { &mut *self.front_chunk }.back_mut() {
73 self.front_chunk = if let Some(chunk) = self.chunk_iter.next() {
74 *chunk
75 } else {
76 self.back_chunk
77 };
78 self.front_elem = unsafe {
79 let front_chunk: &mut Chunk<T> = &mut *self.front_chunk;
80 front_chunk.front_mut()
81 }
82 }
83
84 Some(res)
85 }
86 }
87
88 fn size_hint(&self) -> (usize, Option<usize>) {
89 (self.size, Some(self.size))
90 }
91}
92
93impl<T: Sized> Iterator for IntoIter<T> {
94 type Item = T;
95
96 fn next(&mut self) -> Option<Self::Item> {
97 self.0.pop_front()
98 }
99
100 fn size_hint(&self) -> (usize, Option<usize>) {
101 let size = self.0.len();
102 (size, Some(size))
103 }
104}
105
106impl<T> DoubleEndedIterator for Iter<'_, T>
107where
108 T: Sized,
109{
110 fn next_back(&mut self) -> Option<Self::Item> {
111 if self.size == 0 {
112 None
113 } else {
114 self.size -= 1;
115 let res = unsafe { &*self.back_elem };
116
117 self.back_elem = self.back_elem.wrapping_sub(1);
118 if self.back_elem < unsafe { &*self.back_chunk }.front() {
119 self.back_chunk = if let Some(chunk) = self.chunk_iter.next_back() {
120 *chunk as *const Chunk<T>
121 } else {
122 self.front_chunk
123 };
124 self.back_elem = unsafe {
125 let back_chunk: &Chunk<T> = &*self.back_chunk;
126 back_chunk.back()
127 }
128 }
129
130 Some(res)
131 }
132 }
133}
134
135impl<T> DoubleEndedIterator for IterMut<'_, T>
136where
137 T: Sized,
138{
139 fn next_back(&mut self) -> Option<Self::Item> {
140 if self.size == 0 {
141 None
142 } else {
143 self.size -= 1;
144 let res = unsafe { &mut *self.back_elem };
145
146 self.back_elem = self.back_elem.wrapping_sub(1);
147 if self.back_elem < unsafe { &mut *self.back_chunk }.front_mut() {
148 self.back_chunk = if let Some(chunk) = self.chunk_iter.next_back() {
149 *chunk
150 } else {
151 self.front_chunk
152 };
153 self.back_elem = unsafe {
154 let back_chunk: &mut Chunk<T> = &mut *self.back_chunk;
155 back_chunk.back_mut()
156 }
157 }
158
159 Some(res)
160 }
161 }
162}
163
164impl<T: Sized> DoubleEndedIterator for IntoIter<T> {
165 fn next_back(&mut self) -> Option<Self::Item> {
166 self.0.pop_back()
167 }
168}
169
170impl<T: Sized> ExactSizeIterator for Iter<'_, T> {}
171
172impl<T: Sized> ExactSizeIterator for IterMut<'_, T> {}
173
174impl<T: Sized> ExactSizeIterator for IntoIter<T> {}
175
176impl<'a, T> Iter<'a, T>
177where
178 T: Sized,
179{
180 pub(crate) fn new(deque: &'a PinnedDeque<T>) -> Self {
181 let mut chunk_iter = deque.used.iter();
182 if let Some(front_chunk) = chunk_iter.next() {
183 let front_chunk = *front_chunk as *const Chunk<T>;
184 let front_elem: *const _ = unsafe {
185 let front_chunk: &_ = &*front_chunk;
186 front_chunk.front()
187 };
188 let back_chunk: *const _ = if let Some(back_chunk) = chunk_iter.next_back() {
189 *back_chunk as *const Chunk<T>
190 } else {
191 front_chunk
192 };
193 let back_elem: *const _ = unsafe {
194 let back_chunk: &Chunk<T> = &*back_chunk;
195 back_chunk.back()
196 };
197 Self {
198 size: deque.len(),
199 chunk_iter,
200 front_chunk,
201 front_elem,
202 back_chunk,
203 back_elem,
204 }
205 } else {
206 assert_eq!(deque.len(), 0);
207 Self {
208 size: deque.len(),
209 chunk_iter,
210 front_chunk: ptr::null(),
211 front_elem: ptr::null(),
212 back_chunk: ptr::null(),
213 back_elem: ptr::null(),
214 }
215 }
216 }
217}
218
219impl<'a, T> IterMut<'a, T>
220where
221 T: Sized,
222{
223 pub(crate) fn new(deque: &'a mut PinnedDeque<T>) -> Self {
224 let size = deque.len();
225 let mut chunk_iter = deque.used.iter_mut();
226 if let Some(front_chunk) = chunk_iter.next() {
227 let front_chunk = *front_chunk;
228 let front_elem: *mut _ = unsafe {
229 let front_chunk = &mut *front_chunk;
230 front_chunk.front_mut()
231 };
232 let back_chunk = if let Some(back_chunk) = chunk_iter.next_back() {
233 *back_chunk
234 } else {
235 front_chunk
236 };
237 let back_elem: *mut _ = unsafe {
238 let back_chunk = &mut *back_chunk;
239 back_chunk.back_mut()
240 };
241 Self {
242 size,
243 chunk_iter,
244 front_chunk,
245 front_elem,
246 back_chunk,
247 back_elem,
248 }
249 } else {
250 assert_eq!(size, 0);
251 Self {
252 size,
253 chunk_iter,
254 front_chunk: ptr::null_mut(),
255 front_elem: ptr::null_mut(),
256 back_chunk: ptr::null_mut(),
257 back_elem: ptr::null_mut(),
258 }
259 }
260 }
261}
262
263impl<T: Sized> IntoIterator for PinnedDeque<T> {
264 type Item = T;
265 type IntoIter = IntoIter<T>;
266
267 fn into_iter(self) -> Self::IntoIter {
268 IntoIter(self)
269 }
270}
271
272impl<'a, T: Sized> IntoIterator for &'a PinnedDeque<T> {
273 type Item = &'a T;
274 type IntoIter = Iter<'a, T>;
275
276 fn into_iter(self) -> Self::IntoIter {
277 Iter::new(self)
278 }
279}
280
281impl<'a, T: Sized> IntoIterator for &'a mut PinnedDeque<T> {
282 type Item = &'a mut T;
283 type IntoIter = IterMut<'a, T>;
284
285 fn into_iter(self) -> Self::IntoIter {
286 IterMut::new(self)
287 }
288}