Struct UnionFind

pub struct UnionFind<K> { /* private fields */ }

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.”

Implementations

impl<K> UnionFind<K>

where K: IndexType,

pub fn new(n: usize) -> Self

Create a new UnionFind of n disjoint sets.

pub fn find(&self, x: K) -> K

Return the representative for x.

Panics if x is out of bounds.

pub fn find_mut(&mut self, x: K) -> K

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 equiv(&self, x: K, y: K) -> bool

Returns true if the given elements belong to the same set, and returns false otherwise.

pub fn union(&mut self, x: K, y: K) -> bool

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 into_labeling(self) -> Vec<K>

Return a vector mapping each element to its representative.

Trait Implementations

impl<K: Clone> Clone for UnionFind<K>

fn clone(&self) -> UnionFind<K>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug> Debug for UnionFind<K>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.