use crate::{
UnionFindError,
union_find::{UnionFind, find, generate_tests, get_roots},
};
pub struct WeightedQuickUnionWPC {
id: Vec<usize>,
size: Vec<usize>,
count: usize,
}
impl UnionFind for WeightedQuickUnionWPC {
fn new(size: usize) -> Self {
assert!(size > 0);
Self {
id: (0..size).collect(),
size: vec![1; size],
count: size,
}
}
fn count(&self) -> usize {
self.count
}
fn union(&mut self, p: usize, q: usize) -> Result<(), UnionFindError> {
let (p_root, q_root) = get_roots!(p, q, self);
if self.size[p_root] < self.size[q_root] {
self.id[p_root] = q_root;
self.size[q_root] += self.size[p_root];
} else {
self.id[q_root] = p_root;
self.size[p_root] += self.size[q_root];
}
self.count -= 1;
Ok(())
}
fn find(&mut self, p: usize) -> Option<usize> {
find!(pc p, self.id)
}
}
generate_tests!(WeightedQuickUnionWPC);