Struct UnionFind

pub struct UnionFind { /* private fields */ }

Union-Find structure.

Implementations

impl UnionFind

pub fn new(size: usize) -> Self

Build a new structure with size items.

Panics

If size is zero.

Examples

use causal_hub::utils::UnionFind;

// Initialize a new union-find.
let union_find = UnionFind::new(5);

// The new union-find contains only disjoint sets.
assert!(!union_find.contains(0, 1));

pub fn len(&self) -> usize

Gets the number of items in the structure.

Examples

use causal_hub::utils::UnionFind;

// Initialize a new union-find.
let union_find = UnionFind::new(5);

// The new union-find contains only disjoint sets.
assert_eq!(union_find.len(), 5);

pub fn contains(&self, x: usize, y: usize) -> bool

Checks if two items are in the same set.

Panics

At least one of the items does not exist in the structure.

Examples

use causal_hub::utils::UnionFind;

// Initialize a new union-find.
let union_find = UnionFind::new(5);

// The new union-find contains only disjoint sets.
assert!(!union_find.contains(0, 1));

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

Gets the root of a given item.

Panics

The items does not exist in the structure.

Examples

use causal_hub::utils::UnionFind;

// Initialize a new union-find.
let union_find = UnionFind::new(5);

// The new union-find contains only disjoint sets.
for x in 0..union_find.len() {
    assert_eq!(union_find.find(x), x);
}

pub fn find_mut(&mut self, x: usize) -> usize

Gets the root of a given item, while compressing the paths.

Panics

The items does not exist in the structure.

Examples

use causal_hub::utils::UnionFind;

// Initialize a new union-find.
let mut union_find = UnionFind::new(5);

// The new union-find contains only disjoint sets.
for x in 0..union_find.len() {
    assert_eq!(union_find.find_mut(x), x);
}

pub fn union(&mut self, x: usize, y: usize) -> bool

Make two items into the same set, if not already.

Panics

At least one of the items does not exist in the structure.

Examples

use causal_hub::utils::UnionFind;

// Initialize a new union-find.
let mut union_find = UnionFind::new(5);

// The new union-find contains only disjoint sets.
for x in 0..union_find.len() {
    assert_eq!(union_find.find(x), x);
}

// Merge item set 0 and 3.
assert!(union_find.union(0, 3));

// Now, items 0 and 3 are in the same set.
assert!(union_find.contains(0, 3));

Trait Implementations

impl Clone for UnionFind

fn clone(&self) -> UnionFind

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for UnionFind

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

Formats the value using the given formatter.

impl Extend<usize> for UnionFind

fn extend<I: IntoIterator<Item = usize>>(&mut self, iter: I)

Union all the items from an iterator into the same set.

Panics

At least one of the items does not exist in the structure.

Examples

use causal_hub::utils::UnionFind;

// Initialize a new union-find.
let mut union_find = UnionFind::new(5);

// The new union-find contains only disjoint sets.
for x in 0..union_find.len() {
    assert_eq!(union_find.find(x), x);
}

// Merge items from 0 to 3.
union_find.extend(0..4);

// Now, items from 0 to 3 are in the same set.
assert!(union_find.contains(0, 1));
assert!(union_find.contains(0, 2));
assert!(union_find.contains(0, 3));

// Item 4 is is not in the same set
assert!(!union_find.contains(0, 4));
assert!(!union_find.contains(1, 4));
assert!(!union_find.contains(2, 4));
assert!(!union_find.contains(3, 4));

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.