module Exercise_7 where
import Data.List

{-WETT-}
{-very long since wrong input data on the testserver confused me much-}
trancl :: Eq a => [(Integer,(a,a))] -> [(Integer,(a,a))]
trancl xs = tranclAux improvedList improvedList
	where improvedList = improved xs

improved :: Eq a => [(Integer,(a,a))] -> [(Integer,(a,a))]
improved [] = []
improved (x:xs) | (filter (\(distance,r) -> ((r == (snd x)) && (distance < (fst x)))) xs) /= [] = improved xs
                | otherwise = x : (improved (filter (\(distance, r) -> r /= (snd x)) xs))

{- toCheck -> resultSoFar -> result -}
tranclAux :: Eq a => [(Integer,(a,a))] -> [(Integer,(a,a))] -> [(Integer,(a,a))] 
tranclAux [] v = v
tranclAux (x:xs) v = tranclAux ((replaceConnections bessereVerbindungen xs) ++ neueVerbindungen) ((replaceConnections bessereVerbindungen v) ++ neueVerbindungen)
   where ausgehende = map (\(w, (von, nach)) -> (fst x + w, (fst $ snd x, nach))) (filter (\t -> (fst $ snd t) == (snd $ snd x)) v)
         neueVerbindungen = filter (\t -> not $ inList t v) ausgehende
         bessereVerbindungen = filter (\t -> (inList t v && betterConnection t v)) ausgehende

inList :: Eq a => (Integer,(a,a)) -> [(Integer,(a,a))] -> Bool
inList pair [] = False
inList pair (x:xs) | snd pair == snd x = True
                   | otherwise = inList pair xs
   
betterConnection :: Eq a => (Integer,(a,a)) -> [(Integer,(a,a))] -> Bool
betterConnection pair [] = False
betterConnection pair (x:xs) = (snd pair == snd x && fst pair < fst x) || betterConnection pair xs

replaceConnections :: Eq a => [(Integer,(a,a))] -> [(Integer,(a,a))]  -> [(Integer,(a,a))]
replaceConnections [] xs = xs
replaceConnections xs [] = xs
replaceConnections (x:xs) ys = replaceConnections xs (replaceConnection x ys)

replaceConnection :: Eq a => (Integer,(a,a)) -> [(Integer,(a,a))] -> [(Integer,(a,a))]
replaceConnection pair [] = [pair]
replaceConnection pair (x:xs) | snd pair == snd x = pair : xs
                              | otherwise = x : (replaceConnection pair xs)

{-TTEW-}