1use std::collections::HashSet;
2
3use solverforge_core::domain::PlanningSolution;
4
5use super::assignment_candidate::{ordered_entities, ScalarAssignmentMoveOptions};
6use super::assignment_cycle::CycleWindowCursor;
7use super::assignment_entity::{AssignmentMoveKind, CapacityCursor, OptionalAdjustmentCursor};
8use super::assignment_family::{AssignmentFamilyCursor, AssignmentMoveFamily};
9use super::assignment_pair::PairWindowCursor;
10use super::assignment_required_batch::required_batch_move;
11use super::assignment_state::ScalarAssignmentState;
12use crate::builder::ScalarAssignmentBinding;
13use crate::heuristic::r#move::CompoundScalarMove;
14
15type AssignmentMoveKey = Vec<(usize, usize, usize, &'static str, Option<usize>)>;
16
17pub struct ScalarAssignmentMoveCursor<S>
18where
19 S: PlanningSolution,
20{
21 group: ScalarAssignmentBinding<S>,
22 solution: S,
23 options: ScalarAssignmentMoveOptions,
24 state: ScalarAssignmentState,
25 batch_required: bool,
26 family_slots: Vec<AssignmentFamilySlot>,
27 family_pos: usize,
28 seen: HashSet<AssignmentMoveKey>,
29 yielded: usize,
30}
31
32pub struct ScalarAssignmentRequiredStreamingCursor<S>
33where
34 S: PlanningSolution,
35{
36 group: ScalarAssignmentBinding<S>,
37 options: ScalarAssignmentMoveOptions,
38 state: ScalarAssignmentState,
39 cursor: AssignmentFamilyCursor,
40 yielded: usize,
41}
42
43struct AssignmentFamilySlot {
44 family: AssignmentMoveFamily,
45 cursor: AssignmentFamilyCursor,
46 exhausted: bool,
47}
48
49impl<S> ScalarAssignmentMoveCursor<S>
50where
51 S: PlanningSolution,
52{
53 pub(crate) fn new(
54 group: ScalarAssignmentBinding<S>,
55 solution: S,
56 options: ScalarAssignmentMoveOptions,
57 ) -> Self {
58 Self::from_family_range(
59 group,
60 solution,
61 options,
62 AssignmentMoveFamily::Required,
63 AssignmentMoveFamily::EjectionReinsert,
64 true,
65 false,
66 )
67 }
68
69 pub fn required_construction(
70 group: ScalarAssignmentBinding<S>,
71 solution: S,
72 options: ScalarAssignmentMoveOptions,
73 ) -> Self {
74 Self::from_family_range(
75 group,
76 solution,
77 options,
78 AssignmentMoveFamily::Required,
79 AssignmentMoveFamily::Required,
80 false,
81 true,
82 )
83 }
84
85 pub fn required_streaming_construction(
86 group: ScalarAssignmentBinding<S>,
87 solution: S,
88 options: ScalarAssignmentMoveOptions,
89 ) -> Self {
90 Self::from_family_range(
91 group,
92 solution,
93 options.with_required_scarcity_ordering(false),
94 AssignmentMoveFamily::Required,
95 AssignmentMoveFamily::Required,
96 false,
97 false,
98 )
99 }
100
101 pub fn next_required_streaming_construction_move(
102 group: ScalarAssignmentBinding<S>,
103 solution: &S,
104 options: ScalarAssignmentMoveOptions,
105 ) -> Option<CompoundScalarMove<S>> {
106 let options = options.with_required_scarcity_ordering(false);
107 if options.max_moves == 0 {
108 return None;
109 }
110 let mut state = ScalarAssignmentState::new(&group, solution);
111 let mut cursor =
112 AssignmentFamilyCursor::required_entity_values(&group, solution, &state, options);
113 next_family_move(&mut cursor, &group, solution, &mut state)
114 }
115
116 pub fn commit_move(&mut self, mov: &CompoundScalarMove<S>) {
117 for edit in mov.edits() {
118 self.state.set_value(
119 &self.group,
120 &self.solution,
121 edit.entity_index,
122 edit.to_value,
123 );
124 (edit.setter)(
125 &mut self.solution,
126 edit.entity_index,
127 edit.variable_index,
128 edit.to_value,
129 );
130 }
131 }
132
133 pub(crate) fn required(
134 group: ScalarAssignmentBinding<S>,
135 solution: S,
136 options: ScalarAssignmentMoveOptions,
137 ) -> Self {
138 Self::from_family_range(
139 group,
140 solution,
141 options,
142 AssignmentMoveFamily::Required,
143 AssignmentMoveFamily::Required,
144 false,
145 false,
146 )
147 }
148
149 pub(crate) fn optional_construction(
150 group: ScalarAssignmentBinding<S>,
151 solution: S,
152 options: ScalarAssignmentMoveOptions,
153 ) -> Self {
154 Self::from_family_range(
155 group,
156 solution,
157 options,
158 AssignmentMoveFamily::OptionalAssign,
159 AssignmentMoveFamily::OptionalAssign,
160 false,
161 false,
162 )
163 }
164
165 fn from_family_range(
166 group: ScalarAssignmentBinding<S>,
167 solution: S,
168 options: ScalarAssignmentMoveOptions,
169 family: AssignmentMoveFamily,
170 stop_after: AssignmentMoveFamily,
171 spread_budget: bool,
172 batch_required: bool,
173 ) -> Self {
174 let families = if spread_budget {
175 AssignmentMoveFamily::range(family, stop_after)
176 } else {
177 vec![family]
178 };
179 Self {
180 state: ScalarAssignmentState::new(&group, &solution),
181 group,
182 solution,
183 options,
184 batch_required,
185 family_slots: families
186 .into_iter()
187 .map(|family| AssignmentFamilySlot {
188 family,
189 cursor: AssignmentFamilyCursor::Empty,
190 exhausted: false,
191 })
192 .collect(),
193 family_pos: 0,
194 seen: HashSet::new(),
195 yielded: 0,
196 }
197 }
198
199 pub fn next_move(&mut self) -> Option<CompoundScalarMove<S>> {
200 if self.options.max_moves == 0 || self.yielded >= self.options.max_moves {
201 return None;
202 }
203
204 if self.batch_required {
205 self.batch_required = false;
206 if let Some(candidate) =
207 required_batch_move(&self.group, &self.solution, &mut self.state, self.options)
208 {
209 self.seen.insert(normalized_move_key(&candidate));
210 self.yielded += 1;
211 return Some(candidate);
212 }
213 }
214
215 let mut exhausted_turns = 0;
216 while exhausted_turns < self.family_slots.len() {
217 let slot_index = self.family_pos % self.family_slots.len();
218 self.family_pos = (slot_index + 1) % self.family_slots.len();
219 if self.family_slots[slot_index].exhausted {
220 exhausted_turns += 1;
221 continue;
222 }
223 let Some(candidate) = self.next_slot_move(slot_index) else {
224 exhausted_turns += 1;
225 continue;
226 };
227 exhausted_turns = 0;
228 if !self.seen.insert(normalized_move_key(&candidate)) {
229 continue;
230 }
231 self.yielded += 1;
232 return Some(candidate);
233 }
234 None
235 }
236
237 fn next_slot_move(&mut self, slot_index: usize) -> Option<CompoundScalarMove<S>> {
238 if matches!(
239 self.family_slots[slot_index].cursor,
240 AssignmentFamilyCursor::Empty
241 ) {
242 let family = self.family_slots[slot_index].family;
243 self.family_slots[slot_index].cursor = self.open_family_cursor(family, self.options);
244 if matches!(
245 self.family_slots[slot_index].cursor,
246 AssignmentFamilyCursor::Empty
247 ) {
248 self.family_slots[slot_index].exhausted = true;
249 return None;
250 }
251 }
252
253 let candidate = {
254 let cursor = &mut self.family_slots[slot_index].cursor;
255 next_family_move(cursor, &self.group, &self.solution, &mut self.state)
256 };
257 if candidate.is_none() {
258 self.family_slots[slot_index].exhausted = true;
259 }
260 candidate
261 }
262
263 fn open_family_cursor(
264 &mut self,
265 family: AssignmentMoveFamily,
266 options: ScalarAssignmentMoveOptions,
267 ) -> AssignmentFamilyCursor {
268 match family {
269 AssignmentMoveFamily::Required => AssignmentFamilyCursor::required_entity_values(
270 &self.group,
271 &self.solution,
272 &self.state,
273 options,
274 ),
275 AssignmentMoveFamily::OptionalAssign => AssignmentFamilyCursor::entity_values(
276 ordered_entities(&self.group, &self.solution, |entity_index| {
277 !self.state.is_required(entity_index)
278 && self.state.current_value(entity_index).is_none()
279 }),
280 options,
281 AssignmentMoveKind::Optional,
282 ),
283 AssignmentMoveFamily::SequenceWindow => AssignmentFamilyCursor::PairWindow(
284 PairWindowCursor::sequence_window(&self.group, &self.solution, options),
285 ),
286 AssignmentMoveFamily::Rematch => AssignmentFamilyCursor::PairWindow(
287 PairWindowCursor::rematch(&self.group, &self.solution, &self.state, options),
288 ),
289 AssignmentMoveFamily::AugmentingRematch => AssignmentFamilyCursor::CycleWindow(
290 CycleWindowCursor::augmenting(&self.group, &self.solution, &self.state, options),
291 ),
292 AssignmentMoveFamily::Swap => AssignmentFamilyCursor::PairWindow(
293 PairWindowCursor::swap(&self.group, &self.solution, &self.state, options),
294 ),
295 AssignmentMoveFamily::PairedReassignment => AssignmentFamilyCursor::PairWindow(
296 PairWindowCursor::paired(&self.group, &self.solution, &self.state, options),
297 ),
298 AssignmentMoveFamily::ValueWindowSwap => AssignmentFamilyCursor::ValueWindow(
299 super::assignment_block::ValueWindowCursor::new(
300 &self.group,
301 &self.solution,
302 &self.state,
303 options,
304 ),
305 ),
306 AssignmentMoveFamily::ValueLongWindowSwap => AssignmentFamilyCursor::ValueLongWindow(
307 super::assignment_block::ValueLongWindowCursor::new(
308 &self.group,
309 &self.solution,
310 &self.state,
311 options,
312 ),
313 ),
314 AssignmentMoveFamily::ValueRunGapSwap => AssignmentFamilyCursor::ValueRunGapSwap(
315 super::assignment_value_run::ValueRunGapSwapCursor::new(
316 &self.group,
317 &self.solution,
318 &self.state,
319 options,
320 ),
321 ),
322 AssignmentMoveFamily::ValueRunRelease => AssignmentFamilyCursor::ValueRunRelease(
323 super::assignment_value_release::ValueRunReleaseCursor::new(
324 &self.group,
325 &self.solution,
326 &self.state,
327 options,
328 ),
329 ),
330 AssignmentMoveFamily::ValueWindowCycle => AssignmentFamilyCursor::ValueWindowCycle(
331 super::assignment_value_cycle::ValueWindowCycleCursor::new(
332 &self.group,
333 &self.solution,
334 &self.state,
335 options,
336 ),
337 ),
338 AssignmentMoveFamily::ValueBlockReassignment => {
339 AssignmentFamilyCursor::ValueBlockReassignment(
340 super::assignment_block::ValueBlockReassignmentCursor::new(
341 &self.group,
342 &self.solution,
343 &self.state,
344 options,
345 ),
346 )
347 }
348 AssignmentMoveFamily::Reassignment => AssignmentFamilyCursor::entity_values(
349 {
350 let mut entities =
351 ordered_entities(&self.group, &self.solution, |entity_index| {
352 self.state.current_value(entity_index).is_some()
353 });
354 self.state.sort_entities_by_current_value_pressure(
355 &self.group,
356 &self.solution,
357 &mut entities,
358 );
359 entities
360 },
361 options,
362 AssignmentMoveKind::Reassignment,
363 ),
364 AssignmentMoveFamily::OptionalTransfer => {
365 AssignmentFamilyCursor::OptionalAdjustment(OptionalAdjustmentCursor::transfer(
366 &self.group,
367 &self.solution,
368 &self.state,
369 options,
370 ))
371 }
372 AssignmentMoveFamily::OptionalRelease => {
373 AssignmentFamilyCursor::OptionalAdjustment(OptionalAdjustmentCursor::release(
374 &self.group,
375 &self.solution,
376 &self.state,
377 options,
378 ))
379 }
380 AssignmentMoveFamily::EjectionReinsert => AssignmentFamilyCursor::CycleWindow(
381 CycleWindowCursor::ejection(&self.group, &self.solution, &self.state, options),
382 ),
383 AssignmentMoveFamily::Capacity => AssignmentFamilyCursor::Capacity(
384 CapacityCursor::new(&self.group, &self.solution, &self.state, options),
385 ),
386 AssignmentMoveFamily::Done => AssignmentFamilyCursor::Empty,
387 }
388 }
389}
390
391impl<S> ScalarAssignmentRequiredStreamingCursor<S>
392where
393 S: PlanningSolution,
394{
395 pub fn new(
396 group: ScalarAssignmentBinding<S>,
397 solution: &S,
398 options: ScalarAssignmentMoveOptions,
399 ) -> Self {
400 let options = options.with_required_scarcity_ordering(false);
401 let state = ScalarAssignmentState::new(&group, solution);
402 let cursor =
403 AssignmentFamilyCursor::required_entity_values(&group, solution, &state, options);
404 Self {
405 group,
406 options,
407 state,
408 cursor,
409 yielded: 0,
410 }
411 }
412
413 pub fn next_move(&mut self, solution: &S) -> Option<CompoundScalarMove<S>> {
414 if self.options.max_moves == 0 || self.yielded >= self.options.max_moves {
415 return None;
416 }
417 let candidate = next_family_move(&mut self.cursor, &self.group, solution, &mut self.state)?;
418 self.yielded += 1;
419 Some(candidate)
420 }
421
422 pub fn commit_move(&mut self, solution: &S, mov: &CompoundScalarMove<S>) {
423 for edit in mov.edits() {
424 self.state
425 .set_value(&self.group, solution, edit.entity_index, edit.to_value);
426 }
427 }
428}
429
430fn next_family_move<S>(
431 cursor: &mut AssignmentFamilyCursor,
432 group: &ScalarAssignmentBinding<S>,
433 solution: &S,
434 state: &mut ScalarAssignmentState,
435) -> Option<CompoundScalarMove<S>>
436where
437 S: PlanningSolution,
438{
439 match cursor {
440 AssignmentFamilyCursor::EntityValues(entity_cursor) => {
441 let candidate = entity_cursor.next(group, solution, state);
442 if candidate.is_none() {
443 *cursor = AssignmentFamilyCursor::Empty;
444 }
445 candidate
446 }
447 AssignmentFamilyCursor::Capacity(capacity_cursor) => {
448 let candidate = capacity_cursor.next(group, solution, state);
449 if candidate.is_none() {
450 *cursor = AssignmentFamilyCursor::Empty;
451 }
452 candidate
453 }
454 AssignmentFamilyCursor::OptionalAdjustment(optional_cursor) => {
455 let candidate = optional_cursor.next(group, solution, state);
456 if candidate.is_none() {
457 *cursor = AssignmentFamilyCursor::Empty;
458 }
459 candidate
460 }
461 AssignmentFamilyCursor::PairWindow(pair_cursor) => {
462 let candidate = pair_cursor.next(group, solution, state);
463 if candidate.is_none() {
464 *cursor = AssignmentFamilyCursor::Empty;
465 }
466 candidate
467 }
468 AssignmentFamilyCursor::CycleWindow(cycle_cursor) => {
469 let candidate = cycle_cursor.next(group, solution, state);
470 if candidate.is_none() {
471 *cursor = AssignmentFamilyCursor::Empty;
472 }
473 candidate
474 }
475 AssignmentFamilyCursor::ValueWindow(value_window_cursor) => {
476 let candidate = value_window_cursor.next(group, solution, state);
477 if candidate.is_none() {
478 *cursor = AssignmentFamilyCursor::Empty;
479 }
480 candidate
481 }
482 AssignmentFamilyCursor::ValueLongWindow(long_window_cursor) => {
483 let candidate = long_window_cursor.next(group, solution, state);
484 if candidate.is_none() {
485 *cursor = AssignmentFamilyCursor::Empty;
486 }
487 candidate
488 }
489 AssignmentFamilyCursor::ValueRunGapSwap(run_gap_cursor) => {
490 let candidate = run_gap_cursor.next(group, solution, state);
491 if candidate.is_none() {
492 *cursor = AssignmentFamilyCursor::Empty;
493 }
494 candidate
495 }
496 AssignmentFamilyCursor::ValueRunRelease(run_release_cursor) => {
497 let candidate = run_release_cursor.next(group, solution, state);
498 if candidate.is_none() {
499 *cursor = AssignmentFamilyCursor::Empty;
500 }
501 candidate
502 }
503 AssignmentFamilyCursor::ValueWindowCycle(value_window_cycle_cursor) => {
504 let candidate = value_window_cycle_cursor.next(group, solution, state);
505 if candidate.is_none() {
506 *cursor = AssignmentFamilyCursor::Empty;
507 }
508 candidate
509 }
510 AssignmentFamilyCursor::ValueBlockReassignment(block_cursor) => {
511 let candidate = block_cursor.next(group, solution, state);
512 if candidate.is_none() {
513 *cursor = AssignmentFamilyCursor::Empty;
514 }
515 candidate
516 }
517 AssignmentFamilyCursor::Empty => None,
518 }
519}
520
521#[cfg(test)]
522pub(crate) fn collect_assignment_moves<S>(
523 group: &ScalarAssignmentBinding<S>,
524 solution: &S,
525 options: ScalarAssignmentMoveOptions,
526) -> Vec<CompoundScalarMove<S>>
527where
528 S: PlanningSolution,
529{
530 let mut cursor = ScalarAssignmentMoveCursor::new(*group, solution.clone(), options);
531 let mut moves = Vec::new();
532 while let Some(candidate) = cursor.next_move() {
533 moves.push(candidate);
534 }
535 moves
536}
537
538#[cfg(test)]
539pub(crate) fn rematch_assignment_moves<S>(
540 group: &ScalarAssignmentBinding<S>,
541 solution: &S,
542 options: ScalarAssignmentMoveOptions,
543) -> Vec<CompoundScalarMove<S>>
544where
545 S: PlanningSolution,
546{
547 let mut cursor = ScalarAssignmentMoveCursor::from_family_range(
548 *group,
549 solution.clone(),
550 options,
551 AssignmentMoveFamily::Rematch,
552 AssignmentMoveFamily::Rematch,
553 false,
554 false,
555 );
556 let mut moves = Vec::new();
557 while let Some(candidate) = cursor.next_move() {
558 moves.push(candidate);
559 }
560 moves
561}
562
563#[cfg(test)]
564pub(crate) fn value_block_reassignment_assignment_moves<S>(
565 group: &ScalarAssignmentBinding<S>,
566 solution: &S,
567 options: ScalarAssignmentMoveOptions,
568) -> Vec<CompoundScalarMove<S>>
569where
570 S: PlanningSolution,
571{
572 let mut cursor = ScalarAssignmentMoveCursor::from_family_range(
573 *group,
574 solution.clone(),
575 options,
576 AssignmentMoveFamily::ValueBlockReassignment,
577 AssignmentMoveFamily::ValueBlockReassignment,
578 false,
579 false,
580 );
581 let mut moves = Vec::new();
582 while let Some(candidate) = cursor.next_move() {
583 moves.push(candidate);
584 }
585 moves
586}
587
588#[cfg(test)]
589pub(crate) fn value_window_assignment_moves<S>(
590 group: &ScalarAssignmentBinding<S>,
591 solution: &S,
592 options: ScalarAssignmentMoveOptions,
593) -> Vec<CompoundScalarMove<S>>
594where
595 S: PlanningSolution,
596{
597 let mut cursor = ScalarAssignmentMoveCursor::from_family_range(
598 *group,
599 solution.clone(),
600 options,
601 AssignmentMoveFamily::ValueWindowSwap,
602 AssignmentMoveFamily::ValueWindowSwap,
603 false,
604 false,
605 );
606 let mut moves = Vec::new();
607 while let Some(candidate) = cursor.next_move() {
608 moves.push(candidate);
609 }
610 moves
611}
612
613fn normalized_move_key<S>(candidate: &CompoundScalarMove<S>) -> AssignmentMoveKey {
614 let mut key = candidate
615 .edits()
616 .iter()
617 .map(|edit| {
618 (
619 edit.descriptor_index,
620 edit.entity_index,
621 edit.variable_index,
622 edit.variable_name,
623 edit.to_value,
624 )
625 })
626 .collect::<Vec<_>>();
627 key.sort_unstable();
628 key
629}