solverforge_solver/phase/construction/
placer.rs

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

solverforge_solver/phase/construction/
placer.rs
