-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | union find data structure
--   
--   ST based implementation of Tarjan's disjoint set forests, using
--   mutable arrays storing indices instead of references internally. There
--   is also a pure, immutable version of the data structure, which is
--   useful for querying the result of a union find construction.
@package union-find-array
@version 0.1.0.4

module Data.Union.Type

-- | An immutable disjoint set forest.
data Union a
Union :: !Int -> UArray Int Int -> Array Int a -> Union a
[size] :: Union a -> !Int
[up] :: Union a -> UArray Int Int
[label] :: Union a -> Array Int a

-- | A node in a disjoint set forest.
newtype Node
Node :: Int -> Node
[fromNode] :: Node -> Int
instance GHC.Ix.Ix Data.Union.Type.Node
instance GHC.Classes.Ord Data.Union.Type.Node
instance GHC.Classes.Eq Data.Union.Type.Node


-- | Low-level interface for managing a disjoint set data structure, based
--   on <a>ST</a>. For a higher level convenience interface, look at
--   <a>Union</a>.
module Data.Union.ST

-- | A disjoint set forest, with nodes numbered from 0, which can carry
--   labels.
data UnionST s l

-- | Analogous to <a>runSTArray</a>.
runUnionST :: (forall s. ST s (UnionST s l)) -> Union l

-- | Create a new disjoint set forest, of given capacity.
new :: Int -> l -> ST s (UnionST s l)

-- | Grow the capacity of a disjoint set forest. Shrinking is not possible.
--   Trying to shrink a disjoint set forest will return the same forest
--   unmodified.
grow :: UnionST s l -> Int -> ST s (UnionST s l)

-- | Copy a disjoint set forest.
copy :: UnionST s l -> ST s (UnionST s l)

-- | Look up the representative of a given node and its label.
lookup :: UnionST s l -> Int -> ST s (Int, l)

-- | Annotate a node with a new label.
annotate :: UnionST s l -> Int -> l -> ST s ()

-- | Merge two nodes if they are in distinct equivalence classes. The
--   passed function is used to combine labels, if a merge happens.
merge :: UnionST s l -> (l -> l -> (l, a)) -> Int -> Int -> ST s (Maybe a)

-- | Flatten a disjoint set forest, for faster lookups.
flatten :: UnionST s l -> ST s ()
size :: UnionST s l -> Int

-- | Analogous to <a>unsafeFreeze</a>
unsafeFreeze :: UnionST s l -> ST s (Union l)


-- | Immutable disjoint set forests.
module Data.Union

-- | An immutable disjoint set forest.
data Union a

-- | A node in a disjoint set forest.
newtype Node
Node :: Int -> Node
[fromNode] :: Node -> Int

-- | Get the number of nodes in the forest.
size :: Union l -> Int

-- | Look up the representative of a node, and its label.
lookup :: Union l -> Node -> (Node, l)

-- | Version of <a>lookup</a> that assumes the forest to be flattened. (cf.
--   <a>flatten</a>.)
--   
--   Do not use otherwise: It will give wrong results!
lookupFlattened :: Union a -> Node -> (Node, a)

module Control.Monad.Union.Class
class Monad m => MonadUnion l m | m -> l

-- | Add a new node, with a given label.
new :: MonadUnion l m => l -> m Node

-- | Find the node representing a given node, and its label.
lookup :: MonadUnion l m => Node -> m (Node, l)

-- | Merge two sets. The first argument is a function that takes the labels
--   of the corresponding sets' representatives and computes a new label
--   for the joined set. Returns Nothing if the given nodes are in the same
--   set already.
merge :: MonadUnion l m => (l -> l -> (l, a)) -> Node -> Node -> m (Maybe a)

-- | Re-label a node.
annotate :: MonadUnion l m => Node -> l -> m ()

-- | Flatten the disjoint set forest for faster lookups.
flatten :: MonadUnion l m => m ()
instance (Control.Monad.Union.Class.MonadUnion l m, Control.Monad.Trans.Class.MonadTrans t, GHC.Base.Monad (t m)) => Control.Monad.Union.Class.MonadUnion l (t m)


-- | Monadic interface for creating a disjoint set data structure.
module Control.Monad.Union

-- | Union find monad.
data UnionM l a

-- | An immutable disjoint set forest.
data Union a
Union :: !Int -> UArray Int Int -> Array Int a -> Union a
[size] :: Union a -> !Int
[up] :: Union a -> UArray Int Int
[label] :: Union a -> Array Int a
class Monad m => MonadUnion l m | m -> l

-- | Add a new node, with a given label.
new :: MonadUnion l m => l -> m Node

-- | Find the node representing a given node, and its label.
lookup :: MonadUnion l m => Node -> m (Node, l)

-- | Merge two sets. The first argument is a function that takes the labels
--   of the corresponding sets' representatives and computes a new label
--   for the joined set. Returns Nothing if the given nodes are in the same
--   set already.
merge :: MonadUnion l m => (l -> l -> (l, a)) -> Node -> Node -> m (Maybe a)

-- | Re-label a node.
annotate :: MonadUnion l m => Node -> l -> m ()

-- | Flatten the disjoint set forest for faster lookups.
flatten :: MonadUnion l m => m ()

-- | A node in a disjoint set forest.
data Node

-- | Run a union find computation.
run :: UnionM l a -> a

-- | Run a union find computation; also return the final disjoint set
--   forest for querying.
run' :: UnionM l a -> (Union l, a)
instance GHC.Base.Monad (Control.Monad.Union.UnionM l)
instance GHC.Base.Functor (Control.Monad.Union.UnionM l)
instance GHC.Base.Applicative (Control.Monad.Union.UnionM l)
instance Control.Monad.Fix.MonadFix (Control.Monad.Union.UnionM l)
instance Control.Monad.Union.Class.MonadUnion l (Control.Monad.Union.UnionM l)