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, RecordingDirector};
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 mut recording = RecordingDirector::new(score_director);
244 mov.do_move(&mut recording);
245 let score = recording.calculate_score();
246 recording.undo_changes();
247 score
248 }
249
250 fn choose_first_fit<D: Director<S>>(
251 &self,
252 score_director: &mut D,
253 entity_index: usize,
254 ) -> Option<usize>
255 where
256 S: PlanningSolution,
257 S::Score: Score,
258 {
259 let baseline_score = self
260 .allows_unassigned
261 .then(|| score_director.calculate_score());
262 for value in self
263 .value_source
264 .values_for_entity(score_director.working_solution(), entity_index)
265 {
266 let mov = ChangeMove::new(
267 entity_index,
268 Some(value),
269 self.getter,
270 self.setter,
271 self.variable_index,
272 self.variable_name,
273 self.descriptor_index,
274 );
275 if !mov.is_doable(score_director) {
276 continue;
277 }
278 let score = self.evaluate_candidate(score_director, &mov);
279 if baseline_score.is_none_or(|baseline| score > baseline) {
280 return Some(value);
281 }
282 }
283 None
284 }
285
286 fn choose_cheapest_insertion<D: Director<S>>(
287 &self,
288 score_director: &mut D,
289 entity_index: usize,
290 ) -> Option<usize>
291 where
292 S: PlanningSolution,
293 S::Score: Score,
294 {
295 let baseline_score = self
296 .allows_unassigned
297 .then(|| score_director.calculate_score());
298 let mut best: Option<(usize, usize, S::Score)> = None;
299
300 for (value_index, value) in self
301 .value_source
302 .values_for_entity(score_director.working_solution(), entity_index)
303 .into_iter()
304 .enumerate()
305 {
306 let mov = ChangeMove::new(
307 entity_index,
308 Some(value),
309 self.getter,
310 self.setter,
311 self.variable_index,
312 self.variable_name,
313 self.descriptor_index,
314 );
315 if !mov.is_doable(score_director) {
316 continue;
317 }
318 let score = self.evaluate_candidate(score_director, &mov);
319 let should_replace = match best {
320 None => true,
321 Some((best_value_index, _, best_score)) => {
322 score > best_score || (score == best_score && value_index < best_value_index)
323 }
324 };
325 if should_replace {
326 best = Some((value_index, value, score));
327 }
328 }
329
330 best.and_then(|(_, value, best_score)| {
331 baseline_score
332 .is_none_or(|baseline| best_score >= baseline)
333 .then_some(value)
334 })
335 }
336
337 fn required_assignments_can_be_recreated(&self, solution: &S) -> bool {
338 self.allows_unassigned
339 || self.entity_indices.iter().all(|&entity_index| {
340 (self.getter)(solution, entity_index, self.variable_index).is_none()
341 || self
342 .value_source
343 .has_values_for_entity(solution, entity_index)
344 })
345 }
346}
347
348impl<S> Move<S> for RuinRecreateMove<S>
349where
350 S: PlanningSolution,
351 S::Score: Score,
352{
353 fn is_doable<D: Director<S>>(&self, score_director: &D) -> bool {
354 let solution = score_director.working_solution();
355 self.required_assignments_can_be_recreated(solution)
356 && self.entity_indices.iter().any(|&entity_index| {
357 (self.getter)(solution, entity_index, self.variable_index).is_some()
358 })
359 }
360
361 fn do_move<D: Director<S>>(&self, score_director: &mut D) {
362 if !self.is_doable(score_director) {
363 return;
364 }
365
366 let old_values: SmallVec<[(usize, Option<usize>); 8]> = self
367 .entity_indices
368 .iter()
369 .map(|&entity_index| {
370 (
371 entity_index,
372 (self.getter)(
373 score_director.working_solution(),
374 entity_index,
375 self.variable_index,
376 ),
377 )
378 })
379 .collect();
380
381 for &entity_index in &self.entity_indices {
382 self.apply_value(score_director, entity_index, None);
383 }
384
385 for &entity_index in &self.entity_indices {
386 if (self.getter)(
387 score_director.working_solution(),
388 entity_index,
389 self.variable_index,
390 )
391 .is_some()
392 {
393 continue;
394 }
395
396 let selected = match self.recreate_heuristic_type {
397 RecreateHeuristicType::FirstFit => {
398 self.choose_first_fit(score_director, entity_index)
399 }
400 RecreateHeuristicType::CheapestInsertion => {
401 self.choose_cheapest_insertion(score_director, entity_index)
402 }
403 };
404
405 if let Some(value) = selected {
406 self.apply_value(score_director, entity_index, Some(value));
407 }
408 }
409
410 let setter = self.setter;
411 let variable_index = self.variable_index;
412 score_director.register_undo(Box::new(move |solution: &mut S| {
413 for (entity_index, old_value) in old_values {
414 setter(solution, entity_index, variable_index, old_value);
415 }
416 }));
417 }
418
419 fn descriptor_index(&self) -> usize {
420 self.descriptor_index
421 }
422
423 fn entity_indices(&self) -> &[usize] {
424 &self.entity_indices
425 }
426
427 fn variable_name(&self) -> &str {
428 self.variable_name
429 }
430
431 fn tabu_signature<D: Director<S>>(&self, score_director: &D) -> MoveTabuSignature {
432 let variable_id = hash_str(self.variable_name);
433 let heuristic_id = match self.recreate_heuristic_type {
434 RecreateHeuristicType::FirstFit => hash_str("first_fit"),
435 RecreateHeuristicType::CheapestInsertion => hash_str("cheapest_insertion"),
436 };
437 let scope = MoveTabuScope::new(self.descriptor_index, self.variable_name);
438 let entity_ids: SmallVec<[u64; 2]> = self
439 .entity_indices
440 .iter()
441 .map(|&entity_index| encode_usize(entity_index))
442 .collect();
443 let entity_tokens: SmallVec<[ScopedEntityTabuToken; 2]> = entity_ids
444 .iter()
445 .copied()
446 .map(|entity_id| scope.entity_token(entity_id))
447 .collect();
448 let mut move_id = smallvec![
449 hash_str("ruin_recreate"),
450 encode_usize(self.descriptor_index),
451 variable_id,
452 heuristic_id,
453 encode_usize(self.entity_indices.len()),
454 ];
455 let mut undo_move_id = move_id.clone();
456 for &entity_index in &self.entity_indices {
457 move_id.push(encode_usize(entity_index));
458 undo_move_id.push(encode_usize(entity_index));
459 let current = (self.getter)(
460 score_director.working_solution(),
461 entity_index,
462 self.variable_index,
463 );
464 move_id.push(encode_option_usize(current));
465 undo_move_id.push(encode_option_usize(current));
466 }
467
468 MoveTabuSignature::new(scope, move_id, undo_move_id).with_entity_tokens(entity_tokens)
469 }
470}