use super::CascadePropagation;
use crate::domain::PlanningSolution;
impl CascadePropagation {
pub(super) fn rebuild_groups<S: PlanningSolution>(&mut self, solution: &S, count: usize) {
self.node.clear();
self.member_offsets.clear();
self.members.clear();
let mut parent: Vec<usize> = Vec::new();
for element in 0..count {
self.scratch.clear();
solution.cascading_peers(element, &mut self.scratch);
for &peer in &self.scratch {
assert!(
peer < count,
"cascading element {element} declares peer {peer}, but there are only {count} elements"
);
if parent.is_empty() {
parent = (0..count).collect();
}
let (a, b) = (root(&mut parent, element), root(&mut parent, peer));
parent[a.max(b)] = a.min(b);
}
}
self.scratch.clear();
if parent.is_empty() {
return;
}
self.node = (0..count)
.map(|element| root(&mut parent, element))
.collect();
self.member_offsets.resize(count + 1, 0);
for &node in &self.node {
self.member_offsets[node + 1] += 1;
}
for node in 0..count {
self.member_offsets[node + 1] += self.member_offsets[node];
}
self.members.resize(count, 0);
let mut fill = self.member_offsets.clone();
for element in 0..count {
let node = self.node[element];
self.members[fill[node]] = element;
fill[node] += 1;
}
}
#[inline(always)]
pub(super) fn node_of<const GROUPED: bool>(&self, element: usize) -> usize {
if !GROUPED {
element
} else {
self.node[element]
}
}
#[inline(always)]
pub(super) fn member_count<const GROUPED: bool>(&self, node: usize) -> usize {
if !GROUPED {
1
} else {
self.member_offsets[node + 1] - self.member_offsets[node]
}
}
#[inline(always)]
pub(super) fn member<const GROUPED: bool>(&self, node: usize, index: usize) -> usize {
if !GROUPED {
node
} else {
self.members[self.member_offsets[node] + index]
}
}
}
fn root(parent: &mut [usize], mut element: usize) -> usize {
while parent[element] != element {
parent[element] = parent[parent[element]];
element = parent[element];
}
element
}