1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

use crate::Bitset;

/// Iterator over set bits in a bitset
pub struct BitsetIterator<'a> {
    bitset: &'a Bitset,
    current: usize,
}

impl<'a> BitsetIterator<'a> {
    fn next_set_bits(&mut self, buffer: &mut [usize]) -> usize {
        let mut current = self.current;
        let len = unsafe {
            ffi::bitset_next_set_bits(
                &self.bitset.bitset,
                buffer.as_mut_ptr(),
                buffer.len(),
                &mut current,
            )
        };
        self.current = current + 1;
        len
    }
}

impl<'a> Iterator for BitsetIterator<'a> {
    type Item = usize;

    #[doc(alias = "bitset_next_set_bit")]
    fn next(&mut self) -> Option<Self::Item> {
        let has_value = unsafe { ffi::bitset_next_set_bit(&self.bitset.bitset, &mut self.current) };
        let value = self.current;
        self.current += 1;
        has_value.then_some(value)
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (0, Some(self.bitset.size_in_bits() - self.current))
    }

    #[doc(alias = "bitset_next_set_bits")]
    fn fold<B, F>(mut self, init: B, mut f: F) -> B
    where
        Self: Sized,
        F: FnMut(B, Self::Item) -> B,
    {
        let mut acc = init;
        let mut buffer = [0; 512];
        loop {
            let count = self.next_set_bits(&mut buffer);
            if count == 0 {
                return acc;
            }
            for &value in &buffer[..count] {
                acc = f(acc, value);
            }
        }
    }
}

impl<'a> IntoIterator for &'a Bitset {
    type Item = usize;
    type IntoIter = BitsetIterator<'a>;

    #[inline]
    fn into_iter(self) -> Self::IntoIter {
        self.iter()
    }
}

impl Bitset {
    /// Returns an iterator over the set bits in the bitset
    #[inline]
    #[must_use]
    pub const fn iter(&self) -> BitsetIterator<'_> {
        BitsetIterator {
            bitset: self,
            current: 0,
        }
    }
}