Struct kimchi::snarky::union_find::DisjointSet

pub struct DisjointSet<T> { /* private fields */ }

Tarjan’s Union-Find Data structure

Implementations

impl<T> DisjointSet<T>where T: Clone + Hash + Eq,

pub fn new() -> Self

pub fn make_set(&mut self, x: T)

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

Returns Some(num), num is the tag of subset in which x is. If x is not in the data structure, it returns None.

pub fn union(&mut self, x: T, y: T) -> Option<usize>

Union the subsets to which x and y belong. If it returns Some<u32>, it is the tag for unified subset. If it returns None, at least one of x and y is not in the disjoint-set.

Trait Implementations

impl<T: Clone> Clone for DisjointSet<T>

fn clone(&self) -> DisjointSet<T>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for DisjointSet<T>

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

Formats the value using the given formatter.

impl<T: Default> Default for DisjointSet<T>

fn default() -> DisjointSet<T>

Returns the “default value” for a type.