Struct DisjointSets

pub struct DisjointSets<T: NodeTrait> { /* private fields */ }

A collection of disjoint sets over cheaply-cloned objects.

Implementations

impl<T: NodeTrait> DisjointSets<T>

pub fn new() -> Self

Constructs an empty disjoint set.

pub fn add(&mut self, v: T)

Adds a disjoint singleton {v} if v has not already been added.`

pub fn find(&mut self, v: T) -> Option<T>

Finds the canonical representative of the set to which v belongs, if v in fact has been added via a call to DisjointSets::add.

pub fn union(&mut self, a: T, b: T, by_rank: bool) -> Option<T>

Merges the sets to which a and b belong to, returning their new canonical representative. If by_rank is true, the union-by-rank optimization is used, acheiving near-linear time complexity. Otherwise, the canonical representative of b is chosen as the new canonical representative, which leads to log-linear complexity.

pub fn collapse(&mut self)

Optimizes find and union access for all nodes.

Trait Implementations

impl<T> Debug for DisjointSets<T>

where T: Debug + NodeTrait,

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'a, T: NodeTrait> IntoIterator for &'a DisjointSets<T>

type Item = (&'a T, &'a T)

The type of the elements being iterated over.

type IntoIter = Map<Iter<'a, T, NodeData<T>>, fn((&'a T, &'a NodeData<T>)) -> (&'a T, &'a T)>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.