Struct disjoint::DisjointSet

source ·

pub struct DisjointSet { /* private fields */ }

Expand description

A disjoint-set data structure for tracking which elements are joined, without managing any additional data associated to the elements.

This structure has methods like join or is_joined to modify or query which data is joined to which. For all of these, the elements are identified with their corresponding index. A DisjointSet of len n tracks elements from 0 to n - 1.

§Examples

use disjoint::DisjointSet;

// Initially, elements are totally disjoint.
let mut ds = DisjointSet::with_len(3); // {0}, {1}, {2}
assert!(ds.is_joined(0, 0));
assert!(!ds.is_joined(0, 1));

// Elements can be joined together
ds.join(0, 1); // {0, 1}, {2}
assert!(ds.is_joined(0, 1));
assert!(ds.is_joined(1, 0));
assert!(!ds.is_joined(0, 2));

// Since 0 was joined to 1, if we join 1 to 2, then 0 is joined to 2.
ds.join(1, 2); // {0, 1, 2}
assert!(ds.is_joined(0, 2));

For a real word application example, see the crate examples.

Implementations§

source §

impl DisjointSet

source

pub fn root_of(&self, child: usize) -> usize

Returns an element of the subset containing child. This exact element is returned for every member of the subset.

§Important

The specific choice of the returned element is an implementation detail. There are no further guarantees beyond what is documented here. If you just want to check if two elements are in the same subset, use is_joined.

§Examples

use disjoint::DisjointSet;

let mut ds = DisjointSet::with_len(3); // {0}, {1}, {2}
assert_eq!(ds.root_of(0), 0);
assert_eq!(ds.root_of(1), 1);
assert_eq!(ds.root_of(2), 2);


ds.join(0, 1); // {0, 1}, {2}
assert_eq!(ds.root_of(0), ds.root_of(1));
assert_ne!(ds.root_of(0), ds.root_of(2));

ds.join(1, 2); // {0, 1, 2}
assert_eq!(ds.root_of(0), ds.root_of(1));
assert_eq!(ds.root_of(0), ds.root_of(2));

source

pub fn with_len(len: usize) -> Self

Constructs a new DisjointSet with len elements, named 0 to n - 1, each in its own set.

§Examples

use disjoint::DisjointSet;

let mut ds = DisjointSet::with_len(4);

// The disjoint set contains 4 elements.
assert_eq!(ds.len(), 4);

// Two elements i and j are not joined in the same set, unless i = j.
assert!(!ds.is_joined(0, 3));
assert!(ds.is_joined(1, 1));

source

pub fn with_capacity(capacity: usize) -> Self

Constructs a new, empty DisjointSet with at least the specified capacity.

It will be able to hold at least capacity elements without reallocating. This method is allowed to allocate for more elements than capacity. If capacity is 0, it will not allocate.

It is important to note that although the returned DisjointSet has the minimum capacity specified, it will have a zero length.

§Panics

Panics if the new capacity exceeds isize::MAX bytes.

§Examples

use disjoint::DisjointSet;

let mut ds = DisjointSet::with_capacity(10);

// It contains no elements, even though it has capacity for more.
assert_eq!(ds.len(), 0);

// These are all done without reallocating...
for _ in 0..10 {
    ds.add_singleton();
}

// ...but this may make the disjoint set reallocate.
ds.add_singleton();

source

pub fn add_singleton(&mut self)

Adds a new element, not joined to any other element.

§Panics

Panics if the new capacity exceeds isize::MAX bytes.

§Examples

use disjoint::DisjointSet;

let mut ds = DisjointSet::with_len(1);
ds.add_singleton();
assert_eq!(ds.len(), 2);
assert!(!ds.is_joined(0, 1));

source

pub fn join(&mut self, first_element: usize, second_element: usize) -> bool

If first_element and second_element are in different sets, joins them together and returns true.

Otherwise, does nothing and returns false.

§Panics

Panics if first_element or second_element is out of bounds.

§Examples

use disjoint::DisjointSet;

// Initially, each element is in its own set.
let mut ds = DisjointSet::with_len(4); // {0}, {1}, {2}, {3}
assert!(!ds.is_joined(0, 3));

// By joining 0 to 1 and 2 to 3, we get two sets of two elements each.
ds.join(0, 1); // {0, 1}, {2}, {3}
ds.join(2, 3); // {0, 1}, {2, 3}
assert!(ds.is_joined(0, 1));
assert!(ds.is_joined(2, 3));
assert!(!ds.is_joined(0, 3));

// By further joining 2 to 3, all elements are now in the same set.
ds.join(1, 2); // {0, 1, 2, 3}
assert!(ds.is_joined(0, 3));

source

pub fn is_joined(&self, first_element: usize, second_element: usize) -> bool

Returns true if first_element and second_element are in the same subset.

§Panics

Panics if first_element or second_element is out of bounds.

§Examples

use disjoint::DisjointSet;

// Initially, elements are only joined to themselves.
let mut ds = DisjointSet::with_len(3); // {0}, {1}, {2}
assert!(ds.is_joined(0, 0));
assert!(!ds.is_joined(0, 1));
assert!(!ds.is_joined(0, 2));

// By joining 1 to 0, we implicitely join 0 to 1.
ds.join(1, 0); // {0, 1}, {2}
assert!(ds.is_joined(1, 0));
assert!(ds.is_joined(0, 1));

// By joining 0 to 1 and 1 to 2, we implicitely join 0 to 2.
ds.join(1, 2); // {0, 1, 2}
assert!(ds.is_joined(0, 2));

source

pub fn len(&self) -> usize

Returns the number of elements in the disjoint set, regardless of how they are joined together.

§Examples

use disjoint::DisjointSet;

let mut ds = DisjointSet::with_len(4);
assert_eq!(ds.len(), 4);

ds.join(1, 3);
assert_eq!(ds.len(), 4);

source

pub fn is_empty(&self) -> bool

Returns true if the disjoint set contains no elements.

§Examples

use disjoint::DisjointSet;

assert!(DisjointSet::new().is_empty());
assert!(DisjointSet::with_len(0).is_empty());
assert!(!DisjointSet::with_len(10).is_empty());

source

pub fn new() -> Self

Constructs a new, empty DisjointSet.

The disjoint set will not allocate until elements are added to it.

§Examples

let mut vec: Vec<i32> = Vec::new();

source

pub fn sets(&self) -> Vec<Vec<usize>>

Returns a Vec of all sets. Each entry corresponds to one set, and is a Vec of its elements.

The sets are ordered by their smallest contained element. The elements inside each sets are ordered.

§Examples

use disjoint::DisjointSet;

let mut ds = DisjointSet::with_len(4); // {0}, {1}, {2}, {3}
ds.join(3, 1); // {0}, {1, 3}, {2}
assert_eq!(ds.sets(), vec![vec![0], vec![1, 3], vec![2]]);