union-find-array-0.1: union find data structure

Safe HaskellNone



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



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 lSource

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.

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

Analogous to unsafeFreeze