use std::collections::HashMap;
use uuid::Uuid;
#[derive(Debug, Default)]
pub struct UnionFind {
parent: HashMap<Uuid, Uuid>,
}
impl UnionFind {
pub fn new() -> Self {
Self {
parent: HashMap::new(),
}
}
pub fn with_capacity(capacity: usize) -> Self {
Self {
parent: HashMap::with_capacity(capacity),
}
}
pub fn make_set(&mut self, x: Uuid) {
self.parent.entry(x).or_insert(x);
}
pub fn find(&mut self, x: Uuid) -> Uuid {
let mut node = x;
let mut path = Vec::new();
while let Some(&parent) = self.parent.get(&node) {
if parent == node {
break;
}
path.push(node);
node = parent;
}
for child in path {
self.parent.insert(child, node);
}
node
}
pub fn union(&mut self, x: Uuid, y: Uuid) {
self.union_by_key(x, y, |id| id);
}
pub fn union_by_key<K, F>(&mut self, x: Uuid, y: Uuid, root_key: F)
where
K: Ord,
F: Fn(Uuid) -> K,
{
let root_x = self.find(x);
let root_y = self.find(y);
if root_x != root_y {
if root_key(root_x) <= root_key(root_y) {
self.parent.insert(root_y, root_x);
} else {
self.parent.insert(root_x, root_y);
}
}
}
pub fn nodes(&self) -> Vec<Uuid> {
self.parent.keys().copied().collect()
}
pub fn len(&self) -> usize {
self.parent.len()
}
pub fn is_empty(&self) -> bool {
self.parent.is_empty()
}
pub fn from_pairs(pairs: &[(Uuid, Uuid)]) -> HashMap<Uuid, Uuid> {
if pairs.is_empty() {
return HashMap::new();
}
let mut uf = Self::with_capacity(pairs.len() * 2);
for &(child, parent) in pairs {
uf.make_set(child);
uf.make_set(parent);
}
for &(child, parent) in pairs {
uf.union(child, parent);
}
let all_nodes: Vec<Uuid> = uf.nodes();
let mut assignments = HashMap::new();
for node in all_nodes {
let root = uf.find(node);
if root != node {
assignments.insert(node, root);
}
}
assignments
}
}
#[cfg(test)]
mod tests {
use super::*;
fn uuid(s: &str) -> Uuid {
Uuid::parse_str(s).unwrap()
}
#[test]
fn test_basic_union_find() {
let mut uf = UnionFind::new();
let a = uuid("00000000-0000-0000-0000-000000000001");
let b = uuid("00000000-0000-0000-0000-000000000002");
uf.make_set(a);
uf.make_set(b);
uf.union(a, b);
assert_eq!(uf.find(a), a);
assert_eq!(uf.find(b), a);
}
#[test]
fn test_transitivity_chain() {
let mut uf = UnionFind::new();
let a = uuid("00000000-0000-0000-0000-000000000001");
let b = uuid("00000000-0000-0000-0000-000000000002");
let c = uuid("00000000-0000-0000-0000-000000000003");
uf.make_set(a);
uf.make_set(b);
uf.make_set(c);
uf.union(b, c); uf.union(a, b);
assert_eq!(uf.find(a), a);
assert_eq!(uf.find(b), a);
assert_eq!(uf.find(c), a);
}
#[test]
fn test_from_pairs() {
let a = uuid("00000000-0000-0000-0000-000000000001");
let b = uuid("00000000-0000-0000-0000-000000000002");
let c = uuid("00000000-0000-0000-0000-000000000003");
let pairs = vec![(b, a), (c, b)];
let assignments = UnionFind::from_pairs(&pairs);
assert_eq!(assignments.get(&b), Some(&a));
assert_eq!(assignments.get(&c), Some(&a));
assert_eq!(assignments.get(&a), None);
}
#[test]
fn test_empty_pairs() {
let assignments = UnionFind::from_pairs(&[]);
assert!(assignments.is_empty());
}
#[test]
fn test_lexicographic_ordering() {
let mut uf = UnionFind::new();
let a = uuid("00000000-0000-0000-0000-000000000001");
let b = uuid("ffffffff-ffff-ffff-ffff-ffffffffffff");
uf.make_set(a);
uf.make_set(b);
uf.union(b, a);
assert_eq!(uf.find(a), a);
assert_eq!(uf.find(b), a);
}
#[test]
fn test_path_compression() {
let mut uf = UnionFind::new();
let a = uuid("00000000-0000-0000-0000-000000000001");
let b = uuid("00000000-0000-0000-0000-000000000002");
let c = uuid("00000000-0000-0000-0000-000000000003");
let d = uuid("00000000-0000-0000-0000-000000000004");
uf.make_set(a);
uf.make_set(b);
uf.make_set(c);
uf.make_set(d);
uf.union(b, a);
uf.union(c, b);
uf.union(d, c);
assert_eq!(uf.find(d), a);
assert_eq!(uf.find(d), a);
}
#[test]
fn test_find_handles_long_chain_iteratively() {
let mut uf = UnionFind::new();
let root = Uuid::from_u128(0);
uf.parent.insert(root, root);
for i in 1..=20_000u128 {
uf.parent.insert(Uuid::from_u128(i), Uuid::from_u128(i - 1));
}
let tail = Uuid::from_u128(20_000);
assert_eq!(uf.find(tail), root);
assert_eq!(uf.parent.get(&tail), Some(&root));
}
#[test]
fn test_disjoint_sets() {
let mut uf = UnionFind::new();
let a = uuid("00000000-0000-0000-0000-000000000001");
let b = uuid("00000000-0000-0000-0000-000000000002");
let c = uuid("00000000-0000-0000-0000-000000000003");
let d = uuid("00000000-0000-0000-0000-000000000004");
uf.make_set(a);
uf.make_set(b);
uf.make_set(c);
uf.make_set(d);
uf.union(a, b);
uf.union(c, d);
assert_eq!(uf.find(a), uf.find(b));
assert_eq!(uf.find(c), uf.find(d));
assert_ne!(uf.find(a), uf.find(c));
}
}