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
160                    .iter_typed(
161                        score_director,
162                        entity_ref.descriptor_index,
163                        entity_ref.entity_index,
164                    )
165                    .collect::<Vec<_>>();
166                (entity_ref, values)
167            })
168            .collect();
169
170        entity_values
171            .into_iter()
172            .flat_map(move |(entity_ref, values)| {
173                values.into_iter().map(move |value| {
174                    ChangeMove::new(
175                        entity_ref.entity_index,
176                        Some(value),
177                        getter,
178                        setter,
179                        variable_name,
180                        descriptor_index,
181                    )
182                })
183            })
184    }
185
186    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
187        self.entity_selector
188            .iter(score_director)
189            .map(|entity_ref| {
190                self.value_selector.size(
191                    score_director,
192                    entity_ref.descriptor_index,
193                    entity_ref.entity_index,
194                )
195            })
196            .sum()
197    }
198}
199
200/// A swap move selector that generates `SwapMove` instances.
201///
202/// Uses typed function pointers for zero-erasure access to variable values.
203pub struct SwapMoveSelector<S, V, LES, RES> {
204    left_entity_selector: LES,
205    right_entity_selector: RES,
206    // Typed getter function pointer - zero erasure.
207    getter: fn(&S, usize) -> Option<V>,
208    // Typed setter function pointer - zero erasure.
209    setter: fn(&mut S, usize, Option<V>),
210    descriptor_index: usize,
211    variable_name: &'static str,
212    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
213}
214
215impl<S, V, LES: Debug, RES: Debug> Debug for SwapMoveSelector<S, V, LES, RES> {
216    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
217        f.debug_struct("SwapMoveSelector")
218            .field("left_entity_selector", &self.left_entity_selector)
219            .field("right_entity_selector", &self.right_entity_selector)
220            .field("descriptor_index", &self.descriptor_index)
221            .field("variable_name", &self.variable_name)
222            .finish()
223    }
224}
225
226impl<S: PlanningSolution, V, LES, RES> SwapMoveSelector<S, V, LES, RES> {
227    pub fn new(
228        left_entity_selector: LES,
229        right_entity_selector: RES,
230        getter: fn(&S, usize) -> Option<V>,
231        setter: fn(&mut S, usize, Option<V>),
232        descriptor_index: usize,
233        variable_name: &'static str,
234    ) -> Self {
235        Self {
236            left_entity_selector,
237            right_entity_selector,
238            getter,
239            setter,
240            descriptor_index,
241            variable_name,
242            _phantom: PhantomData,
243        }
244    }
245}
246
247impl<S: PlanningSolution, V>
248    SwapMoveSelector<S, V, FromSolutionEntitySelector, FromSolutionEntitySelector>
249{
250    /// Creates a simple selector for swapping within a single entity type.
251    ///
252    /// # Arguments
253    /// * `getter` - Typed getter function pointer
254    /// * `setter` - Typed setter function pointer
255    /// * `descriptor_index` - Index in the entity descriptor
256    /// * `variable_name` - Name of the variable to swap
257    pub fn simple(
258        getter: fn(&S, usize) -> Option<V>,
259        setter: fn(&mut S, usize, Option<V>),
260        descriptor_index: usize,
261        variable_name: &'static str,
262    ) -> Self {
263        Self {
264            left_entity_selector: FromSolutionEntitySelector::new(descriptor_index),
265            right_entity_selector: FromSolutionEntitySelector::new(descriptor_index),
266            getter,
267            setter,
268            descriptor_index,
269            variable_name,
270            _phantom: PhantomData,
271        }
272    }
273}
274
275impl<S, V, LES, RES> MoveSelector<S, SwapMove<S, V>> for SwapMoveSelector<S, V, LES, RES>
276where
277    S: PlanningSolution,
278    V: Clone + PartialEq + Send + Sync + Debug + 'static,
279    LES: EntitySelector<S>,
280    RES: EntitySelector<S>,
281{
282    fn open_cursor<'a, D: Director<S>>(
283        &'a self,
284        score_director: &D,
285    ) -> impl Iterator<Item = SwapMove<S, V>> + 'a {
286        let descriptor_index = self.descriptor_index;
287        let variable_name = self.variable_name;
288        let getter = self.getter;
289        let setter = self.setter;
290
291        // Collect entities once — needed for triangular pairing.
292        let left_entities: Vec<EntityReference> =
293            self.left_entity_selector.iter(score_director).collect();
294        let right_entities: Vec<EntityReference> =
295            self.right_entity_selector.iter(score_director).collect();
296
297        // Eager triangular pairing — no Rc, no shared pointers.
298        let mut moves =
299            Vec::with_capacity(left_entities.len() * left_entities.len().saturating_sub(1) / 2);
300        for (i, left) in left_entities.iter().enumerate() {
301            for right in &right_entities[i + 1..] {
302                if left.descriptor_index == right.descriptor_index
303                    && left.descriptor_index == descriptor_index
304                {
305                    moves.push(SwapMove::new(
306                        left.entity_index,
307                        right.entity_index,
308                        getter,
309                        setter,
310                        variable_name,
311                        descriptor_index,
312                    ));
313                }
314            }
315        }
316
317        moves.into_iter()
318    }
319
320    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
321        let left_count = self.left_entity_selector.size(score_director);
322        let right_count = self.right_entity_selector.size(score_director);
323
324        if left_count == right_count {
325            left_count * left_count.saturating_sub(1) / 2
326        } else {
327            left_count * right_count / 2
328        }
329    }
330}
331
332#[cfg(test)]
333#[path = "move_selector_tests.rs"]
334mod tests;
solverforge_solver/heuristic/selector/move_selector.rs

solverforge_solver/heuristic/selector/
move_selector.rs
