use super::PlanningSolution;
const UNVISITED: usize = usize::MAX;
#[derive(Default)]
pub struct CascadePropagation {
offsets: Vec<usize>,
dependents: Vec<usize>,
in_cone: Vec<bool>,
dirty: Vec<bool>,
done: Vec<bool>,
cycle: Vec<bool>,
pending_inputs: Vec<usize>,
order: Vec<usize>,
low: Vec<usize>,
on_stack: Vec<bool>,
cone: Vec<usize>,
stack: Vec<usize>,
ready: Vec<usize>,
scratch: Vec<usize>,
}
impl CascadePropagation {
pub fn new<S: PlanningSolution>(solution: &S) -> Self {
let mut propagation = Self::default();
propagation.rebuild_dependencies(solution);
propagation
}
pub fn rebuild_dependencies<S: PlanningSolution>(&mut self, solution: &S) {
let count = solution.cascading_element_count();
self.offsets.clear();
self.offsets.resize(count + 1, 0);
for element in 0..count {
self.scratch.clear();
solution.cascading_dependencies(element, &mut self.scratch);
for &dependency in &self.scratch {
assert!(
dependency < count,
"cascading element {element} depends on element {dependency}, but there are only {count} elements"
);
self.offsets[dependency + 1] += 1;
}
}
for element in 0..count {
self.offsets[element + 1] += self.offsets[element];
}
self.dependents.clear();
self.dependents.resize(self.offsets[count], 0);
let mut fill = self.offsets.clone();
for element in 0..count {
self.scratch.clear();
solution.cascading_dependencies(element, &mut self.scratch);
for &dependency in &self.scratch {
self.dependents[fill[dependency]] = element;
fill[dependency] += 1;
}
}
self.scratch.clear();
for flags in [
&mut self.in_cone,
&mut self.dirty,
&mut self.done,
&mut self.cycle,
&mut self.on_stack,
] {
flags.clear();
flags.resize(count, false);
}
self.pending_inputs.clear();
self.pending_inputs.resize(count, 0);
self.order.clear();
self.order.resize(count, UNVISITED);
self.low.clear();
self.low.resize(count, UNVISITED);
}
pub fn refresh_all<S: PlanningSolution>(solution: &mut S) {
let mut propagation = Self::new(solution);
let count = solution.cascading_element_count();
propagation.propagate(solution, 0..count, |_, _| {});
}
pub fn propagate<S, I, W>(&mut self, solution: &mut S, changed: I, mut before_write: W)
where
S: PlanningSolution,
I: IntoIterator<Item = usize>,
W: FnMut(&S, usize),
{
for element in changed {
self.dirty[element] = true;
if !self.in_cone[element] {
self.in_cone[element] = true;
self.cone.push(element);
self.stack.push(element);
}
}
while let Some(element) = self.stack.pop() {
if let Some(next) = solution.cascading_next(element) {
self.reach(next);
}
for position in self.offsets[element]..self.offsets[element + 1] {
self.reach(self.dependents[position]);
}
}
self.ready.extend(
self.cone
.iter()
.copied()
.filter(|&element| self.pending_inputs[element] == 0),
);
let mut finished = 0;
loop {
while let Some(element) = self.ready.pop() {
self.done[element] = true;
finished += 1;
let assigned = solution.cascading_assigned(element);
if (self.dirty[element] || (assigned && solution.cascading_unset(element)))
&& solution.update_cascading_shadow(element, assigned, |solution| {
before_write(solution, element)
})
{
self.mark_outputs_dirty(solution, element);
}
self.release_outputs(solution, element);
}
if finished == self.cone.len() {
break;
}
self.mark_cycles(solution);
for index in 0..self.cone.len() {
let element = self.cone[index];
if self.cycle[element] && !self.done[element] {
self.done[element] = true;
finished += 1;
if solution.update_cascading_shadow(element, false, |solution| {
before_write(solution, element)
}) {
self.mark_outputs_dirty(solution, element);
}
}
}
for index in 0..self.cone.len() {
let element = self.cone[index];
if self.cycle[element] {
self.release_outputs(solution, element);
}
}
}
for &element in &self.cone {
self.in_cone[element] = false;
self.dirty[element] = false;
self.done[element] = false;
self.cycle[element] = false;
self.pending_inputs[element] = 0;
self.order[element] = UNVISITED;
self.low[element] = UNVISITED;
}
self.cone.clear();
}
fn reach(&mut self, element: usize) {
self.pending_inputs[element] += 1;
if !self.in_cone[element] {
self.in_cone[element] = true;
self.cone.push(element);
self.stack.push(element);
}
}
fn mark_outputs_dirty<S: PlanningSolution>(&mut self, solution: &S, element: usize) {
if let Some(next) = solution.cascading_next(element) {
self.dirty[next] = true;
}
for position in self.offsets[element]..self.offsets[element + 1] {
self.dirty[self.dependents[position]] = true;
}
}
fn release_outputs<S: PlanningSolution>(&mut self, solution: &S, element: usize) {
if let Some(next) = solution.cascading_next(element) {
self.release(next);
}
for position in self.offsets[element]..self.offsets[element + 1] {
self.release(self.dependents[position]);
}
}
fn release(&mut self, element: usize) {
self.pending_inputs[element] -= 1;
if self.pending_inputs[element] == 0 && !self.done[element] && !self.cycle[element] {
self.ready.push(element);
}
}
#[cold]
fn mark_cycles<S: PlanningSolution>(&mut self, solution: &S) {
let mut next_order = 0;
let mut components = Vec::new();
let mut frames: Vec<(usize, Vec<usize>)> = Vec::new();
for index in 0..self.cone.len() {
let root = self.cone[index];
if self.done[root] || self.order[root] != UNVISITED {
continue;
}
self.enter(
solution,
root,
&mut next_order,
&mut components,
&mut frames,
);
while let Some((element, outputs)) = frames.last_mut() {
let element = *element;
if let Some(output) = outputs.pop() {
if self.order[output] == UNVISITED {
self.enter(
solution,
output,
&mut next_order,
&mut components,
&mut frames,
);
} else if self.on_stack[output] {
self.low[element] = self.low[element].min(self.order[output]);
}
continue;
}
frames.pop();
if let Some((parent, _)) = frames.last() {
self.low[*parent] = self.low[*parent].min(self.low[element]);
}
if self.low[element] == self.order[element] {
let start = components
.iter()
.rposition(|&member| member == element)
.expect("component root is on the stack");
let self_loop = self.depends_on_itself(solution, element);
let is_cycle = components.len() - start > 1 || self_loop;
for member in components.drain(start..) {
self.on_stack[member] = false;
self.cycle[member] = is_cycle;
}
}
}
}
}
fn enter<S: PlanningSolution>(
&mut self,
solution: &S,
element: usize,
next_order: &mut usize,
components: &mut Vec<usize>,
frames: &mut Vec<(usize, Vec<usize>)>,
) {
self.order[element] = *next_order;
self.low[element] = *next_order;
*next_order += 1;
self.on_stack[element] = true;
components.push(element);
let mut outputs = Vec::new();
if let Some(next) = solution.cascading_next(element) {
outputs.push(next);
}
outputs
.extend_from_slice(&self.dependents[self.offsets[element]..self.offsets[element + 1]]);
outputs.retain(|&output| self.in_cone[output] && !self.done[output]);
frames.push((element, outputs));
}
fn depends_on_itself<S: PlanningSolution>(&self, solution: &S, element: usize) -> bool {
solution.cascading_next(element) == Some(element)
|| self.dependents[self.offsets[element]..self.offsets[element + 1]].contains(&element)
}
}