solverforge_solver/heuristic/selector/
move_selector.rs

1/* Typed move selectors for zero-allocation move generation.
2
3Typed move selectors yield concrete move types directly, enabling
4monomorphization and arena allocation.
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::MoveArena;
14use crate::heuristic::r#move::{ChangeMove, Move, SwapMove};
15
16use super::entity::{EntityReference, EntitySelector, FromSolutionEntitySelector};
17use super::value_selector::{StaticValueSelector, ValueSelector};
18
19mod either;
20mod list_adapters;
21
22pub use either::{EitherChangeMoveSelector, EitherSwapMoveSelector};
23pub use list_adapters::{
24    ListMoveKOptSelector, ListMoveListChangeSelector, ListMoveListRuinSelector,
25    ListMoveNearbyKOptSelector,
26};
27
28/// A typed move selector that yields moves of type `M` directly.
29///
30/// Unlike erased selectors, this returns concrete moves inline,
31/// eliminating heap allocation per move.
32///
33/// # Type Parameters
34/// * `S` - The planning solution type
35/// * `M` - The move type
36pub trait MoveSelector<S: PlanningSolution, M: Move<S>>: Send + Debug {
37    // Opens an owned move cursor that must not borrow the score director.
38    fn open_cursor<'a, D: Director<S>>(
39        &'a self,
40        score_director: &D,
41    ) -> impl Iterator<Item = M> + 'a;
42
43    // Returns an iterator over typed moves.
44    fn iter_moves<'a, D: Director<S>>(
45        &'a self,
46        score_director: &D,
47    ) -> impl Iterator<Item = M> + 'a {
48        self.open_cursor(score_director)
49    }
50
51    fn size<D: Director<S>>(&self, score_director: &D) -> usize;
52
53    fn append_moves<D: Director<S>>(&self, score_director: &D, arena: &mut MoveArena<M>) {
54        arena.extend(self.open_cursor(score_director));
55    }
56
57    // Returns true if this selector may return the same move multiple times.
58    fn is_never_ending(&self) -> bool {
59        false
60    }
61}
62
63/// A change move selector that generates `ChangeMove` instances.
64///
65/// Stores typed function pointers for zero-erasure move generation.
66pub struct ChangeMoveSelector<S, V, ES, VS> {
67    entity_selector: ES,
68    value_selector: VS,
69    getter: fn(&S, usize) -> Option<V>,
70    setter: fn(&mut S, usize, Option<V>),
71    descriptor_index: usize,
72    variable_name: &'static str,
73    allows_unassigned: bool,
74    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
75}
76
77impl<S, V: Debug, ES: Debug, VS: Debug> Debug for ChangeMoveSelector<S, V, ES, VS> {
78    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
79        f.debug_struct("ChangeMoveSelector")
80            .field("entity_selector", &self.entity_selector)
81            .field("value_selector", &self.value_selector)
82            .field("descriptor_index", &self.descriptor_index)
83            .field("variable_name", &self.variable_name)
84            .field("allows_unassigned", &self.allows_unassigned)
85            .finish()
86    }
87}
88
89impl<S: PlanningSolution, V: Clone, ES, VS> ChangeMoveSelector<S, V, ES, VS> {
90    /// Creates a new change move selector with typed function pointers.
91    ///
92    /// # Arguments
93    /// * `entity_selector` - Selects entities to modify
94    /// * `value_selector` - Selects values to assign
95    /// * `getter` - Function pointer to get current value from solution
96    /// * `setter` - Function pointer to set value on solution
97    /// * `descriptor_index` - Index of the entity descriptor
98    /// * `variable_name` - Name of the variable
99    pub fn new(
100        entity_selector: ES,
101        value_selector: VS,
102        getter: fn(&S, usize) -> Option<V>,
103        setter: fn(&mut S, usize, Option<V>),
104        descriptor_index: usize,
105        variable_name: &'static str,
106    ) -> Self {
107        Self {
108            entity_selector,
109            value_selector,
110            getter,
111            setter,
112            descriptor_index,
113            variable_name,
114            allows_unassigned: false,
115            _phantom: PhantomData,
116        }
117    }
118
119    pub fn with_allows_unassigned(mut self, allows_unassigned: bool) -> Self {
120        self.allows_unassigned = allows_unassigned;
121        self
122    }
123}
124
125impl<S: PlanningSolution, V: Clone + Send + Sync + Debug + 'static>
126    ChangeMoveSelector<S, V, FromSolutionEntitySelector, StaticValueSelector<S, V>>
127{
128    pub fn simple(
129        getter: fn(&S, usize) -> Option<V>,
130        setter: fn(&mut S, usize, Option<V>),
131        descriptor_index: usize,
132        variable_name: &'static str,
133        values: Vec<V>,
134    ) -> Self {
135        Self {
136            entity_selector: FromSolutionEntitySelector::new(descriptor_index),
137            value_selector: StaticValueSelector::new(values),
138            getter,
139            setter,
140            descriptor_index,
141            variable_name,
142            allows_unassigned: false,
143            _phantom: PhantomData,
144        }
145    }
146}
147
148impl<S, V, ES, VS> MoveSelector<S, ChangeMove<S, V>> for ChangeMoveSelector<S, V, ES, VS>
149where
150    S: PlanningSolution,
151    V: Clone + PartialEq + Send + Sync + Debug + 'static,
152    ES: EntitySelector<S>,
153    VS: ValueSelector<S, V>,
154{
155    fn open_cursor<'a, D: Director<S>>(
156        &'a self,
157        score_director: &D,
158    ) -> impl Iterator<Item = ChangeMove<S, V>> + 'a {
159        let descriptor_index = self.descriptor_index;
160        let variable_name = self.variable_name;
161        let getter = self.getter;
162        let setter = self.setter;
163        let allows_unassigned = self.allows_unassigned;
164        let value_selector = &self.value_selector;
165        let solution = score_director.working_solution();
166        let entity_values: Vec<_> = self
167            .entity_selector
168            .iter(score_director)
169            .map(|entity_ref| {
170                let current_assigned = getter(solution, entity_ref.entity_index).is_some();
171                let values = value_selector.iter_typed(
172                    score_director,
173                    entity_ref.descriptor_index,
174                    entity_ref.entity_index,
175                );
176                (entity_ref, values, current_assigned)
177            })
178            .collect();
179
180        entity_values
181            .into_iter()
182            .flat_map(move |(entity_ref, values, current_assigned)| {
183                let to_none = (allows_unassigned && current_assigned).then(|| {
184                    ChangeMove::new(
185                        entity_ref.entity_index,
186                        None,
187                        getter,
188                        setter,
189                        variable_name,
190                        descriptor_index,
191                    )
192                });
193                values
194                    .map(move |value| {
195                        ChangeMove::new(
196                            entity_ref.entity_index,
197                            Some(value),
198                            getter,
199                            setter,
200                            variable_name,
201                            descriptor_index,
202                        )
203                    })
204                    .chain(to_none)
205            })
206    }
207
208    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
209        self.entity_selector
210            .iter(score_director)
211            .map(|entity_ref| {
212                self.value_selector.size(
213                    score_director,
214                    entity_ref.descriptor_index,
215                    entity_ref.entity_index,
216                ) + usize::from(
217                    self.allows_unassigned
218                        && (self.getter)(
219                            score_director.working_solution(),
220                            entity_ref.entity_index,
221                        )
222                        .is_some(),
223                )
224            })
225            .sum()
226    }
227}
228
229/// A swap move selector that generates `SwapMove` instances.
230///
231/// Uses typed function pointers for zero-erasure access to variable values.
232pub struct SwapMoveSelector<S, V, LES, RES> {
233    left_entity_selector: LES,
234    right_entity_selector: RES,
235    // Typed getter function pointer - zero erasure.
236    getter: fn(&S, usize) -> Option<V>,
237    // Typed setter function pointer - zero erasure.
238    setter: fn(&mut S, usize, Option<V>),
239    descriptor_index: usize,
240    variable_name: &'static str,
241    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
242}
243
244impl<S, V, LES: Debug, RES: Debug> Debug for SwapMoveSelector<S, V, LES, RES> {
245    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
246        f.debug_struct("SwapMoveSelector")
247            .field("left_entity_selector", &self.left_entity_selector)
248            .field("right_entity_selector", &self.right_entity_selector)
249            .field("descriptor_index", &self.descriptor_index)
250            .field("variable_name", &self.variable_name)
251            .finish()
252    }
253}
254
255impl<S: PlanningSolution, V, LES, RES> SwapMoveSelector<S, V, LES, RES> {
256    pub fn new(
257        left_entity_selector: LES,
258        right_entity_selector: RES,
259        getter: fn(&S, usize) -> Option<V>,
260        setter: fn(&mut S, usize, Option<V>),
261        descriptor_index: usize,
262        variable_name: &'static str,
263    ) -> Self {
264        Self {
265            left_entity_selector,
266            right_entity_selector,
267            getter,
268            setter,
269            descriptor_index,
270            variable_name,
271            _phantom: PhantomData,
272        }
273    }
274}
275
276impl<S: PlanningSolution, V>
277    SwapMoveSelector<S, V, FromSolutionEntitySelector, FromSolutionEntitySelector>
278{
279    /// Creates a simple selector for swapping within a single entity type.
280    ///
281    /// # Arguments
282    /// * `getter` - Typed getter function pointer
283    /// * `setter` - Typed setter function pointer
284    /// * `descriptor_index` - Index in the entity descriptor
285    /// * `variable_name` - Name of the variable to swap
286    pub fn simple(
287        getter: fn(&S, usize) -> Option<V>,
288        setter: fn(&mut S, usize, Option<V>),
289        descriptor_index: usize,
290        variable_name: &'static str,
291    ) -> Self {
292        Self {
293            left_entity_selector: FromSolutionEntitySelector::new(descriptor_index),
294            right_entity_selector: FromSolutionEntitySelector::new(descriptor_index),
295            getter,
296            setter,
297            descriptor_index,
298            variable_name,
299            _phantom: PhantomData,
300        }
301    }
302}
303
304impl<S, V, LES, RES> MoveSelector<S, SwapMove<S, V>> for SwapMoveSelector<S, V, LES, RES>
305where
306    S: PlanningSolution,
307    V: Clone + PartialEq + Send + Sync + Debug + 'static,
308    LES: EntitySelector<S>,
309    RES: EntitySelector<S>,
310{
311    fn open_cursor<'a, D: Director<S>>(
312        &'a self,
313        score_director: &D,
314    ) -> impl Iterator<Item = SwapMove<S, V>> + 'a {
315        let descriptor_index = self.descriptor_index;
316        let variable_name = self.variable_name;
317        let getter = self.getter;
318        let setter = self.setter;
319
320        // Collect entities once — needed for triangular pairing.
321        let left_entities: Vec<EntityReference> =
322            self.left_entity_selector.iter(score_director).collect();
323        let right_entities: Vec<EntityReference> =
324            self.right_entity_selector.iter(score_director).collect();
325
326        // Eager triangular pairing — no Rc, no shared pointers.
327        let mut moves =
328            Vec::with_capacity(left_entities.len() * left_entities.len().saturating_sub(1) / 2);
329        for (i, left) in left_entities.iter().enumerate() {
330            for right in &right_entities[i + 1..] {
331                if left.descriptor_index == right.descriptor_index
332                    && left.descriptor_index == descriptor_index
333                {
334                    moves.push(SwapMove::new(
335                        left.entity_index,
336                        right.entity_index,
337                        getter,
338                        setter,
339                        variable_name,
340                        descriptor_index,
341                    ));
342                }
343            }
344        }
345
346        moves.into_iter()
347    }
348
349    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
350        let left_count = self.left_entity_selector.size(score_director);
351        let right_count = self.right_entity_selector.size(score_director);
352
353        if left_count == right_count {
354            left_count * left_count.saturating_sub(1) / 2
355        } else {
356            left_count * right_count / 2
357        }
358    }
359}
solverforge_solver/heuristic/selector/move_selector.rs

solverforge_solver/heuristic/selector/
move_selector.rs
