-----------------------------------------
-- Programm "Routenberechnung"  --
-----------------------------------------
module Main where
import System   -- stellt getArgs :: IO [String] bereit


------------------------
-- Die Hauptfunktion  --
------------------------    

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


main :: IO ()
main =  do args <- getArgs
           if length args < 3 
            then putStrLn "Parameter: Start ZielreadArguments Dateiname"
            else do let (from,to,datei) = readArguments args
                    roads           <- readRoads datei
                    let result = route  roads from to
                    putStrLn (formatRoute result)
{-
readArguments :: [String] -> (Town,Town,String)
readRoads     :: String -> IO [Road]
route         :: [Road] -> Town -> Town -> Route
formatRoute   :: Route  -> String
-}






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


type Town = String

readArguments :: [String] -> (Town,Town,String)
readArguments (from:to:datei:_) = (from,to,datei)
















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

type Road = (Town,Town,Int) 
readRoads :: String -> IO [Road]
readRoads dat =  do contents <- readFile dat
                    return (toRoads contents)
                    
                    
toRoads :: String -> [Road]
toRoads cs = [(from,to,dist) 
             | (from:to:distAlsString:_) <- map words $ 
                                                   lines cs,
               let dist = read distAlsString]





















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

type Route = (Town, Town, Int, [(Town,Int)])
           -- von - nach - Laenge - Verlauf

formatRoute :: Maybe Route -> String
formatRoute (Just (from, to, dist, stages)) 
  = "Beste Route von " ++ from ++ " nach " ++ to ++
    "\nhat die Gesamtlaenge " ++ show dist ++
    "\nVerlauf:" ++ concatMap formatStage stages
formatRoute Nothing 
  = "Keine Route gefunden"

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

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



----------------------------------------------------
-- Teilschritt 4: Berechnung der kürzesten Route  --
----------------------------------------------------
-- data Maybe a = Nothing | Just a

route :: [Road] -> Town -> Town -> Maybe Route
route roads from to = routeAvoid [] roads from to

routeAvoid :: [Town] -> [Road] -> Town -> Town -> Maybe Route
routeAvoid ts roads from to 
  | from == to  = Just (from, from, 0, [])
  | otherwise   
    = best [ joinRoutes (road2Route road)
                        furtherRoute
           | road <- bothWays roads, 
             startP road == from,
             let furtherRoute = routeAvoid (from:ts) roads (endP road) to,
             not (elem (endP road) ts)  
           ]

-- foldr1 erwartet mindestens 1 Argument
best :: [Maybe Route] -> Maybe Route
best = foldr better Nothing 

better :: Maybe Route -> Maybe Route -> Maybe Route
better route1@(Just (_,_,dist1,verlauf1))
       route2@(Just (_,_,dist2,verlauf2))
 | dist1 < dist2 = route1
 | dist2 < dist1 = route2
 | length verlauf1 < length verlauf2 = route2
 | otherwise     = route1
better Nothing route2  = route2
better route1  Nothing = route1 


joinRoutes :: Route -> Maybe Route -> Maybe Route
joinRoutes route1@(from1,to1,dist1,verlauf1)
           route2@(Just (from2,to2,dist2,verlauf2))
  | to1 == from2 = Just (from1,to2,dist1+dist2,
                    verlauf1 ++ 
                     [(t,d+dist1) | (t,d) <- verlauf2])
joinRoutes _ Nothing = Nothing 
  
road2Route :: Road -> Route
road2Route (from,to,dist) 
  = (from, to, dist, [(to,dist)])

startP :: Road -> Town
startP (from,_,_) = from

endP :: Road -> Town
endP (_,to,_) = to

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

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



debugroute :: [Town] -> [Road] -> Town -> Town -> [Road] 
debugroute ts  roads from to | from  == to = []
debugroute ts  roads from to 
   = concat [road : debugroute (from:ts) roads (endP road) to
         | road <- bothWays roads, 
           startP road == from, 
           not (elem (endP road) ts)
         ]
         -}