{-# 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
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
/= :: 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
Eq
data Link s a
= Info {-# UNPACK #-} !(STRef s (Info a))
| Link {-# UNPACK #-} !(Point s a)
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
/= :: 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
Eq
data Info a = MkInfo
{ Info a -> Int
weight :: {-# UNPACK #-} !Int
, 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
/= :: Info a -> Info a -> Bool
$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
Eq
fresh :: a -> ST s (Point s a)
fresh :: a -> ST s (Point s a)
fresh desc :: a
desc = do
STRef s (Info a)
info <- Info a -> ST s (STRef s (Info a))
forall a s. a -> ST s (STRef s a)
newSTRef ($WMkInfo :: forall a. Int -> a -> Info a
MkInfo { weight :: Int
weight = 1, descr :: a
descr = a
desc })
STRef s (Link s a)
l <- Link s a -> ST s (STRef s (Link s a))
forall a s. a -> ST s (STRef s a)
newSTRef (STRef s (Info a) -> Link s a
forall s a. STRef s (Info a) -> Link s a
Info STRef s (Info a)
info)
Point s a -> ST s (Point s a)
forall (m :: * -> *) a. Monad m => a -> m a
return (STRef s (Link s a) -> Point s a
forall s a. STRef s (Link s a) -> Point s a
Pt STRef s (Link s a)
l)
repr :: Point s a -> ST s (Point s a)
repr :: Point s a -> ST s (Point s a)
repr point :: Point s a
point@(Pt l :: STRef s (Link s a)
l) = do
Link s a
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 s a
link of
Info _ -> Point s a -> ST s (Point s a)
forall (m :: * -> *) a. Monad m => a -> m a
return Point s a
point
Link pt' :: Point s a
pt'@(Pt l' :: STRef s (Link s a)
l') -> do
Point s a
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'
Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Point s a
pt'' Point s a -> Point s a -> Bool
forall a. Eq a => a -> a -> Bool
/= Point s a
pt') (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
Link s a
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'
STRef s (Link s a) -> Link s a -> ST s ()
forall s a. STRef s a -> a -> ST s ()
writeSTRef STRef s (Link s a)
l Link s a
link'
Point s a -> ST s (Point s a)
forall (m :: * -> *) a. Monad m => a -> m a
return Point s a
pt''
descrRef :: Point s a -> ST s (STRef s (Info a))
descrRef :: Point s a -> ST s (STRef s (Info a))
descrRef point :: Point s a
point@(Pt link_ref :: STRef s (Link s a)
link_ref) = do
Link s a
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 s a
link of
Info info :: STRef s (Info a)
info -> STRef s (Info a) -> ST s (STRef s (Info a))
forall (m :: * -> *) a. Monad m => a -> m a
return STRef s (Info a)
info
Link (Pt link'_ref :: STRef s (Link s a)
link'_ref) -> do
Link s a
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 s a
link' of
Info info :: STRef s (Info a)
info -> STRef s (Info a) -> ST s (STRef s (Info a))
forall (m :: * -> *) a. Monad m => a -> m a
return STRef s (Info a)
info
_ -> 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
descriptor :: Point s a -> ST s a
descriptor :: Point s a -> ST s a
descriptor point :: 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)
setDescriptor :: Point s a -> a -> ST s ()
setDescriptor :: Point s a -> a -> ST s ()
setDescriptor point :: Point s a
point new_descr :: a
new_descr = do
STRef s (Info a)
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
STRef s (Info a) -> (Info a -> Info a) -> ST s ()
forall s a. STRef s a -> (a -> a) -> ST s ()
modifySTRef STRef s (Info a)
r ((Info a -> Info a) -> ST s ()) -> (Info a -> Info a) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \i :: Info a
i -> Info a
i { descr :: a
descr = a
new_descr }
modifyDescriptor :: Point s a -> (a -> a) -> ST s ()
modifyDescriptor :: Point s a -> (a -> a) -> ST s ()
modifyDescriptor point :: Point s a
point f :: a -> a
f = do
STRef s (Info a)
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
STRef s (Info a) -> (Info a -> Info a) -> ST s ()
forall s a. STRef s a -> (a -> a) -> ST s ()
modifySTRef STRef s (Info a)
r ((Info a -> Info a) -> ST s ()) -> (Info a -> Info a) -> ST s ()
forall a b. (a -> b) -> a -> b
$ \i :: Info a
i -> Info a
i { descr :: a
descr = a -> a
f (Info a -> a
forall a. Info a -> a
descr Info a
i) }
union :: Point s a -> Point s a -> ST s ()
union :: Point s a -> Point s a -> ST s ()
union p1 :: Point s a
p1 p2 :: 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 (\_ d2 :: a
d2 -> a -> ST s a
forall (m :: * -> *) a. Monad m => a -> m a
return a
d2)
union' :: Point s a -> Point s a -> (a -> a -> ST s a) -> ST s ()
union' :: Point s a -> Point s a -> (a -> a -> ST s a) -> ST s ()
union' p1 :: Point s a
p1 p2 :: Point s a
p2 update :: a -> a -> ST s a
update = do
point1 :: Point s a
point1@(Pt link_ref1 :: STRef s (Link s a)
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 :: Point s a
point2@(Pt link_ref2 :: STRef s (Link s a)
link_ref2) <- Point s a -> ST s (Point s a)
forall s a. Point s a -> ST s (Point s a)
repr Point s a
p2
Bool -> ST s () -> ST s ()
forall (f :: * -> *). Applicative f => Bool -> f () -> f ()
when (Point s a
point1 Point s a -> Point s a -> Bool
forall a. Eq a => a -> a -> Bool
/= Point s a
point2) (ST s () -> ST s ()) -> ST s () -> ST s ()
forall a b. (a -> b) -> a -> b
$ do
Info info_ref1 :: STRef s (Info a)
info_ref1 <- 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_ref1
Info info_ref2 :: STRef s (Info a)
info_ref2 <- 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_ref2
MkInfo w1 :: Int
w1 d1 :: a
d1 <- STRef s (Info a) -> ST s (Info a)
forall s a. STRef s a -> ST s a
readSTRef STRef s (Info a)
info_ref1
MkInfo w2 :: Int
w2 d2 :: a
d2 <- STRef s (Info a) -> ST s (Info a)
forall s a. STRef s a -> ST s a
readSTRef STRef s (Info a)
info_ref2
a
d2' <- a -> a -> ST s a
update a
d1 a
d2
if Int
w1 Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
>= Int
w2 then do
STRef s (Link s a) -> Link s a -> ST s ()
forall s a. STRef s a -> a -> ST s ()
writeSTRef STRef s (Link s a)
link_ref2 (Point s a -> Link s a
forall s a. Point s a -> Link s a
Link Point s a
point1)
STRef s (Info a) -> Info a -> ST s ()
forall s a. STRef s a -> a -> ST s ()
writeSTRef STRef s (Info a)
info_ref1 (Int -> a -> Info a
forall a. Int -> a -> Info a
MkInfo (Int
w1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
w2) a
d2')
else do
STRef s (Link s a) -> Link s a -> ST s ()
forall s a. STRef s a -> a -> ST s ()
writeSTRef STRef s (Link s a)
link_ref1 (Point s a -> Link s a
forall s a. Point s a -> Link s a
Link Point s a
point2)
STRef s (Info a) -> Info a -> ST s ()
forall s a. STRef s a -> a -> ST s ()
writeSTRef STRef s (Info a)
info_ref2 (Int -> a -> Info a
forall a. Int -> a -> Info a
MkInfo (Int
w1 Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Int
w2) a
d2')
equivalent :: Point s a -> Point s a -> ST s Bool
equivalent :: Point s a -> Point s a -> ST s Bool
equivalent p1 :: Point s a
p1 p2 :: 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 (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
redundant :: Point s a -> ST s Bool
redundant :: Point s a -> ST s Bool
redundant (Pt link_r :: STRef s (Link s a)
link_r) = do
Link s a
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 s a
link of
Info _ -> Bool -> ST s Bool
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
False
Link _ -> Bool -> ST s Bool
forall (m :: * -> *) a. Monad m => a -> m a
return Bool
True