Data.Union.ST

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

Documentation

data UnionST s l

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

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

Analogous to runSTArray.

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

Create a new disjoint set forest, of given capacity.

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

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)

Copy a disjoint set forest.

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

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

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

Annotate a node with a new label.

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

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 ()

Flatten a disjoint set forest, for faster lookups.

size :: UnionST s l -> Int

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

Analogous to unsafeFreeze