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    /// Drop the undo log without touching the working domain.
62    ///
63    /// Used by the restart driver to bake a post-propagation "baseline"
64    /// domain in place: the reductions already applied to `domain` are kept,
65    /// but their depth-tagged log entries are discarded so subsequent
66    /// `restore()` calls at any search depth cannot un-prune them. This is
67    /// the seam fix that stops a depth-0 backtrack from silently undoing
68    /// `solve_with_given`'s initial AC-3.
69    pub fn clear_log(&mut self) {
70        self.pruned.clear();
71    }
72
73    /// Reset the working domain to `domain` and clear the undo log.
74    ///
75    /// The restart driver calls this to return every variable to the shared
76    /// post-initial-propagation baseline before re-descending.
77    pub fn reset_to(&mut self, domain: D) {
78        self.domain = domain;
79        self.pruned.clear();
80    }
81
82    /// Restrict domain to a single value, recording all other removals at `depth`.
83    /// This is the fast path for backtracking assignment — avoids collecting
84    /// domain values into a Vec just to prune them.
85    ///
86    /// Delegates the actual domain mutation to `Domain::restrict_to`, which
87    /// for `BitsetDomain` clears every bit but `val`'s in one bitwise AND
88    /// (O(1)) instead of this method's previous per-value iterate-and-remove
89    /// loop (O(domain size) bit ops, on top of the `Vec` collect it used to
90    /// allocate). This method's own job shrinks to what only it can do:
91    /// recording each removed value on the depth-keyed undo log.
92    pub fn restrict_to(&mut self, val: &D::Value, depth: usize) {
93        for v in self.domain.restrict_to(val) {
94            self.pruned.push((depth, v));
95        }
96    }
97}
csp_solver/variable.rs

csp_solver/
variable.rs
