Struct pulau_rs::UnionFind

pub struct UnionFind<'a, A, T, const N: usize>where
    T: VertexType + 'a,
    A: AlgorithmContainer,{ /* private fields */ }

UnionFind data structure

This data structure stores a collection of disjoint (non-overlapping) sets.

UnionFind is parameterized by the following

• A - Algorithm, e.g., QuickFind, QuickUnion
• T - Any unsigned integral types, e.g., u8, u16, u32, u64, usize or any type that implements VertexType
• N - Constant size of internal representative buffer

Example

use pulau_rs::{UnionFind, QuickFind, QuickUnion};
fn make_uf_quickfind() {
    // construct with quickfind algorithm with fixed size 10
    let mut uf = UnionFind::<QuickFind, u32, 10>::default();
}

fn make_uf_quickunion() {
    // construct with weighted quickunion with path compression algorithm with fixed size 10
    let mut uf = UnionFind::<QuickUnion, u32, 10>::default();
}

Size Guarantees

Size of UnionFind depends on whether the algorithm you have chosen is weighted

Assuming no padding, If it’s weighted then, size of UnionFind is T * N + size_of(usize) * N

Else it will be T * N

If you are using borrowed buffers, then the size will be the core::mem::size_of::<usize>() * 2 if it’s weighted, else it will just be core::mem::size_of::<usize>()

Implementations

impl<'a, T, const N: usize> UnionFind<'a, QuickFind<true>, T, N>where
    T: VertexType,

pub fn new(representative: &'a mut [T]) -> Self

impl<'a, T, const N: usize> UnionFind<'a, QuickUnion<BySize<true>>, T, N>where
    T: VertexType,

pub fn new(representative: &'a mut [T], heuristic: &'a mut [usize]) -> Self

impl<'a, T, const N: usize> UnionFind<'a, QuickUnion<ByRank<true>>, T, N>where
    T: VertexType,

pub fn new(representative: &'a mut [T], heuristic: &'a mut [usize]) -> Self

impl<'a, T, const N: usize, const PATH_COMPRESS: bool> UnionFind<'a, QuickUnion<Unweighted<true>, PATH_COMPRESS>, T, N>where
    T: VertexType,

pub fn new(representative: &'a mut [T]) -> Self

impl<'a, A, T, const N: usize> UnionFind<'a, A, T, N>where
    T: VertexType,
    A: AlgorithmContainer + Union<T> + Find<T> + Connected<T>,

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

Checks whether 2 nodes are connected to each other

pub fn find(&mut self, a: T::IdentifierType) -> T

Finds a node

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

Unions 2 node. If those 2 nodes are already part of the same component then this does nothing

pub fn representative(&self) -> &A::RepresentativeContainer<'a, T, N>

Gets the representative slice

pub fn heuristic(&self) -> &A::HeuristicContainer<'a, N>

Gets the heuristic slice

Trait Implementations

impl<const N: usize> Default for UnionFind<'_, QuickFind, u16, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize> Default for UnionFind<'_, QuickFind, u32, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize> Default for UnionFind<'_, QuickFind, u64, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize> Default for UnionFind<'_, QuickFind, u8, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize> Default for UnionFind<'_, QuickFind, usize, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize> Default for UnionFind<'_, QuickUnion, u16, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize> Default for UnionFind<'_, QuickUnion, u32, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize> Default for UnionFind<'_, QuickUnion, u64, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize> Default for UnionFind<'_, QuickUnion, u8, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize> Default for UnionFind<'_, QuickUnion, usize, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize> Default for UnionFind<'_, QuickUnion<BySize>, u16, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize> Default for UnionFind<'_, QuickUnion<BySize>, u32, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize> Default for UnionFind<'_, QuickUnion<BySize>, u64, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize> Default for UnionFind<'_, QuickUnion<BySize>, u8, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize> Default for UnionFind<'_, QuickUnion<BySize>, usize, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize, const PATH_COMPRESS: bool> Default for UnionFind<'_, QuickUnion<Unweighted, PATH_COMPRESS>, u16, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize, const PATH_COMPRESS: bool> Default for UnionFind<'_, QuickUnion<Unweighted, PATH_COMPRESS>, u32, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize, const PATH_COMPRESS: bool> Default for UnionFind<'_, QuickUnion<Unweighted, PATH_COMPRESS>, u64, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize, const PATH_COMPRESS: bool> Default for UnionFind<'_, QuickUnion<Unweighted, PATH_COMPRESS>, u8, N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize, const PATH_COMPRESS: bool> Default for UnionFind<'_, QuickUnion<Unweighted, PATH_COMPRESS>, usize, N>

fn default() -> Self

Returns the “default value” for a type.