csp_solver/
variable.rs

1//! CSP variable with domain tracking and pruned-value undo log.
2
3use crate::domain::Domain;
4
5/// A CSP variable holding its current domain and an undo log for backtracking.
6#[derive(Debug, Clone)]
7pub struct Variable<D: Domain> {
8    /// Current (working) domain -- mutated during search.
9    pub domain: D,
10    /// Original domain -- used for full reset.
11    original_domain: D,
12    /// Undo log: `(depth, removed_value)` pairs. During backtracking, all entries
13    /// at the given depth are restored into the domain.
14    pruned: Vec<(usize, D::Value)>,
15}
16
17impl<D: Domain> Variable<D> {
18    /// Create a new variable with the given initial domain.
19    pub fn new(domain: D) -> Self {
20        Self {
21            original_domain: domain.clone(),
22            domain,
23            pruned: Vec::new(),
24        }
25    }
26
27    /// Record that `val` was pruned at `depth`, and remove it from the domain.
28    /// Returns `true` if the value was actually present and removed.
29    pub fn prune(&mut self, val: &D::Value, depth: usize) -> bool {
30        if self.domain.remove(val) {
31            self.pruned.push((depth, val.clone()));
32            true
33        } else {
34            false
35        }
36    }
37
38    /// Restore all values pruned at the given `depth`.
39    pub fn restore(&mut self, depth: usize) {
40        while let Some(&(d, _)) = self.pruned.last() {
41            if d == depth {
42                let (_, val) = self.pruned.pop().unwrap();
43                self.domain.add(&val);
44            } else {
45                break;
46            }
47        }
48    }
49
50    /// Reset to the original domain, clearing the undo log.
51    pub fn reset(&mut self) {
52        self.domain = self.original_domain.clone();
53        self.pruned.clear();
54    }
55
56    /// Replace the current domain entirely (used during initial propagation).
57    pub fn set_domain(&mut self, domain: D) {
58        self.domain = domain;
59    }
60
61    /// Restrict domain to a single value, recording all other removals at `depth`.
62    /// This is the fast path for backtracking assignment — avoids collecting
63    /// domain values into a Vec just to prune them.
64    ///
65    /// Delegates the actual domain mutation to `Domain::restrict_to`, which
66    /// for `BitsetDomain` clears every bit but `val`'s in one bitwise AND
67    /// (O(1)) instead of this method's previous per-value iterate-and-remove
68    /// loop (O(domain size) bit ops, on top of the `Vec` collect it used to
69    /// allocate). This method's own job shrinks to what only it can do:
70    /// recording each removed value on the depth-keyed undo log.
71    pub fn restrict_to(&mut self, val: &D::Value, depth: usize) {
72        for v in self.domain.restrict_to(val) {
73            self.pruned.push((depth, v));
74        }
75    }
76}
csp_solver/variable.rs

csp_solver/
variable.rs
