milli_core/update/
available_ids.rs

1use std::iter::{Chain, FromIterator};
2use std::ops::RangeInclusive;
3
4use roaring::bitmap::{IntoIter, RoaringBitmap};
5
6pub struct AvailableIds {
7    iter: Chain<IntoIter, RangeInclusive<u32>>,
8}
9
10impl AvailableIds {
11    pub fn new(docids: &RoaringBitmap) -> AvailableIds {
12        match docids.max() {
13            Some(last_id) => {
14                let mut available = RoaringBitmap::from_iter(0..last_id);
15                available -= docids;
16
17                let iter = match last_id.checked_add(1) {
18                    Some(id) => id..=u32::MAX,
19                    #[allow(clippy::reversed_empty_ranges)]
20                    None => 1..=0, // empty range iterator
21                };
22
23                AvailableIds { iter: available.into_iter().chain(iter) }
24            }
25            None => {
26                let empty = RoaringBitmap::new().into_iter();
27                AvailableIds { iter: empty.chain(0..=u32::MAX) }
28            }
29        }
30    }
31}
32
33impl Iterator for AvailableIds {
34    type Item = u32;
35
36    fn next(&mut self) -> Option<Self::Item> {
37        self.iter.next()
38    }
39}
40
41#[cfg(test)]
42mod tests {
43    use super::*;
44
45    #[test]
46    fn empty() {
47        let base = RoaringBitmap::new();
48        let left = AvailableIds::new(&base);
49        let right = 0..=u32::MAX;
50        left.zip(right).take(500).for_each(|(l, r)| assert_eq!(l, r));
51    }
52
53    #[test]
54    fn scattered() {
55        let mut base = RoaringBitmap::new();
56        base.insert(0);
57        base.insert(10);
58        base.insert(100);
59        base.insert(405);
60
61        let left = AvailableIds::new(&base);
62        let right = (0..=u32::MAX).filter(|&n| n != 0 && n != 10 && n != 100 && n != 405);
63        left.zip(right).take(500).for_each(|(l, r)| assert_eq!(l, r));
64    }
65}
milli_core/update/available_ids.rs

milli_core/update/
available_ids.rs
