Struct unionfind::UnionFind

pub struct UnionFind<T, M = HashMap<T, T>, E = ()> { /* private fields */ }

A union find datastructure. Note that this implementation clones elements a lot. Generally, you should use the datastructure with small, preferably Copyable types, like integers. However, arbitrary Clone+PartialEq types are possible.

Implementations

impl UnionFind<usize, Vec<usize>, ByRank<Vec<usize>, usize>>

pub fn new_vec(
    elems: impl IntoIterator<Item = usize> + Clone
) -> Result<Self, AddError>

Constructs a new union find, using a hashmap as backing

impl<T> UnionFind<T, HashMap<T, T>, ()> where
    T: Clone + Hash + Eq, 

pub fn new_hashmap(
    elems: impl IntoIterator<Item = T> + Clone
) -> Result<Self, AddError>

Constructs a new union find, using a hashmap as backing

impl<T> UnionFind<T, BTreeMap<T, T>, ()> where
    T: Clone + Ord, 

pub fn new_btreemap(
    elems: impl IntoIterator<Item = T> + Clone
) -> Result<Self, AddError>

Constructs a new union find, using a btreemap as backing

impl<T, M, E> UnionFind<T, M, E> where
    M: ParentMapping<T>,
    T: Clone,
    E: Extra<T>, 

pub fn new(
    elems: impl IntoIterator<Item = T> + Clone
) -> Result<Self, NewUnionFindError<<M as ParentMapping<T>>::Err, <E as Extra<T>>::ConstructErr>>

Constructs a new union find, allowing you to specify all type parameters.

impl<T: PartialEq, M: Mapping<T, T>, E> UnionFind<T, M, E>

pub fn find(&self, elem: &T) -> Option<T> where
    T: Clone, 

Find an element in the union find. Performs no path shortening, but can be used through an immutable reference.

Use [find_shorten] for a more efficient find.

pub fn find_shorten(&mut self, elem: &T) -> Option<T> where
    T: Clone, 

Find an element in the union find. Performs path shortening, which means you need mutable access to the union find.

Use [find] for an immutable version.

impl<T: PartialEq, ParentMapping: Mapping<T, T>> UnionFind<T, ParentMapping, ()> where
    ParentMapping: Mapping<T, T>, 

pub fn union_by<U: Union<T>>(
    &mut self,
    elem1: &T,
    elem2: &T,
    union: U
) -> Result<UnionStatus, UnionError<U::Err>> where
    T: Clone, 

union two elements in the union find

impl<T: PartialEq, ParentMapping: Mapping<T, T>, RankMapping> UnionFind<T, ParentMapping, ByRank<RankMapping, T>> where
    ParentMapping: Mapping<T, T>,
    RankMapping: Mapping<T, usize>,
    T: Clone, 

pub fn union_by_rank(
    &mut self,
    elem1: &T,
    elem2: &T
) -> Result<UnionStatus, UnionByRankError>

union two elements in the union find

impl<T: Clone, M, E> UnionFind<T, M, E> where
    M: IdentityMapping<T>,
    E: AddExtra<T>, 

pub fn add(
    &mut self,
    elem: T
) -> Result<(), AddError<AddError, <E as AddExtra<T>>::AddErr>>