standard_lib/collections/linked/list/
iter.rs

1use std::iter::{FusedIterator, TrustedLen};
2use std::marker::PhantomData;
3
4use ListState::*;
5
6use super::{LinkedList, ListContents, ListState};
7
8impl<T> IntoIterator for LinkedList<T> {
9    type Item = T;
10
11    type IntoIter = IntoIter<T>;
12
13    fn into_iter(self) -> Self::IntoIter {
14        IntoIter {
15            list: self,
16        }
17    }
18}
19
20pub struct IntoIter<T> {
21    // There is no point me rewriting all of this when the iterator can just hold the list and call
22    // pop front/back.
23    pub(crate) list: LinkedList<T>,
24}
25
26impl<T> Iterator for IntoIter<T> {
27    type Item = T;
28
29    fn next(&mut self) -> Option<Self::Item> {
30        self.list.pop_front()
31    }
32
33    fn size_hint(&self) -> (usize, Option<usize>) {
34        (self.len(), Some(self.len()))
35    }
36}
37
38impl<T> DoubleEndedIterator for IntoIter<T> {
39    fn next_back(&mut self) -> Option<Self::Item> {
40        self.list.pop_back()
41    }
42}
43
44impl<T> FusedIterator for IntoIter<T> {}
45
46impl<T> ExactSizeIterator for IntoIter<T> {
47    fn len(&self) -> usize {
48        self.list.len()
49    }
50}
51
52// SAFETY: IntoIter::size_hint returns the exact length of the iterator.
53unsafe impl<T> TrustedLen for IntoIter<T> {}
54
55impl<'a, T> IntoIterator for &'a mut LinkedList<T> {
56    type Item = &'a mut T;
57
58    type IntoIter = IterMut<'a, T>;
59
60    fn into_iter(self) -> Self::IntoIter {
61        IterMut {
62            state: self.state.clone(),
63            _phantom: PhantomData,
64        }
65    }
66}
67
68pub struct IterMut<'a, T> {
69    // Although ths fields are exactly the same as a list, this structure doesn't modify the
70    // underlying nodes and uses len to track the number of items left to yield.
71    pub(crate) state: ListState<T>,
72    pub(crate) _phantom: PhantomData<&'a mut T>,
73}
74
75impl<'a, T> Iterator for IterMut<'a, T> {
76    type Item = &'a mut T;
77
78    fn next(&mut self) -> Option<Self::Item> {
79        match &mut self.state {
80            Empty => None,
81            Full(ListContents { len, head, .. }) => {
82                let value = head.value_mut();
83
84                match len.checked_sub(1) {
85                    Some(new_len) => {
86                        // SAFETY: Previous length is greater than 1, so the first element is
87                        // preceded by at least one more.
88                        let new_head = unsafe { head.next().unwrap_unchecked() };
89                        *head = new_head;
90                        // Never actually modify the node itself.
91                        *len = new_len;
92                    },
93                    None => self.state = Empty,
94                }
95
96                Some(value)
97            },
98        }
99    }
100
101    fn size_hint(&self) -> (usize, Option<usize>) {
102        (self.len(), Some(self.len()))
103    }
104}
105
106impl<'a, T> DoubleEndedIterator for IterMut<'a, T> {
107    fn next_back(&mut self) -> Option<Self::Item> {
108        match &mut self.state {
109            Empty => None,
110            Full(ListContents { len, tail, .. }) => {
111                let value = tail.value_mut();
112
113                match len.checked_sub(1) {
114                    Some(new_len) => {
115                        // SAFETY: Previous length is greater than 1, so the last element is
116                        // preceded by at least one more.
117                        let new_tail = unsafe { tail.prev().unwrap_unchecked() };
118                        *tail = new_tail;
119                        // Never actually modify the node itself.
120                        *len = new_len;
121                    },
122                    None => self.state = Empty,
123                }
124
125                Some(value)
126            },
127        }
128    }
129}
130
131impl<'a, T> FusedIterator for IterMut<'a, T> {}
132
133impl<'a, T> ExactSizeIterator for IterMut<'a, T> {
134    fn len(&self) -> usize {
135        self.state.len()
136    }
137}
138
139// SAFETY: IterMut::size_hint returns the exact length of the iterator.
140unsafe impl<'a, T> TrustedLen for IterMut<'a, T> {}
141
142impl<'a, T> IntoIterator for &'a LinkedList<T> {
143    type Item = &'a T;
144
145    type IntoIter = Iter<'a, T>;
146
147    fn into_iter(self) -> Self::IntoIter {
148        Iter {
149            state: self.state.clone(),
150            _phantom: PhantomData,
151        }
152    }
153}
154
155pub struct Iter<'a, T> {
156    pub(crate) state: ListState<T>,
157    pub(crate) _phantom: PhantomData<&'a T>,
158}
159
160impl<'a, T> Iterator for Iter<'a, T> {
161    type Item = &'a T;
162
163    fn next(&mut self) -> Option<Self::Item> {
164        match &mut self.state {
165            Empty => None,
166            Full(ListContents { len, head, .. }) => {
167                let value = head.value();
168
169                match len.checked_sub(1) {
170                    Some(new_len) => {
171                        // SAFETY: Previous length is greater than 1, so the first element is
172                        // preceded by at least one more.
173                        let new_head = unsafe { head.next().unwrap_unchecked() };
174                        *head = new_head;
175                        // Never actually modify the node itself.
176                        *len = new_len;
177                    },
178                    None => self.state = Empty,
179                }
180
181                Some(value)
182            },
183        }
184    }
185
186    fn size_hint(&self) -> (usize, Option<usize>) {
187        (self.len(), Some(self.len()))
188    }
189}
190
191impl<'a, T> DoubleEndedIterator for Iter<'a, T> {
192    fn next_back(&mut self) -> Option<Self::Item> {
193        match &mut self.state {
194            Empty => None,
195            Full(ListContents { len, tail, .. }) => {
196                let value = tail.value();
197
198                match len.checked_sub(1) {
199                    Some(new_len) => {
200                        // SAFETY: Previous length is greater than 1, so the last element is
201                        // preceded by at least one more.
202                        let new_tail = unsafe { tail.prev().unwrap_unchecked() };
203                        *tail = new_tail;
204                        // Never actually modify the node itself.
205                        *len = new_len;
206                    },
207                    None => self.state = Empty,
208                }
209
210                Some(value)
211            },
212        }
213    }
214}
215
216impl<'a, T> FusedIterator for Iter<'a, T> {}
217
218impl<'a, T> ExactSizeIterator for Iter<'a, T> {
219    fn len(&self) -> usize {
220        self.state.len()
221    }
222}
223
224// SAFETY: IterMut::size_hint returns the exact length of the iterator.
225unsafe impl<'a, T> TrustedLen for Iter<'a, T> {}
standard_lib/collections/linked/list/iter.rs

standard_lib/collections/linked/list/
iter.rs
