Safe Haskell | None |
---|---|

Language | Haskell2010 |

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.

- data DisjointIntSetMonadic m where
- 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 = DisjointIntSet (Vector Int) (Vector Int) Int Int
- newDisjointIntSetFixed :: (PrimMonad m, MonadRef m) => Int -> m (DisjointIntSetMonadic m)
- newDisjointIntSetVariable :: (PrimMonad m, MonadRef m) => m (DisjointIntSetMonadic m)
- union :: MonadT m => DisjointIntSetMonadic m -> Int -> Int -> m Bool
- find :: MonadT m => DisjointIntSetMonadic m -> Int -> m Int
- count :: MonadT m => DisjointIntSetMonadic m -> Int -> m Int
- findAndCount :: MonadT m => DisjointIntSetMonadic m -> Int -> m (Int, Int)
- numSets :: MonadT m => DisjointIntSetMonadic m -> m Int
- size :: MonadT m => DisjointIntSetMonadic m -> m Int
- nextInSet :: MonadT m => DisjointIntSetMonadic m -> Int -> m Int
- setToList :: forall m. MonadT m => DisjointIntSetMonadic m -> Int -> m [Int]
- unsafeFreeze :: MonadT m => DisjointIntSetMonadic m -> m DisjointIntSet
- freeze :: MonadT m => DisjointIntSetMonadic m -> m DisjointIntSet
- runDisjointIntSet :: (forall s. ST s (DisjointIntSetMonadic (ST s))) -> DisjointIntSet

# Documentation

data DisjointIntSetMonadic m where Source #

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.

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 Source #

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.

Alternatively `create`

can create a disjoint set
directly from any `Foldable`

structure of int pairs, e.g. and `[(Int, Int)]`

.

There's not a variable and fixed length version of this because well, you can't modify the non-monadic version anyway.

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

Creates a new disjoint set of fixed size.

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

Creates a new disjoint set of variable size.

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

Merges the two elements passed into one set.

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

Finds the representative set for that element.

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

Gives how many elements in this element's set.

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

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

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 Source #

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 Source #

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

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

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

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

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 Source #

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 Source #

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`

.