Struct UnionFind

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

A disjoint-set data structure backed by a disjoint set forest.

Example

use rust_dsa::UnionFind;

// First, we create a new structure.
let mut uf = UnionFind::new();

// Then we can insert values.
uf.insert(1);
uf.insert(2);
uf.insert(3);
uf.insert(4);
uf.insert(5);

// And union some of the elements.
uf.union(&1, &2);
uf.union(&2, &4);
uf.union(&3, &5);

// Now, we can query to see if elements are in the same set.
assert_eq!(uf.find(&1), uf.find(&2));
assert_eq!(uf.find(&2), uf.find(&4));
assert_eq!(uf.find(&4), uf.find(&1));
assert_eq!(uf.find(&3), uf.find(&5));
assert_eq!(uf.find(&5), uf.find(&3));

assert_ne!(uf.find(&1), uf.find(&3));
assert_ne!(uf.find(&5), uf.find(&4));

// We can also create `UnionFind`s from arrays.
let uf = UnionFind::from(["foo", "bar"]);

assert!(!uf.friends(&"foo", &"bar").unwrap());

// And iterators.
let uf: UnionFind<_> = "string".chars().collect();

assert!(!uf.friends(&'s', &'t').unwrap());

Implementations

impl<T> UnionFind<T>

pub fn new() -> UnionFind<T>

Creates a new UnionFind structure.

pub fn with_capacity(capacity: usize) -> UnionFind<T>

Creates a new UnionFind structure with the specified capacity.

pub fn insert(&mut self, value: T) -> bool

where T: Hash + Eq,

Inserts a value into the UnionFind structure.

Returns true if the UnionFind structure did not contain value and false if it did.

Example

use rust_dsa::UnionFind;

let mut uf = UnionFind::new();

uf.insert('a');
uf.insert('b');

assert!(uf.contains(&'a'));
assert!(uf.contains(&'b'));

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

where T: Hash + Eq,

Returns a usize representing the set that contains value or None if the UnionFind structure does not contain value.

This method applies path compression as it searches.

Example

use rust_dsa::UnionFind;

let mut uf = UnionFind::from([1, 2, 3]);
uf.union(&1, &2);

assert_eq!(uf.find(&1), uf.find(&2));
assert_ne!(uf.find(&1), uf.find(&3));

pub fn static_find(&self, value: &T) -> Option<usize>

where T: Hash + Eq,

Returns a usize representing the set that contains value or None if the UnionFind structure does not contain value.

This method does not apply path compression as it searches.

Example

use rust_dsa::UnionFind;

let mut uf = UnionFind::from([1, 2, 3]);
uf.union(&1, &2);

assert_eq!(uf.static_find(&1), uf.static_find(&2));
assert_ne!(uf.static_find(&1), uf.static_find(&3));

pub fn union(&mut self, a: &T, b: &T) -> Option<bool>

where T: Hash + Eq,

Joins the two sets containing a and b. Returns None if a or b is not in the UnionFind structure. Returns Some(true) if a and b were in different sets before the union operation was preformed and Some(false) if they were already in the same set.

Example

use rust_dsa::UnionFind;

let mut uf = UnionFind::from(['x', 'y', 'z']);

assert_eq!(uf.union(&'x', &'y'), Some(true));

// Returns `Some(false)` if we try again.
assert_eq!(uf.union(&'x', &'y'), Some(false));

assert!(uf.friends(&'x', &'y').unwrap());
assert!(!uf.friends(&'y', &'z').unwrap());

pub fn friends(&self, a: &T, b: &T) -> Option<bool>

where T: Hash + Eq,

Returns Some(true) if a and b are members of the same set and Some(false) if they are not. If a or b is not in the UnionFind structure, None is returned.

Example

use rust_dsa::UnionFind;

let mut uf = UnionFind::from([1, 2, 3]);

uf.union(&1, &2);

assert_eq!(uf.friends(&1, &2), Some(true));
assert_eq!(uf.friends(&1, &3), Some(false));
assert_eq!(uf.friends(&1, &999), None);

pub fn contains(&self, value: &T) -> bool

where T: Hash + Eq,

Returns true if the value is in the UnionFind structure.

Example

use rust_dsa::UnionFind;

let mut uf = UnionFind::new();

uf.insert('a');
uf.insert('b');

assert!(uf.contains(&'a'));
assert!(uf.contains(&'b'));

pub fn len(&self) -> usize

Returns the number of elements in the UnionFind structure.

Example

use rust_dsa::UnionFind;

let mut uf: UnionFind<_> = (0..42).collect();

assert_eq!(uf.len(), 42);

uf.clear();

assert_eq!(uf.len(), 0);

pub fn is_empty(&self) -> bool

Returns true if the UnionFind structure is empty.

Example

use rust_dsa::UnionFind;

let mut uf: UnionFind<_> = "chars".chars().collect();

assert!(!uf.is_empty());

uf.clear();

assert!(uf.is_empty());

pub fn clear(&mut self)

Clears the UnionFind structure.

Example

use rust_dsa::UnionFind;

let mut uf: UnionFind<_> = "chars".chars().collect();

assert!(!uf.is_empty());

uf.clear();

assert!(uf.is_empty());

Trait Implementations

impl<T> Default for UnionFind<T>

fn default() -> UnionFind<T>

Returns the “default value” for a type.

impl<T, const N: usize> From<[T; N]> for UnionFind<T>

where T: Hash + Eq,

fn from(array: [T; N]) -> UnionFind<T>

Converts to this type from the input type.

impl<T> FromIterator<T> for UnionFind<T>

where T: Hash + Eq,

fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> UnionFind<T>

Creates a value from an iterator.