#!/usr/bin/env python3

from typing import List, Tuple, Dict, Optional, TextIO
import random
import sys
import re
import copy


class Graph:

    Adj: List[List[Tuple[float, int]]]

    def __init__(self, n: int, A: Optional[List[List[Tuple[float, int]]]]):
        """initialise un graphe à partir de ses listes d'adjacences `A`"""
        if A is None:
            self.Adj = [[] for _ in range(n)]
        else:
            if len(A) > n:
                print(len(A), n)
                raise ValueError("adjacency list too long!")
            self.Adj = copy.deepcopy(A) + [[] for _ in range(n - len(A))]

    def __len__(self) -> int:
        return len(self.Adj)

    def __getitem__(self, idx: int) -> List[Tuple[float, int]]:
        return self.Adj[idx]

    def randomize(self) -> None:
        for i in range(len(self.Adj)):
            random.shuffle(self.Adj[i])

    @classmethod
    def random_graph(cls, n: int, min_d: int, max_d: int,
                     min_w: float, max_w: float, symmetric: bool = False) -> "Graph":
        G: List[Dict[int, float]] = [{} for _ in range(n)]
        for s in range(n):
            d = random.randint(min_d, max_d)
            for _ in range(d):
                v = random.randrange(n)
                p = random.uniform(min_w, max_w)
                G[s][v] = p
                if symmetric:
                    G[v][s] = p
        return cls(v, [[(G[s][v], v) for v in G[s]] for s in range(n)])

    @property
    def N(self) -> int:
        return len(self.Adj)

    @classmethod
    def from_file(cls, filename: str) -> "Graph":
        """initialise un graphe à partir d'un fichier"""
        A: List[List[Tuple[float, int]]] = []
        if filename != "-":
            f: TextIO = open(filename, encoding="utf-8-sig")
        else:
            f = sys.stdin
        s = -1
        for L in f:
            if re.search(r"^\s*#", L):
                # comment
                continue

            s += 1
            A.append([])

            if L.strip() == "-":
                # no neighboors
                continue

            for e in L.split(';'):
                try:
                    p, v = e.split(',')
                    A[s].append((float(p), int(v)))
                except ValueError:
                    raise ValueError(f"invalid line: '{L}' (line {int(v)+1})")
        f.close()
        return cls(s+1, A)

    def to_file(self, filename: str,
                header: Optional[str] = None, precision: int = 3) -> None:
        if filename != "-" and filename.lower() != "stdout":
            f: TextIO = open(filename, mode="w", encoding="utf-8")
        else:
            f = sys.stdout

        if header:
            f.write("# "+header+"\n")
        for L in self.Adj:
            if not L:
                f.write("-\n")
                continue

            if L:
                sep = ""
                for p, v in L:
                    f.write(sep)
                    f.write("{p:.{precision:}g},{v:}"
                            .format(p=p, v=v, precision=precision))
                    sep = " ; "
            else:
                f.write("-")
            f.write("\n")
        if filename != "-" and filename.lower() != "stdout":
            f.close()

    def __str__(self) -> str:
        return super().__str__()


class Grid(Graph):
    width: int
    height: int
    grid: List[str]             # FIXME

    def __init__(self, width: int, height: int,
                 A: Optional[List[List[Tuple[float, int]]]] = None) -> None:
        self.width = width
        self.height = height
        self.grid = [" "*width for _ in range(height)]      # FIXME
        super().__init__(width*height, A)

    def idx(self, x: int, y: int) -> int:
        return x + self.width * y

    def xy(self, idx: int) -> Tuple[int, int]:
        return idx % self.width, idx // self.width

    @classmethod
    def from_file(cls, filename: str,
                  weight: Tuple[float, float, float, float] = (0, 1, 2, 3)) -> "Grid":
        f = open(filename, encoding="utf-8-sig")
        M = []
        width = None
        for L in f:
            L = L.strip()
            if L:
                M.append(L.strip().replace(' ', '.'))
                if width is not None and width != len(L):
                    raise ValueError(f"file '{filename}' contains lines of different lengths")
                width = len(L)
        return cls.from_matrix(M, weight=weight)

    @classmethod
    def random_grid(cls, width: int, height: int,
                    cells: str = ".<>v^#",
                    weight: Tuple[float, float, float, float] = (0, 1, 2, 3),
                    savefile: str = "-") -> "Grid":
        M = []
        for c in cells:
            if c not in ".<>v^#":
                raise ValueError(f"'{c}' is not a valid cell")
        for i in range(height):
            M.append("".join([random.choice(cells) for _ in range(width)]))

        if savefile != "-" and savefile.lower() != "stdout":
            f: TextIO = open(savefile, mode="w", encoding="ASCII")
        else:
            f = sys.stdout
        for L in M:
            f.write(L)
            f.write("\n")
        if savefile != "-" and savefile.lower() != "stdout":
            f.close()
        return cls.from_matrix(M, weight=weight)

    @classmethod
    def from_matrix(cls, M: List[str],
                    weight: Tuple[float, float, float, float] = (0, 1, 2, 3)) -> "Grid":
        """initialise un graphe à partir d'une grille"""

        height = len(M)
        width = len(M[0])
        G = cls(width, height)
        for x in range(width):
            for y in range(height):
                s = G.idx(x, y)
                if x > 0:
                    v = G.idx(x-1, y)
                    if M[y][x] == '#':
                        pass    # no edge
                    elif M[y][x] == '<':
                        G[s].append((weight[0], v))
                    elif M[y][x] == '>':
                        G[s].append((weight[3], v))
                    elif M[y][x] == '.':
                        G[s].append((weight[1], v))
                    else:
                        G[s].append((weight[2], v))
                if x < width-1:
                    v = G.idx(x+1, y)
                    if M[y][x] == '#':
                        pass    # no edge
                    elif M[y][x] == '>':
                        G[s].append((weight[0], v))
                    elif M[y][x] == '<':
                        G[s].append((weight[3], v))
                    elif M[y][x] == '.':
                        G[s].append((weight[1], v))
                    else:
                        G[s].append((weight[2], v))
                if y > 0:
                    v = G.idx(x, y-1)
                    if M[y][x] == '#':
                        pass    # no edge
                    elif M[y][x] == '^':
                        G[s].append((weight[0], v))
                    elif M[y][x] == 'v':
                        G[s].append((weight[3], v))
                    elif M[y][x] == '.':
                        G[s].append((weight[1], v))
                    else:
                        G[s].append((weight[2], v))
                if y < height-1:
                    v = G.idx(x, y+1)
                    if M[y][x] == '#':
                        pass    # no edge
                    elif M[y][x] == 'v':
                        G[s].append((weight[0], v))
                    elif M[y][x] == '^':
                        G[s].append((weight[3], v))
                    elif M[y][x] == '.':
                        G[s].append((weight[1], v))
                    else:
                        G[s].append((weight[2], v))
        grid = Grid(width, height, G.Adj)
        grid.grid = M
        return grid