Struct UnionFind

pub(crate) struct UnionFind<Key: Idx> {
    table: IndexVec<Key, UnionFindEntry<Key>>,
}

Simple implementation of a union-find data structure, i.e. a disjoint-set forest.

Fields

table: IndexVec<Key, UnionFindEntry<Key>>

Implementations

impl<Key: Idx> UnionFind<Key>

pub(crate) fn new(num_keys: usize) -> Self

Creates a new disjoint-set forest containing the keys 0..num_keys. Initially, every key is part of its own one-element set.

pub(crate) fn find(&mut self, key: Key) -> Key

Returns the “root” key of the disjoint-set containing the given key. If two keys have the same root, they belong to the same set.

Also updates internal data structures to make subsequent find operations faster.

pub(crate) fn unify(&mut self, a: Key, b: Key) -> Key

Merges the set containing a and the set containing b into one set.

Returns the common root of both keys, after the merge.

pub(crate) fn snapshot(&mut self) -> IndexVec<Key, Key>

Takes a “snapshot” of the current state of this disjoint-set forest, in the form of a vector that directly maps each key to its current root.

Trait Implementations

impl<Key: Debug + Idx> Debug for UnionFind<Key>

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

Formats the value using the given formatter.

Layout

Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...) attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.

Size: 24 bytes