-- | 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
-- @O(1)@):
--
--  1. Check whether two elements are in the same equivalence class.
--
--  2. Create a union of two equivalence classes.
--
--  3. Look up the descriptor of the equivalence class.
-- 
-- 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.
--
{-# OPTIONS_GHC -funbox-strict-fields #-}
module Data.UnionFind.ST
  ( Point, fresh, repr, union, union', equivalent, redundant,
    descriptor, setDescriptor, modifyDescriptor )
where

import Control.Applicative
import Control.Monad ( when )
import Control.Monad.ST
import Data.STRef

-- | The abstract type of an element of the sets we work on.  It is
-- parameterised over the type of the descriptor.
newtype Point s a = Pt (STRef s (Link s a)) deriving Point s a -> Point s a -> Bool
(Point s a -> Point s a -> Bool)
-> (Point s a -> Point s a -> Bool) -> Eq (Point s a)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall s a. Point s a -> Point s a -> Bool
$c== :: forall s a. Point s a -> Point s a -> Bool
== :: Point s a -> Point s a -> Bool
$c/= :: forall s a. Point s a -> Point s a -> Bool
/= :: Point s a -> Point s a -> Bool
Eq

data Link s a
    = Info {-# UNPACK #-} !(STRef s (Info a))
      -- ^ This is the descriptive element of the equivalence class.
    | Link {-# UNPACK #-} !(Point s a)
      -- ^ Pointer to some other element of the equivalence class.
     deriving Link s a -> Link s a -> Bool
(Link s a -> Link s a -> Bool)
-> (Link s a -> Link s a -> Bool) -> Eq (Link s a)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall s a. Link s a -> Link s a -> Bool
$c== :: forall s a. Link s a -> Link s a -> Bool
== :: Link s a -> Link s a -> Bool
$c/= :: forall s a. Link s a -> Link s a -> Bool
/= :: Link s a -> Link s a -> Bool
Eq

data Info a = MkInfo
  { forall a. Info a -> Int
weight :: {-# UNPACK #-} !Int
    -- ^ The size of the equivalence class, used by 'union'.
  , forall a. Info a -> a
descr  :: a
  } deriving Info a -> Info a -> Bool
(Info a -> Info a -> Bool)
-> (Info a -> Info a -> Bool) -> Eq (Info a)
forall a. Eq a => Info a -> Info a -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall a. Eq a => Info a -> Info a -> Bool
== :: Info a -> Info a -> Bool
$c/= :: forall a. Eq a => Info a -> Info a -> Bool
/= :: Info a -> Info a -> Bool
Eq

-- | /O(1)/. 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)
fresh :: forall a s. a -> ST s (Point s a)
fresh a
desc = do
  info <- Info a -> ST s (STRef s (Info a))
forall a s. a -> ST s (STRef s a)
newSTRef (MkInfo { weight :: Int
weight = Int
1, descr :: a
descr = a
desc })
  l <- newSTRef (Info info)
  return (Pt l)

-- | /O(1)/. @repr point@ returns the representative point of
-- @point@'s equivalence class.
--
-- This method performs the path compresssion.
repr :: Point s a -> ST s (Point s a)
repr :: forall s a. Point s a -> ST s (Point s a)
repr point :: Point s a
point@(Pt STRef s (Link s a)
l) = do
  link <- STRef s (Link s a) -> ST s (Link s a)
forall s a. STRef s a -> ST s a
readSTRef STRef s (Link s a)
l
  case link of
    Info STRef s (Info a)
_ -> Point s a -> ST s (Point s a)
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return Point s a
point
    Link pt' :: Point s a
pt'@(Pt STRef s (Link s a)
l') -> do
      pt'' <- Point s a -> ST s (Point s a)
forall s a. Point s a -> ST s (Point s a)
repr Point s a
pt'
      when (pt'' /= pt') $ do
        -- At this point we know that @pt'@ is not the representative
        -- element of @point@'s equivalent class.  Therefore @pt'@'s
        -- link must be of the form @Link r@.  We write this same
        -- value into @point@'s link reference and thereby perform
        -- path compression.
        link' <- readSTRef l'
        writeSTRef l link'
      return pt''

-- | Return the reference to the point's equivalence class's
-- descriptor.
descrRef :: Point s a -> ST s (STRef s (Info a))
descrRef :: forall s a. Point s a -> ST s (STRef s (Info a))
descrRef point :: Point s a
point@(Pt STRef s (Link s a)
link_ref) = do
  link <- STRef s (Link s a) -> ST s (Link s a)
forall s a. STRef s a -> ST s a
readSTRef STRef s (Link s a)
link_ref
  case link of
    Info STRef s (Info a)
info -> STRef s (Info a) -> ST s (STRef s (Info a))
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return STRef s (Info a)
info
    Link (Pt STRef s (Link s a)
link'_ref) -> do
      link' <- STRef s (Link s a) -> ST s (Link s a)
forall s a. STRef s a -> ST s a
readSTRef STRef s (Link s a)
link'_ref
      case link' of
        Info STRef s (Info a)
info -> STRef s (Info a) -> ST s (STRef s (Info a))
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return STRef s (Info a)
info
        Link s a
_ -> Point s a -> ST s (STRef s (Info a))
forall s a. Point s a -> ST s (STRef s (Info a))
descrRef (Point s a -> ST s (STRef s (Info a)))
-> ST s (Point s a) -> ST s (STRef s (Info a))
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Point s a -> ST s (Point s a)
forall s a. Point s a -> ST s (Point s a)
repr Point s a
point

-- | /O(1)/. Return the descriptor associated with argument point's
-- equivalence class.
descriptor :: Point s a -> ST s a
descriptor :: forall s a. Point s a -> ST s a
descriptor Point s a
point = do
  Info a -> a
forall a. Info a -> a
descr (Info a -> a) -> ST s (Info a) -> ST s a
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> (STRef s (Info a) -> ST s (Info a)
forall s a. STRef s a -> ST s a
readSTRef (STRef s (Info a) -> ST s (Info a))
-> ST s (STRef s (Info a)) -> ST s (Info a)
forall (m :: * -> *) a b. Monad m => (a -> m b) -> m a -> m b
=<< Point s a -> ST s (STRef s (Info a))
forall s a. Point s a -> ST s (STRef s (Info a))
descrRef Point s a
point)

-- | /O(1)/. Replace the descriptor of the point's equivalence class
-- with the second argument.
setDescriptor :: Point s a -> a -> ST s ()
setDescriptor :: forall s a. Point s a -> a -> ST s ()
setDescriptor Point s a
point a
new_descr = do
  r <- Point s a -> ST s (STRef s (Info a))
forall s a. Point s a -> ST s (STRef s (Info a))
descrRef Point s a
point
  modifySTRef r $ \Info a
i -> Info a
i { descr = new_descr }

modifyDescriptor :: Point s a -> (a -> a) -> ST s ()
modifyDescriptor :: forall s a. Point s a -> (a -> a) -> ST s ()
modifyDescriptor Point s a
point a -> a
f = do
  r <- Point s a -> ST s (STRef s (Info a))
forall s a. Point s a -> ST s (STRef s (Info a))
descrRef Point s a
point
  modifySTRef r $ \Info a
i -> Info a
i { descr = f (descr i) }

-- | /O(1)/. 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 ()
union :: forall s a. Point s a -> Point s a -> ST s ()
union Point s a
p1 Point s a
p2 = Point s a -> Point s a -> (a -> a -> ST s a) -> ST s ()
forall s a. Point s a -> Point s a -> (a -> a -> ST s a) -> ST s ()
union' Point s a
p1 Point s a
p2 (\a
_ a
d2 -> a -> ST s a
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return a
d2)

-- | Like 'union', 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 ()
union' :: forall s a. Point s a -> Point s a -> (a -> a -> ST s a) -> ST s ()
union' Point s a
p1 Point s a
p2 a -> a -> ST s a
update = do
  point1@(Pt link_ref1) <- Point s a -> ST s (Point s a)
forall s a. Point s a -> ST s (Point s a)
repr Point s a
p1
  point2@(Pt link_ref2) <- repr p2
  -- The precondition ensures that we don't create cyclic structures.
  when (point1 /= point2) $ do
    ir1 <- readSTRef link_ref1
    let Info info_ref1 = ir1
    ir2 <- readSTRef link_ref2
    let Info info_ref2 = ir2
    i1 <- readSTRef info_ref1 -- d1 is discarded
    let MkInfo w1 d1 = i1
    i2 <- readSTRef info_ref2
    let MkInfo w2 d2 = i2
    d2' <- update d1 d2
    -- Make the smaller tree a a subtree of the bigger one.  The idea
    -- is this: We increase the path length of one set by one.
    -- Assuming all elements are accessed equally often, this means
    -- the penalty is smaller if we do it for the smaller set of the
    -- two.
    if w1 >= w2 then do
      writeSTRef link_ref2 (Link point1)
      writeSTRef info_ref1 (MkInfo (w1 + w2) d2')
     else do
      writeSTRef link_ref1 (Link point2)
      writeSTRef info_ref2 (MkInfo (w1 + w2) d2')

-- | /O(1)/. Return @True@ if both points belong to the same
-- | equivalence class.
equivalent :: Point s a -> Point s a -> ST s Bool
equivalent :: forall s a. Point s a -> Point s a -> ST s Bool
equivalent Point s a
p1 Point s a
p2 = Point s a -> Point s a -> Bool
forall a. Eq a => a -> a -> Bool
(==) (Point s a -> Point s a -> Bool)
-> ST s (Point s a) -> ST s (Point s a -> Bool)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Point s a -> ST s (Point s a)
forall s a. Point s a -> ST s (Point s a)
repr Point s a
p1 ST s (Point s a -> Bool) -> ST s (Point s a) -> ST s Bool
forall a b. ST s (a -> b) -> ST s a -> ST s b
forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> Point s a -> ST s (Point s a)
forall s a. Point s a -> ST s (Point s a)
repr Point s a
p2

-- | /O(1)/. Returns @True@ for all but one element of an equivalence
-- class.  That is, if @ps = [p1, .., pn]@ are all in the same
-- equivalence class, then the following assertion holds.
-- 
-- > do rs <- mapM redundant ps
-- >    assert (length (filter (==False) rs) == 1)
-- 
-- It is unspecified for which element function returns @False@, so be
-- really careful when using this.
redundant :: Point s a -> ST s Bool
redundant :: forall s a. Point s a -> ST s Bool
redundant (Pt STRef s (Link s a)
link_r) = do
  link <- STRef s (Link s a) -> ST s (Link s a)
forall s a. STRef s a -> ST s a
readSTRef STRef s (Link s a)
link_r
  case link of
    Info STRef s (Info a)
_ -> Bool -> ST s Bool
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
    Link Point s a
_ -> Bool -> ST s Bool
forall a. a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True