-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | A pure disjoint set (union find) data structure
--
@package data-partition
@version 0.3.0.0
-- | 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.
module Data.Partition
-- | 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.
data Partition a
-- | A partition in which every element of a is in its own set.
-- Semantics: [[discrete]] = { { x } | x in a }
discrete :: Partition a
-- | Synonym for discrete.
empty :: Partition a
-- | 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.
fromSets :: Ord a => [Set a] -> Partition a
-- | 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.
fromDisjointSets :: Ord a => [Set a] -> Partition a
-- | Returns a list of all nontrivial sets (sets with more than one
-- element) in the partition.
nontrivialSets :: Partition a -> [Set a]
-- | 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.
joinElems :: Ord a => a -> a -> Partition a -> Partition a
-- | 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.
find :: Ord a => Partition a -> a -> Set a
-- | rep p x finds the minimum element in the set containing
-- x.
rep :: Ord a => Partition a -> a -> a
instance Eq a => Eq (Partition a)
instance Ord a => Ord (Partition a)
instance Show a => Show (Partition a)