Struct UnionFind

pub struct UnionFind<T: NumericId> { /* private fields */ }

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

impl<T: NumericId> UnionFind<T>

where T::Atomic: AtomicInt<Underlying = T::Rep>,

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.

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.

pub fn with_capacity(capacity: usize) -> Self

Initialize a union-find with capacity elements pointing to themselves.

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.

pub fn same_set(&self, l: T, r: T) -> bool

Check if l and r belong to the same equivalence class.

pub fn union(&self, l: T, r: T) -> (T, T)

Merge the equivalence classes of l and r, returning the new parent and new child classes. If l and r are already in the same class, then their canonical representative is returned twice.

Trait Implementations

impl<T: NumericId> Clone for UnionFind<T>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: NumericId> Default for UnionFind<T>

where T::Atomic: AtomicInt,

fn default() -> Self

Returns the “default value” for a type.