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    fn iter(&self) -> impl Iterator<Item = Self::Value> {
57        self.values().into_iter()
58    }
59}
60
61/// A domain whose values carry associated costs for optimization.
62///
63/// Extends `Domain` with cost information, enabling branch-and-bound search
64/// to prune infeasible branches and order values by preference.
65pub trait CostDomain: Domain {
66    /// Cost of assigning this value. Lower is better.
67    fn cost(&self, val: &Self::Value) -> f64;
68
69    /// Lower bound on the minimum cost achievable from this domain.
70    ///
71    /// Default implementation scans all values; override for O(1) if your
72    /// domain tracks the minimum incrementally.
73    fn min_cost(&self) -> f64 {
74        self.values()
75            .into_iter()
76            .map(|v| self.cost(&v))
77            .fold(f64::INFINITY, f64::min)
78    }
79}
80
81/// Extension trait for monotonic lattice domains (e.g. FIRST/FOLLOW sets).
82///
83/// A lattice domain contains a single "current value" that grows monotonically
84/// via `join`. Because the value is always a singleton, no search is needed —
85/// propagation alone reaches the fixed point.
86pub trait LatticeDomain: Domain {
87    /// The bottom element of the lattice.
88    fn bottom() -> Self;
89
90    /// Join (least upper bound) with `other`. Returns `true` if `self` changed.
91    fn join(&mut self, other: &Self) -> bool;
92}
csp_solver/domain/traits.rs

csp_solver/domain/
traits.rs
