pub struct UnionFind<K> { /* private fields */ }
Expand description
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§
source§impl<K> UnionFind<K>where
K: IndexType,
impl<K> UnionFind<K>where
K: IndexType,
sourcepub fn find_mut(&mut self, x: K) -> K
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.
sourcepub fn equiv(&self, x: K, y: K) -> bool
pub fn equiv(&self, x: K, y: K) -> bool
Returns true
if the given elements belong to the same set, and returns
false
otherwise.
sourcepub fn union(&mut self, x: K, y: K) -> bool
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.
sourcepub fn into_labeling(self) -> Vec<K>
pub fn into_labeling(self) -> Vec<K>
Return a vector mapping each element to its representative.
Trait Implementations§
Auto Trait Implementations§
impl<K> Freeze for UnionFind<K>
impl<K> RefUnwindSafe for UnionFind<K>where
K: RefUnwindSafe,
impl<K> Send for UnionFind<K>where
K: Send,
impl<K> Sync for UnionFind<K>where
K: Sync,
impl<K> Unpin for UnionFind<K>where
K: Unpin,
impl<K> UnwindSafe for UnionFind<K>where
K: UnwindSafe,
Blanket Implementations§
source§impl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
source§fn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
source§impl<T> CloneToUninit for Twhere
T: Clone,
impl<T> CloneToUninit for Twhere
T: Clone,
source§default unsafe fn clone_to_uninit(&self, dst: *mut T)
default unsafe fn clone_to_uninit(&self, dst: *mut T)
clone_to_uninit
)