Data.DisjointSet.Int.Monadic

This module implements data types and monadic operations to build, modify and query disjoint int sets in a monadic way (such as through ST). Keep in mind that that this module assumes your int set is 0 based, i.e has no negatives, and is contiguous from zero. Storage space required is two machine integers per int in the set.

For more information see the Disjoint Sets article on wikipedia, noting that this modules only deals with disjoint sets with elements of type Int, in particular contiguous and starting at 0.

Documentation

data DisjointIntSetMonadic m where

There are two sorts of monadic int sets, one of fixed size and one of variable size. The variable sized one automatically expands but is presumably a bit slower due to the extra indirection and time taken for copies when resizing.

Note that when the variable sized int set expands, it expands to at least twice it's current size, so you won't get O(n^2) behaviour due to frequent resizings.

Whilst the following is implementation details, it might be interesting to know. Each int set has two vectors of Ints. The first either contains a positive or negative number, if it's positive, it's a pointer which eventually points to the representative set. However, if it's negative, this element is the representative set, and the absolute value of it is the number of elements in the set.

The second set maintains a circular linked lists for each set. This allows one to iterate though elements of a set quickly.

For more information on the algorithms, the disjoint set data structure page on Wikipedia is a good start.

Constructors

DisjointIntSetMonadicFixed :: Monad m => MVectorT m -> MVectorT m -> Ref m Int -> Int -> DisjointIntSetMonadic m

DisjointIntSetMonadicVariable :: Monad m => Ref m (MVectorT m) -> Ref m (MVectorT m) -> Ref m Int -> Ref m Int -> DisjointIntSetMonadic m

data DisjointIntSet

This is the non-monadic disjoint int set. It can be created by using the monadic operations and then calling freeze, unsafeFreeze or runDisjointIntSet as appropriate. There's not a variable and fixed length version of this because well, you can't modify the non-monadic version anyway.

Constructors

DisjointIntSet (Vector Int) (Vector Int) Int Int

Instances

Show DisjointIntSet

Methods

showsPrec :: Int -> DisjointIntSet -> ShowS

show :: DisjointIntSet -> String

showList :: [DisjointIntSet] -> ShowS

newDisjointIntSetFixed :: (PrimMonad m, MonadRef m) => Int -> m (DisjointIntSetMonadic m)

Creates a new disjoint set of fixed size.

newDisjointIntSetVariable :: (PrimMonad m, MonadRef m) => m (DisjointIntSetMonadic m)

Creates a new disjoint set of variable size.

union :: MonadT m => DisjointIntSetMonadic m -> Int -> Int -> m Bool

Merges the two elements passed into one set.

find :: MonadT m => DisjointIntSetMonadic m -> Int -> m Int

Finds the representative set for that element.

count :: MonadT m => DisjointIntSetMonadic m -> Int -> m Int

Gives how many elements in this element's set.

findAndCount :: MonadT m => DisjointIntSetMonadic m -> Int -> m (Int, Int)

Both find and count, but in one operation, so in theory faster than running them separately.

numSets :: MonadT m => DisjointIntSetMonadic m -> m Int

How many distinct sets. Note for fixed size disjoint sets this starts at the size, all ints are assumed to be in separate sets.

size :: MonadT m => DisjointIntSetMonadic m -> m Int

How many elements in this disjoint set. Note for fixed size disjoint sets this is always the size they are created with, regardless of whether these elements have been assigned to sets.

nextInSet :: MonadT m => DisjointIntSetMonadic m -> Int -> m Int

Repeated calls iterates through the circular linked list of elements in this set

setToList :: forall m. MonadT m => DisjointIntSetMonadic m -> Int -> m [Int]

Repeatedly calls nextInSet to generate a list of elements in this set.

unsafeFreeze :: MonadT m => DisjointIntSetMonadic m -> m DisjointIntSet

Freezes the disjoint int set into a non-mondaic set, but without copying. You should not modify the monadic disjoint int set after this operation.

freeze :: MonadT m => DisjointIntSetMonadic m -> m DisjointIntSet

Safely freezes the disjoint int set into a non-mondaic set by doing a full copy. You should not modify the monadic disjoint int set after this operation.

runDisjointIntSet :: (forall s. ST s (DisjointIntSetMonadic (ST s))) -> DisjointIntSet

A bit like runST, runs the ST action which must have the result of DisjointIntSetMonadic, but then returns a non monadic DisjointIntSet. It uses unsafeFreeze interally, but this is perfectly safe as nothing is done to the monadic disjoint int set after unsafeFreeze.