Copyright | (c) Luke Palmer, 2013 |
---|---|

License | BSD3 |

Maintainer | Luke Palmer <lrpalmer@gmail.com> |

Stability | experimental |

Portability | portable |

Safe Haskell | Safe-Inferred |

Language | Haskell98 |

Disjoint set data structure -- `Partition a`

maintains a collection of
disjoint sets of type `a`

, with the ability to find which set a particular
item belongs to and the ability to merge any two such sets into one.

- data Partition a
- discrete :: Partition a
- empty :: Partition a
- fromSets :: Ord a => [Set a] -> Partition a
- fromDisjointSets :: Ord a => [Set a] -> Partition a
- nontrivialSets :: Partition a -> [Set a]
- joinElems :: Ord a => a -> a -> Partition a -> Partition a
- find :: Ord a => Partition a -> a -> Set a
- rep :: Ord a => Partition a -> a -> a

# Documentation

A Partition of `a`

: represents a collection of disjoint sets of `a`

whose
union includes every element of `a`

. Semantics: `[[Partition a]] = P(P(a))`

where `P`

is the power set operation.

discrete :: Partition a Source

A partition in which every element of `a`

is in its own set. Semantics:
`[[discrete]] = { { x } | x in a }`

fromSets :: Ord a => [Set a] -> Partition a Source

Takes a list of (not necessarily disjoint) sets and constructs a partition
that associates all elements shared in *any* of the sets.

*O* (*n* *k* log *n*), where *k* is the maximum set-size and *n* = *l* *k* is
the total number of non-discrete elements.

fromDisjointSets :: Ord a => [Set a] -> Partition a Source

Takes a list of disjoint sets and constructs a partition containing those sets, with every remaining element being given its own set. The precondition is not checked.

*O* (*n* log *n*), where *n* is the total number of elements in the given sets.

nontrivialSets :: Partition a -> [Set a] Source

Returns a list of all nontrivial sets (sets with more than one element) in the partition.

joinElems :: Ord a => a -> a -> Partition a -> Partition a Source

`joinElems x y`

merges the two sets containing `x`

and `y`

into a single set. Semantics:
`[[joinElems x y p]] = (p `minus` find x `minus` find y) `union` { find x `union` find y }`

.

*O* (max(*k* log *n*, *k* log *k*)), where *k* is the size of nontrivial subsets
and *n* is the total number of elements in such sets.