Safe Haskell | None |
---|

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.

- data DSet a
- singletons :: MArray a Int m => (Int, Int) -> m (DSet a)
- find :: MArray a Int m => DSet a -> Int -> m Int
- union :: MArray a Int m => DSet a -> Int -> Int -> m Bool
- classes :: MArray a Int m => DSet a -> m Int
- singletonsIO :: (Int, Int) -> IO (DSet IOUArray)
- singletonsST :: (Int, Int) -> ST s (DSet (STUArray s))
- sameClass :: MArray a Int m => DSet a -> Int -> Int -> m Bool

# Core functions.

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 IntSource

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

# Utility functions.

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

A convenience function for creating an efficient, `IO`

-based array.