solverforge_solver/heuristic/move/
list_union.rs

1/* ListMoveUnion - a monomorphized union of all list-variable move types.
2
3This allows local search to combine all list move types in a single arena
4without trait-object dispatch.
5*/
6
7use std::borrow::Cow;
8use std::fmt::Debug;
9
10use solverforge_core::domain::PlanningSolution;
11use solverforge_scoring::Director;
12
13use crate::stats::CandidateTraceIdentity;
14
15use super::{
16    KOptMove, ListChangeMove, ListMultiSwapMove, ListPermuteMove, ListReverseMove, ListRuinMove,
17    ListSwapMove, Move, MoveTabuSignature, SublistChangeMove, SublistSwapMove,
18};
19
20/// A monomorphized union of all list-variable move types.
21///
22/// Implements `Move<S>` by delegating to the inner variant.
23/// Enables combining `ListChangeMoveSelector`, `ListSwapMoveSelector`,
24/// `ListPermuteMoveSelector`, `SublistChangeMoveSelector`, `SublistSwapMoveSelector`,
25/// `ListReverseMoveSelector`, `KOptMoveSelector`, and
26/// `ListRuinMoveSelector` without type erasure.
27///
28/// # Example
29///
30/// ```
31/// use solverforge_solver::heuristic::r#move::ListMoveUnion;
32/// ```
33#[allow(clippy::large_enum_variant)]
34pub enum ListMoveUnion<S, V> {
35    ListChange(ListChangeMove<S, V>),
36    ListSwap(ListSwapMove<S, V>),
37    ListMultiSwap(ListMultiSwapMove<S, V>),
38    ListPermute(ListPermuteMove<S, V>),
39    SublistChange(SublistChangeMove<S, V>),
40    SublistSwap(SublistSwapMove<S, V>),
41    ListReverse(ListReverseMove<S, V>),
42    KOpt(KOptMove<S, V>),
43    ListRuin(ListRuinMove<S, V>),
44}
45
46pub enum ListMoveUnionUndo<S, V>
47where
48    S: PlanningSolution,
49    V: Clone + PartialEq + Send + Sync + Debug + 'static,
50{
51    ListChange(<ListChangeMove<S, V> as Move<S>>::Undo),
52    ListSwap(<ListSwapMove<S, V> as Move<S>>::Undo),
53    ListMultiSwap(<ListMultiSwapMove<S, V> as Move<S>>::Undo),
54    ListPermute(<ListPermuteMove<S, V> as Move<S>>::Undo),
55    SublistChange(<SublistChangeMove<S, V> as Move<S>>::Undo),
56    SublistSwap(<SublistSwapMove<S, V> as Move<S>>::Undo),
57    ListReverse(<ListReverseMove<S, V> as Move<S>>::Undo),
58    KOpt(<KOptMove<S, V> as Move<S>>::Undo),
59    ListRuin(<ListRuinMove<S, V> as Move<S>>::Undo),
60}
61
62impl<S, V> Debug for ListMoveUnion<S, V>
63where
64    S: PlanningSolution,
65    V: Clone + PartialEq + Send + Sync + Debug + 'static,
66{
67    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
68        match self {
69            Self::ListChange(m) => m.fmt(f),
70            Self::ListSwap(m) => m.fmt(f),
71            Self::ListMultiSwap(m) => m.fmt(f),
72            Self::ListPermute(m) => m.fmt(f),
73            Self::SublistChange(m) => m.fmt(f),
74            Self::SublistSwap(m) => m.fmt(f),
75            Self::ListReverse(m) => m.fmt(f),
76            Self::KOpt(m) => m.fmt(f),
77            Self::ListRuin(m) => m.fmt(f),
78        }
79    }
80}
81
82impl<S, V> Move<S> for ListMoveUnion<S, V>
83where
84    S: PlanningSolution,
85    V: Clone + PartialEq + Send + Sync + Debug + 'static,
86{
87    type Undo = ListMoveUnionUndo<S, V>;
88
89    fn is_doable<D: Director<S>>(&self, score_director: &D) -> bool {
90        match self {
91            Self::ListChange(m) => m.is_doable(score_director),
92            Self::ListSwap(m) => m.is_doable(score_director),
93            Self::ListMultiSwap(m) => m.is_doable(score_director),
94            Self::ListPermute(m) => m.is_doable(score_director),
95            Self::SublistChange(m) => m.is_doable(score_director),
96            Self::SublistSwap(m) => m.is_doable(score_director),
97            Self::ListReverse(m) => m.is_doable(score_director),
98            Self::KOpt(m) => m.is_doable(score_director),
99            Self::ListRuin(m) => m.is_doable(score_director),
100        }
101    }
102
103    fn do_move<D: Director<S>>(&self, score_director: &mut D) -> Self::Undo {
104        match self {
105            Self::ListChange(m) => {
106                m.do_move(score_director);
107                ListMoveUnionUndo::ListChange(())
108            }
109            Self::ListSwap(m) => {
110                m.do_move(score_director);
111                ListMoveUnionUndo::ListSwap(())
112            }
113            Self::ListMultiSwap(m) => {
114                m.do_move(score_director);
115                ListMoveUnionUndo::ListMultiSwap(())
116            }
117            Self::ListPermute(m) => ListMoveUnionUndo::ListPermute(m.do_move(score_director)),
118            Self::SublistChange(m) => {
119                m.do_move(score_director);
120                ListMoveUnionUndo::SublistChange(())
121            }
122            Self::SublistSwap(m) => {
123                m.do_move(score_director);
124                ListMoveUnionUndo::SublistSwap(())
125            }
126            Self::ListReverse(m) => {
127                m.do_move(score_director);
128                ListMoveUnionUndo::ListReverse(())
129            }
130            Self::KOpt(m) => ListMoveUnionUndo::KOpt(m.do_move(score_director)),
131            Self::ListRuin(m) => ListMoveUnionUndo::ListRuin(m.do_move(score_director)),
132        }
133    }
134
135    fn do_move_with_scratch<D: Director<S>>(
136        &self,
137        score_director: &mut D,
138        journal_pool: &mut Vec<Self::Undo>,
139    ) -> Self::Undo {
140        match self {
141            Self::KOpt(m) => {
142                // The outer pool stores union undos; a K-opt-shaped entry
143                // carries an inner journal whose inlined capacity this arm
144                // reuses.
145                let mut journal = journal_pool
146                    .iter()
147                    .rposition(|undo| matches!(undo, ListMoveUnionUndo::KOpt(_)))
148                    .map(|index| match journal_pool.swap_remove(index) {
149                        ListMoveUnionUndo::KOpt(journal) => journal,
150                        _ => unreachable!("rposition matched the KOpt shape"),
151                    })
152                    .unwrap_or_default();
153                m.do_move_into_journal(score_director, &mut journal);
154                ListMoveUnionUndo::KOpt(journal)
155            }
156            other => other.do_move(score_director),
157        }
158    }
159
160    fn undo_move_with_scratch<D: Director<S>>(
161        &self,
162        score_director: &mut D,
163        undo: Self::Undo,
164        journal_pool: &mut Vec<Self::Undo>,
165    ) {
166        match (self, undo) {
167            (Self::KOpt(m), ListMoveUnionUndo::KOpt(undo)) => {
168                m.undo_move(score_director, undo);
169                journal_pool.push(ListMoveUnionUndo::KOpt(
170                    <KOptMove<S, V> as Move<S>>::Undo::new(),
171                ));
172            }
173            (other, undo) => other.undo_move(score_director, undo),
174        }
175    }
176
177    fn undo_move<D: Director<S>>(&self, score_director: &mut D, undo: Self::Undo) {
178        match (self, undo) {
179            (Self::ListChange(m), ListMoveUnionUndo::ListChange(undo)) => {
180                m.undo_move(score_director, undo)
181            }
182            (Self::ListSwap(m), ListMoveUnionUndo::ListSwap(undo)) => {
183                m.undo_move(score_director, undo)
184            }
185            (Self::ListMultiSwap(m), ListMoveUnionUndo::ListMultiSwap(undo)) => {
186                m.undo_move(score_director, undo)
187            }
188            (Self::ListPermute(m), ListMoveUnionUndo::ListPermute(undo)) => {
189                m.undo_move(score_director, undo)
190            }
191            (Self::SublistChange(m), ListMoveUnionUndo::SublistChange(undo)) => {
192                m.undo_move(score_director, undo)
193            }
194            (Self::SublistSwap(m), ListMoveUnionUndo::SublistSwap(undo)) => {
195                m.undo_move(score_director, undo)
196            }
197            (Self::ListReverse(m), ListMoveUnionUndo::ListReverse(undo)) => {
198                m.undo_move(score_director, undo)
199            }
200            (Self::KOpt(m), ListMoveUnionUndo::KOpt(undo)) => m.undo_move(score_director, undo),
201            (Self::ListRuin(m), ListMoveUnionUndo::ListRuin(undo)) => {
202                m.undo_move(score_director, undo)
203            }
204            _ => panic!("list move undo shape must match move shape"),
205        }
206    }
207
208    fn descriptor_index(&self) -> usize {
209        match self {
210            Self::ListChange(m) => m.descriptor_index(),
211            Self::ListSwap(m) => m.descriptor_index(),
212            Self::ListMultiSwap(m) => m.descriptor_index(),
213            Self::ListPermute(m) => m.descriptor_index(),
214            Self::SublistChange(m) => m.descriptor_index(),
215            Self::SublistSwap(m) => m.descriptor_index(),
216            Self::ListReverse(m) => m.descriptor_index(),
217            Self::KOpt(m) => m.descriptor_index(),
218            Self::ListRuin(m) => m.descriptor_index(),
219        }
220    }
221
222    fn entity_indices(&self) -> &[usize] {
223        match self {
224            Self::ListChange(m) => m.entity_indices(),
225            Self::ListSwap(m) => m.entity_indices(),
226            Self::ListMultiSwap(m) => m.entity_indices(),
227            Self::ListPermute(m) => m.entity_indices(),
228            Self::SublistChange(m) => m.entity_indices(),
229            Self::SublistSwap(m) => m.entity_indices(),
230            Self::ListReverse(m) => m.entity_indices(),
231            Self::KOpt(m) => m.entity_indices(),
232            Self::ListRuin(m) => m.entity_indices(),
233        }
234    }
235
236    fn variable_name(&self) -> &str {
237        match self {
238            Self::ListChange(m) => m.variable_name(),
239            Self::ListSwap(m) => m.variable_name(),
240            Self::ListMultiSwap(m) => m.variable_name(),
241            Self::ListPermute(m) => m.variable_name(),
242            Self::SublistChange(m) => m.variable_name(),
243            Self::SublistSwap(m) => m.variable_name(),
244            Self::ListReverse(m) => m.variable_name(),
245            Self::KOpt(m) => m.variable_name(),
246            Self::ListRuin(m) => m.variable_name(),
247        }
248    }
249
250    fn telemetry_label(&self) -> &'static str {
251        match self {
252            Self::ListChange(m) => m.telemetry_label(),
253            Self::ListSwap(m) => m.telemetry_label(),
254            Self::ListMultiSwap(m) => m.telemetry_label(),
255            Self::ListPermute(m) => m.telemetry_label(),
256            Self::SublistChange(m) => m.telemetry_label(),
257            Self::SublistSwap(m) => m.telemetry_label(),
258            Self::ListReverse(m) => m.telemetry_label(),
259            Self::KOpt(m) => m.telemetry_label(),
260            Self::ListRuin(m) => m.telemetry_label(),
261        }
262    }
263
264    fn requires_hard_improvement(&self) -> bool {
265        match self {
266            Self::ListChange(m) => m.requires_hard_improvement(),
267            Self::ListSwap(m) => m.requires_hard_improvement(),
268            Self::ListMultiSwap(m) => m.requires_hard_improvement(),
269            Self::ListPermute(m) => m.requires_hard_improvement(),
270            Self::SublistChange(m) => m.requires_hard_improvement(),
271            Self::SublistSwap(m) => m.requires_hard_improvement(),
272            Self::ListReverse(m) => m.requires_hard_improvement(),
273            Self::KOpt(m) => m.requires_hard_improvement(),
274            Self::ListRuin(m) => m.requires_hard_improvement(),
275        }
276    }
277
278    fn requires_score_improvement(&self) -> bool {
279        match self {
280            Self::ListChange(m) => m.requires_score_improvement(),
281            Self::ListSwap(m) => m.requires_score_improvement(),
282            Self::ListMultiSwap(m) => m.requires_score_improvement(),
283            Self::ListPermute(m) => m.requires_score_improvement(),
284            Self::SublistChange(m) => m.requires_score_improvement(),
285            Self::SublistSwap(m) => m.requires_score_improvement(),
286            Self::ListReverse(m) => m.requires_score_improvement(),
287            Self::KOpt(m) => m.requires_score_improvement(),
288            Self::ListRuin(m) => m.requires_score_improvement(),
289        }
290    }
291
292    fn tabu_signature<D: Director<S>>(&self, score_director: &D) -> Cow<'_, MoveTabuSignature> {
293        match self {
294            Self::ListChange(m) => m.tabu_signature(score_director),
295            Self::ListSwap(m) => m.tabu_signature(score_director),
296            Self::ListMultiSwap(m) => m.tabu_signature(score_director),
297            Self::ListPermute(m) => m.tabu_signature(score_director),
298            Self::SublistChange(m) => m.tabu_signature(score_director),
299            Self::SublistSwap(m) => m.tabu_signature(score_director),
300            Self::ListReverse(m) => m.tabu_signature(score_director),
301            Self::KOpt(m) => m.tabu_signature(score_director),
302            Self::ListRuin(m) => m.tabu_signature(score_director),
303        }
304    }
305
306    fn candidate_trace_identity(&self) -> Option<CandidateTraceIdentity> {
307        match self {
308            Self::ListChange(m) => m.candidate_trace_identity(),
309            Self::ListSwap(m) => m.candidate_trace_identity(),
310            Self::ListMultiSwap(m) => m.candidate_trace_identity(),
311            Self::ListPermute(m) => m.candidate_trace_identity(),
312            Self::SublistChange(m) => m.candidate_trace_identity(),
313            Self::SublistSwap(m) => m.candidate_trace_identity(),
314            Self::ListReverse(m) => m.candidate_trace_identity(),
315            Self::KOpt(m) => m.candidate_trace_identity(),
316            Self::ListRuin(m) => m.candidate_trace_identity(),
317        }
318    }
319}
solverforge_solver/heuristic/move/list_union.rs

solverforge_solver/heuristic/move/
list_union.rs
