Struct StaticTreeSetUnion 

pub struct StaticTreeSetUnion { /* private fields */ }

Static tree set union data structure (Gabow-Tarjan Section 2).

The tree must be known in advance. Supports link and find operations in O(1) amortized time, with O(m + n) total for m operations on n nodes.

Semantics

• Initially every node is its own set name (marked).
• link(v) removes v as a set name, merging it into parent(v)’s set. After this, find will skip past v.
• find(v) returns the nearest ancestor of v that is still a set name (has not been linked). A node is its own ancestor.
• link(root) panics: the root has no parent.

Implementations

impl StaticTreeSetUnion

pub fn from_parents(parents: &[usize]) -> Self

Construct from a parent array. parents[i] is the parent of node i. The root node must satisfy parents[root] == root.

pub fn link(&mut self, v: usize)

Link node v: remove v as a set name, merging it into its parent’s set.

pub fn find(&mut self, v: usize) -> usize

Find the nearest ancestor of v that is still a set name (has not been linked). A node is its own ancestor.

pub fn len(&self) -> usize

pub fn is_empty(&self) -> bool

Trait Implementations

impl Clone for StaticTreeSetUnion

fn clone(&self) -> StaticTreeSetUnion

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for StaticTreeSetUnion

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

Formats the value using the given formatter.