Struct dfir_lang::union_find::UnionFind

pub struct UnionFind<K>
where
    K: Key,
{ /* private fields */ }

Union-find data structure.

Used to efficiently track sets of equivalent items.

https://en.wikipedia.org/wiki/Disjoint-set_data_structure

Implementations

impl<K> UnionFind<K>

where K: Key,

pub fn new() -> Self

Creates a new UnionFind, same as Default::default().

pub fn with_capacity(capacity: usize) -> Self

Creates a new UnionFind with the given key capacity pre-allocated.

pub fn union(&mut self, a: K, b: K)

Combines two items a and b as equivalent, in the same set.

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

Finds the “representative” item for k. Each set of equivalent items is represented by one of its member items.

pub fn same_set(&mut self, a: K, b: K) -> bool

Returns if a and b are equivalent, i.e. in the same set.

Trait Implementations

impl<K> Clone for UnionFind<K>

where K: Key + Clone,

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> Default for UnionFind<K>

where K: Key + Default,

fn default() -> UnionFind<K>

Returns the “default value” for a type.