Struct fera_unionfind::UnionFind

pub struct UnionFind<Key, Parent = IndexedHashMap<Key, Key>, Rank = IndexedHashMap<Key, usize>> where
    Key: Copy + PartialEq,
    Parent: IndexMut<Key, Output = Key>,
    Rank: IndexMut<Key, Output = usize>,  { /* fields omitted */ }

A union-find (disjoint-set) struct.

Methods

impl<Key, Parent, Rank> UnionFind<Key, Parent, Rank> where
    Key: Copy + PartialEq,
    Parent: IndexMut<Key, Output = Key>,
    Rank: IndexMut<Key, Output = usize>, 

fn make_set(&mut self, x: Key)

Adds the key in it's own set. The number of sets is increased by 1.

It's undefined behavior to call this method with a key that is already in a set.

fn union(&mut self, x: Key, y: Key)

Joins the sets with the keys x and y. The number of sets is decreased by 1.

Panics

If x or y is not in any set or if both are in the same set.

fn in_same_set(&mut self, x: Key, y: Key) -> bool

Returns true if x and y is in the same set, otherwise false.

Panics

If x or y is not in any set.

fn find_set(&mut self, x: Key) -> Key

Returns the representative of the set that contains x.

Panics

If x is not in any set.

fn num_sets(&self) -> usize

Returns the number of distinct sets.

impl<K: Copy + Hash + Eq> UnionFind<K>

fn new() -> Self

Creates a new UnionFind.

Trait Implementations

impl<Key: Clone, Parent: Clone, Rank: Clone> Clone for UnionFind<Key, Parent, Rank> where
    Key: Copy + PartialEq,
    Parent: IndexMut<Key, Output = Key>,
    Rank: IndexMut<Key, Output = usize>, 

fn clone(&self) -> UnionFind<Key, Parent, Rank>

Returns a copy of the value.

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

Performs copy-assignment from source.