Data.Partition.Int

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.

Documentation

data Partition

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

Instances

Eq Partition

Defined in Data.Partition.Int

Methods

(==) :: Partition -> Partition -> Bool

(/=) :: Partition -> Partition -> Bool

Ord Partition

Defined in Data.Partition.Int

Methods

compare :: Partition -> Partition -> Ordering

(<) :: Partition -> Partition -> Bool

(<=) :: Partition -> Partition -> Bool

(>) :: Partition -> Partition -> Bool

(>=) :: Partition -> Partition -> Bool

max :: Partition -> Partition -> Partition

min :: Partition -> Partition -> Partition

Show Partition

Defined in Data.Partition.Int

Methods

showsPrec :: Int -> Partition -> ShowS

show :: Partition -> String

showList :: [Partition] -> ShowS

discrete :: Partition

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

empty :: Partition

Synonym for discrete.

fromSets :: [IntSet] -> Partition

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]

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

nontrivialRepresentatives :: Partition -> [Int]

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

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

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

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