1use std::fmt::{self, Debug};
2
3use smallvec::{smallvec, SmallVec};
4use solverforge_config::RecreateHeuristicType;
5use solverforge_core::domain::PlanningSolution;
6use solverforge_core::score::Score;
7use solverforge_scoring::Director;
8
9use super::metadata::{
10 encode_option_usize, encode_usize, hash_str, MoveTabuScope, ScopedEntityTabuToken,
11};
12use super::{ChangeMove, Move, MoveTabuSignature};
13
14pub enum ScalarRecreateValueSource<S> {
15 Empty,
16 CountableRange {
17 from: usize,
18 to: usize,
19 },
20 SolutionCount {
21 count_fn: fn(&S, usize) -> usize,
22 provider_index: usize,
23 value_candidate_limit: Option<usize>,
24 },
25 EntitySlice {
26 values_for_entity: for<'a> fn(&'a S, usize, usize) -> &'a [usize],
27 variable_index: usize,
28 value_candidate_limit: Option<usize>,
29 },
30 CandidateSlice {
31 candidate_values: for<'a> fn(&'a S, usize, usize) -> &'a [usize],
32 variable_index: usize,
33 value_candidate_limit: Option<usize>,
34 },
35}
36
37impl<S> Clone for ScalarRecreateValueSource<S> {
38 fn clone(&self) -> Self {
39 *self
40 }
41}
42
43impl<S> Copy for ScalarRecreateValueSource<S> {}
44
45impl<S> Debug for ScalarRecreateValueSource<S> {
46 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
47 match self {
48 Self::Empty => write!(f, "ScalarRecreateValueSource::Empty"),
49 Self::CountableRange { from, to } => {
50 write!(f, "ScalarRecreateValueSource::CountableRange({from}..{to})")
51 }
52 Self::SolutionCount { provider_index, .. } => {
53 write!(
54 f,
55 "ScalarRecreateValueSource::SolutionCount(provider={provider_index})"
56 )
57 }
58 Self::EntitySlice { .. } => write!(f, "ScalarRecreateValueSource::EntitySlice(..)"),
59 Self::CandidateSlice {
60 value_candidate_limit,
61 ..
62 } => f
63 .debug_struct("ScalarRecreateValueSource::CandidateSlice")
64 .field("value_candidate_limit", value_candidate_limit)
65 .finish(),
66 }
67 }
68}
69
70impl<S> ScalarRecreateValueSource<S> {
71 pub fn values_for_entity(&self, solution: &S, entity_index: usize) -> Vec<usize> {
72 match self {
73 Self::Empty => Vec::new(),
74 Self::CountableRange { from, to } => (*from..*to).collect(),
75 Self::SolutionCount {
76 count_fn,
77 provider_index,
78 value_candidate_limit,
79 } => match value_candidate_limit {
80 Some(limit) => (0..count_fn(solution, *provider_index))
81 .take(*limit)
82 .collect(),
83 None => (0..count_fn(solution, *provider_index)).collect(),
84 },
85 Self::EntitySlice {
86 values_for_entity,
87 variable_index,
88 value_candidate_limit,
89 } => {
90 let values = values_for_entity(solution, entity_index, *variable_index);
91 match value_candidate_limit {
92 Some(limit) => values.iter().copied().take(*limit).collect(),
93 None => values.to_vec(),
94 }
95 }
96 Self::CandidateSlice {
97 candidate_values,
98 variable_index,
99 value_candidate_limit,
100 } => {
101 let values = candidate_values(solution, entity_index, *variable_index);
102 match value_candidate_limit {
103 Some(limit) => values.iter().copied().take(*limit).collect(),
104 None => values.to_vec(),
105 }
106 }
107 }
108 }
109
110 pub fn has_values_for_entity(&self, solution: &S, entity_index: usize) -> bool {
111 match self {
112 Self::Empty => false,
113 Self::CountableRange { from, to } => from < to,
114 Self::SolutionCount {
115 count_fn,
116 provider_index,
117 value_candidate_limit,
118 } => {
119 let count = count_fn(solution, *provider_index);
120 value_candidate_limit.map_or_else(|| count > 0, |limit| limit > 0 && count > 0)
121 }
122 Self::EntitySlice {
123 values_for_entity,
124 variable_index,
125 value_candidate_limit,
126 } => {
127 let values = values_for_entity(solution, entity_index, *variable_index);
128 value_candidate_limit.map_or_else(
129 || !values.is_empty(),
130 |limit| limit > 0 && !values.is_empty(),
131 )
132 }
133 Self::CandidateSlice {
134 candidate_values,
135 variable_index,
136 value_candidate_limit,
137 } => {
138 let values = candidate_values(solution, entity_index, *variable_index);
139 value_candidate_limit.map_or_else(
140 || !values.is_empty(),
141 |limit| limit > 0 && !values.is_empty(),
142 )
143 }
144 }
145 }
146}
147
148pub struct RuinRecreateMove<S> {
149 entity_indices: SmallVec<[usize; 8]>,
150 getter: fn(&S, usize, usize) -> Option<usize>,
151 setter: fn(&mut S, usize, usize, Option<usize>),
152 descriptor_index: usize,
153 variable_index: usize,
154 variable_name: &'static str,
155 value_source: ScalarRecreateValueSource<S>,
156 recreate_heuristic_type: RecreateHeuristicType,
157 allows_unassigned: bool,
158}
159
160impl<S> Clone for RuinRecreateMove<S> {
161 fn clone(&self) -> Self {
162 Self {
163 entity_indices: self.entity_indices.clone(),
164 getter: self.getter,
165 setter: self.setter,
166 descriptor_index: self.descriptor_index,
167 variable_index: self.variable_index,
168 variable_name: self.variable_name,
169 value_source: self.value_source,
170 recreate_heuristic_type: self.recreate_heuristic_type,
171 allows_unassigned: self.allows_unassigned,
172 }
173 }
174}
175
176impl<S> Debug for RuinRecreateMove<S> {
177 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
178 f.debug_struct("RuinRecreateMove")
179 .field("entity_indices", &self.entity_indices)
180 .field("descriptor_index", &self.descriptor_index)
181 .field("variable_index", &self.variable_index)
182 .field("variable_name", &self.variable_name)
183 .field("recreate_heuristic_type", &self.recreate_heuristic_type)
184 .field("allows_unassigned", &self.allows_unassigned)
185 .finish()
186 }
187}
188
189impl<S> RuinRecreateMove<S>
190where
191 S: PlanningSolution,
192{
193 #[allow(clippy::too_many_arguments)]
194 pub fn new(
195 entity_indices: &[usize],
196 getter: fn(&S, usize, usize) -> Option<usize>,
197 setter: fn(&mut S, usize, usize, Option<usize>),
198 descriptor_index: usize,
199 variable_index: usize,
200 variable_name: &'static str,
201 value_source: ScalarRecreateValueSource<S>,
202 recreate_heuristic_type: RecreateHeuristicType,
203 allows_unassigned: bool,
204 ) -> Self {
205 Self {
206 entity_indices: SmallVec::from_slice(entity_indices),
207 getter,
208 setter,
209 descriptor_index,
210 variable_index,
211 variable_name,
212 value_source,
213 recreate_heuristic_type,
214 allows_unassigned,
215 }
216 }
217
218 fn apply_value<D: Director<S>>(
219 &self,
220 score_director: &mut D,
221 entity_index: usize,
222 value: Option<usize>,
223 ) {
224 score_director.before_variable_changed(self.descriptor_index, entity_index);
225 (self.setter)(
226 score_director.working_solution_mut(),
227 entity_index,
228 self.variable_index,
229 value,
230 );
231 score_director.after_variable_changed(self.descriptor_index, entity_index);
232 }
233
234 fn evaluate_candidate<D: Director<S>>(
235 &self,
236 score_director: &mut D,
237 mov: &ChangeMove<S, usize>,
238 ) -> S::Score
239 where
240 S: PlanningSolution,
241 S::Score: Score,
242 {
243 let score_state = score_director.snapshot_score_state();
244 let undo = mov.do_move(score_director);
245 let score = score_director.calculate_score();
246 mov.undo_move(score_director, undo);
247 score_director.restore_score_state(score_state);
248 score
249 }
250
251 fn choose_first_fit<D: Director<S>>(
252 &self,
253 score_director: &mut D,
254 entity_index: usize,
255 ) -> Option<usize>
256 where
257 S: PlanningSolution,
258 S::Score: Score,
259 {
260 let baseline_score = self
261 .allows_unassigned
262 .then(|| score_director.calculate_score());
263 for value in self
264 .value_source
265 .values_for_entity(score_director.working_solution(), entity_index)
266 {
267 let mov = ChangeMove::new(
268 entity_index,
269 Some(value),
270 self.getter,
271 self.setter,
272 self.variable_index,
273 self.variable_name,
274 self.descriptor_index,
275 );
276 if !mov.is_doable(score_director) {
277 continue;
278 }
279 let score = self.evaluate_candidate(score_director, &mov);
280 if baseline_score.is_none_or(|baseline| score > baseline) {
281 return Some(value);
282 }
283 }
284 None
285 }
286
287 fn choose_cheapest_insertion<D: Director<S>>(
288 &self,
289 score_director: &mut D,
290 entity_index: usize,
291 ) -> Option<usize>
292 where
293 S: PlanningSolution,
294 S::Score: Score,
295 {
296 let baseline_score = self
297 .allows_unassigned
298 .then(|| score_director.calculate_score());
299 let mut best: Option<(usize, usize, S::Score)> = None;
300
301 for (value_index, value) in self
302 .value_source
303 .values_for_entity(score_director.working_solution(), entity_index)
304 .into_iter()
305 .enumerate()
306 {
307 let mov = ChangeMove::new(
308 entity_index,
309 Some(value),
310 self.getter,
311 self.setter,
312 self.variable_index,
313 self.variable_name,
314 self.descriptor_index,
315 );
316 if !mov.is_doable(score_director) {
317 continue;
318 }
319 let score = self.evaluate_candidate(score_director, &mov);
320 let should_replace = match best {
321 None => true,
322 Some((best_value_index, _, best_score)) => {
323 score > best_score || (score == best_score && value_index < best_value_index)
324 }
325 };
326 if should_replace {
327 best = Some((value_index, value, score));
328 }
329 }
330
331 best.and_then(|(_, value, best_score)| {
332 baseline_score
333 .is_none_or(|baseline| best_score >= baseline)
334 .then_some(value)
335 })
336 }
337
338 fn required_assignments_can_be_recreated(&self, solution: &S) -> bool {
339 self.allows_unassigned
340 || self.entity_indices.iter().all(|&entity_index| {
341 (self.getter)(solution, entity_index, self.variable_index).is_none()
342 || self
343 .value_source
344 .has_values_for_entity(solution, entity_index)
345 })
346 }
347}
348
349impl<S> Move<S> for RuinRecreateMove<S>
350where
351 S: PlanningSolution,
352 S::Score: Score,
353{
354 type Undo = SmallVec<[(usize, Option<usize>); 8]>;
355
356 fn is_doable<D: Director<S>>(&self, score_director: &D) -> bool {
357 let solution = score_director.working_solution();
358 self.required_assignments_can_be_recreated(solution)
359 && self.entity_indices.iter().any(|&entity_index| {
360 (self.getter)(solution, entity_index, self.variable_index).is_some()
361 })
362 }
363
364 fn do_move<D: Director<S>>(&self, score_director: &mut D) -> Self::Undo {
365 if !self.is_doable(score_director) {
366 return SmallVec::new();
367 }
368
369 let old_values: SmallVec<[(usize, Option<usize>); 8]> = self
370 .entity_indices
371 .iter()
372 .map(|&entity_index| {
373 (
374 entity_index,
375 (self.getter)(
376 score_director.working_solution(),
377 entity_index,
378 self.variable_index,
379 ),
380 )
381 })
382 .collect();
383
384 for &entity_index in &self.entity_indices {
385 self.apply_value(score_director, entity_index, None);
386 }
387
388 for &entity_index in &self.entity_indices {
389 if (self.getter)(
390 score_director.working_solution(),
391 entity_index,
392 self.variable_index,
393 )
394 .is_some()
395 {
396 continue;
397 }
398
399 let selected = match self.recreate_heuristic_type {
400 RecreateHeuristicType::FirstFit => {
401 self.choose_first_fit(score_director, entity_index)
402 }
403 RecreateHeuristicType::CheapestInsertion => {
404 self.choose_cheapest_insertion(score_director, entity_index)
405 }
406 };
407
408 if let Some(value) = selected {
409 self.apply_value(score_director, entity_index, Some(value));
410 }
411 }
412
413 old_values
414 }
415
416 fn undo_move<D: Director<S>>(&self, score_director: &mut D, undo: Self::Undo) {
417 for (entity_index, _) in &undo {
418 score_director.before_variable_changed(self.descriptor_index, *entity_index);
419 }
420 for (entity_index, old_value) in undo {
421 (self.setter)(
422 score_director.working_solution_mut(),
423 entity_index,
424 self.variable_index,
425 old_value,
426 );
427 }
428 for &entity_index in &self.entity_indices {
429 score_director.after_variable_changed(self.descriptor_index, entity_index);
430 }
431 }
432
433 fn descriptor_index(&self) -> usize {
434 self.descriptor_index
435 }
436
437 fn entity_indices(&self) -> &[usize] {
438 &self.entity_indices
439 }
440
441 fn variable_name(&self) -> &str {
442 self.variable_name
443 }
444
445 fn tabu_signature<D: Director<S>>(&self, score_director: &D) -> MoveTabuSignature {
446 let variable_id = hash_str(self.variable_name);
447 let heuristic_id = match self.recreate_heuristic_type {
448 RecreateHeuristicType::FirstFit => hash_str("first_fit"),
449 RecreateHeuristicType::CheapestInsertion => hash_str("cheapest_insertion"),
450 };
451 let scope = MoveTabuScope::new(self.descriptor_index, self.variable_name);
452 let entity_ids: SmallVec<[u64; 2]> = self
453 .entity_indices
454 .iter()
455 .map(|&entity_index| encode_usize(entity_index))
456 .collect();
457 let entity_tokens: SmallVec<[ScopedEntityTabuToken; 2]> = entity_ids
458 .iter()
459 .copied()
460 .map(|entity_id| scope.entity_token(entity_id))
461 .collect();
462 let mut move_id = smallvec![
463 hash_str("ruin_recreate"),
464 encode_usize(self.descriptor_index),
465 variable_id,
466 heuristic_id,
467 encode_usize(self.entity_indices.len()),
468 ];
469 let mut undo_move_id = move_id.clone();
470 for &entity_index in &self.entity_indices {
471 move_id.push(encode_usize(entity_index));
472 undo_move_id.push(encode_usize(entity_index));
473 let current = (self.getter)(
474 score_director.working_solution(),
475 entity_index,
476 self.variable_index,
477 );
478 move_id.push(encode_option_usize(current));
479 undo_move_id.push(encode_option_usize(current));
480 }
481
482 MoveTabuSignature::new(scope, move_id, undo_move_id).with_entity_tokens(entity_tokens)
483 }
484}