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 total_entities(&self, score_director: &D) -> usize;
34}
35
36/// A simple value-based decider that works with any value type.
37///
38/// Uses typed setter for zero-erasure variable assignment.
39///
40/// # Type Parameters
41/// * `S` - The planning solution type
42/// * `V` - The value type to assign
43/// * `B` - The bounder type (use `Option<B>` for optional bounding)
44pub struct SimpleDecider<S: PlanningSolution, V: Clone + Send + Sync + 'static, B = ()> {
45    // Descriptor index of the entity collection.
46    descriptor_index: usize,
47    // Variable name to assign.
48    variable_name: String,
49    // Possible values to try.
50    values: Vec<V>,
51    // Score bounder for optimistic bounds (None = no bounding).
52    bounder: Option<B>,
53    // Typed setter for zero-erasure variable assignment.
54    setter: fn(&mut S, usize, Option<V>),
55}
56
57impl<S: PlanningSolution, V: Clone + Send + Sync + 'static> SimpleDecider<S, V, ()> {
58    /// Creates a new simple decider with typed setter and no bounder.
59    ///
60    /// # Arguments
61    /// * `descriptor_index` - Index of the entity descriptor
62    /// * `variable_name` - Name of the variable being assigned
63    /// * `values` - Possible values to try
64    /// * `setter` - Typed setter function `fn(&mut S, entity_index, value)`
65    pub fn new(
66        descriptor_index: usize,
67        variable_name: impl Into<String>,
68        values: Vec<V>,
69        setter: fn(&mut S, usize, Option<V>),
70    ) -> Self {
71        Self {
72            descriptor_index,
73            variable_name: variable_name.into(),
74            values,
75            bounder: None,
76            setter,
77        }
78    }
79}
80
81impl<S: PlanningSolution, V: Clone + Send + Sync + 'static, B> SimpleDecider<S, V, B> {
82    pub fn with_bounder<B2>(self, bounder: B2) -> SimpleDecider<S, V, B2> {
83        SimpleDecider {
84            descriptor_index: self.descriptor_index,
85            variable_name: self.variable_name,
86            values: self.values,
87            bounder: Some(bounder),
88            setter: self.setter,
89        }
90    }
91}
92
93impl<S: PlanningSolution, V: Clone + Send + Sync + Debug + 'static, B: Debug> Debug
94    for SimpleDecider<S, V, B>
95{
96    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
97        f.debug_struct("SimpleDecider")
98            .field("descriptor_index", &self.descriptor_index)
99            .field("variable_name", &self.variable_name)
100            .field("value_count", &self.values.len())
101            .finish()
102    }
103}
104
105impl<S, V, B, D> ExhaustiveSearchDecider<S, D> for SimpleDecider<S, V, B>
106where
107    S: PlanningSolution,
108    V: Clone + Send + Sync + Debug + 'static,
109    B: ScoreBounder<S, D>,
110    D: Director<S>,
111{
112    fn expand(
113        &self,
114        parent_index: usize,
115        parent: &ExhaustiveSearchNode<S>,
116        score_director: &mut D,
117    ) -> Vec<ExhaustiveSearchNode<S>> {
118        let entity_index = parent.depth();
119        let new_depth = parent.depth() + 1;
120
121        // Check if we've assigned all entities
122        let total = self.total_entities(score_director);
123        if entity_index >= total {
124            return Vec::new();
125        }
126
127        let mut children = Vec::with_capacity(self.values.len());
128
129        for (value_index, value) in self.values.iter().enumerate() {
130            // Apply assignment using typed setter
131            score_director.before_variable_changed(self.descriptor_index, entity_index);
132
133            (self.setter)(
134                score_director.working_solution_mut(),
135                entity_index,
136                Some(value.clone()),
137            );
138
139            score_director.after_variable_changed(self.descriptor_index, entity_index);
140
141            // Calculate score for this assignment
142            let score = score_director.calculate_score();
143
144            // Create child node
145            let mut child = ExhaustiveSearchNode::child(
146                parent_index,
147                new_depth,
148                score,
149                entity_index,
150                value_index,
151            );
152
153            // Calculate optimistic bound if bounder is available
154            if let Some(ref bounder) = self.bounder {
155                if let Some(bound) = bounder.calculate_optimistic_bound(score_director) {
156                    child.set_optimistic_bound(bound);
157                }
158            }
159
160            children.push(child);
161
162            // Undo the assignment for the next iteration
163            score_director.before_variable_changed(self.descriptor_index, entity_index);
164
165            (self.setter)(score_director.working_solution_mut(), entity_index, None);
166
167            score_director.after_variable_changed(self.descriptor_index, entity_index);
168        }
169
170        children
171    }
172
173    fn total_entities(&self, score_director: &D) -> usize {
174        score_director
175            .entity_count(self.descriptor_index)
176            .unwrap_or(0)
177    }
178}
179
180// Implement ScoreBounder for () to allow SimpleDecider<S, V> (no bounder)
181impl<S: PlanningSolution, D: Director<S>> ScoreBounder<S, D> for () {
182    fn calculate_optimistic_bound(&self, _score_director: &D) -> Option<S::Score> {
183        None
184    }
185}
186
187#[cfg(test)]
188mod tests {
189    use super::*;
190    use solverforge_core::score::SoftScore;
191
192    #[derive(Clone, Debug)]
193    struct TestSolution {
194        score: Option<SoftScore>,
195    }
196
197    impl PlanningSolution for TestSolution {
198        type Score = SoftScore;
199
200        fn score(&self) -> Option<Self::Score> {
201            self.score
202        }
203
204        fn set_score(&mut self, score: Option<Self::Score>) {
205            self.score = score;
206        }
207    }
208
209    // Dummy setter for tests
210    fn set_row(_s: &mut TestSolution, _idx: usize, _v: Option<i32>) {
211        // No-op for this minimal test
212    }
213
214    #[test]
215    fn test_simple_decider_creation() {
216        let decider: SimpleDecider<TestSolution, i32> =
217            SimpleDecider::new(0, "row", vec![0, 1, 2, 3], set_row);
218
219        let debug = format!("{:?}", decider);
220        assert!(debug.contains("SimpleDecider"));
221        assert!(debug.contains("value_count: 4"));
222    }
223}
solverforge_solver/phase/exhaustive/decider.rs

solverforge_solver/phase/exhaustive/
decider.rs
