-----------------------------------------
-- Programm "Routenberechnung"  --
-----------------------------------------
module Route where
import System 
------------------------
-- Die Hauptfunktion  --
------------------------    

main :: IO ()
main =  do (from,to,datei) <- readArguments
           roads           <- readRoads datei
           putStr (formatRoute (route roads from to))

{-
readArguments :: IO (Town,Town,String)
readRoads     :: IO [Road]
route         :: [Road] -> Town -> Town -> Maybe Route
formatRoute   :: Maybe Route  -> String
-}

-----------------------------------------------------
-- Teilschritt 1: Einlesen der Argumente           --
-----------------------------------------------------

-- vordefiniert in Bibliothek System
-- getArgs :: IO [String] 

type Town = String

readArguments :: IO (Town,Town,String)
readArguments =  do [from,to,datei] <- getArgs
                    return (from,to,datei) 


-----------------------------------------------
-- Teilschritt 2: Einlesen der Straßeninfos  --
-----------------------------------------------

type Road = (Town,Town,Int) 
readRoads :: String -> IO [Road]
readRoads dat =  do cs <- readFile dat
                    return [ road (words line) 
                           | line <- lines cs ]

road :: [String] -> Road
road [from,to,dist] = (from,to,read dist) 


-----------------------------------------------
-- Teilschritt 3: Formatierung der Ausgabe   --
-----------------------------------------------

type Route = (Town, Town, Int, [(Town,Int)])

formatRoute :: Maybe Route -> String
formatRoute Nothing = "Keine Route gefunden"
formatRoute (Just (from, to, dist, stages)) 
  = unlines [formatStage s | s <- stages]

formatStage :: (String,Int) -> String
formatStage (t,d) = pad 5 (show d) ++ ' ':t

pad :: Int -> String -> String 
pad n s = [' ' | i <- [length s+1 .. n]] ++ s

----------------------------------------------------
-- Teilschritt 4: Berechnung der kürzesten Route  --
----------------------------------------------------

route :: [Road] -> Town -> Town -> Maybe Route
route =  routeAvoiding []

routeAvoiding :: [Town] -> [Road] -> Town -> Town -> Maybe Route
routeAvoiding avoid roads from to | from  == to 
  = Just (to,to,0,[])
routeAvoiding avoid roads from to 
  = best 
    [joinRoutes (road2Route road)
                (routeAvoiding (from:avoid) roads (endP road) to)
         | road <- bothWays roads, 
           startP road == from,
           not (endP road `elem` avoid)]

startP, endP :: Road -> Town
startP (from, to, dist) = from
endP   (from, to, dist) = to

better :: Maybe Route -> Maybe Route -> Maybe Route
better r1@(Just (from1,to1,dist1,stages1)) 
       r2@(Just (from2,to2,dist2,stages2))
   | dist1 < dist2 = r1
   | dist1 > dist2 = r2
   | lr1   >= lr2  = r1
   | lr1   <  lr2  = r2
   where lr1 = length stages1
         lr2 = length stages2
better Nothing r2 = r2
better r1 Nothing = r1


best :: [Maybe Route] -> Maybe Route 
best = foldr better Nothing 

joinRoutes :: Route -> Maybe Route -> Maybe Route 
joinRoutes r1@(from1,to1,dist1,stages1) 
           (Just r2@(from2,to2,dist2,stages2))
   | to1 == from2 = Just (from1, to2, dist1+dist2,
                          stages1 ++ [(t,d+dist1) 
                                     | (t,d) <- stages2])
   | otherwise    = Nothing 
joinRoutes r1 Nothing = Nothing 


road2Route :: Road -> Route
road2Route (from, to, dist) 
   = (from, to, dist, [(to,dist)])

bothWays :: [Road] -> [Road]
bothWays roads = roads ++ [(to,from,dist)| 
                             (from,to,dist) <- roads]








-- Routenverfolgung zu Debugging-Zwecken
debugmain :: Town -> Town -> String -> IO ()
debugmain from to datei 
       =  do -- (from,to,datei) <- readArguments
             roads           <- readRoads datei
             putStr $ unlines $ map show (debugrouteA [] roads from to)



debugrouteA :: [Town] -> [Road] -> Town -> Town -> [Road] 
debugrouteA avoid roads from to | from  == to = []
debugrouteA avoid roads from to 
   = concat [road : debugrouteA (from:avoid) roads (endP road) to
         | road <- bothWays roads, 
           startP road == from, 
           not (endP road `elem` avoid)]