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, EitherMove, ListMoveImpl, Move, SwapMove};
15
16use super::entity::{EntityReference, EntitySelector, FromSolutionEntitySelector};
17use super::value_selector::{StaticValueSelector, ValueSelector};
18
19/// A typed move selector that yields moves of type `M` directly.
20///
21/// Unlike erased selectors, this returns concrete moves inline,
22/// eliminating heap allocation per move.
23///
24/// # Type Parameters
25/// * `S` - The planning solution type
26/// * `M` - The move type
27pub trait MoveSelector<S: PlanningSolution, M: Move<S>>: Send + Debug {
28    // Returns an iterator over typed moves.
29    fn iter_moves<'a, D: Director<S>>(
30        &'a self,
31        score_director: &'a D,
32    ) -> impl Iterator<Item = M> + 'a;
33
34    fn size<D: Director<S>>(&self, score_director: &D) -> usize;
35
36    fn append_moves<D: Director<S>>(&self, score_director: &D, arena: &mut MoveArena<M>) {
37        arena.extend(self.iter_moves(score_director));
38    }
39
40    // Returns true if this selector may return the same move multiple times.
41    fn is_never_ending(&self) -> bool {
42        false
43    }
44}
45
46/// A change move selector that generates `ChangeMove` instances.
47///
48/// Stores typed function pointers for zero-erasure move generation.
49pub struct ChangeMoveSelector<S, V, ES, VS> {
50    entity_selector: ES,
51    value_selector: VS,
52    getter: fn(&S, usize) -> Option<V>,
53    setter: fn(&mut S, usize, Option<V>),
54    descriptor_index: usize,
55    variable_name: &'static str,
56    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
57}
58
59impl<S, V: Debug, ES: Debug, VS: Debug> Debug for ChangeMoveSelector<S, V, ES, VS> {
60    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
61        f.debug_struct("ChangeMoveSelector")
62            .field("entity_selector", &self.entity_selector)
63            .field("value_selector", &self.value_selector)
64            .field("descriptor_index", &self.descriptor_index)
65            .field("variable_name", &self.variable_name)
66            .finish()
67    }
68}
69
70impl<S: PlanningSolution, V: Clone, ES, VS> ChangeMoveSelector<S, V, ES, VS> {
71    /// Creates a new change move selector with typed function pointers.
72    ///
73    /// # Arguments
74    /// * `entity_selector` - Selects entities to modify
75    /// * `value_selector` - Selects values to assign
76    /// * `getter` - Function pointer to get current value from solution
77    /// * `setter` - Function pointer to set value on solution
78    /// * `descriptor_index` - Index of the entity descriptor
79    /// * `variable_name` - Name of the variable
80    pub fn new(
81        entity_selector: ES,
82        value_selector: VS,
83        getter: fn(&S, usize) -> Option<V>,
84        setter: fn(&mut S, usize, Option<V>),
85        descriptor_index: usize,
86        variable_name: &'static str,
87    ) -> Self {
88        Self {
89            entity_selector,
90            value_selector,
91            getter,
92            setter,
93            descriptor_index,
94            variable_name,
95            _phantom: PhantomData,
96        }
97    }
98}
99
100impl<S: PlanningSolution, V: Clone + Send + Sync + Debug + 'static>
101    ChangeMoveSelector<S, V, FromSolutionEntitySelector, StaticValueSelector<S, V>>
102{
103    pub fn simple(
104        getter: fn(&S, usize) -> Option<V>,
105        setter: fn(&mut S, usize, Option<V>),
106        descriptor_index: usize,
107        variable_name: &'static str,
108        values: Vec<V>,
109    ) -> Self {
110        Self {
111            entity_selector: FromSolutionEntitySelector::new(descriptor_index),
112            value_selector: StaticValueSelector::new(values),
113            getter,
114            setter,
115            descriptor_index,
116            variable_name,
117            _phantom: PhantomData,
118        }
119    }
120}
121
122impl<S, V, ES, VS> MoveSelector<S, ChangeMove<S, V>> for ChangeMoveSelector<S, V, ES, VS>
123where
124    S: PlanningSolution,
125    V: Clone + PartialEq + Send + Sync + Debug + 'static,
126    ES: EntitySelector<S>,
127    VS: ValueSelector<S, V>,
128{
129    fn iter_moves<'a, D: Director<S>>(
130        &'a self,
131        score_director: &'a D,
132    ) -> impl Iterator<Item = ChangeMove<S, V>> + 'a {
133        let descriptor_index = self.descriptor_index;
134        let variable_name = self.variable_name;
135        let getter = self.getter;
136        let setter = self.setter;
137        let value_selector = &self.value_selector;
138
139        // Lazy iteration: O(1) per .next() call, no upfront allocation
140        self.entity_selector
141            .iter(score_director)
142            .flat_map(move |entity_ref| {
143                value_selector
144                    .iter_typed(
145                        score_director,
146                        entity_ref.descriptor_index,
147                        entity_ref.entity_index,
148                    )
149                    .map(move |value| {
150                        ChangeMove::new(
151                            entity_ref.entity_index,
152                            Some(value),
153                            getter,
154                            setter,
155                            variable_name,
156                            descriptor_index,
157                        )
158                    })
159            })
160    }
161
162    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
163        self.entity_selector
164            .iter(score_director)
165            .map(|entity_ref| {
166                self.value_selector.size(
167                    score_director,
168                    entity_ref.descriptor_index,
169                    entity_ref.entity_index,
170                )
171            })
172            .sum()
173    }
174}
175
176/// A swap move selector that generates `SwapMove` instances.
177///
178/// Uses typed function pointers for zero-erasure access to variable values.
179pub struct SwapMoveSelector<S, V, LES, RES> {
180    left_entity_selector: LES,
181    right_entity_selector: RES,
182    // Typed getter function pointer - zero erasure.
183    getter: fn(&S, usize) -> Option<V>,
184    // Typed setter function pointer - zero erasure.
185    setter: fn(&mut S, usize, Option<V>),
186    descriptor_index: usize,
187    variable_name: &'static str,
188    _phantom: PhantomData<(fn() -> S, fn() -> V)>,
189}
190
191impl<S, V, LES: Debug, RES: Debug> Debug for SwapMoveSelector<S, V, LES, RES> {
192    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
193        f.debug_struct("SwapMoveSelector")
194            .field("left_entity_selector", &self.left_entity_selector)
195            .field("right_entity_selector", &self.right_entity_selector)
196            .field("descriptor_index", &self.descriptor_index)
197            .field("variable_name", &self.variable_name)
198            .finish()
199    }
200}
201
202impl<S: PlanningSolution, V, LES, RES> SwapMoveSelector<S, V, LES, RES> {
203    pub fn new(
204        left_entity_selector: LES,
205        right_entity_selector: RES,
206        getter: fn(&S, usize) -> Option<V>,
207        setter: fn(&mut S, usize, Option<V>),
208        descriptor_index: usize,
209        variable_name: &'static str,
210    ) -> Self {
211        Self {
212            left_entity_selector,
213            right_entity_selector,
214            getter,
215            setter,
216            descriptor_index,
217            variable_name,
218            _phantom: PhantomData,
219        }
220    }
221}
222
223impl<S: PlanningSolution, V>
224    SwapMoveSelector<S, V, FromSolutionEntitySelector, FromSolutionEntitySelector>
225{
226    /// Creates a simple selector for swapping within a single entity type.
227    ///
228    /// # Arguments
229    /// * `getter` - Typed getter function pointer
230    /// * `setter` - Typed setter function pointer
231    /// * `descriptor_index` - Index in the entity descriptor
232    /// * `variable_name` - Name of the variable to swap
233    pub fn simple(
234        getter: fn(&S, usize) -> Option<V>,
235        setter: fn(&mut S, usize, Option<V>),
236        descriptor_index: usize,
237        variable_name: &'static str,
238    ) -> Self {
239        Self {
240            left_entity_selector: FromSolutionEntitySelector::new(descriptor_index),
241            right_entity_selector: FromSolutionEntitySelector::new(descriptor_index),
242            getter,
243            setter,
244            descriptor_index,
245            variable_name,
246            _phantom: PhantomData,
247        }
248    }
249}
250
251impl<S, V, LES, RES> MoveSelector<S, SwapMove<S, V>> for SwapMoveSelector<S, V, LES, RES>
252where
253    S: PlanningSolution,
254    V: Clone + PartialEq + Send + Sync + Debug + 'static,
255    LES: EntitySelector<S>,
256    RES: EntitySelector<S>,
257{
258    fn iter_moves<'a, D: Director<S>>(
259        &'a self,
260        score_director: &'a D,
261    ) -> impl Iterator<Item = SwapMove<S, V>> + 'a {
262        let descriptor_index = self.descriptor_index;
263        let variable_name = self.variable_name;
264        let getter = self.getter;
265        let setter = self.setter;
266
267        // Collect entities once — needed for triangular pairing.
268        let left_entities: Vec<EntityReference> =
269            self.left_entity_selector.iter(score_director).collect();
270        let right_entities: Vec<EntityReference> =
271            self.right_entity_selector.iter(score_director).collect();
272
273        // Eager triangular pairing — no Rc, no shared pointers.
274        let mut moves =
275            Vec::with_capacity(left_entities.len() * left_entities.len().saturating_sub(1) / 2);
276        for (i, left) in left_entities.iter().enumerate() {
277            for right in &right_entities[i + 1..] {
278                if left.descriptor_index == right.descriptor_index
279                    && left.descriptor_index == descriptor_index
280                {
281                    moves.push(SwapMove::new(
282                        left.entity_index,
283                        right.entity_index,
284                        getter,
285                        setter,
286                        variable_name,
287                        descriptor_index,
288                    ));
289                }
290            }
291        }
292
293        moves.into_iter()
294    }
295
296    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
297        let left_count = self.left_entity_selector.size(score_director);
298        let right_count = self.right_entity_selector.size(score_director);
299
300        if left_count == right_count {
301            left_count * left_count.saturating_sub(1) / 2
302        } else {
303            left_count * right_count / 2
304        }
305    }
306}
307
308/* ---------------------------------------------------------------------------
309EitherMove adaptor selectors
310---------------------------------------------------------------------------
311*/
312
313/// Wraps a `ChangeMoveSelector` to yield `EitherMove::Change`.
314pub struct EitherChangeMoveSelector<S, V, ES, VS> {
315    inner: ChangeMoveSelector<S, V, ES, VS>,
316}
317
318impl<S, V: Debug, ES: Debug, VS: Debug> Debug for EitherChangeMoveSelector<S, V, ES, VS> {
319    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
320        f.debug_struct("EitherChangeMoveSelector")
321            .field("inner", &self.inner)
322            .finish()
323    }
324}
325
326impl<S: PlanningSolution, V: Clone + Send + Sync + Debug + 'static>
327    EitherChangeMoveSelector<S, V, FromSolutionEntitySelector, StaticValueSelector<S, V>>
328{
329    pub fn simple(
330        getter: fn(&S, usize) -> Option<V>,
331        setter: fn(&mut S, usize, Option<V>),
332        descriptor_index: usize,
333        variable_name: &'static str,
334        values: Vec<V>,
335    ) -> Self {
336        Self {
337            inner: ChangeMoveSelector::simple(
338                getter,
339                setter,
340                descriptor_index,
341                variable_name,
342                values,
343            ),
344        }
345    }
346}
347
348impl<S, V, ES, VS> MoveSelector<S, EitherMove<S, V>> for EitherChangeMoveSelector<S, V, ES, VS>
349where
350    S: PlanningSolution,
351    V: Clone + PartialEq + Send + Sync + Debug + 'static,
352    ES: EntitySelector<S>,
353    VS: ValueSelector<S, V>,
354{
355    fn iter_moves<'a, D: Director<S>>(
356        &'a self,
357        score_director: &'a D,
358    ) -> impl Iterator<Item = EitherMove<S, V>> + 'a {
359        self.inner
360            .iter_moves(score_director)
361            .map(EitherMove::Change)
362    }
363
364    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
365        self.inner.size(score_director)
366    }
367}
368
369/// Wraps a `SwapMoveSelector` to yield `EitherMove::Swap`.
370pub struct EitherSwapMoveSelector<S, V, LES, RES> {
371    inner: SwapMoveSelector<S, V, LES, RES>,
372}
373
374impl<S, V: Debug, LES: Debug, RES: Debug> Debug for EitherSwapMoveSelector<S, V, LES, RES> {
375    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
376        f.debug_struct("EitherSwapMoveSelector")
377            .field("inner", &self.inner)
378            .finish()
379    }
380}
381
382impl<S: PlanningSolution, V>
383    EitherSwapMoveSelector<S, V, FromSolutionEntitySelector, FromSolutionEntitySelector>
384{
385    pub fn simple(
386        getter: fn(&S, usize) -> Option<V>,
387        setter: fn(&mut S, usize, Option<V>),
388        descriptor_index: usize,
389        variable_name: &'static str,
390    ) -> Self {
391        Self {
392            inner: SwapMoveSelector::simple(getter, setter, descriptor_index, variable_name),
393        }
394    }
395}
396
397impl<S, V, LES, RES> MoveSelector<S, EitherMove<S, V>> for EitherSwapMoveSelector<S, V, LES, RES>
398where
399    S: PlanningSolution,
400    V: Clone + PartialEq + Send + Sync + Debug + 'static,
401    LES: EntitySelector<S>,
402    RES: EntitySelector<S>,
403{
404    fn iter_moves<'a, D: Director<S>>(
405        &'a self,
406        score_director: &'a D,
407    ) -> impl Iterator<Item = EitherMove<S, V>> + 'a {
408        self.inner.iter_moves(score_director).map(EitherMove::Swap)
409    }
410
411    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
412        self.inner.size(score_director)
413    }
414}
415
416/* ---------------------------------------------------------------------------
417ListMoveImpl adaptor selectors
418---------------------------------------------------------------------------
419*/
420
421use super::k_opt::{KOptMoveSelector, ListPositionDistanceMeter, NearbyKOptMoveSelector};
422use super::list_change::ListChangeMoveSelector;
423use super::list_ruin::ListRuinMoveSelector;
424
425/// Wraps a `ListChangeMoveSelector` to yield `ListMoveImpl::ListChange`.
426pub struct ListMoveListChangeSelector<S, V, ES> {
427    inner: ListChangeMoveSelector<S, V, ES>,
428}
429
430impl<S, V: Debug, ES: Debug> Debug for ListMoveListChangeSelector<S, V, ES> {
431    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
432        f.debug_struct("ListMoveListChangeSelector")
433            .field("inner", &self.inner)
434            .finish()
435    }
436}
437
438impl<S, V, ES> ListMoveListChangeSelector<S, V, ES> {
439    /// Wraps an existing [`ListChangeMoveSelector`].
440    pub fn new(inner: ListChangeMoveSelector<S, V, ES>) -> Self {
441        Self { inner }
442    }
443}
444
445impl<S, V, ES> MoveSelector<S, ListMoveImpl<S, V>> for ListMoveListChangeSelector<S, V, ES>
446where
447    S: PlanningSolution,
448    V: Clone + PartialEq + Send + Sync + Debug + 'static,
449    ES: EntitySelector<S>,
450{
451    fn iter_moves<'a, D: Director<S>>(
452        &'a self,
453        score_director: &'a D,
454    ) -> impl Iterator<Item = ListMoveImpl<S, V>> + 'a {
455        self.inner
456            .iter_moves(score_director)
457            .map(ListMoveImpl::ListChange)
458    }
459
460    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
461        self.inner.size(score_director)
462    }
463}
464
465/// Wraps a `KOptMoveSelector` to yield `ListMoveImpl::KOpt`.
466pub struct ListMoveKOptSelector<S, V, ES> {
467    inner: KOptMoveSelector<S, V, ES>,
468}
469
470impl<S, V: Debug, ES: Debug> Debug for ListMoveKOptSelector<S, V, ES> {
471    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
472        f.debug_struct("ListMoveKOptSelector")
473            .field("inner", &self.inner)
474            .finish()
475    }
476}
477
478impl<S, V, ES> ListMoveKOptSelector<S, V, ES> {
479    /// Wraps an existing [`KOptMoveSelector`].
480    pub fn new(inner: KOptMoveSelector<S, V, ES>) -> Self {
481        Self { inner }
482    }
483}
484
485impl<S, V, ES> MoveSelector<S, ListMoveImpl<S, V>> for ListMoveKOptSelector<S, V, ES>
486where
487    S: PlanningSolution,
488    V: Clone + PartialEq + Send + Sync + Debug + 'static,
489    ES: EntitySelector<S>,
490{
491    fn iter_moves<'a, D: Director<S>>(
492        &'a self,
493        score_director: &'a D,
494    ) -> impl Iterator<Item = ListMoveImpl<S, V>> + 'a {
495        self.inner
496            .iter_moves(score_director)
497            .map(ListMoveImpl::KOpt)
498    }
499
500    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
501        self.inner.size(score_director)
502    }
503}
504
505/// Wraps a `NearbyKOptMoveSelector` to yield `ListMoveImpl::KOpt`.
506pub struct ListMoveNearbyKOptSelector<S, V, D: ListPositionDistanceMeter<S>, ES> {
507    inner: NearbyKOptMoveSelector<S, V, D, ES>,
508}
509
510impl<S, V: Debug, D: ListPositionDistanceMeter<S>, ES: Debug> Debug
511    for ListMoveNearbyKOptSelector<S, V, D, ES>
512{
513    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
514        f.debug_struct("ListMoveNearbyKOptSelector")
515            .field("inner", &self.inner)
516            .finish()
517    }
518}
519
520impl<S, V, D: ListPositionDistanceMeter<S>, ES> ListMoveNearbyKOptSelector<S, V, D, ES> {
521    /// Wraps an existing [`NearbyKOptMoveSelector`].
522    pub fn new(inner: NearbyKOptMoveSelector<S, V, D, ES>) -> Self {
523        Self { inner }
524    }
525}
526
527impl<S, V, D, ES> MoveSelector<S, ListMoveImpl<S, V>> for ListMoveNearbyKOptSelector<S, V, D, ES>
528where
529    S: PlanningSolution,
530    V: Clone + PartialEq + Send + Sync + Debug + 'static,
531    D: ListPositionDistanceMeter<S> + 'static,
532    ES: EntitySelector<S>,
533{
534    fn iter_moves<'a, Dir: Director<S>>(
535        &'a self,
536        score_director: &'a Dir,
537    ) -> impl Iterator<Item = ListMoveImpl<S, V>> + 'a {
538        self.inner
539            .iter_moves(score_director)
540            .map(ListMoveImpl::KOpt)
541    }
542
543    fn size<Dir: Director<S>>(&self, score_director: &Dir) -> usize {
544        self.inner.size(score_director)
545    }
546}
547
548/// Wraps a `ListRuinMoveSelector` to yield `ListMoveImpl::ListRuin`.
549pub struct ListMoveListRuinSelector<S, V> {
550    inner: ListRuinMoveSelector<S, V>,
551}
552
553impl<S, V: Debug> Debug for ListMoveListRuinSelector<S, V> {
554    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
555        f.debug_struct("ListMoveListRuinSelector")
556            .field("inner", &self.inner)
557            .finish()
558    }
559}
560
561impl<S, V> ListMoveListRuinSelector<S, V> {
562    /// Wraps an existing [`ListRuinMoveSelector`].
563    pub fn new(inner: ListRuinMoveSelector<S, V>) -> Self {
564        Self { inner }
565    }
566}
567
568impl<S, V> MoveSelector<S, ListMoveImpl<S, V>> for ListMoveListRuinSelector<S, V>
569where
570    S: PlanningSolution,
571    V: Clone + PartialEq + Send + Sync + Debug + 'static,
572{
573    fn iter_moves<'a, D: Director<S>>(
574        &'a self,
575        score_director: &'a D,
576    ) -> impl Iterator<Item = ListMoveImpl<S, V>> + 'a {
577        self.inner
578            .iter_moves(score_director)
579            .map(ListMoveImpl::ListRuin)
580    }
581
582    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
583        self.inner.size(score_director)
584    }
585}
586
587/* Note: ListMoveListSwapSelector, ListMoveSubListChangeSelector,
588ListMoveSubListSwapSelector, and ListMoveListReverseSelector are defined
589in their respective selector source files (list_swap.rs, sublist_change.rs,
590sublist_swap.rs, list_reverse.rs) alongside the selectors they wrap.
591*/
592
593#[cfg(test)]
594#[path = "move_selector_tests.rs"]
595mod tests;
solverforge_solver/heuristic/selector/move_selector.rs

solverforge_solver/heuristic/selector/
move_selector.rs
