union-find-array-0.1.0.4: union find data structure
Safe HaskellSafe-Inferred
LanguageHaskell2010

Data.Union.ST

Description

Low-level interface for managing a disjoint set data structure, based on ST. For a higher level convenience interface, look at Union.

Synopsis

Documentation

data UnionST s l Source #

A disjoint set forest, with nodes numbered from 0, which can carry labels.

runUnionST :: (forall s. ST s (UnionST s l)) -> Union l Source #

Analogous to runSTArray.

new :: Int -> l -> ST s (UnionST s l) Source #

Create a new disjoint set forest, of given capacity.

grow :: UnionST s l -> Int -> ST s (UnionST s l) Source #

Grow the capacity of a disjoint set forest. Shrinking is not possible. Trying to shrink a disjoint set forest will return the same forest unmodified.

copy :: UnionST s l -> ST s (UnionST s l) Source #

Copy a disjoint set forest.

lookup :: UnionST s l -> Int -> ST s (Int, l) Source #

Look up the representative of a given node and its label.

annotate :: UnionST s l -> Int -> l -> ST s () Source #

Annotate a node with a new label.

merge :: UnionST s l -> (l -> l -> (l, a)) -> Int -> Int -> ST s (Maybe a) Source #

Merge two nodes if they are in distinct equivalence classes. The passed function is used to combine labels, if a merge happens.

flatten :: UnionST s l -> ST s () Source #

Flatten a disjoint set forest, for faster lookups.

size :: UnionST s l -> Int Source #

unsafeFreeze :: UnionST s l -> ST s (Union l) Source #

Analogous to unsafeFreeze