Safe Haskell	None
Language	Haskell2010

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

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 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 a disjoint set forest.

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 a disjoint set forest, for faster lookups.

Analogous to unsafeFreeze