1use std::fmt::{self, Debug};
2
3use solverforge_config::{LocalSearchConfig, MoveSelectorConfig, VndConfig};
4use solverforge_core::domain::{PlanningSolution, SolutionDescriptor};
5use solverforge_core::score::{ParseableScore, Score};
6
7use crate::builder::{
8 AcceptorBuilder, AnyAcceptor, AnyForager, ForagerBuilder, ListContext, ListLeafSelector,
9 ListMoveSelectorBuilder,
10};
11use crate::descriptor_standard::{
12 build_descriptor_move_selector, descriptor_has_bindings, DescriptorEitherMove,
13 DescriptorLeafSelector,
14};
15use crate::heuristic::r#move::{ListMoveImpl, Move, MoveArena};
16use crate::heuristic::selector::decorator::VecUnionSelector;
17use crate::heuristic::selector::move_selector::MoveSelector;
18use crate::heuristic::selector::nearby_list_change::CrossEntityDistanceMeter;
19use crate::phase::dynamic_vnd::DynamicVndPhase;
20use crate::phase::localsearch::{
21 AcceptedCountForager, LocalSearchPhase, SimulatedAnnealingAcceptor,
22};
23
24pub enum UnifiedMove<S, V> {
25 Standard(DescriptorEitherMove<S>),
26 List(ListMoveImpl<S, V>),
27}
28
29impl<S, V> Debug for UnifiedMove<S, V>
30where
31 S: PlanningSolution + 'static,
32 V: Clone + PartialEq + Send + Sync + Debug + 'static,
33{
34 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
35 match self {
36 Self::Standard(m) => write!(f, "UnifiedMove::Standard({m:?})"),
37 Self::List(m) => write!(f, "UnifiedMove::List({m:?})"),
38 }
39 }
40}
41
42impl<S, V> Move<S> for UnifiedMove<S, V>
43where
44 S: PlanningSolution + 'static,
45 V: Clone + PartialEq + Send + Sync + Debug + 'static,
46{
47 fn is_doable<D: solverforge_scoring::Director<S>>(&self, score_director: &D) -> bool {
48 match self {
49 Self::Standard(m) => m.is_doable(score_director),
50 Self::List(m) => m.is_doable(score_director),
51 }
52 }
53
54 fn do_move<D: solverforge_scoring::Director<S>>(&self, score_director: &mut D) {
55 match self {
56 Self::Standard(m) => m.do_move(score_director),
57 Self::List(m) => m.do_move(score_director),
58 }
59 }
60
61 fn descriptor_index(&self) -> usize {
62 match self {
63 Self::Standard(m) => m.descriptor_index(),
64 Self::List(m) => m.descriptor_index(),
65 }
66 }
67
68 fn entity_indices(&self) -> &[usize] {
69 match self {
70 Self::Standard(m) => m.entity_indices(),
71 Self::List(m) => m.entity_indices(),
72 }
73 }
74
75 fn variable_name(&self) -> &str {
76 match self {
77 Self::Standard(m) => m.variable_name(),
78 Self::List(m) => m.variable_name(),
79 }
80 }
81}
82
83pub enum UnifiedNeighborhood<S, V, DM, IDM>
84where
85 S: PlanningSolution + 'static,
86 V: Clone + PartialEq + Send + Sync + Debug + 'static,
87 DM: CrossEntityDistanceMeter<S> + Clone,
88 IDM: CrossEntityDistanceMeter<S> + Clone,
89{
90 Standard(VecUnionSelector<S, DescriptorEitherMove<S>, DescriptorLeafSelector<S>>),
91 List(VecUnionSelector<S, ListMoveImpl<S, V>, ListLeafSelector<S, V, DM, IDM>>),
92}
93
94impl<S, V, DM, IDM> Debug for UnifiedNeighborhood<S, V, DM, IDM>
95where
96 S: PlanningSolution + 'static,
97 V: Clone + PartialEq + Send + Sync + Debug + 'static,
98 DM: CrossEntityDistanceMeter<S> + Clone + Debug,
99 IDM: CrossEntityDistanceMeter<S> + Clone + Debug,
100{
101 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
102 match self {
103 Self::Standard(s) => write!(f, "UnifiedNeighborhood::Standard({s:?})"),
104 Self::List(s) => write!(f, "UnifiedNeighborhood::List({s:?})"),
105 }
106 }
107}
108
109impl<S, V, DM, IDM> MoveSelector<S, UnifiedMove<S, V>> for UnifiedNeighborhood<S, V, DM, IDM>
110where
111 S: PlanningSolution + 'static,
112 V: Clone + PartialEq + Send + Sync + Debug + 'static,
113 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
114 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
115{
116 fn iter_moves<'a, D: solverforge_scoring::Director<S>>(
117 &'a self,
118 score_director: &'a D,
119 ) -> impl Iterator<Item = UnifiedMove<S, V>> + 'a {
120 enum UnifiedNeighborhoodIter<A, B> {
121 Standard(A),
122 List(B),
123 }
124
125 impl<T, A, B> Iterator for UnifiedNeighborhoodIter<A, B>
126 where
127 A: Iterator<Item = T>,
128 B: Iterator<Item = T>,
129 {
130 type Item = T;
131
132 fn next(&mut self) -> Option<Self::Item> {
133 match self {
134 Self::Standard(iter) => iter.next(),
135 Self::List(iter) => iter.next(),
136 }
137 }
138 }
139
140 match self {
141 Self::Standard(selector) => UnifiedNeighborhoodIter::Standard(
142 selector
143 .iter_moves(score_director)
144 .map(UnifiedMove::Standard),
145 ),
146 Self::List(selector) => UnifiedNeighborhoodIter::List(
147 selector.iter_moves(score_director).map(UnifiedMove::List),
148 ),
149 }
150 }
151
152 fn size<D: solverforge_scoring::Director<S>>(&self, score_director: &D) -> usize {
153 match self {
154 Self::Standard(selector) => selector.size(score_director),
155 Self::List(selector) => selector.size(score_director),
156 }
157 }
158
159 fn append_moves<D: solverforge_scoring::Director<S>>(
160 &self,
161 score_director: &D,
162 arena: &mut MoveArena<UnifiedMove<S, V>>,
163 ) {
164 match self {
165 Self::Standard(selector) => {
166 for mov in selector.iter_moves(score_director) {
167 arena.push(UnifiedMove::Standard(mov));
168 }
169 }
170 Self::List(selector) => {
171 for mov in selector.iter_moves(score_director) {
172 arena.push(UnifiedMove::List(mov));
173 }
174 }
175 }
176 }
177}
178
179pub type UnifiedLocalSearch<S, V, DM, IDM> = LocalSearchPhase<
180 S,
181 UnifiedMove<S, V>,
182 VecUnionSelector<S, UnifiedMove<S, V>, UnifiedNeighborhood<S, V, DM, IDM>>,
183 AnyAcceptor<S>,
184 AnyForager<S>,
185>;
186
187pub type UnifiedVnd<S, V, DM, IDM> =
188 DynamicVndPhase<S, UnifiedMove<S, V>, UnifiedNeighborhood<S, V, DM, IDM>>;
189
190pub fn build_unified_move_selector<S, V, DM, IDM>(
191 config: Option<&MoveSelectorConfig>,
192 descriptor: &SolutionDescriptor,
193 list_ctx: Option<&ListContext<S, V, DM, IDM>>,
194) -> VecUnionSelector<S, UnifiedMove<S, V>, UnifiedNeighborhood<S, V, DM, IDM>>
195where
196 S: PlanningSolution + 'static,
197 V: Clone + PartialEq + Send + Sync + Debug + 'static,
198 DM: CrossEntityDistanceMeter<S> + Clone + 'static,
199 IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
200{
201 let mut neighborhoods = Vec::new();
202 collect_neighborhoods(config, descriptor, list_ctx, &mut neighborhoods);
203 assert!(
204 !neighborhoods.is_empty(),
205 "stock move selector configuration produced no neighborhoods"
206 );
207 VecUnionSelector::new(neighborhoods)
208}
209
210fn collect_neighborhoods<S, V, DM, IDM>(
211 config: Option<&MoveSelectorConfig>,
212 descriptor: &SolutionDescriptor,
213 list_ctx: Option<&ListContext<S, V, DM, IDM>>,
214 out: &mut Vec<UnifiedNeighborhood<S, V, DM, IDM>>,
215) where
216 S: PlanningSolution + 'static,
217 V: Clone + PartialEq + Send + Sync + Debug + 'static,
218 DM: CrossEntityDistanceMeter<S> + Clone + 'static,
219 IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
220{
221 match config {
222 None => {
223 if descriptor_has_bindings(descriptor) {
224 out.push(UnifiedNeighborhood::Standard(
225 build_descriptor_move_selector(None, descriptor),
226 ));
227 }
228 if let Some(list_ctx) = list_ctx {
229 out.push(UnifiedNeighborhood::List(ListMoveSelectorBuilder::build(
230 None, list_ctx,
231 )));
232 }
233 }
234 Some(MoveSelectorConfig::UnionMoveSelector(union)) => {
235 for child in &union.selectors {
236 collect_neighborhoods(Some(child), descriptor, list_ctx, out);
237 }
238 }
239 Some(MoveSelectorConfig::ChangeMoveSelector(_))
240 | Some(MoveSelectorConfig::SwapMoveSelector(_)) => {
241 out.push(UnifiedNeighborhood::Standard(
242 build_descriptor_move_selector(config, descriptor),
243 ));
244 }
245 Some(MoveSelectorConfig::ListChangeMoveSelector(_))
246 | Some(MoveSelectorConfig::NearbyListChangeMoveSelector(_))
247 | Some(MoveSelectorConfig::ListSwapMoveSelector(_))
248 | Some(MoveSelectorConfig::NearbyListSwapMoveSelector(_))
249 | Some(MoveSelectorConfig::SubListChangeMoveSelector(_))
250 | Some(MoveSelectorConfig::SubListSwapMoveSelector(_))
251 | Some(MoveSelectorConfig::ListReverseMoveSelector(_))
252 | Some(MoveSelectorConfig::KOptMoveSelector(_))
253 | Some(MoveSelectorConfig::ListRuinMoveSelector(_)) => {
254 let Some(list_ctx) = list_ctx else {
255 panic!("list move selector configured against a standard-variable stock context");
256 };
257 out.push(UnifiedNeighborhood::List(ListMoveSelectorBuilder::build(
258 config, list_ctx,
259 )));
260 }
261 Some(MoveSelectorConfig::CartesianProductMoveSelector(_)) => {
262 panic!("cartesian_product move selectors are not supported in stock solving");
263 }
264 }
265}
266
267pub fn build_unified_local_search<S, V, DM, IDM>(
268 config: Option<&LocalSearchConfig>,
269 descriptor: &SolutionDescriptor,
270 list_ctx: Option<&ListContext<S, V, DM, IDM>>,
271) -> UnifiedLocalSearch<S, V, DM, IDM>
272where
273 S: PlanningSolution + 'static,
274 S::Score: Score + ParseableScore,
275 V: Clone + PartialEq + Send + Sync + Debug + 'static,
276 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
277 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
278{
279 let acceptor = config
280 .and_then(|ls| ls.acceptor.as_ref())
281 .map(AcceptorBuilder::build::<S>)
282 .unwrap_or_else(|| {
283 if list_ctx.is_some() {
284 AnyAcceptor::LateAcceptance(
285 crate::phase::localsearch::LateAcceptanceAcceptor::<S>::new(400),
286 )
287 } else {
288 AnyAcceptor::SimulatedAnnealing(SimulatedAnnealingAcceptor::default())
289 }
290 });
291 let forager = config
292 .and_then(|ls| ls.forager.as_ref())
293 .map(|cfg| ForagerBuilder::build::<S>(Some(cfg)))
294 .unwrap_or_else(|| {
295 let accepted = if list_ctx.is_some() { 4 } else { 1 };
296 AnyForager::AcceptedCount(AcceptedCountForager::new(accepted))
297 });
298 let move_selector = build_unified_move_selector(
299 config.and_then(|ls| ls.move_selector.as_ref()),
300 descriptor,
301 list_ctx,
302 );
303
304 LocalSearchPhase::new(move_selector, acceptor, forager, None)
305}
306
307pub fn build_unified_vnd<S, V, DM, IDM>(
308 config: &VndConfig,
309 descriptor: &SolutionDescriptor,
310 list_ctx: Option<&ListContext<S, V, DM, IDM>>,
311) -> UnifiedVnd<S, V, DM, IDM>
312where
313 S: PlanningSolution + 'static,
314 S::Score: Score + ParseableScore,
315 V: Clone + PartialEq + Send + Sync + Debug + 'static,
316 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
317 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
318{
319 let neighborhoods = if config.neighborhoods.is_empty() {
320 let mut neighborhoods = Vec::new();
321 collect_neighborhoods(None, descriptor, list_ctx, &mut neighborhoods);
322 neighborhoods
323 } else {
324 config
325 .neighborhoods
326 .iter()
327 .flat_map(|selector| {
328 let mut neighborhoods = Vec::new();
329 collect_neighborhoods(Some(selector), descriptor, list_ctx, &mut neighborhoods);
330 neighborhoods
331 })
332 .collect()
333 };
334
335 DynamicVndPhase::new(neighborhoods)
336}