-- many-to-many on a call graph of the PAKCS Sort library
-- Michael and Sergio
-- Fri Mar  4 14:29:21 PST 2011


import SetFunctions
import List

data Functions 
   = Quicksort | Split | Concatenation
   | Mergesort | Mergelist | Genruns | Merge | Mergepairs

theNodes = Quicksort ? Split ? Concatenation
   ? Mergesort ? Mergelist ? Genruns ? Merge ? Mergepairs


-- (x,y) is in theEdges is x calls y directly
theEdges 
  = [(Quicksort,Split),(Quicksort,Quicksort),(Quicksort,Concatenation)
    ,(Split,Split),(Mergesort,Mergelist),(Mergesort,Genruns)
    ,(Genruns,Genruns),(Mergelist,Mergelist),(Mergelist,Merge)
    ,(Mergelist,Mergepairs),(Mergepairs,Mergepairs),(Mergepairs,Merge)
    ,(Merge,Merge)]


-- is_called_by x yields y iff y is directly called by x
is_called_by x (_++[(z,y)]++_) | z=:=x = y

-- calls x (_++[(y,z)]++_) | z=:=x = y

-- calls x yields y iff y  directly calls x
calls x g | x =:= is_called_by y g
          = y 
          where y free

-- some function directly called by Mergesort
test1 = is_called_by Mergesort theEdges
-- some function directly calling Merge
test2 = calls Merge theEdges

is_called_by'set x g = set2 is_called_by x g
calls'set x g = set2 calls x g

-- set of functions directly called by Mergesort
stest1 = is_called_by'set Mergesort theEdges
-- set of functions directly calling Merge
stest2 = calls'set Merge theEdges

-- is_called_by'star x yields y iff 
-- y is (directly or indirectly) called by x
is_called_by'star x g = next'star x []
  where next'star z v | not (y `elem` v) = y ? next'star y (y:v)
          where y = is_called_by z g 

-- Returns the set of functions (directly or indirectly) called by x
trans_callees x g = nub (sortValues (set2 is_called_by'star x g))

ttest1 = trans_callees Mergesort theEdges
ttest2 = trans_callees Quicksort theEdges

-- Returns the set of functions (directly or indirectly) calling x
trans_callers x g 
  = filter (\z -> x `elem` trans_callees z g) (sortValues (set0 theNodes))