import List;
import Maybe;



type Cost = Integer
type Vertex = Integer
type MaxVertexNo = Integer
type Edge = (Vertex, Cost, Vertex)
type Row = [Integer]

data ALgraph = ALg [(Vertex,[(Vertex,Cost)])] deriving (Eq,Show)
data ELgraph = ELg MaxVertexNo [Edge] deriving (Eq,Show)
data AMgraph = AMg [Row] deriving (Eq,Show)


type Inp = (MaxVertexNo, [(Vertex,Vertex,Cost)])


{- Helper: -}

fst3 :: (a, b, c) -> a
fst3 (x,_,_) = x

snd3 :: (a, b, c) -> b
snd3 (_,x,_) = x

thd3 :: (a, b, c) -> c
thd3 (_,_,x) = x



{- Bsp 1: -}
available :: [(Vertex, [Vertex])] -> (Vertex,Vertex,Cost) -> Bool
available liste kante = isJust (find (\x ->  (fst x) == min (fst3 kante) (snd3 kante) && isJust (find (\y -> y == (max (fst3 kante) (snd3 kante))) (snd x))) liste)


push :: [(Vertex, [Vertex])] -> (Vertex,Vertex, Cost) -> [(Vertex, [Vertex])]
push liste lst = liste ++ [(von,[zu])]
 where von = min (fst3 lst) (snd3 lst)
       zu  = max (fst3 lst) (snd3 lst)

push2 :: [(Vertex, [Vertex])] -> (Vertex,Vertex, Cost) -> Maybe [(Vertex, [Vertex])]
push2 liste kante
  | available liste kante    = Nothing
  | otherwise                = Just (push liste kante)



{- TODO:
   !!!ACHTUNG!!!
   Bitte schaut noch mal ob validnames-variable passt, oder ob ich die Namenscheck von den Schranken her falsch
   aufgefasst habe!
-}
walktrough :: MaxVertexNo -> [(Vertex,Vertex,Cost)] -> [(Vertex, [Vertex])] -> Maybe [(Vertex, [Vertex])]
walktrough max graph list
  | length graph == 0   = Just list {- Prüft ob noch eine Liste am stack liegt. Wenn nein: Done! -}
  | validnames == False = Nothing   {- Prüft die Namen -}
  | (thd3 cur) <= 0     = Nothing   {- Prüft ob das Gewicht des aktuellen Elements valide ist -}
  | isNothing (newlist) = Nothing   {- Prüft ob eine Kante mit den selben Endpunkten bereits existiert, und retuniert gegebenenfalls -}
  | otherwise           = nextedge  {- Das nächste Element -}
 where
  ngraph = tail graph
  cur  = head graph
  nextedge = walktrough max ngraph (fromJust newlist)
  newlist  = push2 list cur
  validnames = (fst3 cur) >= 0 && (snd3 cur) >= 0 && (fst3 cur) < max && (snd3 cur) < max


isValid :: Inp -> Bool
isValid g = isJust (walktrough (fst g) (snd g) [])



{- Bsp 2: -}


{- Wir gehen von einem validen Graphen aus! kA ob wir das dürfen. -}
inp2el :: Inp -> ELgraph
inp2el g = ELg maxno (map (\x -> (fst3 x, thd3 x, snd3 x)) list)
 where
  maxno = fst g
  list = snd g



{- Bsp 3: -}

{-- Helpers: --}
isEdge :: Vertex -> Vertex -> Edge -> Bool
isEdge a b e = (a == (fst3 e) && b == (thd3 e)) || (b == (fst3 e) && a == (thd3 e))

notMe :: Vertex -> Vertex -> Vertex -> Vertex
notMe a b ich
  | a == ich  = b
  | otherwise = a



{-- Lösungen: --}
isNeighbourOf :: ELgraph -> Vertex -> Vertex -> Bool
isNeighbourOf (ELg max edges) a b = isJust (find (\x -> (isEdge a b x)) edges)

allNeighboursOf :: ELgraph -> Vertex -> [Vertex]
allNeighboursOf (ELg max edges) a = sort (map (\x -> (notMe (fst3 x) (thd3 x) a)) (myfilter (\x -> (fst3 x) == a || (thd3 x) == a) edges))

{- TODO: Sollte funktionieren, sobald Beispiel 2 fertig ist!
numberOfEdges :: AMgraph -> Integer
numberOfEdges g = length (allNeighboursOf (am2el g))
-}



{- Bitte noch mal genauer testen, ob das mit den Restriktionen eh passt. (i.e. zwei Knoten dürfen nur einmal verbunden sein && Kanten sind gerichtet -- dann sollte es egientlich passen.)  -}
isOnCycle :: ALgraph -> Vertex -> Cost -> Bool
isOnCycle g v cost = path g v v cost






{---------------------------------------------}
{-     Helper - kopiert aus aufgabe4.hs!     -}
{---------------------------------------------}


type MyGraph = [(Vertex,[(Vertex,Cost)])]
castGraph :: ALgraph -> MyGraph
castGraph (ALg xs) = xs

{- Prüft ob ein Vertex bereits besucht wurde -}
exist :: [Vertex] -> Vertex -> Bool
exist mypath node =  isNothing (find (==node) mypath) == False


{- Gibt die Liste aller Kanten, passend zu einem Knoten, zurück. -}
getedges :: MyGraph -> Vertex -> [(Vertex,Cost)]
getedges g k
  | isNothing e   = []
  | otherwise     = snd ((maybeToList e)!!0)
 where e = find (\n -> (fst n) == k) g




{- Durchsucht den Graphen rekursiv nach einen Pfad und prüft, sobald ein Pfad gefunden wurde, ob er billig genug ist.
Wenn kein Pfad existiert, oder dieser zu teuer ist, dann wird eine leere Liste zurück gegeben. -}
findPath :: MyGraph -> Vertex -> Vertex -> [Vertex] -> Int -> Integer -> Integer -> Bool -> [Vertex]
findPath g von zu mypath pos max cur first
  | von == zu && cur <= max && first == False = mypath ++ [von]
  | von == zu && first == False               = []
  | (length edges) <= pos                     = []
  | pos == 0 && (exist mypath von)            = []
  | (length current /= 0)                     = current
  | pos < (length edges)                      = next_sibling
  | otherwise                                 = []
 where
  next_sibling = findPath g von zu mypath (pos+1) max cur first
  edges   = getedges g von
  weight  = cur + snd (edges!!pos)
  current = findPath g (fst (edges!!pos)) zu (mypath++[von]) 0 max weight False


{- Versucht erst einen Pfad zu finden. Wenn keiner gefunden wird, werden Start und Endknoten auf Existenz geprüft. -}
path :: ALgraph -> Vertex -> Vertex -> Cost -> Bool
path graph von zu max
  | (length mypath) == 0      = False
  | otherwise                 = True
 where
  mypath = (findPath g von zu [] 0 max 0) True
  g = castGraph graph









myfilter :: (Edge -> Bool) -> [Edge] -> [Edge]
myfilter praedikat list
  | (length list) == 0   = []
  | praedikat cur        = [cur] ++ (myfilter praedikat rest)
  | otherwise            = myfilter praedikat rest
 where
  cur = head list
  rest = tail list