csp_solver/domain/
traits.rs

1//! Core Domain trait and LatticeDomain extension.
2
3use std::fmt::Debug;
4
5/// A domain of possible values for a CSP variable.
6///
7/// The iteration primitive is `iter()`, not `values()`. Implementations should
8/// provide zero-allocation iterators where possible (e.g. `BitsetDomain` iterates
9/// bits from a `u128` without heap allocation).
10pub trait Domain: Clone + PartialEq + Debug {
11    /// The type of individual values in this domain.
12    type Value: Clone + PartialEq + Debug;
13
14    /// Number of values currently in the domain.
15    fn size(&self) -> usize;
16
17    /// Whether the domain is empty (wipe-out).
18    fn is_empty(&self) -> bool {
19        self.size() == 0
20    }
21
22    /// Whether the domain contains exactly one value.
23    fn is_singleton(&self) -> bool {
24        self.size() == 1
25    }
26
27    /// If the domain is a singleton, return its sole value.
28    fn singleton_value(&self) -> Option<Self::Value> {
29        if self.is_singleton() {
30            self.iter().next()
31        } else {
32            None
33        }
34    }
35
36    /// Test membership.
37    fn contains(&self, val: &Self::Value) -> bool;
38
39    /// Remove a value from the domain. Returns `true` if the value was present.
40    fn remove(&mut self, val: &Self::Value) -> bool;
41
42    /// Add a value back into the domain.
43    fn add(&mut self, val: &Self::Value);
44
45    /// Collect all current values into a Vec.
46    fn values(&self) -> Vec<Self::Value>;
47
48    /// Iterate over current values without allocating.
49    ///
50    /// Default delegates to `values().into_iter()`. Override for zero-alloc
51    /// iteration (e.g. `BitsetDomain` yields bits from a `u128` copy).
52    ///
53    /// The returned iterator is owned — it does NOT borrow `&self`, so the
54    /// domain can be mutated while iteration is in progress (the iterator
55    /// holds a snapshot).
56    ///
57    /// `+ use<Self>` is load-bearing, not decorative: edition 2024's
58    /// default RPIT-capture rule ties the opaque return type to the
59    /// elided `&self` lifetime even though no implementation actually
60    /// borrows anything, which blocks exactly the
61    /// `for v in x.iter() { x.remove(&v) }` pattern this trait's own doc
62    /// comment above promises works. The precise-capture bound tells the
63    /// compiler what's already true of every implementation.
64    fn iter(&self) -> impl Iterator<Item = Self::Value> + use<Self> {
65        self.values().into_iter()
66    }
67
68    /// Restrict the domain to hold only `val`, removing every other value.
69    /// Returns an iterator over the values that were removed, for the
70    /// caller's undo log (`Variable::restrict_to`).
71    ///
72    /// Default: iterate + remove one at a time — zero heap allocation
73    /// given `iter()`'s owned-snapshot contract, but O(domain size) bit
74    /// ops. Override where the internal representation allows a single
75    /// bulk mutation instead of a per-value one — e.g. `BitsetDomain`
76    /// clears every bit but `val`'s in one bitwise AND (`bitset.rs`),
77    /// turning an O(domain size) sequence of individual clears into O(1).
78    fn restrict_to(&mut self, val: &Self::Value) -> impl Iterator<Item = Self::Value> + use<Self> {
79        let mut removed = Vec::new();
80        for v in self.iter() {
81            if v != *val {
82                self.remove(&v);
83                removed.push(v);
84            }
85        }
86        removed.into_iter()
87    }
88}
89
90/// A domain whose values carry associated costs for optimization.
91///
92/// Extends `Domain` with cost information, enabling branch-and-bound search
93/// to prune infeasible branches and order values by preference.
94pub trait CostDomain: Domain {
95    /// Cost of assigning this value. Lower is better.
96    fn cost(&self, val: &Self::Value) -> f64;
97
98    /// Lower bound on the minimum cost achievable from this domain.
99    ///
100    /// Default implementation scans all values; override for O(1) if your
101    /// domain tracks the minimum incrementally.
102    fn min_cost(&self) -> f64 {
103        self.values()
104            .into_iter()
105            .map(|v| self.cost(&v))
106            .fold(f64::INFINITY, f64::min)
107    }
108}
109
110/// Extension trait for monotonic lattice domains (e.g. FIRST/FOLLOW sets).
111///
112/// A lattice domain contains a single "current value" that grows monotonically
113/// via `join`. Because the value is always a singleton, no search is needed —
114/// propagation alone reaches the fixed point.
115pub trait LatticeDomain: Domain {
116    /// The bottom element of the lattice.
117    fn bottom() -> Self;
118
119    /// Join (least upper bound) with `other`. Returns `true` if `self` changed.
120    fn join(&mut self, other: &Self) -> bool;
121}
csp_solver/domain/traits.rs

csp_solver/domain/
traits.rs
