atcoder_bv_util.rs

mod bv_util{
    pub fn fill(n: usize) -> u64{
        return (1 << n) - 1;
    }

    pub fn subtract(a: u64, b: u64) -> u64{
        return a & (!b);
    }

    pub fn is_on(a: u64, pos: usize) -> bool{
        return ((a >> pos) & 1) == 1;
    }

    pub fn is_off(a: u64, pos: usize) -> bool{
        return !is_on(a, pos);
    }
    
    pub fn subset(a: u64, b: u64) -> bool{
        return subtract(a, b) == 0;
    }

    pub struct Subsets{
        s: u64,
        current: u64,
        first: bool
    }

    impl Subsets{
        pub fn new(s: u64) -> Self{
            Subsets{s: s, current: s, first: true}
        }
    }

    impl Iterator for Subsets{
        type Item = u64;
        fn next(&mut self) -> Option<Self::Item>{
            if self.first{
                self.first = false;
                return Some(self.s);
            }else{
                if self.current == 0{
                    return None
                }else{
                    self.current -= 1;
                    self.current &= self.s;
                    return Some(self.current)
                }
            }
        }
    }

    #[test]
    fn test_subsets(){
        let x: Vec<u64> = Subsets::new(0b101).collect();
        assert_eq!(x, vec![0b101, 0b100, 0b001, 0b000]);
    }

    #[test]
    fn test_ascending(){
        let mut v: Vec<u64> = Subsets::new(fill(2)).collect();
        v.sort();
        assert_eq!(v, vec![0b00, 0b01, 0b10, 0b11]);
    }
}