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 let moves: Vec<_> = match self {
121 Self::Standard(selector) => selector
122 .iter_moves(score_director)
123 .map(UnifiedMove::Standard)
124 .collect(),
125 Self::List(selector) => selector
126 .iter_moves(score_director)
127 .map(UnifiedMove::List)
128 .collect(),
129 };
130 moves.into_iter()
131 }
132
133 fn size<D: solverforge_scoring::Director<S>>(&self, score_director: &D) -> usize {
134 match self {
135 Self::Standard(selector) => selector.size(score_director),
136 Self::List(selector) => selector.size(score_director),
137 }
138 }
139
140 fn append_moves<D: solverforge_scoring::Director<S>>(
141 &self,
142 score_director: &D,
143 arena: &mut MoveArena<UnifiedMove<S, V>>,
144 ) {
145 match self {
146 Self::Standard(selector) => {
147 for mov in selector.iter_moves(score_director) {
148 arena.push(UnifiedMove::Standard(mov));
149 }
150 }
151 Self::List(selector) => {
152 for mov in selector.iter_moves(score_director) {
153 arena.push(UnifiedMove::List(mov));
154 }
155 }
156 }
157 }
158}
159
160pub type UnifiedLocalSearch<S, V, DM, IDM> = LocalSearchPhase<
161 S,
162 UnifiedMove<S, V>,
163 VecUnionSelector<S, UnifiedMove<S, V>, UnifiedNeighborhood<S, V, DM, IDM>>,
164 AnyAcceptor<S>,
165 AnyForager<S>,
166>;
167
168pub type UnifiedVnd<S, V, DM, IDM> =
169 DynamicVndPhase<S, UnifiedMove<S, V>, UnifiedNeighborhood<S, V, DM, IDM>>;
170
171pub fn build_unified_move_selector<S, V, DM, IDM>(
172 config: Option<&MoveSelectorConfig>,
173 descriptor: &SolutionDescriptor,
174 list_ctx: Option<&ListContext<S, V, DM, IDM>>,
175) -> VecUnionSelector<S, UnifiedMove<S, V>, UnifiedNeighborhood<S, V, DM, IDM>>
176where
177 S: PlanningSolution + 'static,
178 V: Clone + PartialEq + Send + Sync + Debug + 'static,
179 DM: CrossEntityDistanceMeter<S> + Clone + 'static,
180 IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
181{
182 let mut neighborhoods = Vec::new();
183 collect_neighborhoods(config, descriptor, list_ctx, &mut neighborhoods);
184 assert!(
185 !neighborhoods.is_empty(),
186 "stock move selector configuration produced no neighborhoods"
187 );
188 VecUnionSelector::new(neighborhoods)
189}
190
191fn collect_neighborhoods<S, V, DM, IDM>(
192 config: Option<&MoveSelectorConfig>,
193 descriptor: &SolutionDescriptor,
194 list_ctx: Option<&ListContext<S, V, DM, IDM>>,
195 out: &mut Vec<UnifiedNeighborhood<S, V, DM, IDM>>,
196) where
197 S: PlanningSolution + 'static,
198 V: Clone + PartialEq + Send + Sync + Debug + 'static,
199 DM: CrossEntityDistanceMeter<S> + Clone + 'static,
200 IDM: CrossEntityDistanceMeter<S> + Clone + 'static,
201{
202 match config {
203 None => {
204 if descriptor_has_bindings(descriptor) {
205 out.push(UnifiedNeighborhood::Standard(
206 build_descriptor_move_selector(None, descriptor),
207 ));
208 }
209 if let Some(list_ctx) = list_ctx {
210 out.push(UnifiedNeighborhood::List(ListMoveSelectorBuilder::build(
211 None, list_ctx,
212 )));
213 }
214 }
215 Some(MoveSelectorConfig::UnionMoveSelector(union)) => {
216 for child in &union.selectors {
217 collect_neighborhoods(Some(child), descriptor, list_ctx, out);
218 }
219 }
220 Some(MoveSelectorConfig::ChangeMoveSelector(_))
221 | Some(MoveSelectorConfig::SwapMoveSelector(_)) => {
222 out.push(UnifiedNeighborhood::Standard(
223 build_descriptor_move_selector(config, descriptor),
224 ));
225 }
226 Some(MoveSelectorConfig::ListChangeMoveSelector(_))
227 | Some(MoveSelectorConfig::NearbyListChangeMoveSelector(_))
228 | Some(MoveSelectorConfig::ListSwapMoveSelector(_))
229 | Some(MoveSelectorConfig::NearbyListSwapMoveSelector(_))
230 | Some(MoveSelectorConfig::SubListChangeMoveSelector(_))
231 | Some(MoveSelectorConfig::SubListSwapMoveSelector(_))
232 | Some(MoveSelectorConfig::ListReverseMoveSelector(_))
233 | Some(MoveSelectorConfig::KOptMoveSelector(_))
234 | Some(MoveSelectorConfig::ListRuinMoveSelector(_)) => {
235 let Some(list_ctx) = list_ctx else {
236 panic!("list move selector configured against a standard-variable stock context");
237 };
238 out.push(UnifiedNeighborhood::List(ListMoveSelectorBuilder::build(
239 config, list_ctx,
240 )));
241 }
242 Some(MoveSelectorConfig::CartesianProductMoveSelector(_)) => {
243 panic!("cartesian_product move selectors are not supported in stock solving");
244 }
245 }
246}
247
248pub fn build_unified_local_search<S, V, DM, IDM>(
249 config: Option<&LocalSearchConfig>,
250 descriptor: &SolutionDescriptor,
251 list_ctx: Option<&ListContext<S, V, DM, IDM>>,
252) -> UnifiedLocalSearch<S, V, DM, IDM>
253where
254 S: PlanningSolution + 'static,
255 S::Score: Score + ParseableScore,
256 V: Clone + PartialEq + Send + Sync + Debug + 'static,
257 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
258 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
259{
260 let acceptor = config
261 .and_then(|ls| ls.acceptor.as_ref())
262 .map(AcceptorBuilder::build::<S>)
263 .unwrap_or_else(|| {
264 if list_ctx.is_some() {
265 AnyAcceptor::LateAcceptance(
266 crate::phase::localsearch::LateAcceptanceAcceptor::<S>::new(400),
267 )
268 } else {
269 AnyAcceptor::SimulatedAnnealing(SimulatedAnnealingAcceptor::default())
270 }
271 });
272 let forager = config
273 .and_then(|ls| ls.forager.as_ref())
274 .map(|cfg| ForagerBuilder::build::<S>(Some(cfg)))
275 .unwrap_or_else(|| {
276 let accepted = if list_ctx.is_some() { 4 } else { 1 };
277 AnyForager::AcceptedCount(AcceptedCountForager::new(accepted))
278 });
279 let move_selector = build_unified_move_selector(
280 config.and_then(|ls| ls.move_selector.as_ref()),
281 descriptor,
282 list_ctx,
283 );
284
285 LocalSearchPhase::new(move_selector, acceptor, forager, None)
286}
287
288pub fn build_unified_vnd<S, V, DM, IDM>(
289 config: &VndConfig,
290 descriptor: &SolutionDescriptor,
291 list_ctx: Option<&ListContext<S, V, DM, IDM>>,
292) -> UnifiedVnd<S, V, DM, IDM>
293where
294 S: PlanningSolution + 'static,
295 S::Score: Score + ParseableScore,
296 V: Clone + PartialEq + Send + Sync + Debug + 'static,
297 DM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
298 IDM: CrossEntityDistanceMeter<S> + Clone + Debug + 'static,
299{
300 let neighborhoods = if config.neighborhoods.is_empty() {
301 let mut neighborhoods = Vec::new();
302 collect_neighborhoods(None, descriptor, list_ctx, &mut neighborhoods);
303 neighborhoods
304 } else {
305 config
306 .neighborhoods
307 .iter()
308 .flat_map(|selector| {
309 let mut neighborhoods = Vec::new();
310 collect_neighborhoods(Some(selector), descriptor, list_ctx, &mut neighborhoods);
311 neighborhoods
312 })
313 .collect()
314 };
315
316 DynamicVndPhase::new(neighborhoods)
317}