sized_chunks/sparse_chunk/
iter.rs

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

sized_chunks/sparse_chunk/
iter.rs
