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    // Returns an iterator over typed moves.
38    fn iter_moves<'a, D: Director<S>>(
39        &'a self,
40        score_director: &'a D,
41    ) -> impl Iterator<Item = M> + 'a;
42
43    fn size<D: Director<S>>(&self, score_director: &D) -> usize;
44
45    fn append_moves<D: Director<S>>(&self, score_director: &D, arena: &mut MoveArena<M>) {
46        arena.extend(self.iter_moves(score_director));
47    }
48
49    // Returns true if this selector may return the same move multiple times.
50    fn is_never_ending(&self) -> bool {
51        false
52    }
53}
54
55/// A change move selector that generates `ChangeMove` instances.
56///
57/// Stores typed function pointers for zero-erasure move generation.
58pub struct ChangeMoveSelector<S, V, ES, VS> {
59    entity_selector: ES,
60    value_selector: VS,
61    getter: fn(&S, usize) -> Option<V>,
62    setter: fn(&mut S, usize, Option<V>),
63    descriptor_index: usize,
64    variable_name: &'static str,
65    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
66}
67
68impl<S, V: Debug, ES: Debug, VS: Debug> Debug for ChangeMoveSelector<S, V, ES, VS> {
69    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
70        f.debug_struct("ChangeMoveSelector")
71            .field("entity_selector", &self.entity_selector)
72            .field("value_selector", &self.value_selector)
73            .field("descriptor_index", &self.descriptor_index)
74            .field("variable_name", &self.variable_name)
75            .finish()
76    }
77}
78
79impl<S: PlanningSolution, V: Clone, ES, VS> ChangeMoveSelector<S, V, ES, VS> {
80    /// Creates a new change move selector with typed function pointers.
81    ///
82    /// # Arguments
83    /// * `entity_selector` - Selects entities to modify
84    /// * `value_selector` - Selects values to assign
85    /// * `getter` - Function pointer to get current value from solution
86    /// * `setter` - Function pointer to set value on solution
87    /// * `descriptor_index` - Index of the entity descriptor
88    /// * `variable_name` - Name of the variable
89    pub fn new(
90        entity_selector: ES,
91        value_selector: VS,
92        getter: fn(&S, usize) -> Option<V>,
93        setter: fn(&mut S, usize, Option<V>),
94        descriptor_index: usize,
95        variable_name: &'static str,
96    ) -> Self {
97        Self {
98            entity_selector,
99            value_selector,
100            getter,
101            setter,
102            descriptor_index,
103            variable_name,
104            _phantom: PhantomData,
105        }
106    }
107}
108
109impl<S: PlanningSolution, V: Clone + Send + Sync + Debug + 'static>
110    ChangeMoveSelector<S, V, FromSolutionEntitySelector, StaticValueSelector<S, V>>
111{
112    pub fn simple(
113        getter: fn(&S, usize) -> Option<V>,
114        setter: fn(&mut S, usize, Option<V>),
115        descriptor_index: usize,
116        variable_name: &'static str,
117        values: Vec<V>,
118    ) -> Self {
119        Self {
120            entity_selector: FromSolutionEntitySelector::new(descriptor_index),
121            value_selector: StaticValueSelector::new(values),
122            getter,
123            setter,
124            descriptor_index,
125            variable_name,
126            _phantom: PhantomData,
127        }
128    }
129}
130
131impl<S, V, ES, VS> MoveSelector<S, ChangeMove<S, V>> for ChangeMoveSelector<S, V, ES, VS>
132where
133    S: PlanningSolution,
134    V: Clone + PartialEq + Send + Sync + Debug + 'static,
135    ES: EntitySelector<S>,
136    VS: ValueSelector<S, V>,
137{
138    fn iter_moves<'a, D: Director<S>>(
139        &'a self,
140        score_director: &'a D,
141    ) -> impl Iterator<Item = ChangeMove<S, V>> + 'a {
142        let descriptor_index = self.descriptor_index;
143        let variable_name = self.variable_name;
144        let getter = self.getter;
145        let setter = self.setter;
146        let value_selector = &self.value_selector;
147
148        // Lazy iteration: O(1) per .next() call, no upfront allocation
149        self.entity_selector
150            .iter(score_director)
151            .flat_map(move |entity_ref| {
152                value_selector
153                    .iter_typed(
154                        score_director,
155                        entity_ref.descriptor_index,
156                        entity_ref.entity_index,
157                    )
158                    .map(move |value| {
159                        ChangeMove::new(
160                            entity_ref.entity_index,
161                            Some(value),
162                            getter,
163                            setter,
164                            variable_name,
165                            descriptor_index,
166                        )
167                    })
168            })
169    }
170
171    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
172        self.entity_selector
173            .iter(score_director)
174            .map(|entity_ref| {
175                self.value_selector.size(
176                    score_director,
177                    entity_ref.descriptor_index,
178                    entity_ref.entity_index,
179                )
180            })
181            .sum()
182    }
183}
184
185/// A swap move selector that generates `SwapMove` instances.
186///
187/// Uses typed function pointers for zero-erasure access to variable values.
188pub struct SwapMoveSelector<S, V, LES, RES> {
189    left_entity_selector: LES,
190    right_entity_selector: RES,
191    // Typed getter function pointer - zero erasure.
192    getter: fn(&S, usize) -> Option<V>,
193    // Typed setter function pointer - zero erasure.
194    setter: fn(&mut S, usize, Option<V>),
195    descriptor_index: usize,
196    variable_name: &'static str,
197    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
198}
199
200impl<S, V, LES: Debug, RES: Debug> Debug for SwapMoveSelector<S, V, LES, RES> {
201    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
202        f.debug_struct("SwapMoveSelector")
203            .field("left_entity_selector", &self.left_entity_selector)
204            .field("right_entity_selector", &self.right_entity_selector)
205            .field("descriptor_index", &self.descriptor_index)
206            .field("variable_name", &self.variable_name)
207            .finish()
208    }
209}
210
211impl<S: PlanningSolution, V, LES, RES> SwapMoveSelector<S, V, LES, RES> {
212    pub fn new(
213        left_entity_selector: LES,
214        right_entity_selector: RES,
215        getter: fn(&S, usize) -> Option<V>,
216        setter: fn(&mut S, usize, Option<V>),
217        descriptor_index: usize,
218        variable_name: &'static str,
219    ) -> Self {
220        Self {
221            left_entity_selector,
222            right_entity_selector,
223            getter,
224            setter,
225            descriptor_index,
226            variable_name,
227            _phantom: PhantomData,
228        }
229    }
230}
231
232impl<S: PlanningSolution, V>
233    SwapMoveSelector<S, V, FromSolutionEntitySelector, FromSolutionEntitySelector>
234{
235    /// Creates a simple selector for swapping within a single entity type.
236    ///
237    /// # Arguments
238    /// * `getter` - Typed getter function pointer
239    /// * `setter` - Typed setter function pointer
240    /// * `descriptor_index` - Index in the entity descriptor
241    /// * `variable_name` - Name of the variable to swap
242    pub fn simple(
243        getter: fn(&S, usize) -> Option<V>,
244        setter: fn(&mut S, usize, Option<V>),
245        descriptor_index: usize,
246        variable_name: &'static str,
247    ) -> Self {
248        Self {
249            left_entity_selector: FromSolutionEntitySelector::new(descriptor_index),
250            right_entity_selector: FromSolutionEntitySelector::new(descriptor_index),
251            getter,
252            setter,
253            descriptor_index,
254            variable_name,
255            _phantom: PhantomData,
256        }
257    }
258}
259
260impl<S, V, LES, RES> MoveSelector<S, SwapMove<S, V>> for SwapMoveSelector<S, V, LES, RES>
261where
262    S: PlanningSolution,
263    V: Clone + PartialEq + Send + Sync + Debug + 'static,
264    LES: EntitySelector<S>,
265    RES: EntitySelector<S>,
266{
267    fn iter_moves<'a, D: Director<S>>(
268        &'a self,
269        score_director: &'a D,
270    ) -> impl Iterator<Item = SwapMove<S, V>> + 'a {
271        let descriptor_index = self.descriptor_index;
272        let variable_name = self.variable_name;
273        let getter = self.getter;
274        let setter = self.setter;
275
276        // Collect entities once — needed for triangular pairing.
277        let left_entities: Vec<EntityReference> =
278            self.left_entity_selector.iter(score_director).collect();
279        let right_entities: Vec<EntityReference> =
280            self.right_entity_selector.iter(score_director).collect();
281
282        // Eager triangular pairing — no Rc, no shared pointers.
283        let mut moves =
284            Vec::with_capacity(left_entities.len() * left_entities.len().saturating_sub(1) / 2);
285        for (i, left) in left_entities.iter().enumerate() {
286            for right in &right_entities[i + 1..] {
287                if left.descriptor_index == right.descriptor_index
288                    && left.descriptor_index == descriptor_index
289                {
290                    moves.push(SwapMove::new(
291                        left.entity_index,
292                        right.entity_index,
293                        getter,
294                        setter,
295                        variable_name,
296                        descriptor_index,
297                    ));
298                }
299            }
300        }
301
302        moves.into_iter()
303    }
304
305    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
306        let left_count = self.left_entity_selector.size(score_director);
307        let right_count = self.right_entity_selector.size(score_director);
308
309        if left_count == right_count {
310            left_count * left_count.saturating_sub(1) / 2
311        } else {
312            left_count * right_count / 2
313        }
314    }
315}
316
317#[cfg(test)]
318#[path = "move_selector_tests.rs"]
319mod tests;
solverforge_solver/heuristic/selector/move_selector.rs

solverforge_solver/heuristic/selector/
move_selector.rs
