mod cycles;
mod groups;
use super::PlanningSolution;
const UNVISITED: usize = usize::MAX;
#[derive(Default)]
pub struct CascadePropagation {
offsets: Vec<usize>,
dependents: Vec<usize>,
node: Vec<usize>,
member_offsets: Vec<usize>,
members: 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();
self.rebuild_groups(solution, count);
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, before_write: W)
where
S: PlanningSolution,
I: IntoIterator<Item = usize>,
W: FnMut(&S, usize),
{
if self.node.is_empty() {
self.propagate_nodes::<false, S, I, W>(solution, changed, before_write);
} else {
self.propagate_nodes::<true, S, I, W>(solution, changed, before_write);
}
}
fn propagate_nodes<const GROUPED: bool, 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 {
let node = self.node_of::<GROUPED>(element);
self.dirty[node] = true;
if !self.in_cone[node] {
self.in_cone[node] = true;
self.cone.push(node);
self.stack.push(node);
}
}
while let Some(node) = self.stack.pop() {
for index in 0..self.member_count::<GROUPED>(node) {
let member = self.member::<GROUPED>(node, index);
if let Some(next) = solution.cascading_next(member) {
self.reach(self.node_of::<GROUPED>(next));
}
for position in self.offsets[member]..self.offsets[member + 1] {
self.reach(self.node_of::<GROUPED>(self.dependents[position]));
}
}
}
self.ready.extend(
self.cone
.iter()
.copied()
.filter(|&node| self.pending_inputs[node] == 0),
);
let mut finished = 0;
loop {
while let Some(node) = self.ready.pop() {
self.done[node] = true;
finished += 1;
let stale = self.dirty[node]
|| (0..self.member_count::<GROUPED>(node)).any(|index| {
let member = self.member::<GROUPED>(node, index);
solution.cascading_assigned(member) && solution.cascading_unset(member)
});
if stale {
for index in 0..self.member_count::<GROUPED>(node) {
let member = self.member::<GROUPED>(node, index);
let assigned = solution.cascading_assigned(member);
if solution.update_cascading_shadow(member, assigned, |solution| {
before_write(solution, member)
}) {
self.mark_outputs_dirty::<GROUPED, S>(solution, member);
}
}
}
self.release_outputs::<GROUPED, S>(solution, node);
}
if finished == self.cone.len() {
break;
}
self.mark_cycles(solution);
for position in 0..self.cone.len() {
let node = self.cone[position];
if self.cycle[node] && !self.done[node] {
self.done[node] = true;
finished += 1;
for index in 0..self.member_count::<GROUPED>(node) {
let member = self.member::<GROUPED>(node, index);
if solution.update_cascading_shadow(member, false, |solution| {
before_write(solution, member)
}) {
self.mark_outputs_dirty::<GROUPED, S>(solution, member);
}
}
}
}
for position in 0..self.cone.len() {
let node = self.cone[position];
if self.cycle[node] {
self.release_outputs::<GROUPED, S>(solution, node);
}
}
}
for &node in &self.cone {
self.in_cone[node] = false;
self.dirty[node] = false;
self.done[node] = false;
self.cycle[node] = false;
self.pending_inputs[node] = 0;
self.order[node] = UNVISITED;
self.low[node] = UNVISITED;
}
self.cone.clear();
}
fn reach(&mut self, node: usize) {
self.pending_inputs[node] += 1;
if !self.in_cone[node] {
self.in_cone[node] = true;
self.cone.push(node);
self.stack.push(node);
}
}
fn mark_outputs_dirty<const GROUPED: bool, S: PlanningSolution>(
&mut self,
solution: &S,
element: usize,
) {
if let Some(next) = solution.cascading_next(element) {
let node = self.node_of::<GROUPED>(next);
self.dirty[node] = true;
}
for position in self.offsets[element]..self.offsets[element + 1] {
let node = self.node_of::<GROUPED>(self.dependents[position]);
self.dirty[node] = true;
}
}
fn release_outputs<const GROUPED: bool, S: PlanningSolution>(
&mut self,
solution: &S,
node: usize,
) {
for index in 0..self.member_count::<GROUPED>(node) {
let member = self.member::<GROUPED>(node, index);
if let Some(next) = solution.cascading_next(member) {
self.release(self.node_of::<GROUPED>(next));
}
for position in self.offsets[member]..self.offsets[member + 1] {
self.release(self.node_of::<GROUPED>(self.dependents[position]));
}
}
}
fn release(&mut self, node: usize) {
self.pending_inputs[node] -= 1;
if self.pending_inputs[node] == 0 && !self.done[node] && !self.cycle[node] {
self.ready.push(node);
}
}
}