-- 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

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 Eq Node
instance Ord Node
instance Ix 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)

module Control.Monad.Union.Class
class Monad m => MonadUnion l m | m -> l
new :: MonadUnion l m => l -> m Node
lookup :: MonadUnion l m => Node -> m (Node, l)
merge :: MonadUnion l m => (l -> l -> (l, a)) -> Node -> Node -> m (Maybe a)
annotate :: MonadUnion l m => Node -> l -> m ()
flatten :: MonadUnion l m => m ()
instance (MonadUnion l m, MonadTrans t, Monad (t m)) => 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
new :: MonadUnion l m => l -> m Node
lookup :: MonadUnion l m => Node -> m (Node, l)
merge :: MonadUnion l m => (l -> l -> (l, a)) -> Node -> Node -> m (Maybe a)
annotate :: MonadUnion l m => Node -> l -> m ()
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 MonadUnion l (UnionM l)
instance MonadFix (UnionM l)
instance Applicative (UnionM l)
instance Functor (UnionM l)
instance Monad (UnionM 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)