blob: 3ded3350b4a3538ec1407f2b1bddc5af531a7f0d [file] [log] [blame]
 //! `UnionFind` is a disjoint-set data structure. use super::graph::IndexType; /// `UnionFind` is a disjoint-set data structure. It tracks set membership of *n* elements /// indexed from *0* to *n - 1*. The scalar type is `K` which must be an unsigned integer type. /// /// http://en.wikipedia.org/wiki/Disjoint-set_data_structure /// /// Too awesome not to quote: /// /// “The amortized time per operation is **O(α(n))** where **α(n)** is the /// inverse of **f(x) = A(x, x)** with **A** being the extremely fast-growing Ackermann function.” #[derive(Debug, Clone)] pub struct UnionFind { // For element at index *i*, store the index of its parent; the representative itself // stores its own index. This forms equivalence classes which are the disjoint sets, each // with a unique representative. parent: Vec, // It is a balancing tree structure, // so the ranks are logarithmic in the size of the container -- a byte is more than enough. // // Rank is separated out both to save space and to save cache in when searching in the parent // vector. rank: Vec, } #[inline] unsafe fn get_unchecked(xs: &[K], index: usize) -> &K { debug_assert!(index < xs.len()); xs.get_unchecked(index) } impl UnionFind where K: IndexType { /// Create a new `UnionFind` of `n` disjoint sets. pub fn new(n: usize) -> Self { let rank = vec![0; n]; let parent = (0..n).map(K::new).collect::>(); UnionFind{parent: parent, rank: rank} } /// Return the representative for `x`. /// /// **Panics** if `x` is out of bounds. pub fn find(&self, x: K) -> K { assert!(x.index() < self.parent.len()); unsafe { let mut x = x; loop { // Use unchecked indexing because we can trust the internal set ids. let xparent = *get_unchecked(&self.parent, x.index()); if xparent == x { break } x = xparent; } x } } /// Return the representative for `x`. /// /// Write back the found representative, flattening the internal /// datastructure in the process and quicken future lookups. /// /// **Panics** if `x` is out of bounds. pub fn find_mut(&mut self, x: K) -> K { assert!(x.index() < self.parent.len()); unsafe { self.find_mut_recursive(x) } } unsafe fn find_mut_recursive(&mut self, x: K) -> K { let xparent = *get_unchecked(&self.parent, x.index()); if xparent != x { let xrep = self.find_mut_recursive(xparent); let xparent = self.parent.get_unchecked_mut(x.index()); *xparent = xrep; *xparent } else { xparent } } /// Unify the two sets containing `x` and `y`. /// /// Return `false` if the sets were already the same, `true` if they were unified. /// /// **Panics** if `x` or `y` is out of bounds. pub fn union(&mut self, x: K, y: K) -> bool { if x == y { return false } let xrep = self.find_mut(x); let yrep = self.find_mut(y); if xrep == yrep { return false } let xrepu = xrep.index(); let yrepu = yrep.index(); let xrank = self.rank[xrepu]; let yrank = self.rank[yrepu]; // The rank corresponds roughly to the depth of the treeset, so put the // smaller set below the larger if xrank < yrank { self.parent[xrepu] = yrep; } else if xrank > yrank { self.parent[yrepu] = xrep; } else { // put y below x when equal. self.parent[yrepu] = xrep; self.rank[xrepu] += 1; } true } /// Return a vector mapping each element to its representative. pub fn into_labeling(mut self) -> Vec { // write in the labeling of each element unsafe { for ix in 0..self.parent.len() { let k = *get_unchecked(&self.parent, ix); let xrep = self.find_mut_recursive(k); *self.parent.get_unchecked_mut(ix) = xrep; } } self.parent } }