data-partition-0.3.0.0: A pure disjoint set (union find) data structure

Copyright(c) Luke Palmer 2013
LicenseBSD3
MaintainerLuke Palmer <lrpalmer@gmail.com>
Stabilityexperimental
Portabilityportable
Safe HaskellSafe
LanguageHaskell98

Data.Partition.Int

Description

Disjoint set data structure -- Partition maintains a collection of disjoint sets of type Int, with the ability to find which set a particular item belongs to and the ability to merge any two such sets into one.

Synopsis

Documentation

data Partition Source #

An Partition represents a collection of disjoint IntSets whose union includes every Int.

discrete :: Partition Source #

A partition in which every element of Int is in its own set. Semantics: [[discrete]] = { { x } | x in Int }

empty :: Partition Source #

Synonym for discrete.

fromSets :: [IntSet] -> Partition Source #

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

nontrivialSets :: Partition -> [IntSet] Source #

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

nontrivialRepresentatives :: Partition -> [Int] Source #

Returns a list of all representatives (least elements) of nontrivial sets in the partition in ascending order.

nontrivialRepresentatives p = Set.findMin $ nonTrivialSets

join :: Int -> Int -> Partition -> Partition Source #

join x y merges the two sets containing x and y into a single set. Semantics: [[join x y p]] = (p `minus` find x `minus` find y) `union` { find x `union` find y }

find :: Partition -> Int -> IntSet Source #

find p x finds the set that the element x is associated with. Semantics: [[find p x]] = the unique s in p such that x in s.

rep :: Partition -> Int -> Int Source #

rep p x finds the minimum element in the set containing x.