use solverforge_core::domain::{CascadePropagation, PlanningSolution};
use solverforge_core::score::SoftScore;
use solverforge_core::{ConstraintRef, ImpactType};
use crate::api::constraint_set::IncrementalConstraint;
use crate::constraint::incremental::IncrementalUniConstraint;
use crate::director::score_director::ScoreDirector;
use crate::stream::collection_extract::{source, ChangeSource, SourceExtract};
const MACHINES: usize = 0;
const TASKS: usize = 1;
#[derive(Clone, Debug, Default)]
struct Task {
duration: i64,
waits_on: Option<usize>,
machine: Option<usize>,
previous: Option<usize>,
next: Option<usize>,
start: Option<i64>,
}
#[derive(Clone, Debug)]
struct Shop {
machines: Vec<Vec<usize>>,
tasks: Vec<Task>,
score: Option<SoftScore>,
}
impl Shop {
fn end(&self, task: usize) -> Option<i64> {
self.tasks[task]
.start
.map(|start| start + self.tasks[task].duration)
}
fn compute_start(&self, task: usize) -> Option<i64> {
let mut start = 0;
if let Some(previous) = self.tasks[task].previous {
start = start.max(self.end(previous)?);
}
if let Some(dependency) = self.tasks[task].waits_on {
start = start.max(self.end(dependency)?);
}
Some(start)
}
}
impl PlanningSolution for Shop {
type Score = SoftScore;
fn score(&self) -> Option<SoftScore> {
self.score
}
fn set_score(&mut self, score: Option<SoftScore>) {
self.score = score;
}
fn update_entity_shadows(&mut self, descriptor_index: usize, entity_index: usize) {
self.update_list_structure_shadows(descriptor_index, entity_index);
if descriptor_index == MACHINES {
let changed = self.machines[entity_index].clone();
CascadePropagation::new(self).propagate(self, changed, |_, _| {});
}
}
fn update_all_shadows(&mut self) {
for task in 0..self.tasks.len() {
self.clear_list_shadows(task);
}
for machine in 0..self.machines.len() {
self.update_list_structure_shadows(MACHINES, machine);
}
CascadePropagation::refresh_all(self);
}
fn list_shadow_elements(
&self,
descriptor_index: usize,
entity_index: usize,
) -> Option<(usize, &[usize])> {
(descriptor_index == MACHINES).then(|| (TASKS, self.machines[entity_index].as_slice()))
}
fn clear_list_shadows(&mut self, element: usize) {
let task = &mut self.tasks[element];
task.machine = None;
task.previous = None;
task.next = None;
}
const HAS_CASCADING_SHADOWS: bool = true;
fn cascading_element_count(&self) -> usize {
self.tasks.len()
}
fn cascading_assigned(&self, element: usize) -> bool {
self.tasks[element].machine.is_some()
}
fn cascading_next(&self, element: usize) -> Option<usize> {
self.tasks[element].next
}
fn cascading_dependencies(&self, element: usize, dependencies: &mut Vec<usize>) {
dependencies.extend(self.tasks[element].waits_on);
}
fn cascading_unset(&self, element: usize) -> bool {
self.tasks[element].start.is_none()
}
fn update_cascading_shadow<W: FnOnce(&Self)>(
&mut self,
element: usize,
computable: bool,
before_write: W,
) -> bool {
let start = if computable {
self.compute_start(element)
} else {
None
};
if self.tasks[element].start == start {
return false;
}
before_write(self);
self.tasks[element].start = start;
true
}
fn update_list_structure_shadows(&mut self, descriptor_index: usize, entity_index: usize) {
if descriptor_index != MACHINES {
return;
}
let list = &self.machines[entity_index];
for (position, &task) in list.iter().enumerate() {
let task = &mut self.tasks[task];
task.machine = Some(entity_index);
task.previous = position.checked_sub(1).map(|previous| list[previous]);
task.next = list.get(position + 1).copied();
}
}
}
type StartCost = IncrementalUniConstraint<
Shop,
Task,
SourceExtract<fn(&Shop) -> &[Task]>,
fn(&Shop, &Task) -> bool,
fn(&Task) -> SoftScore,
SoftScore,
>;
fn start_cost() -> StartCost {
fn tasks(shop: &Shop) -> &[Task] {
&shop.tasks
}
fn every(_: &Shop, _: &Task) -> bool {
true
}
fn cost(task: &Task) -> SoftScore {
match task.start {
Some(start) => SoftScore::of(
start * 10
+ task.machine.map_or(0, |machine| machine as i64 + 1)
+ task.previous.map_or(0, |previous| previous as i64 * 100),
),
None if task.machine.is_some() => SoftScore::of(5000),
None => SoftScore::of(1000),
}
}
IncrementalUniConstraint::new(
ConstraintRef::new("", "start cost"),
ImpactType::Penalty,
source(
tasks as fn(&Shop) -> &[Task],
ChangeSource::Descriptor(TASKS),
),
every as fn(&Shop, &Task) -> bool,
cost as fn(&Task) -> SoftScore,
false,
)
}
type Director = ScoreDirector<Shop, (StartCost,)>;
fn director(machines: Vec<Vec<usize>>, durations: &[i64], waits_on: &[(usize, usize)]) -> Director {
let mut tasks: Vec<Task> = durations
.iter()
.map(|&duration| Task {
duration,
..Task::default()
})
.collect();
for &(task, dependency) in waits_on {
tasks[task].waits_on = Some(dependency);
}
let mut director = ScoreDirector::new(
Shop {
machines,
tasks,
score: None,
},
(start_cost(),),
);
director.calculate_score();
director
}
fn assert_matches_fresh(director: &mut Director) {
let mut fresh = director.working_solution().clone();
fresh.update_all_shadows();
let starts = |shop: &Shop| shop.tasks.iter().map(|task| task.start).collect::<Vec<_>>();
assert_eq!(
starts(director.working_solution()),
starts(&fresh),
"machines {:?}",
director.working_solution().machines
);
assert_eq!(
director.calculate_score(),
start_cost().evaluate(&fresh),
"machines {:?}",
director.working_solution().machines
);
}
fn change(director: &mut Director, owners: &[usize], edit: impl FnOnce(&mut Vec<Vec<usize>>)) {
for &owner in owners {
director.before_variable_changed(MACHINES, owner);
}
edit(&mut director.working_solution_mut().machines);
for &owner in owners {
director.after_variable_changed(MACHINES, owner);
}
}
#[test]
fn a_task_pushed_later_on_the_saw_retimes_its_milling_on_the_mill() {
let mut director = director(vec![vec![0], vec![1, 2]], &[4, 3, 2, 10], &[(1, 0)]);
assert_matches_fresh(&mut director);
assert_eq!(director.working_solution().tasks[1].start, Some(4));
change(&mut director, &[0], |machines| machines[0].insert(0, 3));
assert_eq!(director.working_solution().tasks[1].start, Some(14));
assert_eq!(director.working_solution().tasks[2].start, Some(17));
assert_matches_fresh(&mut director);
change(&mut director, &[0], |machines| {
machines[0].remove(0);
});
assert_eq!(director.working_solution().tasks[1].start, Some(4));
assert_matches_fresh(&mut director);
}
#[test]
fn a_move_that_closes_a_dependency_cycle_unsets_it_and_its_undo_restores_it() {
let mut director = director(vec![vec![0], vec![2, 1]], &[4, 3, 5], &[(0, 2), (1, 0)]);
assert_matches_fresh(&mut director);
change(&mut director, &[1, 0], |machines| {
machines[1].retain(|&task| task != 2);
machines[0].push(2);
});
let starts: Vec<_> = director
.working_solution()
.tasks
.iter()
.map(|task| task.start)
.collect();
assert_eq!(starts, vec![None, None, None]);
assert_matches_fresh(&mut director);
change(&mut director, &[0, 1], |machines| {
machines[0].retain(|&task| task != 2);
machines[1].insert(0, 2);
});
assert_matches_fresh(&mut director);
}
struct Lcg(u64);
impl Lcg {
fn below(&mut self, bound: usize) -> usize {
self.0 = self
.0
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
((self.0 >> 33) as usize) % bound
}
}
#[test]
fn random_moves_and_undos_on_three_machines_keep_the_score_fresh() {
let durations: Vec<i64> = (0..15).map(|task| (task % 4 + 1) as i64).collect();
let waits: Vec<(usize, usize)> = (5..15)
.map(|task| (task, (task * 3) % 5 + task / 5 - 1))
.collect();
let mut director = director(
vec![(0..5).collect(), (5..10).collect(), (10..13).collect()],
&durations,
&waits,
);
assert_matches_fresh(&mut director);
let mut random = Lcg(11);
for _ in 0..300 {
let before = director.working_solution().machines.clone();
let from = random.below(3);
let to = random.below(3);
let owners: Vec<usize> = if from == to {
vec![from]
} else {
vec![from, to]
};
let unassigned: Vec<usize> = (0..15)
.filter(|&task| director.working_solution().tasks[task].machine.is_none())
.collect();
match random.below(3) {
0 if !before[from].is_empty() => {
let task = before[from][random.below(before[from].len())];
let position = random.below(before[to].len() + 1);
change(&mut director, &owners, |machines| {
machines[from].retain(|&held| held != task);
let position = position.min(machines[to].len());
machines[to].insert(position, task);
});
}
1 if !before[from].is_empty() => {
let position = random.below(before[from].len());
change(&mut director, &[from], |machines| {
machines[from].remove(position);
});
}
_ if !unassigned.is_empty() => {
let task = unassigned[random.below(unassigned.len())];
let position = random.below(before[to].len() + 1);
change(&mut director, &[to], |machines| {
machines[to].insert(position, task)
});
}
_ => continue,
}
assert_matches_fresh(&mut director);
if random.below(2) == 0 {
change(&mut director, &[0, 1, 2], |machines| *machines = before);
assert_matches_fresh(&mut director);
}
}
}