libreda-logic 0.0.3

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

//! Iterate over all versions of a data-type which can be reached by flipping a bit.
//!
//! Used for example to iterate through all truth-tables which can be derived by inverting input signals.

use crate::truth_table::gray_code_flips::gray_code_flips;

use super::gray_code_flips::GrayCodeFlips;

/// Trait for data-types which can be modified by flipping bits.
pub trait BitFlippable {
    /// Get the number of flippable bits.
    fn num_bits(&self) -> usize;

    /// Flip the bit at `bit_idx`.
    fn flip_bit(&mut self, bit_idx: usize);
}

/// Iterator over all combinations of bit-flips.
pub struct BitFlipIter<T> {
    state: T,
    flip_indices: GrayCodeFlips,
    remaining: usize,
}

impl<T> Iterator for BitFlipIter<T>
where
    T: BitFlippable + Clone,
{
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.remaining > 0 {
            let output = self.state.clone();
            self.remaining -= 1;

            if self.remaining > 0 {
                // Generate next state by flipping a single bit.
                self.flip_indices
                    .next()
                    .into_iter()
                    .for_each(|i| self.state.flip_bit(i));
            }

            Some(output)
        } else {
            None
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (self.remaining, Some(self.remaining))
    }
}

/// Iterate over all versions of `t` which can be derived by flipping bits.
/// In each step only a single bit is flipped. This is equivalent to iterating through a 'gray code'.
pub fn bitflips<T>(t: T) -> BitFlipIter<T>
where
    T: BitFlippable + Clone,
{
    let n = t.num_bits();
    let remaining = 1 << n;
    assert!(remaining > 0);

    BitFlipIter {
        state: t,
        flip_indices: gray_code_flips(n),
        remaining,
    }
}

#[test]
fn test_bitflips() {
    #[derive(Clone, Hash, Eq, PartialEq)]
    struct Bits {
        bits: usize,
        num_bits: usize,
    }

    impl BitFlippable for Bits {
        fn num_bits(&self) -> usize {
            self.num_bits
        }

        fn flip_bit(&mut self, bit_idx: usize) {
            self.bits ^= 1 << bit_idx
        }
    }

    let bits = Bits {
        bits: 0,
        num_bits: 4,
    };

    let all_bitflips: std::collections::HashSet<_> = bitflips(bits).collect();

    assert_eq!(all_bitflips.len(), 16);
}