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

Language | Haskell2010 |

This module contains non-monadic functions for querying disjoint int sets. See Data.DisjointSet.Int.Monadic for information about how to create and modify disjoint int sets.

There are two other disjoint int set packages on hackage, namely:

- "disjoint-set"
- "disjoint-sets-st"

The first is a pure disjoint int set implementation, so as it doesn't do in place array updates in ST it will presumably be somewhat slower, with the data structure used likely taking more space and having log(n) access speed.

This package does not include a pure implementation, you're better off using "disjoint-set" for that.

"disjoint-sets-st" does offer an implementation in IO, however, it's missing two features:

1) The ability to "freeze" a disjoint set, and then query it in a pure way. 2) Maintaining a circular linked list of each set so one can quickly discover all the elements of one set without quering through the entire structure.

This package implements both of the above features.

- data DisjointIntSet = DisjointIntSet (Vector Int) (Vector Int) Int Int
- create :: Foldable t => t (Int, Int) -> DisjointIntSet
- find :: DisjointIntSet -> Int -> Int
- count :: DisjointIntSet -> Int -> Int
- findAndCount :: DisjointIntSet -> Int -> (Int, Int)
- numSets :: DisjointIntSet -> Int
- size :: DisjointIntSet -> Int
- nextInSet :: DisjointIntSet -> Int -> Int
- setToList :: DisjointIntSet -> Int -> [Int]

# Documentation

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.

create :: Foldable t => t (Int, Int) -> DisjointIntSet Source #

`create`

creates a `DisjointIntSet`

from a list of int pairs, or indeed any `Foldable`

structure of `(Int, Int)`

.

It basically calls `union`

for each of the pairs and freezes the result. Use this when you've got a list of pairs
for your disjoint set and you have no need to extend it later.

findAndCount :: DisjointIntSet -> Int -> (Int, Int) Source #

numSets :: DisjointIntSet -> Int Source #

How many distinct sets.

size :: DisjointIntSet -> Int Source #

How many elements in this disjoint set.