use crate::domain::{CascadePropagation, PlanningSolution};
use crate::score::SoftScore;
#[derive(Clone, Debug, Default)]
struct Task {
duration: i64,
waits_on: Vec<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>,
computes: usize,
score: Option<SoftScore>,
}
impl Shop {
fn new(machines: Vec<Vec<usize>>, durations: &[i64], waits_on: &[(usize, usize)]) -> Self {
let mut tasks: Vec<Task> = durations
.iter()
.map(|&duration| Task {
duration,
..Task::default()
})
.collect();
for &(task, dependency) in waits_on {
tasks[task].waits_on.push(dependency);
}
let mut shop = Self {
machines,
tasks,
computes: 0,
score: None,
};
shop.refresh();
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)?);
}
for &dependency in &self.tasks[task].waits_on {
start = start.max(self.end(dependency)?);
}
Some(start)
}
fn refresh_structure(&mut self, machine: usize) {
let list = self.machines[machine].clone();
for (position, &task) in list.iter().enumerate() {
let task = &mut self.tasks[task];
task.machine = Some(machine);
task.previous = position.checked_sub(1).map(|previous| list[previous]);
task.next = list.get(position + 1).copied();
}
}
fn refresh(&mut self) {
for task in &mut self.tasks {
task.machine = None;
task.previous = None;
task.next = None;
}
for machine in 0..self.machines.len() {
self.refresh_structure(machine);
}
CascadePropagation::refresh_all(self);
}
fn starts(&self) -> Vec<Option<i64>> {
self.tasks.iter().map(|task| task.start).collect()
}
}
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;
}
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_from_slice(&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.computes += 1;
self.compute_start(element)
} else {
None
};
if self.tasks[element].start == start {
return false;
}
before_write(self);
self.tasks[element].start = start;
true
}
}
fn change(
shop: &mut Shop,
propagation: &mut CascadePropagation,
machines: &[usize],
edit: impl FnOnce(&mut Vec<Vec<usize>>),
) -> Vec<usize> {
let mut changed: Vec<usize> = machines
.iter()
.flat_map(|&machine| shop.machines[machine].clone())
.collect();
edit(&mut shop.machines);
for &machine in machines {
changed.extend(shop.machines[machine].iter().copied());
}
changed.sort_unstable();
changed.dedup();
for &task in &changed {
if !shop.machines.iter().any(|list| list.contains(&task)) {
let task = &mut shop.tasks[task];
task.machine = None;
task.previous = None;
task.next = None;
}
}
for &machine in machines {
shop.refresh_structure(machine);
}
let mut written = Vec::new();
propagation.propagate(shop, changed, |_, element| written.push(element));
written
}
fn assert_fresh(shop: &Shop) {
let mut fresh = shop.clone();
fresh.refresh();
assert_eq!(
shop.starts(),
fresh.starts(),
"machines {:?}",
shop.machines
);
}
fn saw_and_mill() -> Shop {
Shop::new(vec![vec![0, 2], vec![1, 3]], &[4, 3, 5, 2], &[(1, 0)])
}
#[test]
fn a_full_refresh_follows_dependencies_across_lists() {
let shop = saw_and_mill();
assert_eq!(shop.starts(), vec![Some(0), Some(4), Some(4), Some(7)]);
}
#[test]
fn a_change_in_one_list_retimes_the_dependents_in_another() {
let mut shop = saw_and_mill();
let mut propagation = CascadePropagation::new(&shop);
shop.tasks.push(Task {
duration: 10,
..Task::default()
});
propagation.rebuild_dependencies(&shop);
let written = change(&mut shop, &mut propagation, &[0], |machines| {
machines[0].insert(0, 4)
});
assert_eq!(
shop.starts(),
vec![Some(10), Some(14), Some(14), Some(17), Some(0)]
);
assert_fresh(&shop);
let mut written = written;
written.sort_unstable();
assert_eq!(written, vec![0, 1, 2, 3, 4]);
}
#[test]
fn propagation_stops_where_a_value_does_not_change() {
let mut shop = Shop::new(
vec![vec![0, 2], vec![3, 1, 4]],
&[4, 3, 5, 20, 2],
&[(1, 0)],
);
let mut propagation = CascadePropagation::new(&shop);
assert_eq!(shop.tasks[1].start, Some(20));
shop.computes = 0;
let written = change(&mut shop, &mut propagation, &[0], |machines| {
machines[0].swap(0, 1)
});
assert_fresh(&shop);
assert_eq!(written, vec![2, 0]);
assert_eq!(shop.computes, 3);
}
#[test]
fn a_dependency_cycle_is_unset_and_its_dependents_follow() {
let shop = Shop::new(vec![vec![0, 2], vec![1]], &[4, 3, 5], &[(0, 2), (1, 2)]);
assert_eq!(shop.starts(), vec![None, None, None]);
let mut shop = shop;
let mut propagation = CascadePropagation::new(&shop);
change(&mut shop, &mut propagation, &[0, 1], |machines| {
machines[0].retain(|&task| task != 2);
machines[1].insert(0, 2);
});
assert_eq!(shop.starts(), vec![Some(5), Some(5), Some(0)]);
assert_fresh(&shop);
change(&mut shop, &mut propagation, &[0, 1], |machines| {
machines[1].retain(|&task| task != 2);
machines[0].push(2);
});
assert_eq!(shop.starts(), vec![None, None, None]);
assert_fresh(&shop);
}
#[test]
fn an_element_that_depends_on_itself_is_unset() {
let shop = Shop::new(vec![vec![0, 1]], &[4, 3], &[(0, 0)]);
assert_eq!(shop.starts(), vec![None, None]);
}
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_across_three_machines_match_a_full_refresh() {
let durations: Vec<i64> = (0..18).map(|task| (task % 5 + 1) as i64).collect();
let waits: Vec<(usize, usize)> = (6..18)
.flat_map(|task| [(task, task - 6), (task, (task * 7 + 3) % task)])
.filter(|&(task, dependency)| task != dependency)
.collect();
let machines = vec![
(0..6).collect::<Vec<_>>(),
(6..12).collect(),
(12..16).collect(),
];
let mut shop = Shop::new(machines, &durations, &waits);
let mut propagation = CascadePropagation::new(&shop);
let mut random = Lcg(7);
for step in 0..400 {
let from = random.below(3);
let to = random.below(3);
let touched: Vec<usize> = if from == to {
vec![from]
} else {
vec![from, to]
};
let written_before = shop.computes;
match random.below(3) {
0 if !shop.machines[from].is_empty() => {
let task = shop.machines[from][random.below(shop.machines[from].len())];
let position = random.below(shop.machines[to].len() + 1);
change(&mut shop, &mut propagation, &touched, |machines| {
machines[from].retain(|&held| held != task);
let position = position.min(machines[to].len());
machines[to].insert(position, task);
});
}
1 if !shop.machines[from].is_empty() => {
let position = random.below(shop.machines[from].len());
change(&mut shop, &mut propagation, &[from], |machines| {
machines[from].remove(position);
});
}
_ => {
let unassigned: Vec<usize> = (0..shop.tasks.len())
.filter(|&task| shop.tasks[task].machine.is_none())
.collect();
if let Some(&task) = unassigned.get(random.below(unassigned.len().max(1))) {
let position = random.below(shop.machines[to].len() + 1);
change(&mut shop, &mut propagation, &[to], |machines| {
machines[to].insert(position, task)
});
}
}
}
assert!(
shop.computes - written_before <= shop.tasks.len(),
"step {step}: an element was computed more than once"
);
assert_fresh(&shop);
}
}