const NONE: u32 = u32::MAX;
#[derive(Clone, Debug)]
pub(super) struct Skeleton {
parent: Box<[u32]>,
rank: Box<[u8]>,
log: Vec<(u32, bool)>,
}
impl Skeleton {
pub(super) fn new(n: usize) -> Self {
Self {
parent: (0..n as u32).collect(),
rank: vec![0; n].into_boxed_slice(),
log: Vec::new(),
}
}
pub(super) fn find(&self, mut x: u32) -> u32 {
while self.parent[x as usize] != x {
x = self.parent[x as usize];
}
x
}
pub(super) fn same(&self, x: u32, y: u32) -> bool {
self.find(x) == self.find(y)
}
pub(super) fn union(&mut self, x: u32, y: u32) -> bool {
let (mut a, mut b) = (self.find(x), self.find(y));
if a == b {
self.log.push((NONE, false));
return false;
}
if self.rank[a as usize] < self.rank[b as usize] {
(a, b) = (b, a);
}
self.parent[b as usize] = a;
let bumped = self.rank[a as usize] == self.rank[b as usize];
if bumped {
self.rank[a as usize] += 1;
}
self.log.push((b, bumped));
true
}
pub(super) fn undo(&mut self) {
let (b, bumped) = self.log.pop().expect("no union to undo");
if b == NONE {
return;
}
let a = self.parent[b as usize];
self.parent[b as usize] = b;
if bumped {
self.rank[a as usize] -= 1;
}
}
pub(super) fn commit(&mut self, capacity: usize) {
self.log.clear();
self.log.reserve(capacity);
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn union_find_with_undo() {
let mut s = Skeleton::new(6);
assert!(s.union(0, 1));
assert!(s.union(2, 3));
s.commit(4);
assert!(s.same(0, 1) && s.same(2, 3) && !s.same(1, 2));
assert!(s.union(1, 2));
assert!(!s.union(0, 3), "already joined");
assert!(s.union(4, 5));
assert!(s.same(0, 3) && s.same(4, 5) && !s.same(3, 4));
s.undo();
assert!(!s.same(4, 5));
s.undo();
assert!(s.same(0, 3), "undoing a no-op changes nothing");
s.undo();
assert!(!s.same(1, 2) && s.same(0, 1) && s.same(2, 3));
assert_eq!(s.log, []);
assert!(s.rank.iter().all(|&r| r <= 1), "ranks went back down");
}
}