1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146
//! `UnionFind<K>` is a disjoint-set data structure.
use super::graph::IndexType;
use std::cmp::Ordering;
/// `UnionFind<K>` 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<K> {
// 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<K>,
// 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<u8>,
}
#[inline]
unsafe fn get_unchecked<K>(xs: &[K], index: usize) -> &K {
debug_assert!(index < xs.len());
xs.get_unchecked(index)
}
#[inline]
unsafe fn get_unchecked_mut<K>(xs: &mut [K], index: usize) -> &mut K {
debug_assert!(index < xs.len());
xs.get_unchecked_mut(index)
}
impl<K> UnionFind<K>
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::<Vec<K>>();
UnionFind { parent, 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, mut x: K) -> K {
let mut parent = *get_unchecked(&self.parent, x.index());
while parent != x {
let grandparent = *get_unchecked(&self.parent, parent.index());
*get_unchecked_mut(&mut self.parent, x.index()) = grandparent;
x = parent;
parent = grandparent;
}
x
}
/// Returns `true` if the given elements belong to the same set, and returns
/// `false` otherwise.
pub fn equiv(&self, x: K, y: K) -> bool {
self.find(x) == self.find(y)
}
/// 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
match xrank.cmp(&yrank) {
Ordering::Less => self.parent[xrepu] = yrep,
Ordering::Greater => self.parent[yrepu] = xrep,
Ordering::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<K> {
// 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
}
}