Documentation

data UnionFind (mv :: Type -> k -> Type) s (a :: k) Source #

newUnionFind :: forall (v :: Type -> Type) a m. (Vector v a, Monoid a, PrimMonad m) => Int -> m (UnionFind (Mutable v) (PrimState m) a) Source #

>>> import qualified Data.Set as S
>>> import qualified Data.Vector as V
>>> uf <- newUnionFind @V.Vector @(S.Set Int) 3

buildUnionFind :: (Vector v a, PrimMonad m) => v a -> m (UnionFind (Mutable v) (PrimState m) a) Source #

>>> import Data.Bits
>>> import qualified Data.Vector as V
>>> uf <- buildUnionFind (V.generate 3 Xor)

findUF :: forall {k} m (mv :: Type -> k -> Type) (a :: k). PrimMonad m => UnionFind mv (PrimState m) a -> Int -> m Int Source #

sizeUF :: forall {k} m (mv :: Type -> k -> Type) (a :: k). PrimMonad m => UnionFind mv (PrimState m) a -> Int -> m Int Source #

readUF :: forall (v :: Type -> Type) a m. (Vector v a, PrimMonad m) => UnionFind (Mutable v) (PrimState m) a -> Int -> m a Source #

equivUF uf x y ==> readUF uf x == readUF uf y

writeUF :: forall (v :: Type -> Type) a m. (Vector v a, PrimMonad m) => UnionFind (Mutable v) (PrimState m) a -> Int -> a -> m () Source #

>>> import qualified Data.Vector as V
>>> uf <- newUnionFind @V.Vector @String 3
>>> uniteUF_ uf 0 2
>>> writeUF uf 0 "X"
>>> mapM (readUF uf) [0..2]
["X","","X"]

modifyUF :: forall (v :: Type -> Type) a m. (Vector v a, PrimMonad m) => UnionFind (Mutable v) (PrimState m) a -> (a -> a) -> Int -> m () Source #

uniteUF :: forall (v :: Type -> Type) a m. (Vector v a, Monoid a, PrimMonad m) => UnionFind (Mutable v) (PrimState m) a -> Int -> Int -> m Bool Source #

>>> import Data.Monoid
>>> uf <- buildUnionFind (U.replicate 3 (Sum 1))
>>> uniteUF uf 0 2
True
>>> uniteUF uf 0 2
False
>>> mapM (readUF uf) [0..2]
[Sum {getSum = 2.0},Sum {getSum = 1.0},Sum {getSum = 2.0}]

uniteUF_ :: forall (v :: Type -> Type) a m. (Vector v a, Monoid a, PrimMonad m) => UnionFind (Mutable v) (PrimState m) a -> Int -> Int -> m () Source #

>>> import qualified Data.Set as S
>>> import qualified Data.Vector as V
>>> uf <- buildUnionFind (V.generate 3 S.singleton)
>>> uniteUF_ uf 0 2
>>> mapM (readUF uf) [0..2]
[fromList [0,2],fromList [1],fromList [0,2]]

>>> import qualified Data.Vector as V
>>> uf <- buildUnionFind (V.generate 3 (:[]))
>>> uniteUF_ uf 0 1
>>> uniteUF_ uf 2 0
>>> mapM (readUF uf) [0..2]
[[2,0,1],[2,0,1],[2,0,1]]

equivUF :: forall {k} m (mv :: Type -> k -> Type) (a :: k). PrimMonad m => UnionFind mv (PrimState m) a -> Int -> Int -> m Bool Source #

countGroupUF :: forall {k} m (mv :: Type -> k -> Type) (a :: k). PrimMonad m => UnionFind mv (PrimState m) a -> m Int Source #