Struct DsuRoot

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

An owning smart pointer that always points to the root of a DSU tree.

One can logically consider that DsuRoot smart pointers refer to a standalone DSU tree. When merging two DSU trees by calling the merge_into function, the two DSU trees are given through two DsuRoot smart pointers that logically refer to the two trees.

Implementations

impl<T> DsuRoot<T>

pub fn new(value: T) -> Self

Create a new DSU tree node and attach a DsuRoot smart pointer to the new node.

The new DSU tree node contains the given value.

Examples found in repository

examples/kruskal.rs (line 66)

    fn add_root(&mut self, value: usize) {
        self.roots.push(RefCell::new(DsuRoot::new(value)));
    }

pub fn same(lhs: &mut Self, rhs: &mut Self) -> bool

Determine whether the two DsuRoot smart pointers refer to the same tree.

use dsu_tree::DsuRoot;

let mut dsu_1 = DsuRoot::new(10);
let mut dsu_2 = DsuRoot::new(20);
assert!(!DsuRoot::same(&mut dsu_1, &mut dsu_2));

dsu_1.merge_into(&mut dsu_2);
assert!(DsuRoot::same(&mut dsu_1, &mut dsu_2));

pub fn value(&mut self) -> &T

Get the value contained in the DSU tree node pointed to by this DsuRoot smart pointer.

This function requires &mut self since the DsuRoot smart pointer may move around over the DSU tree so that it eventually points to the root node.

Examples found in repository

examples/kruskal.rs (line 70)

    fn find(&self, id: usize) -> usize {
        *self.roots[id].borrow_mut().value()
    }

pub fn merge_into(&mut self, another: &mut Self)

Merge two DSU trees into one.

The first DSU tree is given through self. The second DSU tree is given through another.

If initially, the two trees are the same tree, then this function does nothing. Otherwise, the parent node of the root node of the tree specified through self is set to the root node of the tree specified through another.

Examples found in repository

examples/kruskal.rs (line 80)

    fn merge(&mut self, first: usize, second: usize) {
        if first == second {
            return;
        }

        let mut first_root = self.roots[first].borrow_mut();
        let mut second_root = self.roots[second].borrow_mut();
        first_root.merge_into(&mut second_root);
    }

Trait Implementations

impl<T: Clone> Clone for DsuRoot<T>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<T: Debug> Debug for DsuRoot<T>

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

Formats the value using the given formatter.