sized_chunks/sparse_chunk/
iter.rs

1use bitmaps::{Bitmap, Bits, BitsImpl, Iter as BitmapIter};
2
3use super::SparseChunk;
4
5/// An iterator over references to the elements of a `SparseChunk`.
6pub struct Iter<'a, A, const N: usize>
7where
8    BitsImpl<N>: Bits,
9{
10    pub(crate) indices: BitmapIter<'a, N>,
11    pub(crate) chunk: &'a SparseChunk<A, N>,
12}
13
14impl<'a, A, const N: usize> Iterator for Iter<'a, A, N>
15where
16    BitsImpl<N>: Bits,
17{
18    type Item = &'a A;
19
20    fn next(&mut self) -> Option<Self::Item> {
21        self.indices.next().map(|index| &self.chunk.values()[index])
22    }
23
24    fn size_hint(&self) -> (usize, Option<usize>) {
25        (0, Some(SparseChunk::<A, N>::CAPACITY))
26    }
27}
28
29/// An iterator over mutable references to the elements of a `SparseChunk`.
30pub struct IterMut<'a, A, const N: usize>
31where
32    BitsImpl<N>: Bits,
33{
34    pub(crate) bitmap: Bitmap<N>,
35    pub(crate) chunk: &'a mut SparseChunk<A, N>,
36}
37
38impl<'a, A, const N: usize> Iterator for IterMut<'a, A, N>
39where
40    BitsImpl<N>: Bits,
41{
42    type Item = &'a mut A;
43
44    fn next(&mut self) -> Option<Self::Item> {
45        if let Some(index) = self.bitmap.first_index() {
46            self.bitmap.set(index, false);
47            unsafe {
48                let p: *mut A = &mut self.chunk.values_mut()[index];
49                Some(&mut *p)
50            }
51        } else {
52            None
53        }
54    }
55
56    fn size_hint(&self) -> (usize, Option<usize>) {
57        (0, Some(SparseChunk::<A, N>::CAPACITY))
58    }
59}
60
61/// A draining iterator over the elements of a `SparseChunk`.
62///
63/// "Draining" means that as the iterator yields each element, it's removed from
64/// the `SparseChunk`. When the iterator terminates, the chunk will be empty.
65pub struct Drain<A, const N: usize>
66where
67    BitsImpl<N>: Bits,
68{
69    pub(crate) chunk: SparseChunk<A, N>,
70}
71
72impl<'a, A, const N: usize> Iterator for Drain<A, N>
73where
74    BitsImpl<N>: Bits,
75{
76    type Item = A;
77
78    fn next(&mut self) -> Option<Self::Item> {
79        self.chunk.pop()
80    }
81
82    fn size_hint(&self) -> (usize, Option<usize>) {
83        let len = self.chunk.len();
84        (len, Some(len))
85    }
86}
87
88/// An iterator over `Option`s of references to the elements of a `SparseChunk`.
89///
90/// Iterates over every index in the `SparseChunk`, from zero to its full capacity,
91/// returning an `Option<&A>` for each index.
92pub struct OptionIter<'a, A, const N: usize>
93where
94    BitsImpl<N>: Bits,
95{
96    pub(crate) index: usize,
97    pub(crate) chunk: &'a SparseChunk<A, N>,
98}
99
100impl<'a, A, const N: usize> Iterator for OptionIter<'a, A, N>
101where
102    BitsImpl<N>: Bits,
103{
104    type Item = Option<&'a A>;
105
106    fn next(&mut self) -> Option<Self::Item> {
107        if self.index < N {
108            let result = self.chunk.get(self.index);
109            self.index += 1;
110            Some(result)
111        } else {
112            None
113        }
114    }
115
116    fn size_hint(&self) -> (usize, Option<usize>) {
117        (
118            SparseChunk::<A, N>::CAPACITY - self.index,
119            Some(SparseChunk::<A, N>::CAPACITY - self.index),
120        )
121    }
122}
123
124/// An iterator over `Option`s of mutable references to the elements of a `SparseChunk`.
125///
126/// Iterates over every index in the `SparseChunk`, from zero to its full capacity,
127/// returning an `Option<&mut A>` for each index.
128pub struct OptionIterMut<'a, A, const N: usize>
129where
130    BitsImpl<N>: Bits,
131{
132    pub(crate) index: usize,
133    pub(crate) chunk: &'a mut SparseChunk<A, N>,
134}
135
136impl<'a, A, const N: usize> Iterator for OptionIterMut<'a, A, N>
137where
138    BitsImpl<N>: Bits,
139{
140    type Item = Option<&'a mut A>;
141
142    fn next(&mut self) -> Option<Self::Item> {
143        if self.index < N {
144            let result = if self.chunk.map.get(self.index) {
145                unsafe {
146                    let p: *mut A = &mut self.chunk.values_mut()[self.index];
147                    Some(Some(&mut *p))
148                }
149            } else {
150                Some(None)
151            };
152            self.index += 1;
153            result
154        } else {
155            None
156        }
157    }
158
159    fn size_hint(&self) -> (usize, Option<usize>) {
160        (
161            SparseChunk::<A, N>::CAPACITY - self.index,
162            Some(SparseChunk::<A, N>::CAPACITY - self.index),
163        )
164    }
165}
166
167/// A draining iterator over `Option`s of the elements of a `SparseChunk`.
168///
169/// Iterates over every index in the `SparseChunk`, from zero to its full capacity,
170/// returning an `Option<A>` for each index.
171pub struct OptionDrain<A, const N: usize>
172where
173    BitsImpl<N>: Bits,
174{
175    pub(crate) index: usize,
176    pub(crate) chunk: SparseChunk<A, N>,
177}
178
179impl<'a, A, const N: usize> Iterator for OptionDrain<A, N>
180where
181    BitsImpl<N>: Bits,
182{
183    type Item = Option<A>;
184
185    fn next(&mut self) -> Option<Self::Item> {
186        if self.index < N {
187            let result = self.chunk.remove(self.index);
188            self.index += 1;
189            Some(result)
190        } else {
191            None
192        }
193    }
194
195    fn size_hint(&self) -> (usize, Option<usize>) {
196        (
197            SparseChunk::<A, N>::CAPACITY - self.index,
198            Some(SparseChunk::<A, N>::CAPACITY - self.index),
199        )
200    }
201}
202
203#[cfg(test)]
204mod test {
205    use super::*;
206    use std::iter::FromIterator;
207
208    #[test]
209    fn iter() {
210        let vec: Vec<Option<usize>> =
211            Vec::from_iter((0..64).map(|i| if i % 2 == 0 { Some(i) } else { None }));
212        let chunk: SparseChunk<usize, 64> = vec.iter().cloned().collect();
213        let vec: Vec<usize> = vec
214            .iter()
215            .cloned()
216            .filter(|v| v.is_some())
217            .map(|v| v.unwrap())
218            .collect();
219        assert!(vec.iter().eq(chunk.iter()));
220    }
221
222    #[test]
223    fn iter_mut() {
224        let vec: Vec<Option<usize>> =
225            Vec::from_iter((0..64).map(|i| if i % 2 == 0 { Some(i) } else { None }));
226        let mut chunk: SparseChunk<_, 64> = vec.iter().cloned().collect();
227        let mut vec: Vec<usize> = vec
228            .iter()
229            .cloned()
230            .filter(|v| v.is_some())
231            .map(|v| v.unwrap())
232            .collect();
233        assert!(vec.iter_mut().eq(chunk.iter_mut()));
234    }
235
236    #[test]
237    fn drain() {
238        let vec: Vec<Option<usize>> =
239            Vec::from_iter((0..64).map(|i| if i % 2 == 0 { Some(i) } else { None }));
240        let chunk: SparseChunk<_, 64> = vec.iter().cloned().collect();
241        let vec: Vec<usize> = vec
242            .iter()
243            .cloned()
244            .filter(|v| v.is_some())
245            .map(|v| v.unwrap())
246            .collect();
247        assert!(vec.into_iter().eq(chunk.into_iter()));
248    }
249
250    #[test]
251    fn option_iter() {
252        let vec: Vec<Option<usize>> =
253            Vec::from_iter((0..64).map(|i| if i % 2 == 0 { Some(i) } else { None }));
254        let chunk: SparseChunk<_, 64> = vec.iter().cloned().collect();
255        assert!(vec
256            .iter()
257            .cloned()
258            .eq(chunk.option_iter().map(|v| v.cloned())));
259    }
260
261    #[test]
262    fn option_iter_mut() {
263        let vec: Vec<Option<usize>> =
264            Vec::from_iter((0..64).map(|i| if i % 2 == 0 { Some(i) } else { None }));
265        let mut chunk: SparseChunk<_, 64> = vec.iter().cloned().collect();
266        assert!(vec
267            .iter()
268            .cloned()
269            .eq(chunk.option_iter_mut().map(|v| v.cloned())));
270    }
271
272    #[test]
273    fn option_drain() {
274        let vec: Vec<Option<usize>> =
275            Vec::from_iter((0..64).map(|i| if i % 2 == 0 { Some(i) } else { None }));
276        let chunk: SparseChunk<_, 64> = vec.iter().cloned().collect();
277        assert!(vec.iter().cloned().eq(chunk.option_drain()));
278    }
279}
sized_chunks/sparse_chunk/iter.rs

sized_chunks/sparse_chunk/
iter.rs
