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.