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