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` cardinality fits 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
20impl BitVectorIter {
21    /// Total number of ordinals in this iterator's finite domain.
22    pub fn total_ordinals(&self) -> u128 {
23        self.total
24    }
25
26    /// Number of ordinals not yet emitted.
27    pub fn remaining_ordinals(&self) -> u128 {
28        self.total.saturating_sub(self.next)
29    }
30}
31
32/// Construct a bit-vector iterator, rejecting widths that would overflow the
33/// `u128` cursor.
34pub fn bit_vectors(width: usize) -> Result<BitVectorIter, CombError> {
35    if width > MAX_WIDTH {
36        return Err(CombError::LimitExceeded(format!(
37            "bit-vector width {width} exceeds {MAX_WIDTH}"
38        )));
39    }
40    let total = 1u128 << width;
41    Ok(BitVectorIter {
42        width,
43        next: 0,
44        total,
45    })
46}
47
48impl Iterator for BitVectorIter {
49    type Item = Vec<bool>;
50
51    fn next(&mut self) -> Option<Self::Item> {
52        if self.next >= self.total {
53            return None;
54        }
55        let r = self.next;
56        self.next += 1;
57        Some((0..self.width).map(|j| (r >> j) & 1 == 1).collect())
58    }
59}
60
61/// The ordinal of a bit vector (position 0 = least significant bit).
62pub fn bit_vector_rank(bits: &[bool]) -> BigUint {
63    let mut rank = BigUint::from(0u32);
64    for (j, &b) in bits.iter().enumerate() {
65        if b {
66            rank.set_bit(j as u64, true);
67        }
68    }
69    rank
70}
71
72/// The bit vector of the given `width` for ordinal `rank`.
73pub fn bit_vector_unrank(rank: &BigUint, width: usize) -> Result<Vec<bool>, CombError> {
74    let bound = BigUint::from(1u32) << width;
75    if rank >= &bound {
76        return Err(CombError::OutOfRange {
77            value: rank.to_string(),
78            bound: bound.to_string(),
79        });
80    }
81    Ok((0..width).map(|j| rank.bit(j as u64)).collect())
82}
83
84#[cfg(test)]
85mod tests {
86    use super::*;
87
88    #[test]
89    fn iterates_all_in_order() {
90        let all: Vec<_> = bit_vectors(2).unwrap().collect();
91        assert_eq!(all.len(), 4);
92        assert_eq!(all[0], vec![false, false]);
93        assert_eq!(all[1], vec![true, false]); // ordinal 1 -> bit 0 set
94        assert_eq!(all[3], vec![true, true]);
95    }
96
97    #[test]
98    fn rank_unrank_round_trip() {
99        for (i, bits) in bit_vectors(5).unwrap().enumerate() {
100            let r = bit_vector_rank(&bits);
101            assert_eq!(r, BigUint::from(i as u32));
102            assert_eq!(bit_vector_unrank(&r, 5).unwrap(), bits);
103        }
104    }
105
106    #[test]
107    fn width_limit_enforced() {
108        assert!(matches!(bit_vectors(200), Err(CombError::LimitExceeded(_))));
109    }
110
111    #[test]
112    fn unrank_rejects_cardinality() {
113        assert!(matches!(
114            bit_vector_unrank(&BigUint::from(8u32), 3),
115            Err(CombError::OutOfRange { .. })
116        ));
117    }
118
119    #[test]
120    fn width_127_total_is_exact_domain_size() {
121        let iter = bit_vectors(127).unwrap();
122        assert_eq!(iter.total_ordinals(), 1u128 << 127);
123        assert_eq!(iter.remaining_ordinals(), 1u128 << 127);
124    }
125}
sim_lib_discrete_comb/bit_vector.rs

sim_lib_discrete_comb/
bit_vector.rs
