Struct advanced_collections::disjoint_set::DisjointSet

pub struct DisjointSet<T, S = RandomState>where
    T: Eq + Hash,
    S: BuildHasher,{ /* private fields */ }

where α() - very slowly growing function. α(n) < 4 for any reasonable n. Therefore O(α(n)) ≈ O(1).

Example

extern crate advanced_collections;
use advanced_collections::disjoint_set::DisjointSet;
use std::iter::FromIterator;

fn main(){
   let arr = [1,2,3,4,5,6,7];

   //creates 7 disjoint sets
   let mut ds: DisjointSet<i32> = DisjointSet::from_iter(&arr);

    //you can join existing sets
    ds.union(1, 2);

    //or add elements to existing sets
    ds.union(1,8);

    //you can check if elements are in the same set
    assert!(ds.in_union(&2,&8));
    assert!(!ds.in_union(&3,&4));

    //or if the element has been previously added to the set
    assert!(ds.contains(&7));
    assert!(!ds.contains(&10));

    //finally, you can access sets and content of sets using iterator
    for set in &mut ds {
        println!("A new set:");
        for elem in set.into_iter() {
            print!("{}, ", elem);
        }
        println!("");
    }
}

Implementations

impl<T, S> DisjointSet<T, S>where
    T: Eq + Hash,
    S: BuildHasher,

pub fn new() -> Selfwhere
    S: Default,

Creates a new, empty DisjointSet.

pub fn with_capacity(capacity: usize) -> Selfwhere
    S: Default,

Creates an empty DisjointSet with the specified capacity.

The DisjointSet will be able to hold at least capacity elements without reallocating. If capacity is 0, the DisjointSet will not allocate.

pub fn with_hasher(hash_builder: S) -> Self

Creates an empty DisjointSet which will use the given hash builder to hash keys.

The created set has the default initial capacity.

pub fn with_capacity_and_hasher(capacity: usize, hash_builder: S) -> Self

Creates an empty Counter with the specified capacity, using hash_builder to hash the keys.

The Counter will be able to hold at least capacity elements without reallocating. If capacity is 0, the Counter will not allocate.

pub fn make_set(&mut self, val: T)

Crates a subset with the provided element.

If the given element already exists, nothing happens.

Complexity:: O(1)

pub fn union(&mut self, a: T, b: T)

Joins two subsets using one element from both subsets.

If the provided elements do not exist in the collection when this function is called, a new subset with one element gets created prior to joining.

Complexity: O(α(n)) ≈ O(1)

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

Check if the given element has been added to this collection.

Complexity:* O(α(n)) ≈ O(1)

pub fn in_union(&mut self, a: &T, b: &T) -> bool

Checks if the given two elements are in the same subset.

Complexity:* O(α(n)) ≈ O(1)

pub fn is_empty(&self) -> bool

pub fn len(&self) -> usize

pub fn clear(&mut self)

pub fn reserve(&mut self, additional: usize)

Trait Implementations

impl<T: Clone, S: Clone> Clone for DisjointSet<T, S>where
    T: Eq + Hash,
    S: BuildHasher,

fn clone(&self) -> DisjointSet<T, S>

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<T: Debug, S: Debug> Debug for DisjointSet<T, S>where
    T: Eq + Hash,
    S: BuildHasher,

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

Formats the value using the given formatter.

impl<T, S> Default for DisjointSet<T, S>where
    T: Eq + Hash,
    S: BuildHasher + Default,

fn default() -> Self

Returns the “default value” for a type.

impl<'a, T, S> Extend<&'a T> for DisjointSet<T, S>where
    T: Hash + Eq + Copy,
    S: BuildHasher,

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

Extends collection using the provided iterator.

Elements become a new subsets with just one element (equivalent to calling make_set() multiple times).

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.

impl<T, S> Extend<T> for DisjointSet<T, S>where
    T: Hash + Eq,
    S: BuildHasher,

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

Extends collection using the provided iterator.

Elements become a new subsets with just one element (equivalent to calling make_set() multiple times).

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.

impl<'a, T, S> FromIterator<&'a T> for DisjointSet<T, S>where
    T: Hash + Eq + Clone,
    S: BuildHasher + Default,

fn from_iter<I: IntoIterator<Item = &'a T>>(iter: I) -> Self

Creates DisjointSet from provided iterator.

Elements become a new subsets with just one element (equivalent to calling make_set() multiple times).

impl<T, S> FromIterator<T> for DisjointSet<T, S>where
    T: Hash + Eq,
    S: BuildHasher + Default,

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

Creates DisjointSet from provided iterator.

Elements become a new subsets with just one element (equivalent to calling make_set() multiple times).

impl<'a, T, S> IntoIterator for &'a mut DisjointSet<T, S>where
    T: Hash + Eq,
    S: BuildHasher,

type Item = IntoIter<&'a T, Global>

The type of the elements being iterated over.

type IntoIter = SetIter<'a, T>

Which kind of iterator are we turning this into?

fn into_iter(self) -> <Self as IntoIterator>::IntoIter

Creates an iterator from a value.