Struct disjoint_sets::UnionFindNode

pub struct UnionFindNode<Data = ()>(_);

Tree-based union-find representing disjoint sets with associated data.

This union-find implementation uses nodes to represent set elements in a parent-pointer tree. Each set has associated with it an object of type Data, which can be looked up and modified via any representative of the set.

Construct a new singleton set with UnionFindNode::new.

Methods

impl<Data> UnionFindNode<Data>

fn new(data: Data) -> Self

Creates a new singleton set with associated data.

Initially this set is disjoint from all other sets, but can be joined with other sets using union.

fn union_with<R, F>(&mut self, other: &mut Self, f: F) -> Option<R> where F: FnOnce(Data, Data) -> (Data, R)

Unions two sets, combining their data as specified.

To determine the data associated with the set resulting from a union, we pass a closure f, which will be passed self’s data and other’s data. Then f must return a pair of the data to associate with the unioned set and any remaining value to return to the client.

fn union(&mut self, other: &mut Self) -> Option<Data>

Unions two sets.

Retains the data associated with an arbitrary set, returning the data of the other. Returns None if self and other are already elements of the same set.

fn find(&self) -> Self

Finds a node representing the set of a given node.

For two nodes in the same set, find returns the same node.

fn equiv(&self, other: &Self) -> bool

Are the two nodes representatives of the same set?

fn replace_data(&self, new: Data) -> Data

Replaces the data associated with the set.

fn clone_data(&self) -> Data where Data: Clone

Returns a clone of the data associated with the set.

fn with_data<R, F>(&self, f: F) -> R where F: FnOnce(&mut Data) -> R

Allows modifying the data associated with a set.

Trait Implementations

impl<Data> Debug for UnionFindNode<Data>

fn fmt(&self, formatter: &mut Formatter) -> Result

Formats the value using the given formatter.

impl<Data> PartialEq for UnionFindNode<Data>

fn eq(&self, other: &UnionFindNode<Data>) -> bool

This method tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=.

impl<Data> Eq for UnionFindNode<Data>

impl<Data> PartialOrd for UnionFindNode<Data>

fn partial_cmp(&self, other: &UnionFindNode<Data>) -> Option<Ordering>

This method returns an ordering between self and other values if one exists.

fn lt(&self, other: &Rhs) -> bool

This method tests less than (for self and other) and is used by the < operator.

fn le(&self, other: &Rhs) -> bool

This method tests less than or equal to (for self and other) and is used by the <= operator.

fn gt(&self, other: &Rhs) -> bool

This method tests greater than (for self and other) and is used by the > operator.

fn ge(&self, other: &Rhs) -> bool

This method tests greater than or equal to (for self and other) and is used by the >= operator.

impl<Data> Ord for UnionFindNode<Data>

fn cmp(&self, other: &UnionFindNode<Data>) -> Ordering

This method returns an Ordering between self and other.

impl<Data> Hash for UnionFindNode<Data>

fn hash<H: Hasher>(&self, state: &mut H)

Feeds this value into the state given, updating the hasher as necessary.

fn hash_slice<H>(data: &[Self], state: &mut H) where H: Hasher

Feeds a slice of this type into the state provided.

impl<Data> Clone for UnionFindNode<Data>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<Data: Default> Default for UnionFindNode<Data>

fn default() -> Self

Returns the "default value" for a type.