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

solverforge_solver/phase/construction/
placer.rs
