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

//! Bit manipulation helpers.

use crate::number::UnsignedInteger;

/// Iterator which yields all the set or unset bits in a provided number.
pub struct BitIterator<T: UnsignedInteger> {
    n: T,
}

impl<T: UnsignedInteger> BitIterator<T> {
    /// Returns an iterator that yields the positions and values of all the set bits in the provided
    /// number.
    ///
    /// # Examples
    /// ```
    /// # use utils::bit::BitIterator;
    /// assert_eq!(
    ///     BitIterator::ones(0b1001_1101u8).collect::<Vec<(u32, u8)>>(),
    ///     vec![
    ///         (0, 1),
    ///         (2, 4),
    ///         (3, 8),
    ///         (4, 16),
    ///         (7, 128),
    ///     ],
    /// );
    /// ```
    pub fn ones(n: T) -> Self {
        BitIterator { n }
    }

    /// Returns an iterator that yields the positions and values of all the unset bits in the
    /// provided number.
    ///
    /// # Examples
    /// ```
    /// # use utils::bit::BitIterator;
    /// assert_eq!(
    ///     BitIterator::zeroes(0b1001_1101u8).collect::<Vec<(u32, u8)>>(),
    ///     vec![
    ///         (1, 2),
    ///         (5, 32),
    ///         (6, 64),
    ///     ],
    /// );
    /// ```
    pub fn zeroes(n: T) -> Self {
        BitIterator { n: !n }
    }
}

impl<T: UnsignedInteger> Iterator for BitIterator<T> {
    type Item = (u32, T);

    fn next(&mut self) -> Option<Self::Item> {
        if self.n == T::ZERO {
            None
        } else {
            let position = self.n.trailing_zeros();
            let value = T::ONE << position;
            self.n &= !value;
            Some((position, value))
        }
    }
}