csp_solver/domain/
bitset.rs

1//! BitsetDomain — O(1) domain for non-negative integers, isomorphic to Python's BitsetDomain.
2
3use super::traits::Domain;
4
5/// A domain backed by a 128-bit bitmask.
6///
7/// Values must be non-negative integers in the range `0..128`.
8/// All operations are O(1) via bitwise arithmetic and popcount.
9/// Isomorphic to the Python `BitsetDomain`.
10#[derive(Clone, PartialEq)]
11pub struct BitsetDomain {
12    bits: u128,
13}
14
15impl std::fmt::Debug for BitsetDomain {
16    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
17        let vals: Vec<u32> = self.values();
18        write!(f, "BitsetDomain({vals:?})")
19    }
20}
21
22impl BitsetDomain {
23    /// Create a new bitset domain from an iterator of values.
24    pub fn new(values: impl IntoIterator<Item = u32>) -> Self {
25        let mut bits: u128 = 0;
26        for v in values {
27            debug_assert!(v < 128, "BitsetDomain supports values 0..128");
28            bits |= 1u128 << v;
29        }
30        Self { bits }
31    }
32
33    /// Create an empty bitset domain.
34    pub fn empty() -> Self {
35        Self { bits: 0 }
36    }
37
38    /// Create a domain containing `0..n`.
39    pub fn range(n: u32) -> Self {
40        debug_assert!(n <= 128);
41        let bits = if n == 128 { u128::MAX } else { (1u128 << n) - 1 };
42        Self { bits }
43    }
44
45    /// Raw bits access.
46    pub fn bits(&self) -> u128 {
47        self.bits
48    }
49
50    /// Union with another bitset domain.
51    pub fn union_with(&mut self, other: &Self) {
52        self.bits |= other.bits;
53    }
54
55    /// Intersection with another bitset domain.
56    pub fn intersect_with(&mut self, other: &Self) {
57        self.bits &= other.bits;
58    }
59
60    /// Difference: remove all values present in `other`.
61    pub fn difference_with(&mut self, other: &Self) {
62        self.bits &= !other.bits;
63    }
64
65    /// Iterate over set bits, yielding each value.
66    pub fn iter(&self) -> BitsetIter {
67        BitsetIter { bits: self.bits }
68    }
69}
70
71impl Domain for BitsetDomain {
72    type Value = u32;
73
74    fn size(&self) -> usize {
75        self.bits.count_ones() as usize
76    }
77
78    fn contains(&self, val: &u32) -> bool {
79        if *val >= 128 {
80            return false;
81        }
82        (self.bits & (1u128 << val)) != 0
83    }
84
85    fn remove(&mut self, val: &u32) -> bool {
86        if *val >= 128 {
87            return false;
88        }
89        let mask = 1u128 << val;
90        let was_present = (self.bits & mask) != 0;
91        self.bits &= !mask;
92        was_present
93    }
94
95    fn add(&mut self, val: &u32) {
96        debug_assert!(*val < 128, "BitsetDomain supports values 0..128");
97        self.bits |= 1u128 << val;
98    }
99
100    fn values(&self) -> Vec<u32> {
101        self.iter().collect()
102    }
103
104    fn iter(&self) -> impl Iterator<Item = u32> {
105        BitsetIter { bits: self.bits }
106    }
107
108    fn singleton_value(&self) -> Option<u32> {
109        if self.bits.count_ones() == 1 {
110            Some(self.bits.trailing_zeros())
111        } else {
112            None
113        }
114    }
115}
116
117/// Iterator over set bits in a `BitsetDomain`.
118pub struct BitsetIter {
119    bits: u128,
120}
121
122impl Iterator for BitsetIter {
123    type Item = u32;
124
125    fn next(&mut self) -> Option<u32> {
126        if self.bits == 0 {
127            None
128        } else {
129            let lowest = self.bits.trailing_zeros();
130            self.bits &= self.bits - 1; // clear lowest set bit
131            Some(lowest)
132        }
133    }
134
135    fn size_hint(&self) -> (usize, Option<usize>) {
136        let count = self.bits.count_ones() as usize;
137        (count, Some(count))
138    }
139}
140
141impl ExactSizeIterator for BitsetIter {}
csp_solver/domain/bitset.rs

csp_solver/domain/
bitset.rs
