[project @ 2003-02-21 13:26:58 by simonpj]

[ghc-hetmet.git] / ghc / compiler / utils / Digraph.lhs

diff --git a/ghc/compiler/utils/Digraph.lhs b/ghc/compiler/utils/Digraph.lhs
index f09d465..d8f6220 100644 (file)
--- a/ghc/compiler/utils/Digraph.lhs
+++ b/ghc/compiler/utils/Digraph.lhs
@@ -2,7 +2,7 @@
 module Digraph(
 
        -- At present the only one with a "nice" external interface
-       stronglyConnComp, stronglyConnCompR, SCC(..),
+       stronglyConnComp, stronglyConnCompR, SCC(..), flattenSCC, flattenSCCs,
 
        Graph, Vertex, 
        graphFromEdges, buildG, transposeG, reverseE, outdegree, indegree,
@@ -37,12 +37,19 @@ module Digraph(
 import Util    ( sortLt )
 
 -- Extensions
-import ST
+import MONAD_ST
 
 -- std interfaces
 import Maybe
 import Array
 import List
+import Outputable
+
+#if __GLASGOW_HASKELL__ >= 504
+import Data.Array.ST  hiding ( indices, bounds )
+#else
+import ST
+#endif
 \end{code}
 
 
@@ -56,6 +63,18 @@ import List
 data SCC vertex = AcyclicSCC vertex
                | CyclicSCC  [vertex]
 
+flattenSCCs :: [SCC a] -> [a]
+flattenSCCs = concatMap flattenSCC
+
+flattenSCC (AcyclicSCC v) = [v]
+flattenSCC (CyclicSCC vs) = vs
+
+instance Outputable a => Outputable (SCC a) where
+   ppr (AcyclicSCC v) = text "NONREC" $$ (nest 3 (ppr v))
+   ppr (CyclicSCC vs) = text "REC" $$ (nest 3 (vcat (map ppr vs)))
+\end{code}
+
+\begin{code}
 stronglyConnComp
        :: Ord key
        => [(node, key, [key])]         -- The graph; its ok for the
@@ -76,7 +95,7 @@ stronglyConnCompR
        => [(node, key, [key])]         -- The graph; its ok for the
                                        -- out-list to contain keys which arent
                                        -- a vertex key, they are ignored
-       -> [SCC (node, key, [key])]
+       -> [SCC (node, key, [key])]     -- Topologically sorted
 
 stronglyConnCompR [] = []  -- added to avoid creating empty array in graphFromEdges -- SOF
 stronglyConnCompR edges
@@ -198,7 +217,7 @@ drawTree         = unlines . draw
 draw (Node x ts) = grp this (space (length this)) (stLoop ts)
  where this          = s1 ++ x ++ " "
 
-       space n       = take n (repeat ' ')
+       space n       = replicate n ' '
 
        stLoop []     = [""]
        stLoop [t]    = grp s2 "  " (draw t)
@@ -220,6 +239,17 @@ draw (Node x ts) = grp this (space (length this)) (stLoop ts)
 %************************************************************************
 
 \begin{code}
+#if __GLASGOW_HASKELL__ >= 504
+newSTArray :: Ix i => (i,i) -> e -> ST s (STArray s i e)
+newSTArray = newArray
+
+readSTArray :: Ix i => STArray s i e -> i -> ST s e
+readSTArray = readArray
+
+writeSTArray :: Ix i => STArray s i e -> i -> e -> ST s ()
+writeSTArray = writeArray
+#endif
+
 type Set s    = STArray s Vertex Bool
 
 mkEmpty      :: Bounds -> ST s (Set s)