module Data.Graph.Inductive.Query.Dominators(
    dom
) where

import Data.List
import Data.Graph.Inductive.Graph


type DomSets = [(Node,[Node],[Node])]


intersection :: [[Node]] -> [Node]
intersection cs = foldr intersect (head cs) cs

getdomv :: [Node] -> DomSets -> [[Node]]
getdomv vs  ds = [z|(w,_,z)<-ds,v<-vs,v==w]

builddoms :: DomSets -> [Node] -> DomSets
builddoms ds []     = ds
builddoms ds (v:vs) = builddoms ((fs++[(n,p,sort(n:idv))])++(tail rs)) vs
                      where idv     = intersection (getdomv p ds)
                            (n,p,_) = head rs
                            (fs,rs) = span (\(x,_,_)->x/=v) ds

domr :: DomSets -> [Node] -> DomSets
domr ds vs|xs == ds  = ds
          |otherwise = builddoms xs vs
           where xs = (builddoms ds vs)

{-|
Finds the dominators relationship for a given graph and an initial
node. For each node v, it returns the list of dominators of v.
-}
dom :: Graph gr => gr a b -> Node -> [(Node,[Node])]
dom g u = map (\(x,_,z)->(x,z)) (domr ld n')
           where ld    = (u,[],[u]):map (\v->(v,pre g v,n)) (n')
                 n'    = n\\[u]
                 n     = nodes g