haar_lib/algo/enum_bit/
subset_between.rs

1//! $a \subseteq x \subseteq b$を満たす`x`を列挙する
2use std::iter::successors;
3
4/// $a \subseteq x \subseteq b$を満たす`x`を列挙するイテレータを返す。
5pub fn subset_between(a: u32, b: u32) -> impl Iterator<Item = u32> {
6    let x = b ^ (a & b);
7
8    successors((a & !b == 0).then_some(0), move |&t: &u32| {
9        t.checked_sub(1).map(|a| a % x)
10    })
11    .map(move |t| t | a)
12}
13
14#[cfg(test)]
15mod tests {
16    use super::*;
17    use test_case::test_case;
18
19    #[test_case(0b11111111, 0b11111111)]
20    #[test_case(0b00000000, 0b11111111)]
21    #[test_case(0b10101010, 0b11111111)]
22    #[test_case(0b00000001, 0b01010101)]
23    #[test_case(0b00000001, 0b00000010)]
24    fn check(x: u32, y: u32) {
25        let a = (0..=x)
26            .filter(|i| (x & !i) == 0 && (!y & i) == 0)
27            .collect::<Vec<_>>();
28
29        let b = subset_between(x, y).collect::<Vec<_>>();
30
31        assert_eq!(a, b);
32    }
33}