solverforge_solver/phase/construction/
placer.rs

1/* Entity placers for construction heuristic
2
3Placers enumerate the entities that need values assigned and
4generate candidate moves for each entity.
5*/
6
7use std::fmt::Debug;
8use std::marker::PhantomData;
9
10use solverforge_core::domain::PlanningSolution;
11use solverforge_scoring::Director;
12
13use crate::heuristic::r#move::{ChangeMove, Move};
14use crate::heuristic::selector::{EntityReference, EntitySelector, TypedValueSelector};
15
16/// A placement represents an entity that needs a value assigned,
17/// along with the candidate moves to assign values.
18///
19/// # Type Parameters
20/// * `S` - The planning solution type
21/// * `M` - The move type
22pub struct Placement<S, M>
23where
24    S: PlanningSolution,
25    M: Move<S>,
26{
27    // The entity reference.
28    pub entity_ref: EntityReference,
29    // Candidate moves for this placement.
30    pub moves: Vec<M>,
31    _phantom: PhantomData<fn() -> S>,
32}
33
34impl<S, M> Placement<S, M>
35where
36    S: PlanningSolution,
37    M: Move<S>,
38{
39    pub fn new(entity_ref: EntityReference, moves: Vec<M>) -> Self {
40        Self {
41            entity_ref,
42            moves,
43            _phantom: PhantomData,
44        }
45    }
46
47    pub fn is_empty(&self) -> bool {
48        self.moves.is_empty()
49    }
50
51    /// Takes ownership of a move at the given index.
52    ///
53    /// Uses swap_remove for O(1) removal.
54    pub fn take_move(&mut self, index: usize) -> M {
55        self.moves.swap_remove(index)
56    }
57}
58
59impl<S, M> Debug for Placement<S, M>
60where
61    S: PlanningSolution,
62    M: Move<S>,
63{
64    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
65        f.debug_struct("Placement")
66            .field("entity_ref", &self.entity_ref)
67            .field("move_count", &self.moves.len())
68            .finish()
69    }
70}
71
72/// Trait for placing entities during construction.
73///
74/// Entity placers iterate over uninitialized entities and generate
75/// candidate moves for each.
76///
77/// # Type Parameters
78/// * `S` - The planning solution type
79/// * `M` - The move type
80pub trait EntityPlacer<S, M>: Send + Debug
81where
82    S: PlanningSolution,
83    M: Move<S>,
84{
85    // Returns all placements (entities + their candidate moves).
86    fn get_placements<D: Director<S>>(&self, score_director: &D) -> Vec<Placement<S, M>>;
87}
88
89/// A queued entity placer that processes entities in order.
90///
91/// For each uninitialized entity, generates change moves for all possible values.
92/// Uses typed function pointers for zero-erasure access.
93///
94/// # Type Parameters
95/// * `S` - The planning solution type
96/// * `V` - The value type
97/// * `ES` - The entity selector type
98/// * `VS` - The value selector type
99pub struct QueuedEntityPlacer<S, V, ES, VS>
100where
101    S: PlanningSolution,
102    ES: EntitySelector<S>,
103    VS: TypedValueSelector<S, V>,
104{
105    // The entity selector.
106    entity_selector: ES,
107    // The value selector.
108    value_selector: VS,
109    // Typed getter function pointer.
110    getter: fn(&S, usize) -> Option<V>,
111    // Typed setter function pointer.
112    setter: fn(&mut S, usize, Option<V>),
113    // The variable name.
114    variable_name: &'static str,
115    // The descriptor index.
116    descriptor_index: usize,
117    _phantom: PhantomData<fn() -> V>,
118}
119
120impl<S, V, ES, VS> QueuedEntityPlacer<S, V, ES, VS>
121where
122    S: PlanningSolution,
123    ES: EntitySelector<S>,
124    VS: TypedValueSelector<S, V>,
125{
126    pub fn new(
127        entity_selector: ES,
128        value_selector: VS,
129        getter: fn(&S, usize) -> Option<V>,
130        setter: fn(&mut S, usize, Option<V>),
131        descriptor_index: usize,
132        variable_name: &'static str,
133    ) -> Self {
134        Self {
135            entity_selector,
136            value_selector,
137            getter,
138            setter,
139            variable_name,
140            descriptor_index,
141            _phantom: PhantomData,
142        }
143    }
144}
145
146impl<S, V, ES, VS> Debug for QueuedEntityPlacer<S, V, ES, VS>
147where
148    S: PlanningSolution,
149    ES: EntitySelector<S> + Debug,
150    VS: TypedValueSelector<S, V> + Debug,
151{
152    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
153        f.debug_struct("QueuedEntityPlacer")
154            .field("entity_selector", &self.entity_selector)
155            .field("value_selector", &self.value_selector)
156            .field("variable_name", &self.variable_name)
157            .finish()
158    }
159}
160
161impl<S, V, ES, VS> EntityPlacer<S, ChangeMove<S, V>> for QueuedEntityPlacer<S, V, ES, VS>
162where
163    S: PlanningSolution,
164    V: Clone + PartialEq + Send + Sync + Debug + 'static,
165    ES: EntitySelector<S>,
166    VS: TypedValueSelector<S, V>,
167{
168    fn get_placements<D: Director<S>>(
169        &self,
170        score_director: &D,
171    ) -> Vec<Placement<S, ChangeMove<S, V>>> {
172        let variable_name = self.variable_name;
173        let descriptor_index = self.descriptor_index;
174        let getter = self.getter;
175        let setter = self.setter;
176
177        self.entity_selector
178            .iter(score_director)
179            .filter_map(|entity_ref| {
180                // Check if entity is uninitialized using typed getter - zero erasure
181                let current_value =
182                    getter(score_director.working_solution(), entity_ref.entity_index);
183
184                // Only include uninitialized entities
185                if current_value.is_some() {
186                    return None;
187                }
188
189                // Generate moves for all possible values
190                let moves: Vec<ChangeMove<S, V>> = self
191                    .value_selector
192                    .iter_typed(
193                        score_director,
194                        entity_ref.descriptor_index,
195                        entity_ref.entity_index,
196                    )
197                    .map(|value| {
198                        ChangeMove::new(
199                            entity_ref.entity_index,
200                            Some(value),
201                            getter,
202                            setter,
203                            variable_name,
204                            descriptor_index,
205                        )
206                    })
207                    .collect();
208
209                if moves.is_empty() {
210                    None
211                } else {
212                    Some(Placement::new(entity_ref, moves))
213                }
214            })
215            .collect()
216    }
217}
218
219/// Entity placer that sorts placements by a comparator function.
220///
221/// Wraps an inner placer and sorts its placements using a typed comparator.
222/// This enables FIRST_FIT_DECREASING and similar construction variants.
223///
224/// # Example
225///
226/// ```
227/// use solverforge_solver::phase::construction::{SortedEntityPlacer, QueuedEntityPlacer, EntityPlacer};
228/// use solverforge_solver::heuristic::r#move::ChangeMove;
229/// use solverforge_solver::heuristic::selector::{FromSolutionEntitySelector, StaticTypedValueSelector};
230/// use solverforge_core::domain::PlanningSolution;
231/// use solverforge_core::score::SoftScore;
232/// use solverforge_scoring::ScoreDirector;
233/// use std::cmp::Ordering;
234///
235/// #[derive(Clone, Debug)]
236/// struct Task { difficulty: i32, assigned: Option<i32> }
237///
238/// #[derive(Clone, Debug)]
239/// struct Solution { tasks: Vec<Task>, score: Option<SoftScore> }
240///
241/// impl PlanningSolution for Solution {
242///     type Score = SoftScore;
243///     fn score(&self) -> Option<Self::Score> { self.score }
244///     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
245/// }
246///
247/// fn get_assigned(s: &Solution, i: usize) -> Option<i32> {
248///     s.tasks.get(i).and_then(|t| t.assigned)
249/// }
250/// fn set_assigned(s: &mut Solution, i: usize, v: Option<i32>) {
251///     if let Some(t) = s.tasks.get_mut(i) { t.assigned = v; }
252/// }
253///
254/// // Sort entities by difficulty (descending) for FIRST_FIT_DECREASING
255/// fn difficulty_descending(s: &Solution, a: usize, b: usize) -> Ordering {
256///     let da = s.tasks.get(a).map(|t| t.difficulty).unwrap_or(0);
257///     let db = s.tasks.get(b).map(|t| t.difficulty).unwrap_or(0);
258///     db.cmp(&da)  // Descending order
259/// }
260/// ```
261pub struct SortedEntityPlacer<S, M, Inner>
262where
263    S: PlanningSolution,
264    M: Move<S>,
265    Inner: EntityPlacer<S, M>,
266{
267    inner: Inner,
268    // Comparator function: takes (solution, entity_index_a, entity_index_b) -> Ordering
269    comparator: fn(&S, usize, usize) -> std::cmp::Ordering,
270    _phantom: PhantomData<fn() -> (S, M)>,
271}
272
273impl<S, M, Inner> SortedEntityPlacer<S, M, Inner>
274where
275    S: PlanningSolution,
276    M: Move<S>,
277    Inner: EntityPlacer<S, M>,
278{
279    /// Creates a new sorted entity placer.
280    ///
281    /// # Arguments
282    /// * `inner` - The inner placer to wrap
283    /// * `comparator` - Function to compare entities: `(solution, idx_a, idx_b) -> Ordering`
284    pub fn new(inner: Inner, comparator: fn(&S, usize, usize) -> std::cmp::Ordering) -> Self {
285        Self {
286            inner,
287            comparator,
288            _phantom: PhantomData,
289        }
290    }
291}
292
293impl<S, M, Inner> Debug for SortedEntityPlacer<S, M, Inner>
294where
295    S: PlanningSolution,
296    M: Move<S>,
297    Inner: EntityPlacer<S, M>,
298{
299    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
300        f.debug_struct("SortedEntityPlacer")
301            .field("inner", &self.inner)
302            .finish()
303    }
304}
305
306impl<S, M, Inner> EntityPlacer<S, M> for SortedEntityPlacer<S, M, Inner>
307where
308    S: PlanningSolution,
309    M: Move<S>,
310    Inner: EntityPlacer<S, M>,
311{
312    fn get_placements<D: Director<S>>(&self, score_director: &D) -> Vec<Placement<S, M>> {
313        let mut placements = self.inner.get_placements(score_director);
314        let solution = score_director.working_solution();
315        let cmp = self.comparator;
316
317        placements.sort_by(|a, b| {
318            cmp(
319                solution,
320                a.entity_ref.entity_index,
321                b.entity_ref.entity_index,
322            )
323        });
324
325        placements
326    }
327}
328
329#[cfg(test)]
330#[path = "placer_tests.rs"]
331mod tests;
solverforge_solver/phase/construction/placer.rs

solverforge_solver/phase/construction/
placer.rs
