module Exercise_5 where
import Test.QuickCheck
import Data.List

{- H5.3 -}
{-WETT-}
type Vertex = Int
type Edge = (Vertex, Vertex)
type Graph = ([Vertex], [Edge])

--getIndex: return index(first Position of Vertex) returns index== length if not found
getIndex :: Vertex -> [(Vertex, Int)] -> Int 
getIndex v [] = 1
getIndex v (x:xs) = if(fst(x) == v) then 0 else 1+getIndex v xs

calculatePath :: [Vertex] -> [Edge]-> [(Vertex, Int)] -> [(Vertex, Int)]
calculatePath [] edges distances = distances 
calculatePath (v:vs) edges distances = 
  let outgoingEdges = [s| s<-edges, (fst s)==v]
   in
      calculatePath vs edges (updateDistances v outgoingEdges distances)
  
topologSort :: Vertex -> [Vertex] -> [Vertex] -> [Edge] -> [Vertex] -> [Vertex]
topologSort v predecessors visited edges return =
  let 
    nextVertexes = [(snd n)| n<-edges, fst(n) == v, not(elem (snd n) visited)]
    nextVertex = if (length nextVertexes) >0 then head[nextVertexes] else [-1]
    in
      if((nextVertex!!0) == -1) then 
        if(length predecessors >0) 
            then topologSort (predecessors!!(length predecessors-1)) (take ((length predecessors)-1) predecessors) visited edges (return++[v]) 
            else reverse(return++[v])
      else topologSort (nextVertex!!0) (predecessors++[v]) (visited++[nextVertex!!0]) edges return
  
updateDistances :: Vertex -> [Edge] -> [(Vertex, Int)] -> [(Vertex, Int)]
updateDistances v [] distances = distances
updateDistances v (e:es) distances = 
  let 
    indV = getIndex v distances
    indE = getIndex (snd e) distances
    (ys,zs) = splitAt indE distances
      in 
    if(snd(distances!!indE))< (snd(distances!!indV) + 1) 
      then updateDistances v es (ys++[((snd e), snd(distances!!indV)+1)] ++ tail zs)
      else updateDistances v es distances

findStartNode :: [Vertex] -> [Edge] -> Vertex
findStartNode [] es = -1
findStartNode (v:vs) es = if(elem True [snd(x)==v| x<-es]) then findStartNode vs es else v

createDistanceTemplate :: [Vertex]-> [(Vertex, Int)]-> [(Vertex,Int)]
createDistanceTemplate [] x = x
createDistanceTemplate (v:vs) x = createDistanceTemplate vs (x++[(v,-1)])

longestPath :: Graph -> Vertex -> Int
longestPath graph target = 
  let 
    startNode = findStartNode (fst graph) (snd graph)
    topologSorted = topologSort startNode [] [startNode] (snd graph) []
    path = calculatePath topologSorted (snd graph) (createDistanceTemplate (fst graph) [])
    index = getIndex target path
    in
      snd(path!!index)+1


{-TTEW-}

-- generates a DAG with u vertices and only one node without incoming edges
-- you can use this function to test your implementation using QuickCheck
genDag :: Int -> Gen Graph
genDag n = let v = [1..n] in
  do b <- mapM (\i -> choose (1,n-i)) [1..n-1]
     t <- mapM (\(c,i) -> vectorOf c (choose (i+1, n))) (zip b [1..n])
     let e = nub $ ([(1, i) | i<-[2..n]] ++ edges t 1 [])
     return $ (v,e)
  where
    edges [] _ acc = acc
    edges (ts:xs) i acc = edges xs (i+1) (acc ++ [(i,t) | t<-ts])