module Exercise_5 where
import Test.QuickCheck
import Data.List

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

{-
Idea :
Wir nehmen die Kantenliste und speichern ihre Werte in eine Adjanzenzliste.
[(0,1),(0,2)] => Kante von 0 nach 1 und Kante von 0 nach 2
-> [ [1,2] [] [] ]
-}

update :: Int -> [a] -> a -> [a]
update _ [] _ = []
update 0 (_:ys) x = [x] ++ ys
update index ys x = lYs ++ [x] ++ rYs
  where 
    (lYs,_:rYs) = splitAt index ys

updateList :: [Int] -> [a] -> a -> [a]
updateList [] xs _ = xs
updateList (i:is) xs x = updateList is (update i xs x) x

adjazenz :: Graph -> [(Int,[Int])]-> [(Int,[Int])]
adjazenz ([], _) _ = [] --empty
adjazenz (_, []) xss = xss
adjazenz (vs, es) [] = adjazenz (vs, es) [ (0,[]) | v <- vs] --init adjazenz list
-- Added -1 as data is inputted with vertices >= 1
adjazenz (vs, (from,to):es) xss = adjazenz (vs, es) $ updateList (xss!!(from-1)) --update adjazenz list
    where
      updateInEdge (count,list) = update (to-1) xss (count+1,list)
      updateList (count,list) = update (from-1) (updateInEdge (xss!!(to-1))) (count,(to-1):list)

{-
1. [(Int,[Int])] := Adjazenzliste
2. [Int] := vertices (FIFO)
3. [Int] := current topology
4. [Int] := res topology
-}
topology_aux :: [(Int,[Int])] -> [Int] -> [Int] -> [Int]
topology_aux _ [] top = top
topology_aux ass (q:qs) top = q:(topology_aux updatedAss updatedQueue top)
    where 
      (updatedQueue,updatedAss) = decInedge ass (snd (ass!!q)) qs

decInedge :: [(Int,[Int])] -> [Int] -> [Int] -> ([Int],[(Int,[Int])])
decInedge ass [] queue = (queue,ass)
decInedge ass (c:cs) queue = 
  if (count - 1) == 0 then
    decInedge (update c ass (count-1,list)) cs (queue ++ [c])
  else
    decInedge (update c ass (count-1,list)) cs queue
  where
    (count,list) = ass!!c

{-
Topology :
1. [(Int,[Int])] := Adjazenzliste
2. Int := Starting vertice
3. [Int] := Topologie
-}
topology :: [(Int,[Int])] -> Int -> [Int]
topology ass x = topology_aux ass [x] []

{-
SSLP :
1. [(Int,[Int])] := Adjazenzliste
2. Int := Starting vertice
3. [Int] := Längster Pfad
-}
sslp :: [(Int,[Int])] -> Int -> [Int]
sslp ass x = sslpAux ass (topology ass x) [0 | as <- ass] 

sslpAux :: [(Int,[Int])] -> [Int] -> [Int] -> [Int]
sslpAux ass [] dist = dist
sslpAux ass (t:top) dist = sslpAux ass top (updated (snd(ass!!t)) (dist!!t))
  where
    updated [] _ = dist
    updated (c:cs) parent = if (parent + 1) > dist!!c then update c (updated cs parent) (parent+1) else updated cs parent

whereEmpty :: [(Int,[Int])] -> Int
whereEmpty ass = fst $ head $ filter (\(c,xs) -> c == 0) ass

longestPath :: Graph -> Vertex -> Int
longestPath (vs,es) vert = (sslp ass s)!!(vert-1)
      where
        ass = adjazenz (vs,es) []
        s = whereEmpty ass
{-TTEW-}