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

solverforge_solver/heuristic/selector/
move_selector.rs
