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<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
53impl<S, M> Debug for Placement<S, M>
54where
55    S: PlanningSolution,
56    M: Move<S>,
57{
58    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
59        f.debug_struct("Placement")
60            .field("entity_ref", &self.entity_ref)
61            .field("move_count", &self.moves.len())
62            .finish()
63    }
64}
65
66/// Trait for placing entities during construction.
67///
68/// Entity placers iterate over uninitialized entities and generate
69/// candidate moves for each.
70///
71/// # Type Parameters
72/// * `S` - The planning solution type
73/// * `M` - The move type
74pub trait EntityPlacer<S, M>: Send + Debug
75where
76    S: PlanningSolution,
77    M: Move<S>,
78{
79    /// Returns all placements (entities + their candidate moves).
80    fn get_placements(&self, score_director: &dyn ScoreDirector<S>) -> Vec<Placement<S, M>>;
81}
82
83/// A queued entity placer that processes entities in order.
84///
85/// For each uninitialized entity, generates change moves for all possible values.
86/// Uses typed function pointers for zero-erasure access.
87///
88/// # Type Parameters
89/// * `S` - The planning solution type
90/// * `V` - The value type
91pub struct QueuedEntityPlacer<S, V>
92where
93    S: PlanningSolution,
94{
95    /// The entity selector.
96    entity_selector: Box<dyn EntitySelector<S>>,
97    /// The value selector.
98    value_selector: Box<dyn TypedValueSelector<S, V>>,
99    /// Typed getter function pointer.
100    getter: fn(&S, usize) -> Option<V>,
101    /// Typed setter function pointer.
102    setter: fn(&mut S, usize, Option<V>),
103    /// The variable name.
104    variable_name: &'static str,
105    /// The descriptor index.
106    descriptor_index: usize,
107}
108
109impl<S, V> QueuedEntityPlacer<S, V>
110where
111    S: PlanningSolution,
112{
113    /// Creates a new queued entity placer with typed function pointers.
114    pub fn new(
115        entity_selector: Box<dyn EntitySelector<S>>,
116        value_selector: Box<dyn TypedValueSelector<S, V>>,
117        getter: fn(&S, usize) -> Option<V>,
118        setter: fn(&mut S, usize, Option<V>),
119        descriptor_index: usize,
120        variable_name: &'static str,
121    ) -> Self {
122        Self {
123            entity_selector,
124            value_selector,
125            getter,
126            setter,
127            variable_name,
128            descriptor_index,
129        }
130    }
131}
132
133impl<S, V> Debug for QueuedEntityPlacer<S, V>
134where
135    S: PlanningSolution,
136{
137    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
138        f.debug_struct("QueuedEntityPlacer")
139            .field("entity_selector", &self.entity_selector)
140            .field("value_selector", &self.value_selector)
141            .field("variable_name", &self.variable_name)
142            .finish()
143    }
144}
145
146impl<S, V> EntityPlacer<S, ChangeMove<S, V>> for QueuedEntityPlacer<S, V>
147where
148    S: PlanningSolution,
149    V: Clone + PartialEq + Send + Sync + Debug + 'static,
150{
151    fn get_placements(
152        &self,
153        score_director: &dyn ScoreDirector<S>,
154    ) -> Vec<Placement<S, ChangeMove<S, V>>> {
155        let variable_name = self.variable_name;
156        let descriptor_index = self.descriptor_index;
157        let getter = self.getter;
158        let setter = self.setter;
159
160        self.entity_selector
161            .iter(score_director)
162            .filter_map(|entity_ref| {
163                // Check if entity is uninitialized using typed getter - zero erasure
164                let current_value =
165                    getter(score_director.working_solution(), entity_ref.entity_index);
166
167                // Only include uninitialized entities
168                if current_value.is_some() {
169                    return None;
170                }
171
172                // Generate moves for all possible values
173                let moves: Vec<ChangeMove<S, V>> = self
174                    .value_selector
175                    .iter_typed(
176                        score_director,
177                        entity_ref.descriptor_index,
178                        entity_ref.entity_index,
179                    )
180                    .map(|value| {
181                        ChangeMove::new(
182                            entity_ref.entity_index,
183                            Some(value),
184                            getter,
185                            setter,
186                            variable_name,
187                            descriptor_index,
188                        )
189                    })
190                    .collect();
191
192                if moves.is_empty() {
193                    None
194                } else {
195                    Some(Placement::new(entity_ref, moves))
196                }
197            })
198            .collect()
199    }
200}
201
202/// Entity placer that sorts placements by a comparator function.
203///
204/// Wraps an inner placer and sorts its placements using a typed comparator.
205/// This enables FIRST_FIT_DECREASING and similar construction variants.
206///
207/// # Example
208///
209/// ```
210/// use solverforge_solver::phase::construction::{SortedEntityPlacer, QueuedEntityPlacer, EntityPlacer};
211/// use solverforge_solver::heuristic::r#move::ChangeMove;
212/// use solverforge_solver::heuristic::selector::{FromSolutionEntitySelector, StaticTypedValueSelector};
213/// use solverforge_core::domain::PlanningSolution;
214/// use solverforge_core::score::SimpleScore;
215/// use std::cmp::Ordering;
216///
217/// #[derive(Clone, Debug)]
218/// struct Task { difficulty: i32, assigned: Option<i32> }
219///
220/// #[derive(Clone, Debug)]
221/// struct Solution { tasks: Vec<Task>, score: Option<SimpleScore> }
222///
223/// impl PlanningSolution for Solution {
224///     type Score = SimpleScore;
225///     fn score(&self) -> Option<Self::Score> { self.score }
226///     fn set_score(&mut self, score: Option<Self::Score>) { self.score = score; }
227/// }
228///
229/// fn get_assigned(s: &Solution, i: usize) -> Option<i32> {
230///     s.tasks.get(i).and_then(|t| t.assigned)
231/// }
232/// fn set_assigned(s: &mut Solution, i: usize, v: Option<i32>) {
233///     if let Some(t) = s.tasks.get_mut(i) { t.assigned = v; }
234/// }
235///
236/// // Sort entities by difficulty (descending) for FIRST_FIT_DECREASING
237/// fn difficulty_descending(s: &Solution, a: usize, b: usize) -> Ordering {
238///     let da = s.tasks.get(a).map(|t| t.difficulty).unwrap_or(0);
239///     let db = s.tasks.get(b).map(|t| t.difficulty).unwrap_or(0);
240///     db.cmp(&da)  // Descending order
241/// }
242/// ```
243pub struct SortedEntityPlacer<S, M, Inner>
244where
245    S: PlanningSolution,
246    M: Move<S>,
247    Inner: EntityPlacer<S, M>,
248{
249    inner: Inner,
250    /// Comparator function: takes (solution, entity_index_a, entity_index_b) -> Ordering
251    comparator: fn(&S, usize, usize) -> std::cmp::Ordering,
252    _phantom: PhantomData<(S, M)>,
253}
254
255impl<S, M, Inner> SortedEntityPlacer<S, M, Inner>
256where
257    S: PlanningSolution,
258    M: Move<S>,
259    Inner: EntityPlacer<S, M>,
260{
261    /// Creates a new sorted entity placer.
262    ///
263    /// # Arguments
264    /// * `inner` - The inner placer to wrap
265    /// * `comparator` - Function to compare entities: `(solution, idx_a, idx_b) -> Ordering`
266    pub fn new(inner: Inner, comparator: fn(&S, usize, usize) -> std::cmp::Ordering) -> Self {
267        Self {
268            inner,
269            comparator,
270            _phantom: PhantomData,
271        }
272    }
273}
274
275impl<S, M, Inner> Debug for SortedEntityPlacer<S, M, Inner>
276where
277    S: PlanningSolution,
278    M: Move<S>,
279    Inner: EntityPlacer<S, M>,
280{
281    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
282        f.debug_struct("SortedEntityPlacer")
283            .field("inner", &self.inner)
284            .finish()
285    }
286}
287
288impl<S, M, Inner> EntityPlacer<S, M> for SortedEntityPlacer<S, M, Inner>
289where
290    S: PlanningSolution,
291    M: Move<S>,
292    Inner: EntityPlacer<S, M>,
293{
294    fn get_placements(&self, score_director: &dyn ScoreDirector<S>) -> Vec<Placement<S, M>> {
295        let mut placements = self.inner.get_placements(score_director);
296        let solution = score_director.working_solution();
297        let cmp = self.comparator;
298
299        placements.sort_by(|a, b| {
300            cmp(
301                solution,
302                a.entity_ref.entity_index,
303                b.entity_ref.entity_index,
304            )
305        });
306
307        placements
308    }
309}
310
311#[cfg(test)]
312mod tests {
313    use super::*;
314    use crate::heuristic::selector::{FromSolutionEntitySelector, StaticTypedValueSelector};
315    use solverforge_core::domain::{EntityDescriptor, SolutionDescriptor, TypedEntityExtractor};
316    use solverforge_core::score::SimpleScore;
317    use solverforge_scoring::SimpleScoreDirector;
318    use std::any::TypeId;
319
320    #[derive(Clone, Debug)]
321    struct Queen {
322        row: Option<i32>,
323    }
324
325    #[derive(Clone, Debug)]
326    struct NQueensSolution {
327        queens: Vec<Queen>,
328        score: Option<SimpleScore>,
329    }
330
331    impl PlanningSolution for NQueensSolution {
332        type Score = SimpleScore;
333
334        fn score(&self) -> Option<Self::Score> {
335            self.score
336        }
337
338        fn set_score(&mut self, score: Option<Self::Score>) {
339            self.score = score;
340        }
341    }
342
343    fn get_queens(s: &NQueensSolution) -> &Vec<Queen> {
344        &s.queens
345    }
346
347    fn get_queens_mut(s: &mut NQueensSolution) -> &mut Vec<Queen> {
348        &mut s.queens
349    }
350
351    // Typed getter - zero erasure
352    fn get_queen_row(s: &NQueensSolution, idx: usize) -> Option<i32> {
353        s.queens.get(idx).and_then(|q| q.row)
354    }
355
356    // Typed setter - zero erasure
357    fn set_queen_row(s: &mut NQueensSolution, idx: usize, v: Option<i32>) {
358        if let Some(queen) = s.queens.get_mut(idx) {
359            queen.row = v;
360        }
361    }
362
363    fn create_test_director(
364        initialized: &[bool],
365    ) -> SimpleScoreDirector<NQueensSolution, impl Fn(&NQueensSolution) -> SimpleScore> {
366        let queens: Vec<_> = initialized
367            .iter()
368            .enumerate()
369            .map(|(i, init)| Queen {
370                row: if *init { Some(i as i32) } else { None },
371            })
372            .collect();
373
374        let solution = NQueensSolution {
375            queens,
376            score: None,
377        };
378
379        let extractor = Box::new(TypedEntityExtractor::new(
380            "Queen",
381            "queens",
382            get_queens,
383            get_queens_mut,
384        ));
385        let entity_desc = EntityDescriptor::new("Queen", TypeId::of::<Queen>(), "queens")
386            .with_extractor(extractor);
387
388        let descriptor =
389            SolutionDescriptor::new("NQueensSolution", TypeId::of::<NQueensSolution>())
390                .with_entity(entity_desc);
391
392        SimpleScoreDirector::with_calculator(solution, descriptor, |_| SimpleScore::of(0))
393    }
394
395    #[test]
396    fn test_queued_placer_all_uninitialized() {
397        let director = create_test_director(&[false, false, false]);
398
399        let entity_selector = Box::new(FromSolutionEntitySelector::new(0));
400        let value_selector = Box::new(StaticTypedValueSelector::new(vec![0i32, 1, 2]));
401
402        let placer = QueuedEntityPlacer::new(
403            entity_selector,
404            value_selector,
405            get_queen_row,
406            set_queen_row,
407            0,
408            "row",
409        );
410
411        let placements = placer.get_placements(&director);
412
413        // All 3 entities should have placements
414        assert_eq!(placements.len(), 3);
415
416        // Each should have 3 moves (one per value)
417        for p in &placements {
418            assert_eq!(p.moves.len(), 3);
419        }
420    }
421
422    #[test]
423    fn test_queued_placer_some_initialized() {
424        // First and third are initialized, middle is not
425        let director = create_test_director(&[true, false, true]);
426
427        let entity_selector = Box::new(FromSolutionEntitySelector::new(0));
428        let value_selector = Box::new(StaticTypedValueSelector::new(vec![0i32, 1, 2]));
429
430        let placer = QueuedEntityPlacer::new(
431            entity_selector,
432            value_selector,
433            get_queen_row,
434            set_queen_row,
435            0,
436            "row",
437        );
438
439        let placements = placer.get_placements(&director);
440
441        // Only 1 entity (index 1) should have a placement
442        assert_eq!(placements.len(), 1);
443        assert_eq!(placements[0].entity_ref.entity_index, 1);
444    }
445
446    #[test]
447    fn test_queued_placer_all_initialized() {
448        let director = create_test_director(&[true, true, true]);
449
450        let entity_selector = Box::new(FromSolutionEntitySelector::new(0));
451        let value_selector = Box::new(StaticTypedValueSelector::new(vec![0i32, 1, 2]));
452
453        let placer = QueuedEntityPlacer::new(
454            entity_selector,
455            value_selector,
456            get_queen_row,
457            set_queen_row,
458            0,
459            "row",
460        );
461
462        let placements = placer.get_placements(&director);
463
464        // No placements - all already initialized
465        assert_eq!(placements.len(), 0);
466    }
467
468    #[test]
469    fn test_sorted_entity_placer_descending() {
470        // Create 3 uninitialized queens
471        let director = create_test_director(&[false, false, false]);
472
473        let entity_selector = Box::new(FromSolutionEntitySelector::new(0));
474        let value_selector = Box::new(StaticTypedValueSelector::new(vec![0i32, 1, 2]));
475
476        let inner = QueuedEntityPlacer::new(
477            entity_selector,
478            value_selector,
479            get_queen_row,
480            set_queen_row,
481            0,
482            "row",
483        );
484
485        // Sort by entity index descending (2, 1, 0)
486        fn descending_index(_s: &NQueensSolution, a: usize, b: usize) -> std::cmp::Ordering {
487            b.cmp(&a)
488        }
489
490        let sorted = SortedEntityPlacer::new(inner, descending_index);
491        let placements = sorted.get_placements(&director);
492
493        assert_eq!(placements.len(), 3);
494        assert_eq!(placements[0].entity_ref.entity_index, 2);
495        assert_eq!(placements[1].entity_ref.entity_index, 1);
496        assert_eq!(placements[2].entity_ref.entity_index, 0);
497    }
498}
solverforge_solver/phase/construction/placer.rs

solverforge_solver/phase/construction/
placer.rs
