solverforge_solver/phase/exhaustive/
decider.rs

1/* Exhaustive search decider for node expansion.
2
3The decider is responsible for expanding nodes and generating
4child nodes in the search tree.
5*/
6
7use std::fmt::Debug;
8
9use solverforge_core::domain::PlanningSolution;
10use solverforge_scoring::Director;
11
12use super::bounder::ScoreBounder;
13use super::node::ExhaustiveSearchNode;
14
15/// Decides how to expand nodes in the exhaustive search.
16///
17/// The decider is responsible for:
18/// - Finding the next entity to assign
19/// - Generating all possible value assignments
20/// - Creating child nodes for each assignment
21pub trait ExhaustiveSearchDecider<S: PlanningSolution, D: Director<S>>: Send + Debug {
22    /* Expands a node by generating all child nodes.
23
24    Returns a vector of child nodes, one for each possible assignment.
25    */
26    fn expand(
27        &self,
28        parent_index: usize,
29        parent: &ExhaustiveSearchNode<S>,
30        score_director: &mut D,
31    ) -> Vec<ExhaustiveSearchNode<S>>;
32
33    fn reset_assignments(&self, score_director: &mut D);
34
35    fn apply_assignment(&self, node: &ExhaustiveSearchNode<S>, score_director: &mut D);
36
37    fn total_entities(&self, score_director: &D) -> usize;
38}
39
40/// A simple value-based decider that works with any value type.
41///
42/// Uses concrete setter for zero-erasure variable assignment.
43///
44/// # Type Parameters
45/// * `S` - The planning solution type
46/// * `V` - The value type to assign
47/// * `B` - The bounder type (use `Option<B>` for optional bounding)
48pub struct SimpleDecider<S: PlanningSolution, V: Clone + Send + Sync + 'static, B = ()> {
49    // Descriptor index of the entity collection.
50    descriptor_index: usize,
51    // Variable name to assign.
52    variable_name: String,
53    // Variable index within the descriptor.
54    variable_index: usize,
55    // Possible values to try.
56    values: Vec<V>,
57    // Score bounder for optimistic bounds (None = no bounding).
58    bounder: Option<B>,
59    // Concrete setter for zero-erasure variable assignment.
60    setter: fn(&mut S, usize, Option<V>),
61}
62
63impl<S: PlanningSolution, V: Clone + Send + Sync + 'static> SimpleDecider<S, V, ()> {
64    /// Creates a new simple decider with concrete setter and no bounder.
65    ///
66    /// # Arguments
67    /// * `descriptor_index` - Index of the entity descriptor
68    /// * `variable_name` - Name of the variable being assigned
69    /// * `values` - Possible values to try
70    /// * `setter` - Concrete setter function `fn(&mut S, entity_index, value)`
71    pub fn new(
72        descriptor_index: usize,
73        variable_name: impl Into<String>,
74        values: Vec<V>,
75        setter: fn(&mut S, usize, Option<V>),
76    ) -> Self {
77        Self {
78            descriptor_index,
79            variable_name: variable_name.into(),
80            variable_index: 0,
81            values,
82            bounder: None,
83            setter,
84        }
85    }
86}
87
88impl<S: PlanningSolution, V: Clone + Send + Sync + 'static, B> SimpleDecider<S, V, B> {
89    pub fn with_bounder<B2>(self, bounder: B2) -> SimpleDecider<S, V, B2> {
90        SimpleDecider {
91            descriptor_index: self.descriptor_index,
92            variable_name: self.variable_name,
93            variable_index: self.variable_index,
94            values: self.values,
95            bounder: Some(bounder),
96            setter: self.setter,
97        }
98    }
99
100    pub fn with_variable_index(mut self, variable_index: usize) -> Self {
101        self.variable_index = variable_index;
102        self
103    }
104}
105
106impl<S: PlanningSolution, V: Clone + Send + Sync + Debug + 'static, B: Debug> Debug
107    for SimpleDecider<S, V, B>
108{
109    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
110        f.debug_struct("SimpleDecider")
111            .field("descriptor_index", &self.descriptor_index)
112            .field("variable_name", &self.variable_name)
113            .field("variable_index", &self.variable_index)
114            .field("value_count", &self.values.len())
115            .finish()
116    }
117}
118
119impl<S, V, B, D> ExhaustiveSearchDecider<S, D> for SimpleDecider<S, V, B>
120where
121    S: PlanningSolution,
122    V: Clone + Send + Sync + Debug + 'static,
123    B: ScoreBounder<S, D>,
124    D: Director<S>,
125{
126    fn expand(
127        &self,
128        parent_index: usize,
129        parent: &ExhaustiveSearchNode<S>,
130        score_director: &mut D,
131    ) -> Vec<ExhaustiveSearchNode<S>> {
132        let entity_index = parent.depth();
133        let new_depth = parent.depth() + 1;
134
135        // Check if we've assigned all entities
136        let total = self.total_entities(score_director);
137        if entity_index >= total {
138            return Vec::new();
139        }
140
141        let mut children = Vec::with_capacity(self.values.len());
142
143        for (value_index, value) in self.values.iter().enumerate() {
144            // Apply assignment using concrete setter
145            score_director.before_variable_changed(self.descriptor_index, entity_index);
146
147            (self.setter)(
148                score_director.working_solution_mut(),
149                entity_index,
150                Some(value.clone()),
151            );
152
153            score_director.after_variable_changed(self.descriptor_index, entity_index);
154
155            // Calculate score for this assignment
156            let score = score_director.calculate_score();
157
158            // Create child node
159            let mut child = ExhaustiveSearchNode::child(
160                parent_index,
161                new_depth,
162                score,
163                self.descriptor_index,
164                self.variable_index,
165                entity_index,
166                value_index,
167            );
168
169            // Calculate optimistic bound if bounder is available
170            if let Some(ref bounder) = self.bounder {
171                if let Some(bound) = bounder.calculate_optimistic_bound(score_director) {
172                    child.set_optimistic_bound(bound);
173                }
174            }
175
176            children.push(child);
177
178            // Undo the assignment for the next iteration
179            score_director.before_variable_changed(self.descriptor_index, entity_index);
180
181            (self.setter)(score_director.working_solution_mut(), entity_index, None);
182
183            score_director.after_variable_changed(self.descriptor_index, entity_index);
184        }
185
186        children
187    }
188
189    fn reset_assignments(&self, score_director: &mut D) {
190        for entity_index in 0..self.total_entities(score_director) {
191            score_director.before_variable_changed(self.descriptor_index, entity_index);
192            (self.setter)(score_director.working_solution_mut(), entity_index, None);
193            score_director.after_variable_changed(self.descriptor_index, entity_index);
194        }
195    }
196
197    fn apply_assignment(&self, node: &ExhaustiveSearchNode<S>, score_director: &mut D) {
198        let Some(descriptor_index) = node.descriptor_index() else {
199            return;
200        };
201        let Some(variable_index) = node.variable_index() else {
202            return;
203        };
204        let Some(entity_index) = node.entity_index() else {
205            return;
206        };
207        let Some(candidate_value_index) = node.candidate_value_index() else {
208            return;
209        };
210
211        assert_eq!(descriptor_index, self.descriptor_index);
212        assert_eq!(variable_index, self.variable_index);
213
214        let value = self
215            .values
216            .get(candidate_value_index)
217            .unwrap_or_else(|| {
218                panic!("candidate value index {candidate_value_index} is out of range")
219            })
220            .clone();
221
222        score_director.before_variable_changed(self.descriptor_index, entity_index);
223        (self.setter)(
224            score_director.working_solution_mut(),
225            entity_index,
226            Some(value),
227        );
228        score_director.after_variable_changed(self.descriptor_index, entity_index);
229    }
230
231    fn total_entities(&self, score_director: &D) -> usize {
232        score_director
233            .entity_count(self.descriptor_index)
234            .unwrap_or(0)
235    }
236}
237
238// Implement ScoreBounder for () to allow SimpleDecider<S, V> (no bounder)
239impl<S: PlanningSolution, D: Director<S>> ScoreBounder<S, D> for () {
240    fn calculate_optimistic_bound(&self, _score_director: &D) -> Option<S::Score> {
241        None
242    }
243}
244
245#[cfg(test)]
246#[path = "decider_tests.rs"]
247mod tests;
solverforge_solver/phase/exhaustive/decider.rs

solverforge_solver/phase/exhaustive/
decider.rs
