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, ValueSelector};
15
16use super::ConstructionSlotId;
17
18/// A placement represents an entity that needs a value assigned,
19/// along with the candidate moves to assign values.
20///
21/// # Type Parameters
22/// * `S` - The planning solution type
23/// * `M` - The move type
24pub struct Placement<S, M>
25where
26    S: PlanningSolution,
27    M: Move<S>,
28{
29    // The entity reference.
30    pub entity_ref: EntityReference,
31    // Candidate moves for this placement.
32    pub moves: Vec<M>,
33    // Whether keeping the current value is a legal construction choice.
34    keep_current_legal: bool,
35    slot_id: Option<ConstructionSlotId>,
36    _phantom: PhantomData<fn() -> S>,
37}
38
39impl<S, M> Placement<S, M>
40where
41    S: PlanningSolution,
42    M: Move<S>,
43{
44    pub fn new(entity_ref: EntityReference, moves: Vec<M>) -> Self {
45        Self {
46            entity_ref,
47            moves,
48            keep_current_legal: false,
49            slot_id: None,
50            _phantom: PhantomData,
51        }
52    }
53
54    pub fn is_empty(&self) -> bool {
55        self.moves.is_empty()
56    }
57
58    pub fn with_keep_current_legal(mut self, legal: bool) -> Self {
59        self.keep_current_legal = legal;
60        self
61    }
62
63    pub fn keep_current_legal(&self) -> bool {
64        self.keep_current_legal
65    }
66
67    pub(crate) fn with_slot_id(mut self, slot_id: ConstructionSlotId) -> Self {
68        self.slot_id = Some(slot_id);
69        self
70    }
71
72    pub(crate) fn slot_id(&self) -> Option<ConstructionSlotId> {
73        self.slot_id
74    }
75
76    /// Takes ownership of a move at the given index.
77    ///
78    /// Uses swap_remove for O(1) removal.
79    pub fn take_move(&mut self, index: usize) -> M {
80        self.moves.swap_remove(index)
81    }
82}
83
84impl<S, M> Debug for Placement<S, M>
85where
86    S: PlanningSolution,
87    M: Move<S>,
88{
89    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
90        f.debug_struct("Placement")
91            .field("entity_ref", &self.entity_ref)
92            .field("move_count", &self.moves.len())
93            .field("keep_current_legal", &self.keep_current_legal)
94            .field("slot_id", &self.slot_id)
95            .finish()
96    }
97}
98
99/// Trait for placing entities during construction.
100///
101/// Entity placers iterate over uninitialized entities and generate
102/// candidate moves for each.
103///
104/// # Type Parameters
105/// * `S` - The planning solution type
106/// * `M` - The move type
107pub trait EntityPlacer<S, M>: Send + Debug
108where
109    S: PlanningSolution,
110    M: Move<S>,
111{
112    // Returns all placements (entities + their candidate moves).
113    fn get_placements<D: Director<S>>(&self, score_director: &D) -> Vec<Placement<S, M>>;
114
115    // Returns the next live placement and the number of candidate moves generated
116    // while finding it. The default preserves the eager construction behavior.
117    fn get_next_placement<D, IsCompleted>(
118        &self,
119        score_director: &D,
120        mut is_completed: IsCompleted,
121    ) -> Option<(Placement<S, M>, u64)>
122    where
123        D: Director<S>,
124        IsCompleted: FnMut(usize, usize) -> bool,
125    {
126        let mut selected = None;
127        let mut generated_moves = 0u64;
128
129        for placement in self.get_placements(score_director) {
130            if let Some(slot_id) = placement.slot_id() {
131                if is_completed(slot_id.binding_index(), slot_id.entity_index()) {
132                    continue;
133                }
134            }
135            generated_moves = generated_moves
136                .saturating_add(u64::try_from(placement.moves.len()).unwrap_or(u64::MAX));
137            if selected.is_none() {
138                selected = Some(placement);
139            }
140        }
141
142        selected.map(|placement| (placement, generated_moves))
143    }
144}
145
146/// A queued entity placer that processes entities in order.
147///
148/// For each uninitialized entity, generates change moves for all possible values.
149/// Uses typed function pointers for zero-erasure access.
150///
151/// # Type Parameters
152/// * `S` - The planning solution type
153/// * `V` - The value type
154/// * `ES` - The entity selector type
155/// * `VS` - The value selector type
156pub struct QueuedEntityPlacer<S, V, ES, VS>
157where
158    S: PlanningSolution,
159    ES: EntitySelector<S>,
160    VS: ValueSelector<S, V>,
161{
162    // The entity selector.
163    entity_selector: ES,
164    // The value selector.
165    value_selector: VS,
166    // Typed getter function pointer.
167    getter: fn(&S, usize, usize) -> Option<V>,
168    // Typed setter function pointer.
169    setter: fn(&mut S, usize, usize, Option<V>),
170    variable_index: usize,
171    // The variable name.
172    variable_name: &'static str,
173    // The descriptor index.
174    descriptor_index: usize,
175    // Whether the variable can remain unassigned during construction.
176    allows_unassigned: bool,
177    _phantom: PhantomData<fn() -> V>,
178}
179
180impl<S, V, ES, VS> QueuedEntityPlacer<S, V, ES, VS>
181where
182    S: PlanningSolution,
183    ES: EntitySelector<S>,
184    VS: ValueSelector<S, V>,
185{
186    pub fn new(
187        entity_selector: ES,
188        value_selector: VS,
189        getter: fn(&S, usize, usize) -> Option<V>,
190        setter: fn(&mut S, usize, usize, Option<V>),
191        descriptor_index: usize,
192        variable_index: usize,
193        variable_name: &'static str,
194    ) -> Self {
195        Self {
196            entity_selector,
197            value_selector,
198            getter,
199            setter,
200            variable_index,
201            variable_name,
202            descriptor_index,
203            allows_unassigned: false,
204            _phantom: PhantomData,
205        }
206    }
207
208    pub fn with_allows_unassigned(mut self, allows_unassigned: bool) -> Self {
209        self.allows_unassigned = allows_unassigned;
210        self
211    }
212}
213
214impl<S, V, ES, VS> Debug for QueuedEntityPlacer<S, V, ES, VS>
215where
216    S: PlanningSolution,
217    ES: EntitySelector<S> + Debug,
218    VS: ValueSelector<S, V> + Debug,
219{
220    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
221        f.debug_struct("QueuedEntityPlacer")
222            .field("entity_selector", &self.entity_selector)
223            .field("value_selector", &self.value_selector)
224            .field("variable_name", &self.variable_name)
225            .field("allows_unassigned", &self.allows_unassigned)
226            .finish()
227    }
228}
229
230impl<S, V, ES, VS> EntityPlacer<S, ChangeMove<S, V>> for QueuedEntityPlacer<S, V, ES, VS>
231where
232    S: PlanningSolution,
233    V: Clone + PartialEq + Send + Sync + Debug + 'static,
234    ES: EntitySelector<S>,
235    VS: ValueSelector<S, V>,
236{
237    fn get_placements<D: Director<S>>(
238        &self,
239        score_director: &D,
240    ) -> Vec<Placement<S, ChangeMove<S, V>>> {
241        let variable_name = self.variable_name;
242        let descriptor_index = self.descriptor_index;
243        let getter = self.getter;
244        let setter = self.setter;
245        let variable_index = self.variable_index;
246        let allows_unassigned = self.allows_unassigned;
247
248        self.entity_selector
249            .iter(score_director)
250            .filter_map(|entity_ref| {
251                // Check if entity is uninitialized using typed getter - zero erasure
252                let current_value = getter(
253                    score_director.working_solution(),
254                    entity_ref.entity_index,
255                    variable_index,
256                );
257
258                // Only include uninitialized entities
259                if current_value.is_some() {
260                    return None;
261                }
262
263                // Generate moves for all possible values
264                let moves: Vec<ChangeMove<S, V>> = self
265                    .value_selector
266                    .iter(
267                        score_director,
268                        entity_ref.descriptor_index,
269                        entity_ref.entity_index,
270                    )
271                    .map(|value| {
272                        ChangeMove::new(
273                            entity_ref.entity_index,
274                            Some(value),
275                            getter,
276                            setter,
277                            variable_index,
278                            variable_name,
279                            descriptor_index,
280                        )
281                    })
282                    .collect();
283
284                if moves.is_empty() {
285                    None
286                } else {
287                    Some(
288                        Placement::new(entity_ref, moves)
289                            .with_keep_current_legal(allows_unassigned),
290                    )
291                }
292            })
293            .collect()
294    }
295}
296
297/// Entity placer that sorts placements by a comparator function.
298///
299/// Wraps an inner placer and sorts its placements using a typed comparator.
300/// This enables FIRST_FIT_DECREASING and similar construction variants.
301///
302/// # Example
303///
304/// ```
305/// use solverforge_solver::phase::construction::{SortedEntityPlacer, QueuedEntityPlacer, EntityPlacer};
306/// use solverforge_solver::heuristic::r#move::ChangeMove;
307/// use solverforge_solver::heuristic::selector::{FromSolutionEntitySelector, StaticValueSelector};
308/// use solverforge_core::domain::PlanningSolution;
309/// use solverforge_core::score::SoftScore;
310/// use solverforge_scoring::ScoreDirector;
311/// use std::cmp::Ordering;
312///
313/// #[derive(Clone, Debug)]
314/// struct Task { difficulty: i32, assigned: Option<i32> }
315///
316/// #[derive(Clone, Debug)]
317/// struct Solution { tasks: Vec<Task>, score: Option<SoftScore> }
318///
319/// impl PlanningSolution for Solution {
320///     type Score = SoftScore;
321///     fn score(&self) -> Option<Self::Score> { self.score }
322///     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
323/// }
324///
325/// fn get_assigned(s: &Solution, i: usize) -> Option<i32> {
326///     s.tasks.get(i).and_then(|t| t.assigned)
327/// }
328/// fn set_assigned(s: &mut Solution, i: usize, v: Option<i32>) {
329///     if let Some(t) = s.tasks.get_mut(i) { t.assigned = v; }
330/// }
331///
332/// // Sort entities by difficulty (descending) for FIRST_FIT_DECREASING
333/// fn difficulty_descending(s: &Solution, a: usize, b: usize) -> Ordering {
334///     let da = s.tasks.get(a).map(|t| t.difficulty).unwrap_or(0);
335///     let db = s.tasks.get(b).map(|t| t.difficulty).unwrap_or(0);
336///     db.cmp(&da)  // Descending order
337/// }
338/// ```
339pub struct SortedEntityPlacer<S, M, Inner>
340where
341    S: PlanningSolution,
342    M: Move<S>,
343    Inner: EntityPlacer<S, M>,
344{
345    inner: Inner,
346    // Comparator function: takes (solution, entity_index_a, entity_index_b) -> Ordering
347    comparator: fn(&S, usize, usize) -> std::cmp::Ordering,
348    _phantom: PhantomData<fn() -> (S, M)>,
349}
350
351impl<S, M, Inner> SortedEntityPlacer<S, M, Inner>
352where
353    S: PlanningSolution,
354    M: Move<S>,
355    Inner: EntityPlacer<S, M>,
356{
357    /// Creates a new sorted entity placer.
358    ///
359    /// # Arguments
360    /// * `inner` - The inner placer to wrap
361    /// * `comparator` - Function to compare entities: `(solution, idx_a, idx_b) -> Ordering`
362    pub fn new(inner: Inner, comparator: fn(&S, usize, usize) -> std::cmp::Ordering) -> Self {
363        Self {
364            inner,
365            comparator,
366            _phantom: PhantomData,
367        }
368    }
369}
370
371impl<S, M, Inner> Debug for SortedEntityPlacer<S, M, Inner>
372where
373    S: PlanningSolution,
374    M: Move<S>,
375    Inner: EntityPlacer<S, M>,
376{
377    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
378        f.debug_struct("SortedEntityPlacer")
379            .field("inner", &self.inner)
380            .finish()
381    }
382}
383
384impl<S, M, Inner> EntityPlacer<S, M> for SortedEntityPlacer<S, M, Inner>
385where
386    S: PlanningSolution,
387    M: Move<S>,
388    Inner: EntityPlacer<S, M>,
389{
390    fn get_placements<D: Director<S>>(&self, score_director: &D) -> Vec<Placement<S, M>> {
391        let mut placements = self.inner.get_placements(score_director);
392        let solution = score_director.working_solution();
393        let cmp = self.comparator;
394
395        placements.sort_by(|a, b| {
396            cmp(
397                solution,
398                a.entity_ref.entity_index,
399                b.entity_ref.entity_index,
400            )
401        });
402
403        placements
404    }
405}
406
407#[cfg(test)]
408mod tests;
solverforge_solver/phase/construction/placer.rs

solverforge_solver/phase/construction/
placer.rs
