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