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


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

main :: IO ()
main =  do (start,end,datei) <- readArguments
           roads <- readRoads datei
           let besteRoute = route roads start end 
           putStr (formatRoute besteRoute)

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



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

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

type Town = String

readArguments :: IO (Town,Town,String)
readArguments =  do (start:end:datei:_) <- getArgs
                    return (start,end,datei)



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

type Road = (Town,Town,Int) 
readRoads :: String -> IO [Road]
readRoads dat =  do  cs <- readFile dat
                     let ls = lines cs  -- lines :: String --> [String]
                     return [(start,end, read cs_len) | line <- ls, 
                                     let [start,end,cs_len] = words line]




-----------------------------------------------
-- 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)) 
  = unlines   [formatStage stage | stage <- stages]
formatRoute Nothing = "Keine Route gefunden"

formatStage :: (Town, Int) -> String
formatStage (t,n) = pad 5 (show n) ++ ' ' : 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 []

-- erstes Argument = Liste der bereits besuchten Staedte
routeAvoiding :: [Town] -> [Road] -> Town -> Town -> Maybe Route
routeAvoiding towns roads from to 
   | from == to = Just (from, to, 0, [])
   | otherwise  = best [ joinRoutes (road2route road) 
                                    (routeAvoiding (from:towns)  roads (endP road) to) 
                       | road <- bothWays roads, startP road == from,
                         not (elem (endP road) towns) ] 


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
   | dist2 < dist1 = r2
   | lr1 > lr2     = r1
   | lr1 <= lr2    = r2 
   where lr1 = length stages1
         lr2 = length stages2
better r1 Nothing = r1
better Nothing r2 = r2 

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


joinRoutes :: Route -> Maybe Route -> Maybe Route 
joinRoutes (from1,to1,len1,stages1) (Just (from2,to2,len2,stages2))
  | to1 == from2 = Just $ (from1,to2,len1+len2,stages1 ++ 
                    [(ort, len1+entf) | (ort,entf) <- stages2])
joinRoutes _ Nothing = Nothing


road2route :: Road -> Route
road2route (from, to, len) = (from, to, len, [(to,len)])


bothWays :: [Road] -> [Road]
bothWays rs = rs ++ [ (end,start,len) | (start,end,len) <- rs]

{-
-- 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 (debugroute roads from to)



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