libreda-logic 0.0.3

// SPDX-FileCopyrightText: 2022 Thomas Kramer <code@tkramer.ch>
//
// SPDX-License-Identifier: AGPL-3.0-or-later

//! Tools for iterating through all n-bit patterns by changing only a single bit at a time.

/// Generate the positions of bit flips which step through a binary gray code.
#[derive(Copy, Clone, Debug)]
pub struct GrayCodeFlips {
    state: usize,
    /// Mask the lower `n` bits.
    /// Set to zero when the iterator is finished.
    mask: usize,
}

/// Iterate over the bit-flip positions of a binary gray code.
pub fn gray_code_flips(num_bits: usize) -> GrayCodeFlips {
    assert!(
        num_bits < usize::BITS as usize,
        "number of bits must fit into an usize"
    );
    GrayCodeFlips {
        state: 0,
        mask: (1 << num_bits) - 1,
    }
}

impl Iterator for GrayCodeFlips {
    type Item = usize;

    fn next(&mut self) -> Option<Self::Item> {
        if self.mask == 0 {
            None
        } else {
            let s = self.state;
            let s_next = (s + 1) & self.mask;
            if s_next == 0 {
                self.mask = 0; // Fuse the iterator.
            }

            let bit_flip_position = (s ^ s_next).count_ones() - 1;

            self.state = s_next;

            Some(bit_flip_position as usize)
        }
    }
}

#[test]
fn test_gray_code_flips() {
    let counter_size = 4;
    let code_length = 1 << counter_size;

    let flips = gray_code_flips(counter_size);

    // Test that the generated bit differences indeed generate `code_length` different bit patterns.

    let gray_code: std::collections::HashSet<_> = flips
        // Create the grapy code from the differences.
        .scan(0, |acc, flip_position| {
            let output = *acc;
            // Do bit-flip.
            *acc ^= 1 << flip_position;

            Some(output)
        })
        .collect();

    assert_eq!(gray_code.len(), code_length);
}

#[test]
fn test_gray_code_cyclic() {
    let flips = gray_code_flips(4);
    let mut state = 0;
    for idx in flips {
        dbg!(idx);
        state ^= 1 << idx;
    }
    assert_eq!(state, 0);
}