import numpy as np

import backward_BFS as Bbfs
from utils import util


class ShortestPath:
    def __init__(self):
        self.__distances = []
        self.__eccentricity = None
        self.__idx_farther = None
        self.__reachables = 0
        self.__min_ecc = np.NINF  # minimum possible eccentricity
        self.__name = 'SP'  # Shortest Path
        self.__opposite_path = None

    def get_distances(self):
        return self.__distances

    def get_idx_farther(self):
        return self.__idx_farther

    def get_eccentricity(self):
        return self.__eccentricity

    def compare_eccentricity(self, ecc, idx):
        if self.__eccentricity > ecc:
            return self.__eccentricity, self.__idx_farther
        else:
            return ecc, idx

    def get_min_ecc(self):
        return self.__min_ecc

    def get_reachables(self):
        return self.__reachables

    def get_name(self):
        return self.__name

    def gen_opposite(self, folder, file):
        self.__opposite_path = util.opposite_graph_ascend_traversal(folder=folder, file=file)
        return self.__opposite_path

    def __compute_sp(self, u, v, t, traversal_time, start_node, list_of_sorted_lists):
        # print(list_of_sorted_lists)
        if u == start_node:
            if (0, t) not in list_of_sorted_lists[start_node]:
                list_of_sorted_lists[start_node].append((0, t))

        if list_of_sorted_lists[u]:  # check if list is not empty
            for i, elem in enumerate(list_of_sorted_lists[u]):
                if elem[1] <= t:
                    new_d = elem[0] + traversal_time
                    new_arrival_time = t + traversal_time
                    inserted_new = False  # True if new element is inserted
                    if not list_of_sorted_lists[v]:  # Check if list is empty
                        list_of_sorted_lists[v].append((new_d, new_arrival_time))
                        inserted_new = True
                    else:
                        same_arrival = False  # True if there is another elem. with same arrival time into the list
                        for j, e in enumerate(list_of_sorted_lists[v]):
                            if e[1] == new_arrival_time:
                                if e[0] > new_d:
                                    list_of_sorted_lists[v][j] = (new_d, new_arrival_time)
                                    inserted_new = True
                                same_arrival = True
                        if not same_arrival:

                            # check if new path is dominated
                            new_is_dominated = False
                            for pair in list_of_sorted_lists[v]:
                                if (pair[0] < new_d and pair[1] <= new_arrival_time) or (
                                        pair[0] == new_d and pair[1] < new_arrival_time):
                                    new_is_dominated = True
                            if not new_is_dominated:

                                list_of_sorted_lists[v].append((new_d, new_arrival_time))
                                inserted_new = True
                    if inserted_new:
                        # keep only not dominated paths
                        list_of_sorted_lists[v][:] = [e for e in list_of_sorted_lists[v] if not (
                                (e[0] > new_d and e[1] >= new_arrival_time) or (
                                                              e[0] == new_d and e[1] > new_arrival_time))]

                        # If the minimum duration changes, update it
                        if new_d < self.__distances[v]:
                            self.__distances[v] = new_d
                        # sort list
                        list_of_sorted_lists[v].sort(key=lambda tup: tup[0])
                    break
                else:
                    continue

    def compute_distances(self, graph, start_node, min_time=None, max_time=None):
        """
        :param graph: temporal graph
        :param start_node: node to start from
        :param min_time: lower bound time interval
        :param max_time: upper bound time interval
        :return: numpy array of duration of the fastest path from start_node to every nodes v in V within time interval
        """

        if graph.get_latest_node() is not None:
            raise Exception('Shortest path does not work with dummy nodes, give me in input weighted graph!')

        if min_time is None:
            min_time, _ = graph.get_time_interval()
        if max_time is None:
            _, max_time = graph.get_time_interval()

        list_of_sorted_lists = []
        for elem in range(graph.get_num_nodes()):
            list_of_sorted_lists.append([])

        self.__eccentricity = 0
        self.__idx_farther = start_node
        self.__distances = np.full((graph.get_num_nodes(),), np.inf)
        self.__distances[start_node] = 0

        for line in graph.graph_reader():
            if not line.strip():  # check if line is blank
                break
            li = line.split()
            u = int(li[0])
            v = int(li[1])
            t = int(li[2])

            if len(li) == 4:
                traversal_time = int(li[3])
            else:
                traversal_time = 1

            if t >= min_time and t + traversal_time <= max_time:
                self.__compute_sp(u=u, v=v, t=t, traversal_time=traversal_time, start_node=start_node,
                                  list_of_sorted_lists=list_of_sorted_lists)
                if not graph.get_is_directed():
                    self.__compute_sp(u=v, v=u, t=t, traversal_time=traversal_time, start_node=start_node,
                                      list_of_sorted_lists=list_of_sorted_lists)
            elif t >= max_time:
                break

        # To handle dummy nodes: discard them from the distances vector
        # if graph.get_latest_node() is not None:
        #    self.__distances = self.__distances[:graph.get_latest_node()]

        self.__idx_farther, self.__eccentricity, self.__reachables = util.get_max_ind(self.__distances, np.NINF)


class FastestPathOnePass:
    def __init__(self):
        self.__distances = []
        self.__eccentricity = None
        self.__idx_farther = None
        self.__min_ecc = np.NINF  # minimum possible eccentricity
        self.__reachables = 0
        self.__name = 'FP'  # Fastest Path
        self.__opposite_path = None

    def get_distances(self):
        return self.__distances

    def get_idx_farther(self):
        return self.__idx_farther

    def get_eccentricity(self):
        return self.__eccentricity

    def compare_eccentricity(self, ecc, idx):
        if self.__eccentricity > ecc:
            return self.__eccentricity, self.__idx_farther
        else:
            return ecc, idx

    def get_min_ecc(self):
        return self.__min_ecc

    def get_reachables(self):
        return self.__reachables

    def get_name(self):
        return self.__name

    def gen_opposite(self, folder, file):
        self.__opposite_path = util.opposite_graph_ascend(folder=folder, file=file)
        return self.__opposite_path

    def __compute_fp(self, u, v, t, start_node, list_of_queues):
        if u == start_node:
            if (t, t) not in list_of_queues[start_node]:
                list_of_queues[start_node].append((t, t))

        if list_of_queues[u]:  # check if list is not empty
            for i, elem in reversed(list(enumerate(list_of_queues[u]))):
                if elem[1] <= t:
                    list_of_queues[u] = list_of_queues[u][i:]
                    new_t = elem[0]
                    new_arrival_time = t + 1  # traversal_time = 1
                    if not list_of_queues[v]:  # Check if list is empty
                        list_of_queues[v].append((new_t, new_arrival_time))

                    # If the old path dominates the new (or they are equals), keep only the old
                    elif (list_of_queues[v][-1][0] >= new_t and
                          list_of_queues[v][-1][1] <= new_arrival_time):
                        break

                    # If new path dominates the old, keep only the new
                    elif (list_of_queues[v][-1][0] < new_t and
                          list_of_queues[v][-1][1] >= new_arrival_time) or (list_of_queues[v][-1][0] == new_t and
                                                                            list_of_queues[v][-1][
                                                                                1] > new_arrival_time):
                        list_of_queues[v][-1] = (new_t, new_arrival_time)

                    # Otherwise keep both (newest is added after the oldest)
                    else:
                        list_of_queues[v].append((new_t, new_arrival_time))

                    # If the minimum duration changes, update it
                    if list_of_queues[v][-1][1] - list_of_queues[v][-1][0] < self.__distances[v]:
                        self.__distances[v] = list_of_queues[v][-1][1] - list_of_queues[v][-1][0]

                    break
                else:
                    continue

    def compute_distances(self, graph, start_node, min_time=None, max_time=None):
        """
        :param graph: temporal graph
        :param start_node: node to start from
        :param min_time: lower bound time interval
        :param max_time: upper bound time interval
        :return: numpy array of duration of the fastest path from start_node to every nodes v in V within time interval
        """

        if min_time is None:
            min_time, _ = graph.get_time_interval()
        if max_time is None:
            _, max_time = graph.get_time_interval()

        list_of_queues = []
        for elem in range(graph.get_num_nodes()):
            list_of_queues.append([])

        self.__eccentricity = 0
        self.__idx_farther = start_node
        self.__distances = np.full((graph.get_num_nodes(),), np.inf)
        self.__distances[start_node] = 0

        for line in graph.graph_reader():
            if not line.strip():  # check if line is blank
                break
            li = line.split()
            u = int(li[0])
            v = int(li[1])
            t = int(li[2])

            if t >= min_time and t + 1 <= max_time:
                self.__compute_fp(u=u, v=v, t=t, start_node=start_node, list_of_queues=list_of_queues)
                if not graph.get_is_directed():
                    self.__compute_fp(u=v, v=u, t=t, start_node=start_node, list_of_queues=list_of_queues)
            elif t >= max_time:
                break

        # To handle dummy nodes: discard them from the distances vector
        if graph.get_latest_node() is not None:
            self.__distances = self.__distances[:graph.get_latest_node()]

        self.__idx_farther, self.__eccentricity, self.__reachables = util.get_max_ind(self.__distances, np.NINF)


class EarliestArrivalPath:
    def __init__(self):
        self.__distances = []
        self.__eccentricity = None
        self.__idx_farther = None
        self.__min_ecc = np.NINF  # minimum possible eccentricity
        self.__name = 'EAT'

    def get_distances(self):
        return self.__distances

    def get_eccentricity(self):
        return self.__eccentricity

    def get_idx_farther(self):
        return self.__idx_farther

    def compare_eccentricity(self, ecc, idx):
        if self.__eccentricity > ecc:
            return self.__eccentricity, self.__idx_farther
        else:
            return ecc, idx

    def get_min_ecc(self):
        return self.__min_ecc

    def get_name(self):
        return self.__name

    def compute_distances(self, graph, start_node, min_time=None, max_time=None):
        """
        :param graph: temporal graph in its edge stream representation
        :param start_node: node to start from
        :param min_time: lower bound time interval
        :param max_time: upper bound time interval
        :return: numpy array of the earliest arrival times from start_node to every nodes v in V within time interval
        """

        if min_time is None:
            min_time, _ = graph.get_time_interval()
        if max_time is None:
            _, max_time = graph.get_time_interval()

        self.__eccentricity = min_time
        self.__idx_farther = start_node

        self.__distances = np.full((graph.get_num_nodes(),), np.inf)
        self.__distances[start_node] = min_time

        traversal_time = 1
        for line in graph.graph_reader():
            if not line.strip():  # check if line is blank
                break
            li = line.split()
            u = int(li[0])
            v = int(li[1])
            t = int(li[2])
            if len(li) == 4:
                traversal_time = int(li[3])

            if (t + traversal_time) <= max_time:
                if t >= self.__distances[u]:
                    if (t + traversal_time) < self.__distances[v]:
                        self.__distances[v] = t + traversal_time
                        if self.__distances[v] > self.__eccentricity and \
                                (graph.get_latest_node() is None or v < graph.get_latest_node()):  # to handle dummy
                            self.__eccentricity = self.__distances[v]
                            self.__idx_farther = v

                elif not graph.get_is_directed() and t >= self.__distances[v]:  # If graph is undirected
                    if (t + traversal_time) < self.__distances[u]:
                        self.__distances[u] = t + traversal_time
                        if self.__distances[u] > self.__eccentricity and \
                                (graph.get_latest_node() is None or u < graph.get_latest_node()):  # to handle dummy
                            # nodes
                            self.__eccentricity = self.__distances[u]
                            self.__idx_farther = u
            elif t >= max_time:
                break
            else:
                continue
        # To handle dummy nodes: discard them from the distances vector
        if graph.get_latest_node() is not None:
            self.__distances = self.__distances[:graph.get_latest_node()]


class LatestDeparturePath:  # ( method compute_distances() compute backward LDT)
    def __init__(self):
        self.__distances = []
        self.__eccentricity = None
        self.__idx_farther = None
        self.__min_ecc = np.inf  # minimum possible eccentricity
        self.__name = 'LDT'

    def get_distances(self):
        return self.__distances

    def get_eccentricity(self):
        return self.__eccentricity

    def get_idx_farther(self):
        return self.__idx_farther

    def compare_eccentricity(self, ecc, idx):
        if self.__eccentricity < ecc:
            return self.__eccentricity, self.__idx_farther
        else:
            return ecc, idx

    def get_min_ecc(self):
        return self.__min_ecc

    def get_name(self):
        return self.__name

    def compute_distances(self, graph, start_node, min_time=None, max_time=None):
        """
        :param graph: temporal graph in REVERSE EDGE STREAM representation
        :param start_node: destination node
        :param min_time: lower bound time interval
        :param max_time: upper bound time interval
        :return: numpy array of the latest departure times from every vertex v in V to dest_node within time interval
        """

        if min_time is None:
            min_time, _ = graph.get_time_interval()
        if max_time is None:
            _, max_time = graph.get_time_interval()

        self.__eccentricity = max_time
        self.__idx_farther = start_node

        self.__distances = np.full((graph.get_num_nodes(),), np.NINF)
        self.__distances[start_node] = max_time

        traversal_time = 1
        for line in graph.graph_reader():
            if not line.strip():  # check if line is blank
                break
            li = line.split()

            u = int(li[0])
            v = int(li[1])
            t = int(li[2])
            if len(li) == 4:
                traversal_time = int(li[3])

            if t >= min_time:
                if t + traversal_time <= self.__distances[v]:
                    if t > self.__distances[u]:
                        self.__distances[u] = t
                        # I can compute eccentricity here (online) because the graph is in reverse edge stream
                        if self.__distances[u] < self.__eccentricity and \
                                (graph.get_latest_node() is None or u < graph.get_latest_node()):
                            self.__eccentricity = self.__distances[u]
                            self.__idx_farther = u

                elif not graph.get_is_directed() and t + traversal_time <= self.__distances[u]:
                    if t > self.__distances[v]:
                        self.__distances[v] = t
                        if self.__distances[v] < self.__eccentricity and \
                                (graph.get_latest_node() is None or v < graph.get_latest_node()):
                            self.__eccentricity = self.__distances[v]
                            self.__idx_farther = v
            else:
                break
        # To handle dummy nodes: discard them from the distances vector
        if graph.get_latest_node() is not None:
            self.__distances = self.__distances[:graph.get_latest_node()]
        # self.__idx_farther, self.__eccentricity = util.get_min_ind(self.__distances, np.inf)


def compute_diameter(graph, distance):
    """
    :param graph: temporal graph
    :param distance: Object distance: FastestPathOnePass, earliestArrivalPath etc...
    :return: diameter value
    """
    ecc = distance.get_min_ecc()
    idx = -1
    reachable_pairs = 0
    if graph.get_latest_node() is not None:
        num_nodes = graph.get_latest_node()
    else:
        num_nodes = graph.get_num_nodes()

    for node in range(num_nodes):
        distance.compute_distances(graph=graph, start_node=node)

        if distance.get_name() == 'FP' or distance.get_name() == 'SP':
            reachable_pairs += distance.get_reachables()

        ecc, idx = distance.compare_eccentricity(ecc, idx)
        # print(ecc)

        if (node + 1) % 1000 == 0:
            print('1000 visits done...', flush=True)

    if distance.get_name() == 'FP' or distance.get_name() == 'SP':
        print('Reachable Pairs ' + graph.get_file_path().rsplit('/', 1)[1] + ': ' + str(reachable_pairs), flush=True)
    return ecc


if __name__ == '__main__':
    import temporal_graph as tg

    sp_distance = ShortestPath()

    g = tg.Graph(file_path='./graphs/Weighted/kuopio-weighted-sorted.txt', is_directed=True)

    sp_dist = ShortestPath()

    diam = compute_diameter(graph=g, distance=sp_distance)
    print('diam:')
    print(diam)