#!/usr/bin/env python3

# TP2 info601
# NOM : Alonzo Church
# groupe L3-info-00101101

from typing import List, Optional, Tuple, Any
import sys
from collections import deque
from heapq import heapify, heappush, heappop
import traceback

from graph import Graph, Grid


oo = float("inf")
USE_UTF8 = True


def main_test(*args: str) -> None:
    """fonction de test appelée depuis la ligne de commande avec l'option -T / --test
    `args[0]`, `args[1]`, etc. contiennent les chaines données sur la ligne de
    commande.
    Par exemple,
        $ python3 shortest_ALONZO.py -T pomme poire
    appellera cette fonction avec `args=["pomme", "poire"]`.
    """
    print("fonction main_test")
    G = Graph.from_file(args[0])
    print(f"le graphe contient {G.N} sommets")
    # P = [int(args[i]) for i in range(1, len(args))]
    # p = path_weight(G, P)
    # if p is None:
    #     print("la liste des sommets donnée ne forme PAS un chemin dans le graphe")
    # else:
    #     print(f"le chemin a un poids total de {p}")


def max_out(G: Graph) -> int:
    """cherche et renvoie le sommet de `G` où la somme de poids sortants est
    maximale"""
    ...
    return 0


def path_weight(G: Graph, P: List[int]) -> Optional[float]:
    """renvoie la somme des poids des arêtes du chemin donné par `P`
    Si les sommets de `P` ne forment pas un chemin, renvoie None"""
    ...
    return 0


def BFS(G: Graph, v0: int, v1: int) -> Tuple[List[Optional[int]], List[float]]:
    """Fait un parcours en largeur ("breadth first search") standard sur le
    graphe `G` en partant du sommet `v0`.
    Le parcours est stoppé dès que le sommet `v1` est rencontré.
    Les poids des arêtes sont utilisés uniquement pour calculer la distance de
    `v0` aux sommets parcourus.
    La fonction renvoie un tableau `Pred` contenant l'arbre couvrant construit
    lors du parcours, ainsi que le tableau `D` contenant les distances depuis
    `v0`."""

    Pred: List[Optional[int]] = [None] * G.N
    D = [oo] * G.N
    D[v0] = 0
    ...
    return Pred, D


def extract_best(ATraiter: List[int], D: List[float]) -> int:
    """Recherche et extrait le sommet dans `ATraiter` avec une valeur de `D`
    minimale.
    Le sommet est supprimé de `ATraiter` et renvoyé."""
    ...
    return 0


def shortest_path0(G: Graph, v0: int, v1: int) -> Tuple[List[Optional[int]], List[float]]:
    """Fait une recherche du plus court chemin dans le graphe pondéré en
    utilisant une version naïve de l'algorithme de Dijkstra. À chaque étape le
    sommet choisi est celui qui minimise la distance depuis `v0`. La recherche
    de ce sommet est faite avec la fonction `extract_best`.
    La fonction renvoie un tableau `Pred` contenant l'arbre couvrant construit
    lors du parcours, ainsi que le tableau `D` contenant les distances depuis
    `v0`."""

    Pred: List[Optional[int]] = [None] * G.N
    D = [oo] * G.N
    D[v0] = 0
    ...
    return Pred, D


def shortest_path_dijkstra(G: Graph, v0: int, v1: int) -> Tuple[List[Optional[int]], List[float]]:
    """Fait une recherche du plus court chemin dans le graphe pondéré en
    utilisant l'algorithme de Dijkstra. À chaque étape le
    sommet choisi est celui qui minimise la distance depuis `v0`. La recherche
    de ce sommet est faite en utilisant une file de priorité.
    La fonction renvoie un tableau `Pred` contenant l'arbre couvrant construit
    lors du parcours, ainsi que le tableau `D` contenant les distances depuis
    `v0`."""

    Pred: List[Optional[int]] = [None] * G.N
    D = [oo] * G.N
    D[v0] = 0
    ...
    return Pred, D


def best_first_search(G: Grid, v0: int, v1: int) -> Tuple[List[Optional[int]], List[float]]:
    """Recherche un chemin de v0 à v1 dans le grille G en utilisant
    l'algorithme "best first search".
    À chaque étape le sommet choisi est celui qui minimise la distance
    **estimé** vers `v1`. La recherche de ce sommet est faite en utilisant une
    file de priorité.
    La fonction renvoie un tableau `Pred` contenant l'arbre couvrant construit
    lors du parcours, ainsi que le tableau `D` contenant les distances
    **réelles** depuis `v0`."""

    D = [oo] * G.N
    D[v0] = 0
    Pred: List[Optional[int]] = [None] * G.N
    ...
    return Pred, D


def a_star(G: Grid, v0: int, v1: int) -> Tuple[List[Optional[int]], List[float]]:
    """Recherche un chemin optimal (?) de v0 à v1 dans le grille G en utilisant
    l'algorithme A*.
    À chaque étape le sommet choisi est celui qui minimise la somme des
    distances réelles depuis `v0` et **estimé** vers `v1`. La recherche de ce
    sommet est faite en utilisant une file de priorité.
    La fonction renvoie un tableau `Pred` contenant l'arbre couvrant construit
    lors du parcours, ainsi que le tableau `D` contenant les distances
    **réelles** depuis `v0`."""

    D = [oo] * G.N
    D[v0] = 0
    Pred: List[Optional[int]] = [None] * G.N
    ...
    return Pred, D


#########################################
# NE MODIFIEZ PAS LA SUITE DU PROGRAMME #
#########################################


def show_grid_path(G:Grid, Pred: List[Optional[int]], v0: int, v1: int,
                   utf8: bool = USE_UTF8) -> None:
    path = '█' if utf8 else '*'
    P = set()
    start = G.xy(v0)
    end = G.xy(v1)
    print('#' * (G.width+2))
    v: Optional[int] = v1
    while v is not None:
        P.add(G.xy(v))
        v = Pred[v]
    for j in range(G.height):
        print('#', end="")
        for i in range(G.width):
            if (i, j) == start:
                print('@', end="")
            elif (i, j) == end:
                print('$', end="")
            elif (i, j) in P:
                print(path, end="")
            elif Pred[G.idx(i, j)] is not None:
                print(G.grid[j][i], end="")
            else:
                print(' ', end="")
        print('#')
    print('#' * (G.width+2))


def error(*args: Any, **kwargs: Any) -> None:
    kwargs["file"] = sys.stderr
    print(*args, **kwargs)


ALGORITHMS = ["BFS", "shortest_path0", "shortest_path_dijkstra",
              "best_first_search", "a_star"]


def help(exe: str) -> None:
    print(f"""usage: {exe} [OPTIONS] ARGS
    where available options are
      -A ALGO /  --algorithm=ALGO   choose the search algorithms to use (default: BFS)
      --start=N                     choose the starting vertex (default: 0)
      --end=N                       choose the end vertex (default: N-1)
      -T  /  --test                 run the test function instead of the main function
      -h  /  --help                 this message
      --weights W1,W2,W3,W4         weights of arcs when graph is read from a grid (default: 1,2,3,4)
      --random-graph FILE           generate a random graph to FILE (or STDOUT)
      --random-grid FILE            generate a random grid to FILE (or STDOUT)

With --random-graph, a random graph with N vertices is generated by randomly drawing neighboors and
weights for each vertex. ARGS can be of the following forms
  N D W: for each vertex, D neighboors are generated, with weights between 1 and W
  N D Wmin Wmax: for each vertex, D neighboors are generated, with weights between Wmin and Wmax
  N Dmin Dmax Wmin Wmax: for each vertex, Dmin<=D<=Dmax neighboors are generated, with weights between Wmin and Wmax
Note that neighboors can be drawn several times, and by symmetry, more neighboors can be added at
any point. The degre of any vertex can thus be smaller than Dmin or bigger than Dmax.

    """)


def main(argv: List[str]) -> None:

    from getopt import gnu_getopt as getopt, GetoptError

    short_options = "ThA:"
    long_options = ["test", "help", "algorithm=", "start=", "end=",
                    "random-graph=", "random-grid=", "weights="]

    try:
        opts, args = getopt(argv[1:], short_options, long_options)
    except GetoptError as err:
        error(err)
        help(argv[0])
        sys.exit(2)

    v0s = None
    v1s = None
    algorithms = []
    weights = (1.0, 2.0, 3.0, 4.0)

    for o, a in opts:
        if o in ["--random-graph"]:
            try:
                if len(args) == 3:
                    n = int(args[0])
                    dmin = int(args[1])
                    dmax = dmin
                    wmin = 1.0
                    wmax = float(args[2])
                elif len(args) == 4:
                    n = int(args[0])
                    dmin = int(args[1])
                    dmax = dmin
                    wmin = float(args[2])
                    wmax = float(args[3])
                elif len(args) == 5:
                    n = int(args[0])
                    dmin = int(args[1])
                    dmax = int(args[2])
                    wmin = float(args[3])
                    wmax = float(args[4])
                else:
                    raise ValueError(f"expected 3, 4 or 5 arguments, got {len(args)}")
            except (IndexError, ValueError) as err:
                error(f"*** error:{err}")
                exit(3)
            G = Graph.random_graph(n, dmin, dmax, wmin, wmax, symmetric=True)
            G.to_file(a)
            return

        elif o in ["--random-grid"]:
            try:
                w = int(args[0])
                h = int(args[1])
                cells = args[2]
            except (IndexError, ValueError):
                error("*** expected 3 arguments WIDTH HEIGHT CELLS")
                exit(3)
            G = Grid.random_grid(w, h, cells=cells, savefile=a)
            return

        elif o in ["--weights"]:
            tmp = tuple(map(float, a.split(',')))
            assert len(tmp) == 4
            weights = tmp

        elif o in ["-T", "--test"]:
            return main_test(*args)
        elif o in ["-h", "--help"]:
            help(argv[0])
            sys.exit(0)
        elif o in ["-A", "--algorithm"]:
            algorithms.extend(a.split(","))
        elif o in ["--start"]:
            v0s = a
        elif o in ["--end"]:
            v1s = a

    if len(args) == 0:
        help(sys.argv[0])
        sys.exit(1)

    filename = args[0]
    try:
        G = Grid.from_file(filename, weights)
    except ValueError:
        G = Graph.from_file(filename)

    if v0s is None:
        v0 = 0
    else:
        try:
            v0 = int(v0s)
        except ValueError:
            assert isinstance(G, Grid)
            try:
                x, y = v0s.split(',')
                v0 = G.idx(int(x), int(y))
            except ValueError:
                error(f"invalid vertex '{v0s}'")
                sys.exit(2)

    if v1s is None:
        v1 = G.N-1
    else:
        try:
            v1 = int(v1s)
        except ValueError:
            assert isinstance(G, Grid)
            try:
                x, y = v1s.split(',')
                v1 = G.idx(int(x), int(y))
            except ValueError:
                error(f"invalid vertex '{v1s}'")
                sys.exit(2)

    if not algorithms:
        algorithms = ["BFS"]
    elif "all" in algorithms:
        algorithms = ALGORITHMS

    for algo in algorithms:
        if algo not in ALGORITHMS:
            error(f"unkwnown algorithm: '{algo}'")
            sys.exit(1)

        if len(algorithms) > 1:
            print(f"algorithm: {algo}")

        try:
            R = globals()[algo](G, v0, v1=v1)
            if len(R) != 2 or not isinstance(R[0], list) or not isinstance(R[1], list):
                error(f"*** Problème : le parcours {algo} doit renvoyer un tableau d'entiers 'Pred'"
                      " et un tableau de flottants 'D'")
                sys.exit(1)
            Pred, D = R
        except Exception:
            traceback.print_exc()
            continue

        if Pred[v1] is None:
            print(f"no path from {v0} to {v1}")
        else:
            print(f"found path of weight {D[v1]} from {v0} to {v1}")
            if isinstance(G, Grid) and G.width <= 100 and G.height <= 30:
                show_grid_path(G, Pred, v0, v1)

        if len(algorithms) > 1:
            print()


if __name__ == "__main__":
    main(sys.argv)