from typing import TypeVar, Any, List, Tuple, Dict, Set
from itertools import product
from pprint import pprint

# do we have numpy here?
import numpy as np

from .sets_representation import SolFiniteSetRepresentation
from .posets_product import MyFinitePosetProduct
from .posets_sum import MyFinitePosetDisjointUnion

import act4e_interfaces as I


X = TypeVar("X")

class MyFinitePoset(I.FinitePoset[X]):
    _carrier: I.FiniteSet[X]
    _values: List[Tuple[X,X]] 

    # Implementation using adjacency and reachability matrix
    _adjacency: np.ndarray
    _paths: np.ndarray

    def __init__(self, carrier: I.FiniteSet[X], values: List[Tuple[X,X]]):
        self._carrier = carrier
        self._values = values
        self._paths = np.eye(carrier.size(), dtype=bool)

        if self._values:
            self._compute_paths_naive()
            # self._compute_paths_fast()

    def _compute_paths_naive(self):
        # Create adjancency matrix. Because poset can be represented as a hasse
        # diagram, which is the same as a directed graph we can create an
        # adjacency matrix for the graph of the relation. In particular when
        # the graph is acyclic the adjancency matrix is nilpotent. Even if the
        # graph contains cycles we can still  precompute a reachability matrix
        # and check in O(1) whether there is a relation between two elements

        n = self._carrier.size()
        # We use booleans to avoid overflow, we do not care how long the path
        # is, only whether it exists or not
        self._adjacency = np.zeros((n, n), dtype=bool)

        # Build adjacency matrix
        for a, b in self._values:
            ia = self._carrier.elements().index(a)
            ib = self._carrier.elements().index(b)
            self._adjacency[ia][ib] = True

        # Compute the reachability matrix, i.e. a power series of the adjacency
        # matrix if the adjacency matrix is nilpotent the power series is
        # finite, otherwise it is not, but this is not a problem since we can
        # upper bound the number of terms needed in this case with the number
        # of nodes
        self._paths = np.eye(n, dtype=bool)
        adjpow = np.eye(n, dtype=bool)
        for _ in range(n):
            # compute the p-th power of the adjacency matrix and add it to the
            # series.
            adjpow = (adjpow @ self._adjacency > 0)
            self._paths = np.logical_or(self._paths, adjpow)

            # if the graph is acylic we stop earlier
            if np.allclose(adjpow, 0):
                break

        # if not np.allclose(adjpow, 0):
        #     print(f"Adjacency matrix may not be nilpotent! Ran for {_} "
        #           + "iterations and there are nonzero entries, "
        #           + f"the graph ({n} nodes) may contain cycles")

        # print(f"Computed path matrix for poset with elements {self._carrier.elements()}:")
        # print(self._paths.astype(int))

    def carrier(self) -> I.FiniteSet[X]:
        return self._carrier

    def holds(self, a: X, b: X) -> bool:
        # a is smaller than b, means that there is a path in the graph from a to b
        if self._has_path(a, b):
            return True

        return False

    def _cmp(self, a: X, b: X) -> bool:
        assert self._carrier.contains(a)
        assert self._carrier.contains(b)

        # a is both smaller and bigger than b
        # i.e. they are equivalent
        if self._has_path(a, b) and self._has_path(b, a):
            return 0

        # a is smaller than b
        if self._has_path(a, b):
            return 1
        
        # b is smaller than a, or
        # a is bigger than b
        if self._has_path(b, a):
            return -1

        # else not comparable
        raise RuntimeError(f"Cannot compare {a} with {b}.")


    def _has_path(self, a: X, b: X) -> bool:
        ia = self._carrier.elements().index(a)
        ib = self._carrier.elements().index(b)

        # if self._paths[ia][ib] > 0:
        #     print(f"The path from {a = } to {b = } has length {self._paths[ia][ib]}")

        return self._paths[ia][ib] > 0


class SolFinitePosetRepresentation(I.FinitePosetRepresentation):
    def load(self, h: I.IOHelper, s: I.FinitePoset_desc) -> I.FinitePoset[Any]:
        if "poset_product" in s.keys():
            posets = [self.load(h, p) for p in s["poset_product"]]
            return MyFinitePosetProduct(posets)

        if "poset_sum" in s.keys():
            posets = [self.load(h, p) for p in s["poset_sum"]]
            return MyFinitePosetDisjointUnion(posets)

        if not all(k in s.keys() for k in ["carrier", "hasse"]):
            raise I.InvalidFormat()
        
        fsr = SolFiniteSetRepresentation()
        X = fsr.load(h, s["carrier"])

        return MyFinitePoset(X, s["hasse"])

    def save(self, h: I.IOHelper, p: I.FinitePoset[Any]) -> I.FinitePoset_desc:
        fsr = SolFiniteSetRepresentation()
        d = {"carrier": fsr.save(h, p.carrier()),
             "hasse": []}

        for a in p.carrier().elements():
            for b in p.carrier().elements():
                if p.holds(a, b):
                    d["hasse"].append([a, b])

        return d