pub struct UnionFind<T: NumericId> { /* private fields */ }Expand description
A thread-safe implementation of a union-find datastructure.
This implementation supports concurrent finds and merges, with path compression. Importantly, this implementation supports dynamically resizing the underlying array when new ids appear. This allows callers to generate Ids more flexibly, though huge amounts of resizing will cause contention as callers wait for resizes to complete.
The Clone implementation for this type is shallow: copies of the
data-structure see one another’s updates.
Implementations§
Source§impl<T: NumericId> UnionFind<T>where
T::Atomic: AtomicInt<Underlying = T::Rep>,
impl<T: NumericId> UnionFind<T>where
T::Atomic: AtomicInt<Underlying = T::Rep>,
Sourcepub fn reset(&self)
pub fn reset(&self)
Reset the union-find datastructure, setting each element to point to itself.
This method blocks until all threads have finished their current operations.
Sourcepub fn deep_copy(&self) -> Self
pub fn deep_copy(&self) -> Self
Create a deep copy of the union-find datastructure: subsequent unions on the returned copy will not affect the original.
Sourcepub fn with_capacity(capacity: usize) -> Self
pub fn with_capacity(capacity: usize) -> Self
Initialize a union-find with capacity elements pointing to themselves.
Sourcepub fn find(&self, elt: T) -> T
pub fn find(&self, elt: T) -> T
Get the canonical value associated with elt.
Note that it may be the case that find(x) != find(y) even if x and
y belong to the same equivalence class, as the canonical value for the
class may have changed between the find(x) and find(y) calls. To get
a “ground truth” view on this, use the same_set method.
We expose find because it does work if you know that there are not
any concurrent merge operations on the data-structure: this is common
enough in egglog. It also makes some tests easier to write.