array_linked_list/
iter.rs

1use crate::{ArrayLinkedList, LinkedListNode, id::Id};
2
3impl<T> ArrayLinkedList<T> {
4    /// Returns a borrowing iterator over its elements.
5    pub fn iter(&self) -> impl DoubleEndedIterator<Item = &T> {
6        Values(Indexed::new(self))
7    }
8
9    /// Returns a mutable borrowing iterator over its elements.
10    pub fn iter_mut(&mut self) -> impl DoubleEndedIterator<Item = &mut T> {
11        ValuesMut(IndexedMut::new(self))
12    }
13
14    /// Returns a borrowing iterator over its indexed elements.
15    pub fn indexed(&self) -> impl DoubleEndedIterator<Item = (usize, &T)> {
16        Indexed::new(self)
17    }
18
19    /// Returns a mutable borrowing iterator over its indexed elements.
20    pub fn indexed_mut(&mut self) -> impl DoubleEndedIterator<Item = (usize, &mut T)> {
21        IndexedMut::new(self)
22    }
23
24    /// Returns a borrowing iterator over its indices.
25    pub fn indices(&self) -> impl DoubleEndedIterator<Item = usize> + '_ {
26        Indices(Indexed::new(self))
27    }
28
29    /// Returns a borrowing iterator over its elements, starting after the element at the specified index.
30    ///
31    /// # Panics
32    ///
33    /// Panics if index >= capacity
34    pub fn iter_after(&self, index: usize) -> impl DoubleEndedIterator<Item = &T> {
35        Values(Indexed::after(self, index))
36    }
37
38    /// Returns a mutable borrowing iterator over its elements, starting after the element at the specified index.
39    ///
40    /// # Panics
41    ///
42    /// Panics if index >= capacity
43    pub fn iter_mut_after(&mut self, index: usize) -> impl DoubleEndedIterator<Item = &mut T> {
44        ValuesMut(IndexedMut::after(self, index))
45    }
46
47    /// Returns a borrowing iterator over its indexed elements, starting after the element at the specified index.
48    ///
49    /// # Panics
50    ///
51    /// Panics if index >= capacity
52    pub fn indexed_after(&self, index: usize) -> impl DoubleEndedIterator<Item = (usize, &T)> {
53        Indexed::after(self, index)
54    }
55
56    /// Returns a mutable borrowing iterator over its indexed elements, starting after the element at the specified index.
57    ///
58    /// # Panics
59    ///
60    /// Panics if index >= capacity
61    pub fn indexed_mut_after(
62        &mut self,
63        index: usize,
64    ) -> impl DoubleEndedIterator<Item = (usize, &mut T)> {
65        IndexedMut::after(self, index)
66    }
67
68    /// Returns a borrowing iterator over its indices, starting after the element at the specified index.
69    ///
70    /// # Panics
71    ///
72    /// Panics if index >= capacity
73    pub fn indices_after(&self, index: usize) -> impl DoubleEndedIterator<Item = usize> + '_ {
74        Indices(Indexed::after(self, index))
75    }
76
77    /// Returns a borrowing iterator over its elements, ending before the element at the specified index.
78    ///
79    /// # Panics
80    ///
81    /// Panics if index >= capacity
82    pub fn iter_before(&self, index: usize) -> impl DoubleEndedIterator<Item = &T> {
83        Values(Indexed::before(self, index))
84    }
85
86    /// Returns a mutable borrowing iterator over its elements, ending before the element at the specified index.
87    ///
88    /// # Panics
89    ///
90    /// Panics if index >= capacity
91    pub fn iter_mut_before(&mut self, index: usize) -> impl DoubleEndedIterator<Item = &mut T> {
92        ValuesMut(IndexedMut::before(self, index))
93    }
94
95    /// Returns a borrowing iterator over its indexed elements, ending before the element at the specified index.
96    ///
97    /// # Panics
98    ///
99    /// Panics if index >= capacity
100    pub fn indexed_before(&self, index: usize) -> impl DoubleEndedIterator<Item = (usize, &T)> {
101        Indexed::before(self, index)
102    }
103
104    /// Returns a mutable borrowing iterator over its indexed elements, ending before the element at the specified index.
105    ///
106    /// # Panics
107    ///
108    /// Panics if index >= capacity
109    pub fn indexed_mut_before(
110        &mut self,
111        index: usize,
112    ) -> impl DoubleEndedIterator<Item = (usize, &mut T)> {
113        IndexedMut::before(self, index)
114    }
115
116    /// Returns a borrowing iterator over its indices, ending before the element at the specified index.
117    ///
118    /// # Panics
119    ///
120    /// Panics if index >= capacity
121    pub fn indices_before(&self, index: usize) -> impl DoubleEndedIterator<Item = usize> + '_ {
122        Indices(Indexed::before(self, index))
123    }
124
125    /// Returns an owning iterator returning its indexed elements.
126    pub fn into_indexed(self) -> impl DoubleEndedIterator<Item = (usize, T)> {
127        IntoIndexed(self)
128    }
129
130    /// Returns an owning iterator returning its indices.
131    pub fn into_indices(self) -> impl DoubleEndedIterator<Item = usize> {
132        IntoIndices(IntoIndexed(self))
133    }
134}
135
136struct Indexed<'a, T> {
137    front_index: Id,
138    back_index: Id,
139    array: &'a ArrayLinkedList<T>,
140}
141
142impl<'a, T> Indexed<'a, T> {
143    fn empty(array: &'a ArrayLinkedList<T>) -> Self {
144        Self {
145            front_index: Id::default(),
146            back_index: Id::default(),
147            array,
148        }
149    }
150
151    fn new(array: &'a ArrayLinkedList<T>) -> Self {
152        Self {
153            front_index: array.first_index,
154            back_index: array.last_index,
155            array,
156        }
157    }
158
159    fn after(array: &'a ArrayLinkedList<T>, prev_index: usize) -> Self {
160        let element = &array.elements[prev_index];
161        if element.data.is_some() {
162            Self {
163                front_index: element.next_index,
164                back_index: array.last_index,
165                array,
166            }
167        } else {
168            Self::empty(array)
169        }
170    }
171
172    fn before(array: &'a ArrayLinkedList<T>, next_index: usize) -> Self {
173        let element = &array.elements[next_index];
174        if element.data.is_some() {
175            Self {
176                front_index: array.first_index,
177                back_index: element.prev_index,
178                array,
179            }
180        } else {
181            Self::empty(array)
182        }
183    }
184}
185
186struct IndexedMut<'a, T> {
187    front_index: Id,
188    back_index: Id,
189    elements: &'a mut [LinkedListNode<T>],
190}
191
192impl<'a, T> IndexedMut<'a, T> {
193    fn empty(array: &'a mut ArrayLinkedList<T>) -> Self {
194        Self {
195            front_index: Id::default(),
196            back_index: Id::default(),
197            elements: &mut array.elements,
198        }
199    }
200
201    fn new(array: &'a mut ArrayLinkedList<T>) -> Self {
202        Self {
203            front_index: array.first_index,
204            back_index: array.last_index,
205            elements: &mut array.elements,
206        }
207    }
208
209    fn after(array: &'a mut ArrayLinkedList<T>, prev_index: usize) -> Self {
210        let last_index = array.last_index;
211        let element = &array.elements[prev_index];
212        if element.data.is_some() {
213            let front_index = element.next_index;
214            Self {
215                front_index,
216                back_index: last_index,
217                elements: &mut array.elements,
218            }
219        } else {
220            Self::empty(array)
221        }
222    }
223
224    fn before(array: &'a mut ArrayLinkedList<T>, next_index: usize) -> Self {
225        let first_index = array.first_index;
226        let element = &array.elements[next_index];
227        if element.data.is_some() {
228            let back_index = element.prev_index;
229            Self {
230                front_index: first_index,
231                back_index,
232                elements: &mut array.elements,
233            }
234        } else {
235            Self::empty(array)
236        }
237    }
238}
239
240struct Indices<'a, T>(Indexed<'a, T>);
241
242/// Borrowing iterator over values of the linked array.
243pub struct Values<'a, T>(Indexed<'a, T>);
244
245/// Mutable borrowing iterator over values of the linked array.
246pub struct ValuesMut<'a, T>(IndexedMut<'a, T>);
247
248impl<'a, T> Iterator for Indexed<'a, T> {
249    type Item = (usize, &'a T);
250    #[inline]
251    fn next(&mut self) -> Option<Self::Item> {
252        let index = self.front_index.index()?;
253
254        let element = &self.array.elements[index];
255        if self.front_index == self.back_index {
256            self.front_index = Id::default();
257            self.back_index = Id::default();
258        } else {
259            self.front_index = element.next_index;
260        }
261        Some((index, unsafe { element.data.as_ref().unwrap_unchecked() }))
262    }
263}
264
265impl<T> DoubleEndedIterator for Indexed<'_, T> {
266    #[inline]
267    fn next_back(&mut self) -> Option<Self::Item> {
268        let index = self.back_index.index()?;
269
270        let element = &self.array.elements[index];
271        if self.front_index == self.back_index {
272            self.front_index = Id::default();
273            self.back_index = Id::default();
274        } else {
275            self.back_index = element.prev_index;
276        }
277        Some((index, unsafe { element.data.as_ref().unwrap_unchecked() }))
278    }
279}
280
281impl<'a, T> Iterator for IndexedMut<'a, T> {
282    type Item = (usize, &'a mut T);
283    #[inline]
284    fn next(&mut self) -> Option<Self::Item> {
285        let index = self.front_index.index()?;
286
287        let element: *mut LinkedListNode<T> = &raw mut self.elements[index];
288        if self.front_index == self.back_index {
289            self.front_index = Id::default();
290            self.back_index = Id::default();
291        } else {
292            self.front_index = unsafe { (*element).next_index };
293        }
294        Some((index, unsafe {
295            (*element).data.as_mut().unwrap_unchecked()
296        }))
297    }
298}
299
300impl<T> DoubleEndedIterator for IndexedMut<'_, T> {
301    #[inline]
302    fn next_back(&mut self) -> Option<Self::Item> {
303        let index = self.back_index.index()?;
304
305        let element: *mut LinkedListNode<T> = &raw mut self.elements[index];
306        if self.front_index == self.back_index {
307            self.front_index = Id::default();
308            self.back_index = Id::default();
309        } else {
310            self.back_index = unsafe { (*element).prev_index };
311        }
312        Some((index, unsafe {
313            (*element).data.as_mut().unwrap_unchecked()
314        }))
315    }
316}
317
318impl<T> Iterator for Indices<'_, T> {
319    type Item = usize;
320    fn next(&mut self) -> Option<Self::Item> {
321        self.0.next().map(|(index, _)| index)
322    }
323}
324
325impl<T> DoubleEndedIterator for Indices<'_, T> {
326    fn next_back(&mut self) -> Option<Self::Item> {
327        self.0.next_back().map(|(index, _)| index)
328    }
329}
330
331impl<'a, T> Iterator for Values<'a, T> {
332    type Item = &'a T;
333    fn next(&mut self) -> Option<Self::Item> {
334        self.0.next().map(|(_, value)| value)
335    }
336}
337
338impl<T> DoubleEndedIterator for Values<'_, T> {
339    fn next_back(&mut self) -> Option<Self::Item> {
340        self.0.next_back().map(|(_, value)| value)
341    }
342}
343
344impl<'a, T> Iterator for ValuesMut<'a, T> {
345    type Item = &'a mut T;
346    fn next(&mut self) -> Option<Self::Item> {
347        self.0.next().map(|(_, value)| value)
348    }
349}
350
351impl<T> DoubleEndedIterator for ValuesMut<'_, T> {
352    fn next_back(&mut self) -> Option<Self::Item> {
353        self.0.next_back().map(|(_, value)| value)
354    }
355}
356
357impl<'a, T> IntoIterator for &'a ArrayLinkedList<T> {
358    type Item = &'a T;
359    type IntoIter = Values<'a, T>;
360
361    #[inline]
362    fn into_iter(self) -> Self::IntoIter {
363        Values(Indexed::new(self))
364    }
365}
366
367impl<'a, T> IntoIterator for &'a mut ArrayLinkedList<T> {
368    type Item = &'a mut T;
369    type IntoIter = ValuesMut<'a, T>;
370
371    #[inline]
372    fn into_iter(self) -> Self::IntoIter {
373        ValuesMut(IndexedMut::new(self))
374    }
375}
376
377struct IntoIndexed<T>(ArrayLinkedList<T>);
378struct IntoIndices<T>(IntoIndexed<T>);
379
380/// Owning iterator over values of the linked array.
381pub struct IntoValues<T>(IntoIndexed<T>);
382
383impl<T> Iterator for IntoIndexed<T> {
384    type Item = (usize, T);
385    #[inline]
386    fn next(&mut self) -> Option<Self::Item> {
387        let index = self.0.first_index.index()?;
388
389        let element = &mut self.0.elements[index];
390        if self.0.first_index == self.0.last_index {
391            self.0.first_index = Id::default();
392            self.0.last_index = Id::default();
393        } else {
394            self.0.first_index = element.next_index;
395        }
396        Some((index, unsafe { element.data.take().unwrap_unchecked() }))
397    }
398}
399
400impl<T> DoubleEndedIterator for IntoIndexed<T> {
401    #[inline]
402    fn next_back(&mut self) -> Option<Self::Item> {
403        let index = self.0.last_index.index()?;
404
405        let element = &mut self.0.elements[index];
406        if self.0.first_index == self.0.last_index {
407            self.0.first_index = Id::default();
408            self.0.last_index = Id::default();
409        } else {
410            self.0.last_index = element.prev_index;
411        }
412        Some((index, unsafe { element.data.take().unwrap_unchecked() }))
413    }
414}
415
416impl<T> Iterator for IntoIndices<T> {
417    type Item = usize;
418    fn next(&mut self) -> Option<Self::Item> {
419        self.0.next().map(|(index, _)| index)
420    }
421}
422
423impl<T> DoubleEndedIterator for IntoIndices<T> {
424    fn next_back(&mut self) -> Option<Self::Item> {
425        self.0.next_back().map(|(index, _)| index)
426    }
427}
428
429impl<T> Iterator for IntoValues<T> {
430    type Item = T;
431    fn next(&mut self) -> Option<Self::Item> {
432        self.0.next().map(|(_, value)| value)
433    }
434}
435
436impl<T> DoubleEndedIterator for IntoValues<T> {
437    fn next_back(&mut self) -> Option<Self::Item> {
438        self.0.next_back().map(|(_, value)| value)
439    }
440}
441
442impl<T> IntoIterator for ArrayLinkedList<T> {
443    type Item = T;
444    type IntoIter = IntoValues<T>;
445
446    fn into_iter(self) -> Self::IntoIter {
447        IntoValues(IntoIndexed(self))
448    }
449}
array_linked_list/iter.rs

array_linked_list/
iter.rs
