sim_lib_discrete_comb/
bit_vector.rs

1//! Fixed-width bit vectors in natural binary order, with rank/unrank.
2//!
3//! Position 0 is the least-significant bit, so ordinal `r` maps to the bit
4//! vector whose bit `j` is `(r >> j) & 1`.
5
6use crate::error::CombError;
7use num_bigint::BigUint;
8
9/// The largest width whose `2^width` ordinals fit a `u128` cursor.
10const MAX_WIDTH: usize = 127;
11
12/// Iterator over all `2^width` bit vectors of length `width`, in ordinal order.
13#[derive(Debug, Clone)]
14pub struct BitVectorIter {
15    width: usize,
16    next: u128,
17    total: u128,
18}
19
20/// Construct a bit-vector iterator, rejecting widths that would overflow the
21/// `u128` cursor.
22pub fn bit_vectors(width: usize) -> Result<BitVectorIter, CombError> {
23    if width > MAX_WIDTH {
24        return Err(CombError::LimitExceeded(format!(
25            "bit-vector width {width} exceeds {MAX_WIDTH}"
26        )));
27    }
28    let total = if width == MAX_WIDTH {
29        u128::MAX // 2^127 - 1 cursor range; the final vector is emitted on wrap
30    } else {
31        1u128 << width
32    };
33    Ok(BitVectorIter {
34        width,
35        next: 0,
36        total,
37    })
38}
39
40impl Iterator for BitVectorIter {
41    type Item = Vec<bool>;
42
43    fn next(&mut self) -> Option<Self::Item> {
44        if self.next >= self.total {
45            return None;
46        }
47        let r = self.next;
48        self.next += 1;
49        Some((0..self.width).map(|j| (r >> j) & 1 == 1).collect())
50    }
51}
52
53/// The ordinal of a bit vector (position 0 = least significant bit).
54pub fn bit_vector_rank(bits: &[bool]) -> BigUint {
55    let mut rank = BigUint::from(0u32);
56    for (j, &b) in bits.iter().enumerate() {
57        if b {
58            rank.set_bit(j as u64, true);
59        }
60    }
61    rank
62}
63
64/// The bit vector of the given `width` for ordinal `rank`.
65pub fn bit_vector_unrank(rank: &BigUint, width: usize) -> Vec<bool> {
66    (0..width).map(|j| rank.bit(j as u64)).collect()
67}
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[test]
74    fn iterates_all_in_order() {
75        let all: Vec<_> = bit_vectors(2).unwrap().collect();
76        assert_eq!(all.len(), 4);
77        assert_eq!(all[0], vec![false, false]);
78        assert_eq!(all[1], vec![true, false]); // ordinal 1 -> bit 0 set
79        assert_eq!(all[3], vec![true, true]);
80    }
81
82    #[test]
83    fn rank_unrank_round_trip() {
84        for (i, bits) in bit_vectors(5).unwrap().enumerate() {
85            let r = bit_vector_rank(&bits);
86            assert_eq!(r, BigUint::from(i as u32));
87            assert_eq!(bit_vector_unrank(&r, 5), bits);
88        }
89    }
90
91    #[test]
92    fn width_limit_enforced() {
93        assert!(matches!(bit_vectors(200), Err(CombError::LimitExceeded(_))));
94    }
95}
sim_lib_discrete_comb/bit_vector.rs

sim_lib_discrete_comb/
bit_vector.rs
