Safe Haskell	None

Data.DisjointSet

Contents

Core functions.
Utility functions.

Description

Imperative disjoint sets data structure. - Uses mutable arrays with path compression and union by rank to achieve nearly constant amortized time complexity. - (It's actually the inverted Ackermann function, which is less than 5 for all remotely possible sizes.) - Optimized to be used with unboxed arrays of integers.

Synopsis

Core functions.

data DSet a Source

A collection of disjoint sets on Ints backed by a mutable array of type a.

singletons :: MArray a Int m => (Int, Int) -> m (DSet a)Source

Creates a new disjoint set structure with the specified bounds. Calling mkset (i,j) creates a collection of singleton sets indexed by numbers from i to j (inclusive).

find :: MArray a Int m => DSet a -> Int -> m Int Source

Returns the identifier of the subset a given element is in.

union :: MArray a Int m => DSet a -> Int -> Int -> m Bool Source

Joins the classes of given two elements. Returns True if the two classes were merged (i.e. were distinct before), False otherwise.

classes :: MArray a Int m => DSet a -> m Int Source

Utility functions.

singletonsIO :: (Int, Int) -> IO (DSet IOUArray)Source

A convenience function for creating an efficient, IO-based array.

singletonsST :: (Int, Int) -> ST s (DSet (STUArray s))Source

A convenience function for creating an efficient, ST-based array.

sameClass :: MArray a Int m => DSet a -> Int -> Int -> m Bool Source

Returns True iff the given two elements belong to the same class. In many cases this function is preferred over find.