solverforge_solver/builder/
list_selector.rs

1// List variable move selector enum and builder.
2
3use std::fmt::Debug;
4
5use solverforge_config::MoveSelectorConfig;
6use solverforge_core::domain::PlanningSolution;
7use solverforge_scoring::Director;
8
9use crate::heuristic::r#move::{ListMoveImpl, MoveArena};
10use crate::heuristic::selector::decorator::VecUnionSelector;
11use crate::heuristic::selector::k_opt::KOptConfig;
12use crate::heuristic::selector::move_selector::{
13    ListMoveKOptSelector, ListMoveListChangeSelector, ListMoveListRuinSelector,
14    ListMoveNearbyKOptSelector, MoveSelector,
15};
16use crate::heuristic::selector::nearby_list_change::CrossEntityDistanceMeter;
17
18use super::context::IntraDistanceAdapter;
19use crate::heuristic::selector::{
20    FromSolutionEntitySelector, ListMoveListReverseSelector, ListMoveListSwapSelector,
21    ListMoveNearbyListChangeSelector, ListMoveNearbyListSwapSelector,
22    ListMoveSubListChangeSelector, ListMoveSubListSwapSelector,
23};
24
25use super::context::ListContext;
26
27/// A monomorphized leaf selector for list planning variables.
28///
29/// Each variant wraps one of the available list move selector wrapper types.
30/// Allows `VecUnionSelector<S, ListMoveImpl<S, V>, ListLeafSelector<S, V, DM, IDM>>` to have
31/// a single concrete type regardless of configuration.
32pub enum ListLeafSelector<S, V, DM, IDM>
33where
34    S: PlanningSolution,
35    V: Clone + PartialEq + Send + Sync + Debug + 'static,
36    DM: CrossEntityDistanceMeter<S>,
37    IDM: CrossEntityDistanceMeter<S>,
38{
39    // Nearby list change (distance-pruned relocation).
40    NearbyListChange(ListMoveNearbyListChangeSelector<S, V, DM, FromSolutionEntitySelector>),
41    // Nearby list swap (distance-pruned swap).
42    NearbyListSwap(ListMoveNearbyListSwapSelector<S, V, DM, FromSolutionEntitySelector>),
43    // List reverse (2-opt).
44    ListReverse(ListMoveListReverseSelector<S, V, FromSolutionEntitySelector>),
45    // Sublist change (Or-opt).
46    SubListChange(ListMoveSubListChangeSelector<S, V, FromSolutionEntitySelector>),
47    // K-opt.
48    KOpt(ListMoveKOptSelector<S, V, FromSolutionEntitySelector>),
49    // Nearby k-opt (distance-pruned).
50    NearbyKOpt(
51        ListMoveNearbyKOptSelector<S, V, IntraDistanceAdapter<IDM>, FromSolutionEntitySelector>,
52    ),
53    // List ruin (LNS).
54    ListRuin(ListMoveListRuinSelector<S, V>),
55    // Full list change (unrestricted relocation).
56    ListChange(ListMoveListChangeSelector<S, V, FromSolutionEntitySelector>),
57    // Full list swap (unrestricted swap).
58    ListSwap(ListMoveListSwapSelector<S, V, FromSolutionEntitySelector>),
59    // Sublist swap.
60    SubListSwap(ListMoveSubListSwapSelector<S, V, FromSolutionEntitySelector>),
61}
62
63impl<S, V, DM, IDM> Debug for ListLeafSelector<S, V, DM, IDM>
64where
65    S: PlanningSolution,
66    V: Clone + PartialEq + Send + Sync + Debug + 'static,
67    DM: CrossEntityDistanceMeter<S>,
68    IDM: CrossEntityDistanceMeter<S>,
69{
70    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
71        match self {
72            Self::NearbyListChange(s) => write!(f, "ListLeafSelector::NearbyListChange({s:?})"),
73            Self::NearbyListSwap(s) => write!(f, "ListLeafSelector::NearbyListSwap({s:?})"),
74            Self::ListReverse(s) => write!(f, "ListLeafSelector::ListReverse({s:?})"),
75            Self::SubListChange(s) => write!(f, "ListLeafSelector::SubListChange({s:?})"),
76            Self::KOpt(s) => write!(f, "ListLeafSelector::KOpt({s:?})"),
77            Self::NearbyKOpt(s) => write!(f, "ListLeafSelector::NearbyKOpt({s:?})"),
78            Self::ListRuin(s) => write!(f, "ListLeafSelector::ListRuin({s:?})"),
79            Self::ListChange(s) => write!(f, "ListLeafSelector::ListChange({s:?})"),
80            Self::ListSwap(s) => write!(f, "ListLeafSelector::ListSwap({s:?})"),
81            Self::SubListSwap(s) => write!(f, "ListLeafSelector::SubListSwap({s:?})"),
82        }
83    }
84}
85
86impl<S, V, DM, IDM> MoveSelector<S, ListMoveImpl<S, V>> for ListLeafSelector<S, V, DM, IDM>
87where
88    S: PlanningSolution,
89    V: Clone + PartialEq + Send + Sync + Debug + 'static,
90    DM: CrossEntityDistanceMeter<S>,
91    IDM: CrossEntityDistanceMeter<S> + 'static,
92{
93    fn iter_moves<'a, D: Director<S>>(
94        &'a self,
95        score_director: &'a D,
96    ) -> impl Iterator<Item = ListMoveImpl<S, V>> + 'a {
97        enum ListLeafIter<A, B, C, DIter, E, F, G, H, I, J> {
98            NearbyListChange(A),
99            NearbyListSwap(B),
100            ListReverse(C),
101            SubListChange(DIter),
102            KOpt(E),
103            NearbyKOpt(F),
104            ListRuin(G),
105            ListChange(H),
106            ListSwap(I),
107            SubListSwap(J),
108        }
109
110        impl<T, A, B, C, DIter, E, F, G, H, I, J> Iterator
111            for ListLeafIter<A, B, C, DIter, E, F, G, H, I, J>
112        where
113            A: Iterator<Item = T>,
114            B: Iterator<Item = T>,
115            C: Iterator<Item = T>,
116            DIter: Iterator<Item = T>,
117            E: Iterator<Item = T>,
118            F: Iterator<Item = T>,
119            G: Iterator<Item = T>,
120            H: Iterator<Item = T>,
121            I: Iterator<Item = T>,
122            J: Iterator<Item = T>,
123        {
124            type Item = T;
125
126            fn next(&mut self) -> Option<Self::Item> {
127                match self {
128                    Self::NearbyListChange(iter) => iter.next(),
129                    Self::NearbyListSwap(iter) => iter.next(),
130                    Self::ListReverse(iter) => iter.next(),
131                    Self::SubListChange(iter) => iter.next(),
132                    Self::KOpt(iter) => iter.next(),
133                    Self::NearbyKOpt(iter) => iter.next(),
134                    Self::ListRuin(iter) => iter.next(),
135                    Self::ListChange(iter) => iter.next(),
136                    Self::ListSwap(iter) => iter.next(),
137                    Self::SubListSwap(iter) => iter.next(),
138                }
139            }
140        }
141
142        match self {
143            Self::NearbyListChange(s) => {
144                ListLeafIter::NearbyListChange(s.iter_moves(score_director))
145            }
146            Self::NearbyListSwap(s) => ListLeafIter::NearbyListSwap(s.iter_moves(score_director)),
147            Self::ListReverse(s) => ListLeafIter::ListReverse(s.iter_moves(score_director)),
148            Self::SubListChange(s) => ListLeafIter::SubListChange(s.iter_moves(score_director)),
149            Self::KOpt(s) => ListLeafIter::KOpt(s.iter_moves(score_director)),
150            Self::NearbyKOpt(s) => ListLeafIter::NearbyKOpt(s.iter_moves(score_director)),
151            Self::ListRuin(s) => ListLeafIter::ListRuin(s.iter_moves(score_director)),
152            Self::ListChange(s) => ListLeafIter::ListChange(s.iter_moves(score_director)),
153            Self::ListSwap(s) => ListLeafIter::ListSwap(s.iter_moves(score_director)),
154            Self::SubListSwap(s) => ListLeafIter::SubListSwap(s.iter_moves(score_director)),
155        }
156    }
157
158    fn size<D: Director<S>>(&self, score_director: &D) -> usize {
159        match self {
160            Self::NearbyListChange(s) => s.size(score_director),
161            Self::NearbyListSwap(s) => s.size(score_director),
162            Self::ListReverse(s) => s.size(score_director),
163            Self::SubListChange(s) => s.size(score_director),
164            Self::KOpt(s) => s.size(score_director),
165            Self::NearbyKOpt(s) => s.size(score_director),
166            Self::ListRuin(s) => s.size(score_director),
167            Self::ListChange(s) => s.size(score_director),
168            Self::ListSwap(s) => s.size(score_director),
169            Self::SubListSwap(s) => s.size(score_director),
170        }
171    }
172
173    fn append_moves<D: Director<S>>(
174        &self,
175        score_director: &D,
176        arena: &mut MoveArena<ListMoveImpl<S, V>>,
177    ) {
178        match self {
179            Self::NearbyListChange(s) => arena.extend(s.iter_moves(score_director)),
180            Self::NearbyListSwap(s) => arena.extend(s.iter_moves(score_director)),
181            Self::ListReverse(s) => arena.extend(s.iter_moves(score_director)),
182            Self::SubListChange(s) => arena.extend(s.iter_moves(score_director)),
183            Self::KOpt(s) => arena.extend(s.iter_moves(score_director)),
184            Self::NearbyKOpt(s) => arena.extend(s.iter_moves(score_director)),
185            Self::ListRuin(s) => arena.extend(s.iter_moves(score_director)),
186            Self::ListChange(s) => arena.extend(s.iter_moves(score_director)),
187            Self::ListSwap(s) => arena.extend(s.iter_moves(score_director)),
188            Self::SubListSwap(s) => arena.extend(s.iter_moves(score_director)),
189        }
190    }
191}
192
193/// Builder that constructs a `VecUnionSelector` of `ListLeafSelector` from config.
194pub struct ListMoveSelectorBuilder;
195
196impl ListMoveSelectorBuilder {
197    /// Builds a `VecUnionSelector` from move selector config and domain context.
198    ///
199    /// Default (no config): `Union(NearbyListChange(20), NearbyListSwap(20), ListReverse)`
200    pub fn build<S, V, DM, IDM>(
201        config: Option<&MoveSelectorConfig>,
202        ctx: &ListContext<S, V, DM, IDM>,
203        random_seed: Option<u64>,
204    ) -> VecUnionSelector<S, ListMoveImpl<S, V>, ListLeafSelector<S, V, DM, IDM>>
205    where
206        S: PlanningSolution,
207        V: Clone + PartialEq + Send + Sync + Debug + 'static,
208        DM: CrossEntityDistanceMeter<S> + Clone,
209        IDM: CrossEntityDistanceMeter<S> + Clone,
210    {
211        let mut leaves: Vec<ListLeafSelector<S, V, DM, IDM>> = Vec::new();
212        match config {
213            None => {
214                Self::push_nearby_change(&mut leaves, ctx, 20);
215                Self::push_nearby_swap(&mut leaves, ctx, 20);
216                Self::push_list_reverse(&mut leaves, ctx);
217            }
218            Some(cfg) => Self::collect_leaves(cfg, ctx, random_seed, &mut leaves),
219        }
220        assert!(
221            !leaves.is_empty(),
222            "stock move selector configuration produced no list neighborhoods"
223        );
224        VecUnionSelector::new(leaves)
225    }
226
227    fn collect_leaves<S, V, DM, IDM>(
228        config: &MoveSelectorConfig,
229        ctx: &ListContext<S, V, DM, IDM>,
230        random_seed: Option<u64>,
231        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
232    ) where
233        S: PlanningSolution,
234        V: Clone + PartialEq + Send + Sync + Debug + 'static,
235        DM: CrossEntityDistanceMeter<S> + Clone,
236        IDM: CrossEntityDistanceMeter<S> + Clone,
237    {
238        match config {
239            MoveSelectorConfig::NearbyListChangeMoveSelector(c) => {
240                Self::push_nearby_change(out, ctx, c.max_nearby);
241            }
242            MoveSelectorConfig::NearbyListSwapMoveSelector(c) => {
243                Self::push_nearby_swap(out, ctx, c.max_nearby);
244            }
245            MoveSelectorConfig::ListReverseMoveSelector(_) => {
246                Self::push_list_reverse(out, ctx);
247            }
248            MoveSelectorConfig::SubListChangeMoveSelector(c) => {
249                Self::push_sublist_change(out, ctx, c.min_sublist_size, c.max_sublist_size);
250            }
251            MoveSelectorConfig::SubListSwapMoveSelector(c) => {
252                Self::push_sublist_swap(out, ctx, c.min_sublist_size, c.max_sublist_size);
253            }
254            MoveSelectorConfig::KOptMoveSelector(c) => {
255                Self::push_kopt(out, ctx, c.k, c.min_segment_len, c.max_nearby);
256            }
257            MoveSelectorConfig::ListRuinMoveSelector(c) => {
258                Self::push_list_ruin(
259                    out,
260                    ctx,
261                    c.min_ruin_count,
262                    c.max_ruin_count,
263                    c.moves_per_step,
264                    random_seed,
265                );
266            }
267            MoveSelectorConfig::SelectedCountLimitMoveSelector(_) => {
268                panic!(
269                    "selected_count_limit_move_selector must be handled by the unified stock runtime"
270                );
271            }
272            MoveSelectorConfig::ListChangeMoveSelector(_) => {
273                Self::push_list_change(out, ctx);
274            }
275            MoveSelectorConfig::ListSwapMoveSelector(_) => {
276                Self::push_list_swap(out, ctx);
277            }
278            MoveSelectorConfig::UnionMoveSelector(u) => {
279                for child in &u.selectors {
280                    Self::collect_leaves(child, ctx, random_seed, out);
281                }
282            }
283            MoveSelectorConfig::ChangeMoveSelector(_) | MoveSelectorConfig::SwapMoveSelector(_) => {
284                panic!("standard move selector configured against a list-variable stock context");
285            }
286            MoveSelectorConfig::CartesianProductMoveSelector(_) => {
287                panic!("cartesian_product move selectors are not supported in stock solving");
288            }
289        }
290    }
291
292    fn push_nearby_change<S, V, DM, IDM>(
293        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
294        ctx: &ListContext<S, V, DM, IDM>,
295        max_nearby: usize,
296    ) where
297        S: PlanningSolution,
298        V: Clone + PartialEq + Send + Sync + Debug + 'static,
299        DM: CrossEntityDistanceMeter<S> + Clone,
300        IDM: CrossEntityDistanceMeter<S> + Clone,
301    {
302        use crate::heuristic::selector::nearby_list_change::NearbyListChangeMoveSelector;
303
304        let inner = NearbyListChangeMoveSelector::new(
305            FromSolutionEntitySelector::new(ctx.descriptor_index),
306            ctx.cross_distance_meter.clone(),
307            max_nearby,
308            ctx.list_len,
309            ctx.list_remove,
310            ctx.list_insert,
311            ctx.variable_name,
312            ctx.descriptor_index,
313        );
314        out.push(ListLeafSelector::NearbyListChange(
315            ListMoveNearbyListChangeSelector::new(inner),
316        ));
317    }
318
319    fn push_nearby_swap<S, V, DM, IDM>(
320        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
321        ctx: &ListContext<S, V, DM, IDM>,
322        max_nearby: usize,
323    ) where
324        S: PlanningSolution,
325        V: Clone + PartialEq + Send + Sync + Debug + 'static,
326        DM: CrossEntityDistanceMeter<S> + Clone,
327        IDM: CrossEntityDistanceMeter<S> + Clone,
328    {
329        use crate::heuristic::selector::nearby_list_swap::NearbyListSwapMoveSelector;
330
331        let inner = NearbyListSwapMoveSelector::new(
332            FromSolutionEntitySelector::new(ctx.descriptor_index),
333            ctx.cross_distance_meter.clone(),
334            max_nearby,
335            ctx.list_len,
336            ctx.list_get,
337            ctx.list_set,
338            ctx.variable_name,
339            ctx.descriptor_index,
340        );
341        out.push(ListLeafSelector::NearbyListSwap(
342            ListMoveNearbyListSwapSelector::new(inner),
343        ));
344    }
345
346    fn push_list_reverse<S, V, DM, IDM>(
347        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
348        ctx: &ListContext<S, V, DM, IDM>,
349    ) where
350        S: PlanningSolution,
351        V: Clone + PartialEq + Send + Sync + Debug + 'static,
352        DM: CrossEntityDistanceMeter<S> + Clone,
353        IDM: CrossEntityDistanceMeter<S> + Clone,
354    {
355        use crate::heuristic::selector::list_reverse::ListReverseMoveSelector;
356
357        let inner = ListReverseMoveSelector::new(
358            FromSolutionEntitySelector::new(ctx.descriptor_index),
359            ctx.list_len,
360            ctx.list_reverse,
361            ctx.variable_name,
362            ctx.descriptor_index,
363        );
364        out.push(ListLeafSelector::ListReverse(
365            ListMoveListReverseSelector::new(inner),
366        ));
367    }
368
369    fn push_sublist_change<S, V, DM, IDM>(
370        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
371        ctx: &ListContext<S, V, DM, IDM>,
372        min_sublist_size: usize,
373        max_sublist_size: usize,
374    ) where
375        S: PlanningSolution,
376        V: Clone + PartialEq + Send + Sync + Debug + 'static,
377        DM: CrossEntityDistanceMeter<S> + Clone,
378        IDM: CrossEntityDistanceMeter<S> + Clone,
379    {
380        use crate::heuristic::selector::sublist_change::SubListChangeMoveSelector;
381
382        let inner = SubListChangeMoveSelector::new(
383            FromSolutionEntitySelector::new(ctx.descriptor_index),
384            min_sublist_size,
385            max_sublist_size,
386            ctx.list_len,
387            ctx.sublist_remove,
388            ctx.sublist_insert,
389            ctx.variable_name,
390            ctx.descriptor_index,
391        );
392        out.push(ListLeafSelector::SubListChange(
393            ListMoveSubListChangeSelector::new(inner),
394        ));
395    }
396
397    fn push_sublist_swap<S, V, DM, IDM>(
398        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
399        ctx: &ListContext<S, V, DM, IDM>,
400        min_sublist_size: usize,
401        max_sublist_size: usize,
402    ) where
403        S: PlanningSolution,
404        V: Clone + PartialEq + Send + Sync + Debug + 'static,
405        DM: CrossEntityDistanceMeter<S> + Clone,
406        IDM: CrossEntityDistanceMeter<S> + Clone,
407    {
408        use crate::heuristic::selector::sublist_swap::SubListSwapMoveSelector;
409
410        let inner = SubListSwapMoveSelector::new(
411            FromSolutionEntitySelector::new(ctx.descriptor_index),
412            min_sublist_size,
413            max_sublist_size,
414            ctx.list_len,
415            ctx.sublist_remove,
416            ctx.sublist_insert,
417            ctx.variable_name,
418            ctx.descriptor_index,
419        );
420        out.push(ListLeafSelector::SubListSwap(
421            ListMoveSubListSwapSelector::new(inner),
422        ));
423    }
424
425    fn push_kopt<S, V, DM, IDM>(
426        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
427        ctx: &ListContext<S, V, DM, IDM>,
428        k: usize,
429        min_segment_len: usize,
430        max_nearby: usize,
431    ) where
432        S: PlanningSolution,
433        V: Clone + PartialEq + Send + Sync + Debug + 'static,
434        DM: CrossEntityDistanceMeter<S> + Clone,
435        IDM: CrossEntityDistanceMeter<S> + Clone,
436    {
437        use crate::heuristic::selector::k_opt::{KOptMoveSelector, NearbyKOptMoveSelector};
438
439        let config = KOptConfig::new(k.clamp(2, 5)).with_min_segment_len(min_segment_len);
440        if max_nearby > 0 {
441            let adapter = IntraDistanceAdapter(ctx.intra_distance_meter.clone());
442            let inner = NearbyKOptMoveSelector::new(
443                FromSolutionEntitySelector::new(ctx.descriptor_index),
444                adapter,
445                max_nearby,
446                config,
447                ctx.list_len,
448                ctx.sublist_remove,
449                ctx.sublist_insert,
450                ctx.variable_name,
451                ctx.descriptor_index,
452            );
453            out.push(ListLeafSelector::NearbyKOpt(
454                ListMoveNearbyKOptSelector::new(inner),
455            ));
456        } else {
457            let inner = KOptMoveSelector::new(
458                FromSolutionEntitySelector::new(ctx.descriptor_index),
459                config,
460                ctx.list_len,
461                ctx.sublist_remove,
462                ctx.sublist_insert,
463                ctx.variable_name,
464                ctx.descriptor_index,
465            );
466            out.push(ListLeafSelector::KOpt(ListMoveKOptSelector::new(inner)));
467        }
468    }
469
470    fn push_list_ruin<S, V, DM, IDM>(
471        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
472        ctx: &ListContext<S, V, DM, IDM>,
473        min_ruin_count: usize,
474        max_ruin_count: usize,
475        moves_per_step: Option<usize>,
476        random_seed: Option<u64>,
477    ) where
478        S: PlanningSolution,
479        V: Clone + PartialEq + Send + Sync + Debug + 'static,
480        DM: CrossEntityDistanceMeter<S> + Clone,
481        IDM: CrossEntityDistanceMeter<S> + Clone,
482    {
483        use crate::heuristic::selector::list_ruin::ListRuinMoveSelector;
484
485        let inner = ListRuinMoveSelector::new(
486            min_ruin_count.max(1),
487            max_ruin_count.max(1),
488            ctx.entity_count,
489            ctx.list_len,
490            ctx.ruin_remove,
491            ctx.ruin_insert,
492            ctx.variable_name,
493            ctx.descriptor_index,
494        )
495        .with_moves_per_step(moves_per_step.unwrap_or(10).max(1));
496        let inner = if let Some(seed) = random_seed {
497            inner.with_seed(seed)
498        } else {
499            inner
500        };
501        out.push(ListLeafSelector::ListRuin(ListMoveListRuinSelector::new(
502            inner,
503        )));
504    }
505
506    fn push_list_change<S, V, DM, IDM>(
507        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
508        ctx: &ListContext<S, V, DM, IDM>,
509    ) where
510        S: PlanningSolution,
511        V: Clone + PartialEq + Send + Sync + Debug + 'static,
512        DM: CrossEntityDistanceMeter<S> + Clone,
513        IDM: CrossEntityDistanceMeter<S> + Clone,
514    {
515        use crate::heuristic::selector::list_change::ListChangeMoveSelector;
516
517        let inner = ListChangeMoveSelector::new(
518            FromSolutionEntitySelector::new(ctx.descriptor_index),
519            ctx.list_len,
520            ctx.list_remove,
521            ctx.list_insert,
522            ctx.variable_name,
523            ctx.descriptor_index,
524        );
525        out.push(ListLeafSelector::ListChange(
526            ListMoveListChangeSelector::new(inner),
527        ));
528    }
529
530    fn push_list_swap<S, V, DM, IDM>(
531        out: &mut Vec<ListLeafSelector<S, V, DM, IDM>>,
532        ctx: &ListContext<S, V, DM, IDM>,
533    ) where
534        S: PlanningSolution,
535        V: Clone + PartialEq + Send + Sync + Debug + 'static,
536        DM: CrossEntityDistanceMeter<S> + Clone,
537        IDM: CrossEntityDistanceMeter<S> + Clone,
538    {
539        use crate::heuristic::selector::list_swap::ListSwapMoveSelector;
540
541        let inner = ListSwapMoveSelector::new(
542            FromSolutionEntitySelector::new(ctx.descriptor_index),
543            ctx.list_len,
544            ctx.list_get,
545            ctx.list_set,
546            ctx.variable_name,
547            ctx.descriptor_index,
548        );
549        out.push(ListLeafSelector::ListSwap(ListMoveListSwapSelector::new(
550            inner,
551        )));
552    }
553}
554
555#[cfg(test)]
556mod tests {
557    use super::*;
558    use std::any::TypeId;
559    use std::sync::atomic::{AtomicUsize, Ordering};
560    use std::sync::Arc;
561
562    use solverforge_config::{NearbyListSwapMoveConfig, VariableTargetConfig};
563    use solverforge_core::domain::{
564        EntityCollectionExtractor, EntityDescriptor, PlanningSolution, SolutionDescriptor,
565    };
566    use solverforge_core::score::SoftScore;
567    use solverforge_scoring::ScoreDirector;
568
569    #[derive(Clone, Debug)]
570    struct Vehicle {
571        visits: Vec<usize>,
572    }
573
574    #[derive(Clone, Debug)]
575    struct Plan {
576        vehicles: Vec<Vehicle>,
577        score: Option<SoftScore>,
578    }
579
580    impl PlanningSolution for Plan {
581        type Score = SoftScore;
582
583        fn score(&self) -> Option<Self::Score> {
584            self.score
585        }
586
587        fn set_score(&mut self, score: Option<Self::Score>) {
588            self.score = score;
589        }
590    }
591
592    #[derive(Clone, Debug)]
593    struct CountingMeter {
594        calls: Arc<AtomicUsize>,
595    }
596
597    impl CountingMeter {
598        fn new() -> (Self, Arc<AtomicUsize>) {
599            let calls = Arc::new(AtomicUsize::new(0));
600            (
601                Self {
602                    calls: calls.clone(),
603                },
604                calls,
605            )
606        }
607    }
608
609    impl CrossEntityDistanceMeter<Plan> for CountingMeter {
610        fn distance(
611            &self,
612            _solution: &Plan,
613            _src_entity: usize,
614            _src_pos: usize,
615            _dst_entity: usize,
616            _dst_pos: usize,
617        ) -> f64 {
618            self.calls.fetch_add(1, Ordering::SeqCst);
619            1.0
620        }
621    }
622
623    fn descriptor() -> SolutionDescriptor {
624        SolutionDescriptor::new("Plan", TypeId::of::<Plan>()).with_entity(
625            EntityDescriptor::new("Vehicle", TypeId::of::<Vehicle>(), "vehicles").with_extractor(
626                Box::new(EntityCollectionExtractor::new(
627                    "Vehicle",
628                    "vehicles",
629                    |s: &Plan| &s.vehicles,
630                    |s: &mut Plan| &mut s.vehicles,
631                )),
632            ),
633        )
634    }
635
636    fn list_len(s: &Plan, entity_idx: usize) -> usize {
637        s.vehicles
638            .get(entity_idx)
639            .map_or(0, |vehicle| vehicle.visits.len())
640    }
641
642    fn list_remove(s: &mut Plan, entity_idx: usize, pos: usize) -> Option<usize> {
643        let visits = &mut s.vehicles.get_mut(entity_idx)?.visits;
644        if pos < visits.len() {
645            Some(visits.remove(pos))
646        } else {
647            None
648        }
649    }
650
651    fn list_insert(s: &mut Plan, entity_idx: usize, pos: usize, value: usize) {
652        if let Some(vehicle) = s.vehicles.get_mut(entity_idx) {
653            vehicle.visits.insert(pos, value);
654        }
655    }
656
657    fn list_get(s: &Plan, entity_idx: usize, pos: usize) -> Option<usize> {
658        s.vehicles
659            .get(entity_idx)
660            .and_then(|vehicle| vehicle.visits.get(pos))
661            .copied()
662    }
663
664    fn list_set(s: &mut Plan, entity_idx: usize, pos: usize, value: usize) {
665        if let Some(vehicle) = s.vehicles.get_mut(entity_idx) {
666            vehicle.visits[pos] = value;
667        }
668    }
669
670    fn list_reverse(s: &mut Plan, entity_idx: usize, start: usize, end: usize) {
671        if let Some(vehicle) = s.vehicles.get_mut(entity_idx) {
672            vehicle.visits[start..end].reverse();
673        }
674    }
675
676    fn sublist_remove(s: &mut Plan, entity_idx: usize, start: usize, end: usize) -> Vec<usize> {
677        if let Some(vehicle) = s.vehicles.get_mut(entity_idx) {
678            vehicle.visits.drain(start..end).collect()
679        } else {
680            Vec::new()
681        }
682    }
683
684    fn sublist_insert(s: &mut Plan, entity_idx: usize, pos: usize, values: Vec<usize>) {
685        if let Some(vehicle) = s.vehicles.get_mut(entity_idx) {
686            vehicle.visits.splice(pos..pos, values);
687        }
688    }
689
690    fn ruin_remove(s: &mut Plan, entity_idx: usize, pos: usize) -> usize {
691        s.vehicles[entity_idx].visits.remove(pos)
692    }
693
694    fn ruin_insert(s: &mut Plan, entity_idx: usize, pos: usize, value: usize) {
695        s.vehicles[entity_idx].visits.insert(pos, value);
696    }
697
698    fn entity_count(s: &Plan) -> usize {
699        s.vehicles.len()
700    }
701
702    #[test]
703    fn nearby_list_swap_uses_cross_entity_meter() {
704        let (cross_meter, cross_calls) = CountingMeter::new();
705        let (intra_meter, intra_calls) = CountingMeter::new();
706        let ctx = ListContext::new(
707            list_len,
708            list_remove,
709            list_insert,
710            list_get,
711            list_set,
712            list_reverse,
713            sublist_remove,
714            sublist_insert,
715            ruin_remove,
716            ruin_insert,
717            entity_count,
718            cross_meter,
719            intra_meter,
720            "visits",
721            0,
722        );
723        let config = MoveSelectorConfig::NearbyListSwapMoveSelector(NearbyListSwapMoveConfig {
724            max_nearby: 4,
725            target: VariableTargetConfig::default(),
726        });
727        let selector = ListMoveSelectorBuilder::build(Some(&config), &ctx, None);
728        let solution = Plan {
729            vehicles: vec![Vehicle { visits: vec![10] }, Vehicle { visits: vec![20] }],
730            score: None,
731        };
732        let director = ScoreDirector::simple(solution, descriptor(), |s, descriptor_index| {
733            if descriptor_index == 0 {
734                s.vehicles.len()
735            } else {
736                0
737            }
738        });
739
740        let moves: Vec<_> = selector.iter_moves(&director).collect();
741
742        assert_eq!(moves.len(), 1, "expected a single inter-entity swap");
743        assert!(
744            cross_calls.load(Ordering::SeqCst) > 0,
745            "nearby_list_swap must evaluate distances through the cross-entity meter"
746        );
747        assert_eq!(
748            intra_calls.load(Ordering::SeqCst),
749            0,
750            "nearby_list_swap must not consult the intra-route meter"
751        );
752    }
753}
solverforge_solver/builder/list_selector.rs

solverforge_solver/builder/
list_selector.rs
