{-# LANGUAGE FlexibleContexts, FlexibleInstances, MultiParamTypeClasses #-}

-- (c) 2002 by Martin Erwig [see file COPYRIGHT]
-- | Static IOArray-based Graphs
module Data.Graph.Inductive.Monad.STArray(
    -- * Graph Representation
    SGr(..), GraphRep, Context', USGr,
    defaultGraphSize, emptyN,
    -- * Utilities
    removeDel,
) where

import Data.Graph.Inductive.Graph
import Data.Graph.Inductive.Monad

import Control.Monad
import Control.Monad.ST
import Data.Array
import Data.Array.ST
import System.IO.Unsafe



----------------------------------------------------------------------
-- GRAPH REPRESENTATION
----------------------------------------------------------------------

newtype SGr s a b = SGr (GraphRep s a b)

type GraphRep s a b = (Int,Array Node (Context' a b),STArray s Node Bool)
type Context'   a b = Maybe (Adj b,a,Adj b)

type USGr s = SGr s () ()


----------------------------------------------------------------------
-- CLASS INSTANCES
----------------------------------------------------------------------

-- Show
--
showGraph :: (Show a,Show b) => GraphRep RealWorld a b -> String
showGraph :: forall a b. (Show a, Show b) => GraphRep RealWorld a b -> String
showGraph (Node
_,Array Node (Context' a b)
a,STArray RealWorld Node Bool
m) = forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Node -> String
showAdj (forall i e. Ix i => Array i e -> [i]
indices Array Node (Context' a b)
a)
    where showAdj :: Node -> String
showAdj Node
v | forall a. ST RealWorld a -> a
unsafeST (forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> i -> m e
readArray STArray RealWorld Node Bool
m Node
v) = String
""
                    | Bool
otherwise = case Array Node (Context' a b)
aforall i e. Ix i => Array i e -> i -> e
!Node
v of
                        Context' a b
Nothing      -> String
""
                        Just (Adj b
_,a
l,Adj b
s) -> Char
'\n'forall a. a -> [a] -> [a]
:forall a. Show a => a -> String
show Node
vforall a. [a] -> [a] -> [a]
++String
":"forall a. [a] -> [a] -> [a]
++forall a. Show a => a -> String
show a
lforall a. [a] -> [a] -> [a]
++String
"->"forall a. [a] -> [a] -> [a]
++forall a. Show a => a -> String
show Adj b
s'
                          where s' :: Adj b
s' = forall a. ST RealWorld a -> a
unsafeST (forall s b. STArray s Node Bool -> Adj b -> ST s (Adj b)
removeDel STArray RealWorld Node Bool
m Adj b
s)

unsafeST :: ST RealWorld a -> a
unsafeST :: forall a. ST RealWorld a -> a
unsafeST = forall a. IO a -> a
unsafePerformIO forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a. ST RealWorld a -> IO a
stToIO

-- | Please not that this instance is unsafe.
instance (Show a,Show b) => Show (SGr RealWorld a b) where
  show :: SGr RealWorld a b -> String
show (SGr GraphRep RealWorld a b
g) = forall a b. (Show a, Show b) => GraphRep RealWorld a b -> String
showGraph GraphRep RealWorld a b
g

{-
run :: Show (IO a) => IO a -> IO ()
run x = seq x (print x)
-}

-- GraphM
--
instance GraphM (ST s) (SGr s) where
  emptyM :: forall a b. ST s (SGr s a b)
emptyM = forall s a b. Node -> ST s (SGr s a b)
emptyN Node
defaultGraphSize
  isEmptyM :: forall a b. ST s (SGr s a b) -> ST s Bool
isEmptyM ST s (SGr s a b)
g = do {SGr (Node
n,Array Node (Context' a b)
_,STArray s Node Bool
_) <- ST s (SGr s a b)
g; forall (m :: * -> *) a. Monad m => a -> m a
return (Node
nforall a. Eq a => a -> a -> Bool
==Node
0)}
  matchM :: forall a b. Node -> ST s (SGr s a b) -> ST s (Decomp (SGr s) a b)
matchM Node
v ST s (SGr s a b)
g = do g' :: SGr s a b
g'@(SGr (Node
n,Array Node (Context' a b)
a,STArray s Node Bool
m)) <- ST s (SGr s a b)
g
                  case Array Node (Context' a b)
aforall i e. Ix i => Array i e -> i -> e
!Node
v of
                    Context' a b
Nothing -> forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Maybe a
Nothing,SGr s a b
g')
                    Just (Adj b
pr,a
l,Adj b
su) ->
                       do Bool
b <- forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> i -> m e
readArray STArray s Node Bool
m Node
v
                          if Bool
b then forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. Maybe a
Nothing,SGr s a b
g') else
                             do Adj b
s  <- forall s b. STArray s Node Bool -> Adj b -> ST s (Adj b)
removeDel STArray s Node Bool
m Adj b
su
                                Adj b
p' <- forall s b. STArray s Node Bool -> Adj b -> ST s (Adj b)
removeDel STArray s Node Bool
m Adj b
pr
                                let p :: Adj b
p = forall a. (a -> Bool) -> [a] -> [a]
filter ((forall a. Eq a => a -> a -> Bool
/=Node
v)forall b c a. (b -> c) -> (a -> b) -> a -> c
.forall a b. (a, b) -> b
snd) Adj b
p'
                                forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> i -> e -> m ()
writeArray STArray s Node Bool
m Node
v Bool
True
                                forall (m :: * -> *) a. Monad m => a -> m a
return (forall a. a -> Maybe a
Just (Adj b
p,Node
v,a
l,Adj b
s),forall s a b. GraphRep s a b -> SGr s a b
SGr (Node
nforall a. Num a => a -> a -> a
-Node
1,Array Node (Context' a b)
a,STArray s Node Bool
m))
  mkGraphM :: forall a b. [LNode a] -> [LEdge b] -> ST s (SGr s a b)
mkGraphM [LNode a]
vs [LEdge b]
es = do STArray s Node Bool
m <- forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
(i, i) -> e -> m (a i e)
newArray (Node
1,Node
n) Bool
False
                      forall (m :: * -> *) a. Monad m => a -> m a
return (forall s a b. GraphRep s a b -> SGr s a b
SGr (Node
n,Array Node (Maybe ([(b, Node)], a, [(b, Node)]))
pr,STArray s Node Bool
m))
          where nod :: Array Node (Maybe ([a], a, [a]))
nod  = forall i e. Ix i => (i, i) -> [(i, e)] -> Array i e
array (Node, Node)
bnds (forall a b. (a -> b) -> [a] -> [b]
map (\(Node
v,a
l)->(Node
v,forall a. a -> Maybe a
Just ([],a
l,[]))) [LNode a]
vs)
                su :: Array Node (Maybe ([a], a, [(b, Node)]))
su   = forall i e a.
Ix i =>
(e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
accum forall {a} {b} {a} {b}.
Maybe (a, b, [(a, b)]) -> (a, b) -> Maybe (a, b, [(a, b)])
addSuc forall {a} {a}. Array Node (Maybe ([a], a, [a]))
nod (forall a b. (a -> b) -> [a] -> [b]
map (\(Node
v,Node
w,b
l)->(Node
v,(b
l,Node
w))) [LEdge b]
es)
                pr :: Array Node (Maybe ([(b, Node)], a, [(b, Node)]))
pr   = forall i e a.
Ix i =>
(e -> a -> e) -> Array i e -> [(i, a)] -> Array i e
accum forall {a} {b} {b} {c}.
Maybe ([(a, b)], b, c) -> (a, b) -> Maybe ([(a, b)], b, c)
addPre forall {a}. Array Node (Maybe ([a], a, [(b, Node)]))
su (forall a b. (a -> b) -> [a] -> [b]
map (\(Node
v,Node
w,b
l)->(Node
w,(b
l,Node
v))) [LEdge b]
es)
                bnds :: (Node, Node)
bnds = (forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
minimum [Node]
vs',forall (t :: * -> *) a. (Foldable t, Ord a) => t a -> a
maximum [Node]
vs')
                vs' :: [Node]
vs'  = forall a b. (a -> b) -> [a] -> [b]
map forall a b. (a, b) -> a
fst [LNode a]
vs
                n :: Node
n    = forall (t :: * -> *) a. Foldable t => t a -> Node
length [LNode a]
vs
                addSuc :: Maybe (a, b, [(a, b)]) -> (a, b) -> Maybe (a, b, [(a, b)])
addSuc (Just (a
p,b
l',[(a, b)]
s)) (a
l,b
w) = forall a. a -> Maybe a
Just (a
p,b
l',(a
l,b
w)forall a. a -> [a] -> [a]
:[(a, b)]
s)
                addSuc Maybe (a, b, [(a, b)])
Nothing (a, b)
_ = forall a. HasCallStack => String -> a
error String
"mkGraphM (SGr): addSuc Nothing"
                addPre :: Maybe ([(a, b)], b, c) -> (a, b) -> Maybe ([(a, b)], b, c)
addPre (Just ([(a, b)]
p,b
l',c
s)) (a
l,b
w) = forall a. a -> Maybe a
Just ((a
l,b
w)forall a. a -> [a] -> [a]
:[(a, b)]
p,b
l',c
s)
                addPre Maybe ([(a, b)], b, c)
Nothing (a, b)
_ = forall a. HasCallStack => String -> a
error String
"mkGraphM (SGr): addPre Nothing"
  labNodesM :: forall a b. ST s (SGr s a b) -> ST s [LNode a]
labNodesM ST s (SGr s a b)
g = do (SGr (Node
_,Array Node (Context' a b)
a,STArray s Node Bool
m)) <- ST s (SGr s a b)
g
                   let getLNode :: [(Node, b)] -> (Node, Maybe (a, b, c)) -> m [(Node, b)]
getLNode [(Node, b)]
vs (Node
_,Maybe (a, b, c)
Nothing)      = forall (m :: * -> *) a. Monad m => a -> m a
return [(Node, b)]
vs
                       getLNode [(Node, b)]
vs (Node
v,Just (a
_,b
l,c
_)) =
                           do Bool
b <- forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> i -> m e
readArray STArray s Node Bool
m Node
v
                              forall (m :: * -> *) a. Monad m => a -> m a
return (if Bool
b then [(Node, b)]
vs else (Node
v,b
l)forall a. a -> [a] -> [a]
:[(Node, b)]
vs)
                   forall (t :: * -> *) (m :: * -> *) b a.
(Foldable t, Monad m) =>
(b -> a -> m b) -> b -> t a -> m b
foldM forall {m :: * -> *} {b} {a} {c}.
MArray (STArray s) Bool m =>
[(Node, b)] -> (Node, Maybe (a, b, c)) -> m [(Node, b)]
getLNode [] (forall i e. Ix i => Array i e -> [(i, e)]
assocs Array Node (Context' a b)
a)

defaultGraphSize :: Int
defaultGraphSize :: Node
defaultGraphSize = Node
100

emptyN :: Int -> ST s (SGr s a b)
emptyN :: forall s a b. Node -> ST s (SGr s a b)
emptyN Node
n = do STArray s Node Bool
m <- forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
(i, i) -> e -> m (a i e)
newArray (Node
1,Node
n) Bool
False
              forall (m :: * -> *) a. Monad m => a -> m a
return (forall s a b. GraphRep s a b -> SGr s a b
SGr (Node
0,forall i e. Ix i => (i, i) -> [(i, e)] -> Array i e
array (Node
1,Node
n) [(Node
i,forall a. Maybe a
Nothing) | Node
i <- [Node
1..Node
n]],STArray s Node Bool
m))

----------------------------------------------------------------------
-- UTILITIES
----------------------------------------------------------------------



-- | filter list (of successors\/predecessors) through a boolean ST array
-- representing deleted marks
removeDel :: STArray s Node Bool -> Adj b -> ST s (Adj b)
removeDel :: forall s b. STArray s Node Bool -> Adj b -> ST s (Adj b)
removeDel STArray s Node Bool
m = forall (m :: * -> *) a.
Applicative m =>
(a -> m Bool) -> [a] -> m [a]
filterM (\(b
_,Node
v)->do {Bool
b<-forall (a :: * -> * -> *) e (m :: * -> *) i.
(MArray a e m, Ix i) =>
a i e -> i -> m e
readArray STArray s Node Bool
m Node
v;forall (m :: * -> *) a. Monad m => a -> m a
return (Bool -> Bool
not Bool
b)})