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::move_selector::{CandidateId, MoveCandidateRef, MoveCursor};
15use crate::heuristic::selector::{EntityReference, EntitySelector, ValueSelector};
16use crate::stats::CandidateTracePullToken;
17
18use super::{ConstructionGroupSlotId, ConstructionSlotId};
19
20#[derive(Clone, Debug, Default)]
21pub(crate) struct ConstructionTarget {
22    scalar_slots: Vec<ConstructionSlotId>,
23    group_slot: Option<ConstructionGroupSlotId>,
24}
25
26impl ConstructionTarget {
27    pub(crate) fn new() -> Self {
28        Self::default()
29    }
30
31    pub(crate) fn with_scalar_slots(mut self, mut scalar_slots: Vec<ConstructionSlotId>) -> Self {
32        scalar_slots.sort_unstable();
33        scalar_slots.dedup();
34        self.scalar_slots = scalar_slots;
35        self
36    }
37
38    pub(crate) fn with_group_slot(mut self, group_slot: ConstructionGroupSlotId) -> Self {
39        self.group_slot = Some(group_slot);
40        self
41    }
42
43    pub(crate) fn scalar_slots(&self) -> &[ConstructionSlotId] {
44        &self.scalar_slots
45    }
46
47    pub(crate) fn group_slot(&self) -> Option<&ConstructionGroupSlotId> {
48        self.group_slot.as_ref()
49    }
50
51    pub(crate) fn is_empty(&self) -> bool {
52        self.scalar_slots.is_empty() && self.group_slot.is_none()
53    }
54}
55
56/// A placement represents an entity that needs a value assigned,
57/// along with the candidate moves to assign values.
58///
59/// # Type Parameters
60/// * `S` - The planning solution type
61/// * `M` - The move type
62pub struct Placement<S, M, C = crate::heuristic::selector::move_selector::ArenaMoveCursor<S, M>>
63where
64    S: PlanningSolution,
65    M: Move<S>,
66    C: MoveCursor<S, M>,
67{
68    // The entity reference.
69    pub entity_ref: EntityReference,
70    candidates: C,
71    // Whether keeping the current value is a legal construction choice.
72    keep_current_legal: bool,
73    target: ConstructionTarget,
74    candidate_target: fn(&C, CandidateId) -> Option<&ConstructionTarget>,
75    // Captured-only mapping from a cursor candidate to its bounded diagnostic
76    // pull token. It stays empty trace-off and after trace saturation.
77    candidate_trace_tokens: Vec<(CandidateId, CandidateTracePullToken)>,
78    candidate_scores: Vec<(CandidateId, S::Score)>,
79    _phantom: PhantomData<fn() -> (S, M)>,
80}
81
82impl<S, M, C> Placement<S, M, C>
83where
84    S: PlanningSolution,
85    M: Move<S>,
86    C: MoveCursor<S, M>,
87{
88    pub fn new(entity_ref: EntityReference, candidates: C) -> Self {
89        Self {
90            entity_ref,
91            candidates,
92            keep_current_legal: false,
93            target: ConstructionTarget::new(),
94            candidate_target: |_, _| None,
95            candidate_trace_tokens: Vec::new(),
96            candidate_scores: Vec::new(),
97            _phantom: PhantomData,
98        }
99    }
100
101    pub fn with_keep_current_legal(mut self, legal: bool) -> Self {
102        self.keep_current_legal = legal;
103        self
104    }
105
106    pub fn keep_current_legal(&self) -> bool {
107        self.keep_current_legal
108    }
109
110    pub(crate) fn with_slot_id(mut self, slot_id: ConstructionSlotId) -> Self {
111        self.target = self.target.with_scalar_slots(vec![slot_id]);
112        self
113    }
114
115    pub(crate) fn with_scalar_slots(mut self, mut scalar_slots: Vec<ConstructionSlotId>) -> Self {
116        scalar_slots.sort_unstable();
117        scalar_slots.dedup();
118        self.target = self.target.with_scalar_slots(scalar_slots);
119        self
120    }
121
122    pub(crate) fn with_group_slot(mut self, group_slot: ConstructionGroupSlotId) -> Self {
123        self.target = self.target.with_group_slot(group_slot);
124        self
125    }
126
127    pub(crate) fn with_candidate_target(
128        mut self,
129        candidate_target: fn(&C, CandidateId) -> Option<&ConstructionTarget>,
130    ) -> Self {
131        self.candidate_target = candidate_target;
132        self
133    }
134
135    pub(crate) fn construction_target(&self) -> &ConstructionTarget {
136        &self.target
137    }
138
139    pub(crate) fn construction_target_for_move(
140        &self,
141        candidate_id: CandidateId,
142    ) -> &ConstructionTarget {
143        (self.candidate_target)(&self.candidates, candidate_id).unwrap_or(&self.target)
144    }
145
146    pub fn candidates(&self) -> &C {
147        &self.candidates
148    }
149
150    pub fn candidates_mut(&mut self) -> &mut C {
151        &mut self.candidates
152    }
153
154    pub fn take_move(&mut self, candidate_id: CandidateId) -> M {
155        self.candidates.take_candidate(candidate_id)
156    }
157
158    pub(crate) fn record_candidate_trace_token(
159        &mut self,
160        candidate_id: CandidateId,
161        token: CandidateTracePullToken,
162    ) {
163        self.candidate_trace_tokens.push((candidate_id, token));
164    }
165
166    pub(crate) fn candidate_trace_token(
167        &self,
168        candidate_id: CandidateId,
169    ) -> Option<CandidateTracePullToken> {
170        self.candidate_trace_tokens
171            .iter()
172            .find_map(|(recorded_id, token)| (*recorded_id == candidate_id).then_some(*token))
173    }
174
175    pub(crate) fn record_candidate_score(&mut self, candidate_id: CandidateId, score: S::Score) {
176        self.candidate_scores.push((candidate_id, score));
177    }
178
179    pub(crate) fn candidate_score(&self, candidate_id: CandidateId) -> Option<S::Score>
180    where
181        S::Score: Copy,
182    {
183        self.candidate_scores
184            .iter()
185            .find_map(|(recorded_id, score)| (*recorded_id == candidate_id).then_some(*score))
186    }
187}
188
189impl<S, M, C> Debug for Placement<S, M, C>
190where
191    S: PlanningSolution,
192    M: Move<S>,
193    C: MoveCursor<S, M>,
194{
195    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
196        f.debug_struct("Placement")
197            .field("entity_ref", &self.entity_ref)
198            .field("keep_current_legal", &self.keep_current_legal)
199            .field("target", &self.target)
200            .finish()
201    }
202}
203
204/// Trait for placing entities during construction.
205///
206/// Entity placers iterate over uninitialized entities and generate
207/// candidate moves for each.
208///
209/// # Type Parameters
210/// * `S` - The planning solution type
211/// * `M` - The move type
212pub trait EntityPlacerCursor<S, M>
213where
214    S: PlanningSolution,
215    M: Move<S>,
216{
217    type CandidateCursor: MoveCursor<S, M>;
218
219    fn next_placement<D, IsCompleted, ShouldStop>(
220        &mut self,
221        score_director: &D,
222        is_completed: IsCompleted,
223        should_stop: ShouldStop,
224    ) -> Option<Placement<S, M, Self::CandidateCursor>>
225    where
226        D: Director<S>,
227        IsCompleted: FnMut(&Placement<S, M, Self::CandidateCursor>) -> bool,
228        ShouldStop: FnMut() -> bool;
229}
230
231pub trait EntityPlacer<S, M>: Send + Debug
232where
233    S: PlanningSolution,
234    M: Move<S>,
235{
236    type Cursor<'a>: EntityPlacerCursor<S, M> + 'a
237    where
238        Self: 'a;
239
240    fn open_cursor<'a, D: Director<S>>(&'a self, score_director: &D) -> Self::Cursor<'a>;
241}
242
243include!("placer/queued.rs");
244/// Entity placer that sorts placements by a comparator function.
245///
246/// Wraps an inner placer and sorts its placements using a concrete comparator.
247/// This enables FIRST_FIT_DECREASING and similar construction variants.
248///
249/// # Example
250///
251/// ```
252/// use solverforge_solver::phase::construction::{SortedEntityPlacer, QueuedEntityPlacer, EntityPlacer};
253/// use solverforge_solver::heuristic::r#move::ChangeMove;
254/// use solverforge_solver::heuristic::selector::{FromSolutionEntitySelector, StaticValueSelector};
255/// use solverforge_core::domain::PlanningSolution;
256/// use solverforge_core::score::SoftScore;
257/// use solverforge_scoring::ScoreDirector;
258/// use std::cmp::Ordering;
259///
260/// #[derive(Clone, Debug)]
261/// struct Task { difficulty: i32, assigned: Option<i32> }
262///
263/// #[derive(Clone, Debug)]
264/// struct Solution { tasks: Vec<Task>, score: Option<SoftScore> }
265///
266/// impl PlanningSolution for Solution {
267///     type Score = SoftScore;
268///     fn score(&self) -> Option<Self::Score> { self.score }
269///     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
270/// }
271///
272/// fn get_assigned(s: &Solution, i: usize) -> Option<i32> {
273///     s.tasks.get(i).and_then(|t| t.assigned)
274/// }
275/// fn set_assigned(s: &mut Solution, i: usize, v: Option<i32>) {
276///     if let Some(t) = s.tasks.get_mut(i) { t.assigned = v; }
277/// }
278///
279/// // Sort entities by difficulty (descending) for FIRST_FIT_DECREASING
280/// fn difficulty_descending(s: &Solution, a: usize, b: usize) -> Ordering {
281///     let da = s.tasks.get(a).map(|t| t.difficulty).unwrap_or(0);
282///     let db = s.tasks.get(b).map(|t| t.difficulty).unwrap_or(0);
283///     db.cmp(&da)  // Descending order
284/// }
285/// ```
286pub struct SortedEntityPlacer<S, M, Inner>
287where
288    S: PlanningSolution,
289    M: Move<S>,
290    Inner: EntityPlacer<S, M>,
291{
292    inner: Inner,
293    // Comparator function: takes (solution, entity_index_a, entity_index_b) -> Ordering
294    comparator: fn(&S, usize, usize) -> std::cmp::Ordering,
295    _phantom: PhantomData<fn() -> (S, M)>,
296}
297
298impl<S, M, Inner> SortedEntityPlacer<S, M, Inner>
299where
300    S: PlanningSolution,
301    M: Move<S>,
302    Inner: EntityPlacer<S, M>,
303{
304    /// Creates a new sorted entity placer.
305    ///
306    /// # Arguments
307    /// * `inner` - The inner placer to wrap
308    /// * `comparator` - Function to compare entities: `(solution, idx_a, idx_b) -> Ordering`
309    pub fn new(inner: Inner, comparator: fn(&S, usize, usize) -> std::cmp::Ordering) -> Self {
310        Self {
311            inner,
312            comparator,
313            _phantom: PhantomData,
314        }
315    }
316}
317
318impl<S, M, Inner> Debug for SortedEntityPlacer<S, M, Inner>
319where
320    S: PlanningSolution,
321    M: Move<S>,
322    Inner: EntityPlacer<S, M>,
323{
324    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
325        f.debug_struct("SortedEntityPlacer")
326            .field("inner", &self.inner)
327            .finish()
328    }
329}
330
331type InnerPlacementCandidateCursor<'a, S, M, Inner> =
332    <<Inner as EntityPlacer<S, M>>::Cursor<'a> as EntityPlacerCursor<S, M>>::CandidateCursor;
333
334pub struct SortedEntityPlacerCursor<'a, S, M, Inner>
335where
336    S: PlanningSolution,
337    M: Move<S>,
338    Inner: EntityPlacer<S, M> + 'a,
339{
340    inner: Inner::Cursor<'a>,
341    comparator: fn(&S, usize, usize) -> std::cmp::Ordering,
342    placements:
343        Option<std::vec::IntoIter<Placement<S, M, InnerPlacementCandidateCursor<'a, S, M, Inner>>>>,
344}
345
346impl<'a, S, M, Inner> EntityPlacerCursor<S, M> for SortedEntityPlacerCursor<'a, S, M, Inner>
347where
348    S: PlanningSolution,
349    M: Move<S>,
350    Inner: EntityPlacer<S, M> + 'a,
351{
352    type CandidateCursor = InnerPlacementCandidateCursor<'a, S, M, Inner>;
353
354    fn next_placement<D, IsCompleted, ShouldStop>(
355        &mut self,
356        score_director: &D,
357        mut is_completed: IsCompleted,
358        mut should_stop: ShouldStop,
359    ) -> Option<Placement<S, M, Self::CandidateCursor>>
360    where
361        D: Director<S>,
362        IsCompleted: FnMut(&Placement<S, M, Self::CandidateCursor>) -> bool,
363        ShouldStop: FnMut() -> bool,
364    {
365        if self.placements.is_none() {
366            let mut placements = Vec::new();
367            while let Some(placement) =
368                self.inner
369                    .next_placement(score_director, |_| false, &mut should_stop)
370            {
371                placements.push(placement);
372            }
373            let solution = score_director.working_solution();
374            let comparator = self.comparator;
375            placements.sort_by(|left, right| {
376                comparator(
377                    solution,
378                    left.entity_ref.entity_index,
379                    right.entity_ref.entity_index,
380                )
381            });
382            self.placements = Some(placements.into_iter());
383        }
384
385        let placements = self
386            .placements
387            .as_mut()
388            .expect("sorted placement cursor must be initialized");
389        while !should_stop() {
390            let placement = placements.next()?;
391            if !is_completed(&placement) {
392                return Some(placement);
393            }
394        }
395        None
396    }
397}
398
399impl<S, M, Inner> EntityPlacer<S, M> for SortedEntityPlacer<S, M, Inner>
400where
401    S: PlanningSolution,
402    M: Move<S>,
403    Inner: EntityPlacer<S, M>,
404{
405    type Cursor<'a>
406        = SortedEntityPlacerCursor<'a, S, M, Inner>
407    where
408        Self: 'a;
409
410    fn open_cursor<'a, D: Director<S>>(&'a self, score_director: &D) -> Self::Cursor<'a> {
411        SortedEntityPlacerCursor {
412            inner: self.inner.open_cursor(score_director),
413            comparator: self.comparator,
414            placements: None,
415        }
416    }
417}
418
419#[cfg(test)]
420mod tests;
solverforge_solver/phase/construction/placer.rs

solverforge_solver/phase/construction/
placer.rs
