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


-- | Efficient union and equivalence testing of sets.
--   
--   The Union/Find algorithm implements these operations in (effectively)
--   constant-time:
--   
--   <ol>
--   <li>Check whether two elements are in the same equivalence class.</li>
--   <li>Create a union of two equivalence classes.</li>
--   <li>Look up the descriptor of the equivalence class.</li>
--   </ol>
@package union-find
@version 0.2


-- | An implementation of Tarjan's UNION-FIND algorithm. (Robert E Tarjan.
--   "Efficiency of a Good But Not Linear Set Union Algorithm", JACM 22(2),
--   1975)
--   
--   The algorithm implements three operations efficiently (all amortised
--   <tt>O(1)</tt>):
--   
--   <ol>
--   <li>Check whether two elements are in the same equivalence class.</li>
--   <li>Create a union of two equivalence classes.</li>
--   <li>Look up the descriptor of the equivalence class.</li>
--   </ol>
--   
--   The implementation is based on mutable references. Each equivalence
--   class has exactly one member that serves as its representative
--   element. Every element either is the representative element of its
--   equivalence class or points to another element in the same equivalence
--   class. Equivalence testing thus consists of following the pointers to
--   the representative elements and then comparing these for identity.
--   
--   The algorithm performs lazy path compression. That is, whenever we
--   walk along a path greater than length 1 we automatically update the
--   pointers along the path to directly point to the representative
--   element. Consequently future lookups will be have a path length of at
--   most 1.
module Data.UnionFind.ST

-- | The abstract type of an element of the sets we work on. It is
--   parameterised over the type of the descriptor.
data Point s a

-- | <i>O(1)</i>. Create a fresh point and return it. A fresh point is in
--   the equivalence class that contains only itself.
fresh :: a -> ST s (Point s a)

-- | <i>O(1)</i>. <tt>repr point</tt> returns the representative point of
--   <tt>point</tt>'s equivalence class.
--   
--   This method performs the path compresssion.
repr :: Point s a -> ST s (Point s a)

-- | <i>O(1)</i>. Join the equivalence classes of the points (which must be
--   distinct). The resulting equivalence class will get the descriptor of
--   the second argument.
union :: Point s a -> Point s a -> ST s ()

-- | Like <a>union</a>, but sets the descriptor returned from the callback.
--   
--   The intention is to keep the descriptor of the second argument to the
--   callback, but the callback might adjust the information of the
--   descriptor or perform side effects.
union' :: Point s a -> Point s a -> (a -> a -> ST s a) -> ST s ()

-- | <i>O(1)</i>. Return <tt>True</tt> if both points belong to the same |
--   equivalence class.
equivalent :: Point s a -> Point s a -> ST s Bool

-- | <i>O(1)</i>. Returns <tt>True</tt> for all but one element of an
--   equivalence class. That is, if <tt>ps = [p1, .., pn]</tt> are all in
--   the same equivalence class, then the following assertion holds.
--   
--   <pre>
--   do rs &lt;- mapM redundant ps
--      assert (length (filter (==False) rs) == 1)
--   </pre>
--   
--   It is unspecified for which element function returns <tt>False</tt>,
--   so be really careful when using this.
redundant :: Point s a -> ST s Bool

-- | <i>O(1)</i>. Return the descriptor associated with argument point's
--   equivalence class.
descriptor :: Point s a -> ST s a

-- | <i>O(1)</i>. Replace the descriptor of the point's equivalence class
--   with the second argument.
setDescriptor :: Point s a -> a -> ST s ()
modifyDescriptor :: Point s a -> (a -> a) -> ST s ()
instance Eq a => Eq (Info a)
instance Eq (Link s a)
instance Eq (Point s a)


-- | An implementation of Tarjan's UNION-FIND algorithm. (Robert E Tarjan.
--   "Efficiency of a Good But Not Linear Set Union Algorithm", JACM 22(2),
--   1975)
--   
--   The algorithm implements three operations efficiently (all amortised
--   <tt>O(1)</tt>):
--   
--   <ol>
--   <li>Check whether two elements are in the same equivalence class.</li>
--   <li>Create a union of two equivalence classes.</li>
--   <li>Look up the descriptor of the equivalence class.</li>
--   </ol>
--   
--   The implementation is based on mutable references. Each equivalence
--   class has exactly one member that serves as its representative
--   element. Every element either is the representative element of its
--   equivalence class or points to another element in the same equivalence
--   class. Equivalence testing thus consists of following the pointers to
--   the representative elements and then comparing these for identity.
--   
--   The algorithm performs lazy path compression. That is, whenever we
--   walk along a path greater than length 1 we automatically update the
--   pointers along the path to directly point to the representative
--   element. Consequently future lookups will be have a path length of at
--   most 1.
module Data.UnionFind.IO

-- | The abstract type of an element of the sets we work on. It is
--   parameterised over the type of the descriptor.
data Point a

-- | <i>O(1)</i>. Create a fresh point and return it. A fresh point is in
--   the equivalence class that contains only itself.
fresh :: a -> IO (Point a)

-- | <i>O(1)</i>. <tt>repr point</tt> returns the representative point of
--   <tt>point</tt>'s equivalence class.
--   
--   This method performs the path compresssion.
repr :: Point a -> IO (Point a)

-- | <i>O(1)</i>. Join the equivalence classes of the points (which must be
--   distinct). The resulting equivalence class will get the descriptor of
--   the second argument.
union :: Point a -> Point a -> IO ()

-- | Like <a>union</a>, but sets the descriptor returned from the callback.
--   
--   The intention is to keep the descriptor of the second argument to the
--   callback, but the callback might adjust the information of the
--   descriptor or perform side effects.
union' :: Point a -> Point a -> (a -> a -> IO a) -> IO ()

-- | <i>O(1)</i>. Return <tt>True</tt> if both points belong to the same |
--   equivalence class.
equivalent :: Point a -> Point a -> IO Bool

-- | <i>O(1)</i>. Returns <tt>True</tt> for all but one element of an
--   equivalence class. That is, if <tt>ps = [p1, .., pn]</tt> are all in
--   the same equivalence class, then the following assertion holds.
--   
--   <pre>
--   do rs &lt;- mapM redundant ps
--      assert (length (filter (==False) rs) == 1)
--   </pre>
--   
--   It is unspecified for which element function returns <tt>False</tt>,
--   so be really careful when using this.
redundant :: Point a -> IO Bool

-- | <i>O(1)</i>. Return the descriptor associated with argument point's
--   equivalence class.
descriptor :: Point a -> IO a

-- | <i>O(1)</i>. Replace the descriptor of the point's equivalence class
--   with the second argument.
setDescriptor :: Point a -> a -> IO ()
modifyDescriptor :: Point a -> (a -> a) -> IO ()
instance Eq a => Eq (Info a)
instance Eq (Link a)
instance Eq (Point a)

module Data.UnionFind.IntMap
newPointSupply :: PointSupply a
fresh :: PointSupply a -> a -> (PointSupply a, Point a)
repr :: PointSupply a -> Point a -> Point a
descriptor :: PointSupply a -> Point a -> a
union :: PointSupply a -> Point a -> Point a -> PointSupply a
equivalent :: PointSupply a -> Point a -> Point a -> Bool
data PointSupply a
data Point a
instance Show a => Show (Link a)
instance Show a => Show (PointSupply a)

module Control.Monad.Trans.UnionFind

-- | A monad transformer that adds union find operations.
--   
--   The <tt>p</tt> parameter is the type of points. Uses the
--   <a>Data.UnionFind.IntMap</a> as the underlying union-find
--   implementation.
data UnionFindT p m a
runUnionFind :: Monad m => UnionFindT p m a -> m a
data Point a

-- | Create a new point with the given descriptor. The returned is only
--   equivalent to itself.
--   
--   Note that a <a>Point</a> has its own identity. That is, if two points
--   are equivalent then their descriptors are equal, but not vice versa.
fresh :: Monad m => p -> UnionFindT p m (Point p)

-- | <i>O(1)</i>. <tt>repr point</tt> returns the representative point of
--   <tt>point</tt>'s equivalence class.
repr :: Monad m => Point p -> UnionFindT p m (Point p)

-- | Return the descriptor of the
descriptor :: Monad m => Point p -> UnionFindT p m p

-- | Join the equivalence classes of the points. The resulting equivalence
--   class will get the descriptor of the second argument.
union :: Monad m => Point p -> Point p -> UnionFindT p m ()

-- | Test if the two elements are in the same equivalence class.
--   
--   <pre>
--   liftA2 (==) (repr x) (repr y)
--   </pre>
equivalent :: Monad m => Point p -> Point p -> UnionFindT p m Bool
instance Functor m => Functor (UnionFindT p m)
instance (Monad m, Functor m) => Applicative (UnionFindT p m)
instance Monad m => Monad (UnionFindT p m)
instance MonadTrans (UnionFindT p)
