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> Debug for RuinRecreateMove<S> {
161 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
162 f.debug_struct("RuinRecreateMove")
163 .field("entity_indices", &self.entity_indices)
164 .field("descriptor_index", &self.descriptor_index)
165 .field("variable_index", &self.variable_index)
166 .field("variable_name", &self.variable_name)
167 .field("recreate_heuristic_type", &self.recreate_heuristic_type)
168 .field("allows_unassigned", &self.allows_unassigned)
169 .finish()
170 }
171}
172
173impl<S> RuinRecreateMove<S>
174where
175 S: PlanningSolution,
176{
177 #[allow(clippy::too_many_arguments)]
178 pub fn new(
179 entity_indices: &[usize],
180 getter: fn(&S, usize, usize) -> Option<usize>,
181 setter: fn(&mut S, usize, usize, Option<usize>),
182 descriptor_index: usize,
183 variable_index: usize,
184 variable_name: &'static str,
185 value_source: ScalarRecreateValueSource<S>,
186 recreate_heuristic_type: RecreateHeuristicType,
187 allows_unassigned: bool,
188 ) -> Self {
189 Self {
190 entity_indices: SmallVec::from_slice(entity_indices),
191 getter,
192 setter,
193 descriptor_index,
194 variable_index,
195 variable_name,
196 value_source,
197 recreate_heuristic_type,
198 allows_unassigned,
199 }
200 }
201
202 fn apply_value<D: Director<S>>(
203 &self,
204 score_director: &mut D,
205 entity_index: usize,
206 value: Option<usize>,
207 ) {
208 score_director.before_variable_changed(self.descriptor_index, entity_index);
209 (self.setter)(
210 score_director.working_solution_mut(),
211 entity_index,
212 self.variable_index,
213 value,
214 );
215 score_director.after_variable_changed(self.descriptor_index, entity_index);
216 }
217
218 fn evaluate_candidate<D: Director<S>>(
219 &self,
220 score_director: &mut D,
221 mov: &ChangeMove<S, usize>,
222 ) -> S::Score
223 where
224 S: PlanningSolution,
225 S::Score: Score,
226 {
227 let score_state = score_director.snapshot_score_state();
228 let undo = mov.do_move(score_director);
229 let score = score_director.calculate_score();
230 mov.undo_move(score_director, undo);
231 score_director.restore_score_state(score_state);
232 score
233 }
234
235 fn choose_first_fit<D: Director<S>>(
236 &self,
237 score_director: &mut D,
238 entity_index: usize,
239 ) -> Option<usize>
240 where
241 S: PlanningSolution,
242 S::Score: Score,
243 {
244 let baseline_score = self
245 .allows_unassigned
246 .then(|| score_director.calculate_score());
247 for value in self
248 .value_source
249 .values_for_entity(score_director.working_solution(), entity_index)
250 {
251 let mov = ChangeMove::new(
252 entity_index,
253 Some(value),
254 self.getter,
255 self.setter,
256 self.variable_index,
257 self.variable_name,
258 self.descriptor_index,
259 );
260 if !mov.is_doable(score_director) {
261 continue;
262 }
263 let score = self.evaluate_candidate(score_director, &mov);
264 if baseline_score.is_none_or(|baseline| score > baseline) {
265 return Some(value);
266 }
267 }
268 None
269 }
270
271 fn choose_cheapest_insertion<D: Director<S>>(
272 &self,
273 score_director: &mut D,
274 entity_index: usize,
275 ) -> Option<usize>
276 where
277 S: PlanningSolution,
278 S::Score: Score,
279 {
280 let baseline_score = self
281 .allows_unassigned
282 .then(|| score_director.calculate_score());
283 let mut best: Option<(usize, usize, S::Score)> = None;
284
285 for (value_index, value) in self
286 .value_source
287 .values_for_entity(score_director.working_solution(), entity_index)
288 .into_iter()
289 .enumerate()
290 {
291 let mov = ChangeMove::new(
292 entity_index,
293 Some(value),
294 self.getter,
295 self.setter,
296 self.variable_index,
297 self.variable_name,
298 self.descriptor_index,
299 );
300 if !mov.is_doable(score_director) {
301 continue;
302 }
303 let score = self.evaluate_candidate(score_director, &mov);
304 let should_replace = match best {
305 None => true,
306 Some((best_value_index, _, best_score)) => {
307 score > best_score || (score == best_score && value_index < best_value_index)
308 }
309 };
310 if should_replace {
311 best = Some((value_index, value, score));
312 }
313 }
314
315 best.and_then(|(_, value, best_score)| {
316 baseline_score
317 .is_none_or(|baseline| best_score >= baseline)
318 .then_some(value)
319 })
320 }
321
322 fn required_assignments_can_be_recreated(&self, solution: &S) -> bool {
323 self.allows_unassigned
324 || self.entity_indices.iter().all(|&entity_index| {
325 (self.getter)(solution, entity_index, self.variable_index).is_none()
326 || self
327 .value_source
328 .has_values_for_entity(solution, entity_index)
329 })
330 }
331}
332
333impl<S> Move<S> for RuinRecreateMove<S>
334where
335 S: PlanningSolution,
336 S::Score: Score,
337{
338 type Undo = SmallVec<[(usize, Option<usize>); 8]>;
339
340 fn is_doable<D: Director<S>>(&self, score_director: &D) -> bool {
341 let solution = score_director.working_solution();
342 self.required_assignments_can_be_recreated(solution)
343 && self.entity_indices.iter().any(|&entity_index| {
344 (self.getter)(solution, entity_index, self.variable_index).is_some()
345 })
346 }
347
348 fn do_move<D: Director<S>>(&self, score_director: &mut D) -> Self::Undo {
349 if !self.is_doable(score_director) {
350 return SmallVec::new();
351 }
352
353 let old_values: SmallVec<[(usize, Option<usize>); 8]> = self
354 .entity_indices
355 .iter()
356 .map(|&entity_index| {
357 (
358 entity_index,
359 (self.getter)(
360 score_director.working_solution(),
361 entity_index,
362 self.variable_index,
363 ),
364 )
365 })
366 .collect();
367
368 for &entity_index in &self.entity_indices {
369 self.apply_value(score_director, entity_index, None);
370 }
371
372 for &entity_index in &self.entity_indices {
373 if (self.getter)(
374 score_director.working_solution(),
375 entity_index,
376 self.variable_index,
377 )
378 .is_some()
379 {
380 continue;
381 }
382
383 let selected = match self.recreate_heuristic_type {
384 RecreateHeuristicType::FirstFit => {
385 self.choose_first_fit(score_director, entity_index)
386 }
387 RecreateHeuristicType::CheapestInsertion => {
388 self.choose_cheapest_insertion(score_director, entity_index)
389 }
390 };
391
392 if let Some(value) = selected {
393 self.apply_value(score_director, entity_index, Some(value));
394 }
395 }
396
397 old_values
398 }
399
400 fn undo_move<D: Director<S>>(&self, score_director: &mut D, undo: Self::Undo) {
401 for (entity_index, _) in &undo {
402 score_director.before_variable_changed(self.descriptor_index, *entity_index);
403 }
404 for (entity_index, old_value) in undo {
405 (self.setter)(
406 score_director.working_solution_mut(),
407 entity_index,
408 self.variable_index,
409 old_value,
410 );
411 }
412 for &entity_index in &self.entity_indices {
413 score_director.after_variable_changed(self.descriptor_index, entity_index);
414 }
415 }
416
417 fn descriptor_index(&self) -> usize {
418 self.descriptor_index
419 }
420
421 fn entity_indices(&self) -> &[usize] {
422 &self.entity_indices
423 }
424
425 fn variable_name(&self) -> &str {
426 self.variable_name
427 }
428
429 fn tabu_signature<D: Director<S>>(&self, score_director: &D) -> MoveTabuSignature {
430 let variable_id = hash_str(self.variable_name);
431 let heuristic_id = match self.recreate_heuristic_type {
432 RecreateHeuristicType::FirstFit => hash_str("first_fit"),
433 RecreateHeuristicType::CheapestInsertion => hash_str("cheapest_insertion"),
434 };
435 let scope = MoveTabuScope::new(self.descriptor_index, self.variable_name);
436 let entity_ids: SmallVec<[u64; 2]> = self
437 .entity_indices
438 .iter()
439 .map(|&entity_index| encode_usize(entity_index))
440 .collect();
441 let entity_tokens: SmallVec<[ScopedEntityTabuToken; 2]> = entity_ids
442 .iter()
443 .copied()
444 .map(|entity_id| scope.entity_token(entity_id))
445 .collect();
446 let mut move_id = smallvec![
447 hash_str("ruin_recreate"),
448 encode_usize(self.descriptor_index),
449 variable_id,
450 heuristic_id,
451 encode_usize(self.entity_indices.len()),
452 ];
453 let mut undo_move_id = move_id.clone();
454 for &entity_index in &self.entity_indices {
455 move_id.push(encode_usize(entity_index));
456 undo_move_id.push(encode_usize(entity_index));
457 let current = (self.getter)(
458 score_director.working_solution(),
459 entity_index,
460 self.variable_index,
461 );
462 move_id.push(encode_option_usize(current));
463 undo_move_id.push(encode_option_usize(current));
464 }
465
466 MoveTabuSignature::new(scope, move_id, undo_move_id).with_entity_tokens(entity_tokens)
467 }
468}