import sys

# insert at 1, 0 is the script path (or '' in REPL)
sys.path.insert(1, '../utils')

import temporal_distances as td
import temporal_graph as tg
import backward_BFS as Bbfs
from utils import util

from random import randint


def two_sweep_fw_fpsp(graph, fp_sp_distance, r=None):
    """
    :param graph: graph
    :param fp_sp_distance: Object distance fastest or shortest path
    :param r: starting node
    Return
    r: Starting node
    i1: Starting node of longest path
    i2: Arrival node of longest path
    d: distance of farther node find (our diameter estimate)
    """
    if graph.get_latest_node() is not None:
        num_nodes = graph.get_latest_node()
    else:
        num_nodes = graph.get_num_nodes()

    if r is None:
        r = randint(0, num_nodes - 1)

    # Create opposite graph to compute backward fastest paths distances
    g_path_op = fp_sp_distance.gen_opposite(folder=graph.get_file_path().rsplit('/', 1)[0] + '/',
                                            file=graph.get_file_path().rsplit('/', 1)[1])
    g_op = tg.Graph(file_path=g_path_op, is_directed=graph.get_is_directed(), latest_node=graph.get_latest_node())

    fp_sp_distance.compute_distances(graph=graph, start_node=r)

    i1 = fp_sp_distance.get_idx_farther()

    fp_sp_distance.compute_distances(graph=g_op, start_node=i1)

    d = fp_sp_distance.get_eccentricity()
    i2 = fp_sp_distance.get_idx_farther()

    return r, i2, i1, d


def two_sweep_bw_fpsp(graph, fp_sp_distance, r=None):
    """
    :param graph: graph
    :param fp_sp_distance: Object distance fastest or shortest path
    :param r: starting node
    Return
    r: Start node
    i1: Starting node of longest path
    i2: Arrival node of longest path
    d: distance of farther node find (our diameter estimate)
    """

    if graph.get_latest_node() is not None:
        num_nodes = graph.get_latest_node()
    else:
        num_nodes = graph.get_num_nodes()

    if r is None:
        r = randint(0, num_nodes - 1)

    # Create opposite graph to compute backward fastest paths distances
    g_path_op = fp_sp_distance.gen_opposite(folder=graph.get_file_path().rsplit('/', 1)[0] + '/',
                                            file=graph.get_file_path().rsplit('/', 1)[1])
    g_op = tg.Graph(file_path=g_path_op, is_directed=graph.get_is_directed(), latest_node=graph.get_latest_node())

    fp_sp_distance.compute_distances(graph=g_op, start_node=r)

    i1 = fp_sp_distance.get_idx_farther()

    fp_sp_distance.compute_distances(graph=graph, start_node=i1)

    d = fp_sp_distance.get_eccentricity()
    i2 = fp_sp_distance.get_idx_farther()

    return r, i1, i2, d


def two_sweep_2_fpsp(graph, fp_sp_distance, r=None):
    """
    :param graph: graph
    :param fp_sp_distance: Object distance fastest or shortest path
    :param r: starting node
    Return
    s: Starting node of longest path
    i: Arrival node of longest path
    d: distance of farther node find (our diameter estimate)
    """

    r, i1, i2, d1 = two_sweep_fw_fpsp(graph, fp_sp_distance, r)
    _, s, i, d = two_sweep_bw_fpsp(graph, fp_sp_distance, r)

    if d1 > d:
        s = i1
        i = i2
        d = d1
    return s, i, d


def two_sweep_forward_eat(graph, r=None):
    """
    Return
    r: Start node
    i1: Starting node of longest path
    i2: Arrival node of longest path
    d: distance of farther node find (our diameter estimate)
    """

    if graph.get_latest_node() is not None:
        num_nodes = graph.get_latest_node()
    else:
        num_nodes = graph.get_num_nodes()

    if r is None:
        r = randint(0, num_nodes - 1)
    #    print('Random start node: ' + str(r))

    # Create reverse graph to compute backward EAT distances
    g_path_rev = util.reverse_ef(folder=graph.get_file_path().rsplit('/', 1)[0] + '/',
                                 file=graph.get_file_path().rsplit('/', 1)[1])
    g_rev = tg.Graph(file_path=g_path_rev, is_directed=graph.get_is_directed(), latest_node=graph.get_latest_node())

    eat_dist = td.EarliestArrivalPath()
    eat_dist.compute_distances(graph=graph, start_node=r)

    i1 = eat_dist.get_idx_farther()

    back_bfs = Bbfs.TemporalBackwardBFS(graph=g_rev, start_node=i1)
    back_bfs.bfs()

    d = back_bfs.get_eccentricity_eat()
    i2 = back_bfs.get_idx_farther_eat()

    return r, i2, i1, d


def two_sweep_backward_eat(graph, r=None):
    """
    Return
    r: Start node
    i1: Starting node of longest path
    i2: Arrival node of longest path
    d: distance of farther node find (our diameter estimate)
    """
    if graph.get_latest_node() is not None:
        num_nodes = graph.get_latest_node()
    else:
        num_nodes = graph.get_num_nodes()

    if r is None:
        r = randint(0, num_nodes - 1)
    #    print('Random start node: ' + str(r))

    # Create reverse graph to compute backward EAT distances
    g_path_rev = util.reverse_ef(folder=graph.get_file_path().rsplit('/', 1)[0] + '/',
                                 file=graph.get_file_path().rsplit('/', 1)[1])
    g_rev = tg.Graph(file_path=g_path_rev, is_directed=graph.get_is_directed(), latest_node=graph.get_latest_node())

    back_bfs = Bbfs.TemporalBackwardBFS(graph=g_rev, start_node=r)
    back_bfs.bfs()

    i1 = back_bfs.get_idx_farther_eat()

    eat_dist = td.EarliestArrivalPath()
    eat_dist.compute_distances(graph, start_node=i1)

    d = eat_dist.get_eccentricity()
    i2 = eat_dist.get_idx_farther()

    return r, i1, i2, d


def two_sweep_2_eat(graph, r=None):
    """
    Return
    s: Starting node of longest path
    i: Arrival node of longest path
    d: distance of farther node find (our diameter estimate)
    """

    r, i1, i2, d1 = two_sweep_forward_eat(graph, r)
    _, s, i, d = two_sweep_backward_eat(graph, r)

    if d1 > d:
        s = i1
        i = i2
        d = d1
    return s, i, d


def two_sweep_forward_ldt(graph, r=None):
    """
    Return
    r: Start node
    i1: Starting node of longest path
    i2: Arrival node of longest path
    d: distance of farther node find (our diameter estimate)
    """

    if graph.get_latest_node() is not None:
        num_nodes = graph.get_latest_node()
    else:
        num_nodes = graph.get_num_nodes()

    if r is None:
        r = randint(0, num_nodes - 1)
    #    print('Random start node: ' + str(r))

    # Create opposite graph to compute forward LDT distances
    g_path_op = util.opposite_graph(folder=graph.get_file_path().rsplit('/', 1)[0] + '/',
                                    file=graph.get_file_path().rsplit('/', 1)[1])
    g_op = tg.Graph(file_path=g_path_op, is_directed=graph.get_is_directed(), latest_node=graph.get_latest_node())

    back_bfs = Bbfs.TemporalBackwardBFS(graph=g_op, start_node=r)
    back_bfs.bfs()
    i1 = back_bfs.get_idx_farther_eat()

    # Create reverse graph to compute backward LDT distances
    g_path_rev = util.reverse_ef(folder=graph.get_file_path().rsplit('/', 1)[0] + '/',
                                 file=graph.get_file_path().rsplit('/', 1)[1])
    g_rev = tg.Graph(file_path=g_path_rev, is_directed=graph.get_is_directed(), latest_node=graph.get_latest_node())

    ldt_dist = td.LatestDeparturePath()
    ldt_dist.compute_distances(graph=g_rev, start_node=i1)

    d = ldt_dist.get_eccentricity()
    i2 = ldt_dist.get_idx_farther()

    return r, i2, i1, d


def two_sweep_backward_ldt(graph, r=None):
    """
    Return
    r: Start node
    i1: Starting node of longest path
    i2: Arrival node of longest path
    d: distance of farther node find (our diameter estimate)
    """
    if graph.get_latest_node() is not None:
        num_nodes = graph.get_latest_node()
    else:
        num_nodes = graph.get_num_nodes()

    if r is None:
        r = randint(0, num_nodes - 1)
    #    print('Random start node: ' + str(r))

    # Create reverse graph to compute backward LDT distances
    g_path_rev = util.reverse_ef(folder=graph.get_file_path().rsplit('/', 1)[0] + '/',
                                 file=graph.get_file_path().rsplit('/', 1)[1])
    g_rev = tg.Graph(file_path=g_path_rev, is_directed=graph.get_is_directed(), latest_node=graph.get_latest_node())

    ldt_dist = td.LatestDeparturePath()
    ldt_dist.compute_distances(graph=g_rev, start_node=r)

    i1 = ldt_dist.get_idx_farther()

    # Create opposite graph to compute forward LDT distances
    g_path_op = util.opposite_graph(folder=graph.get_file_path().rsplit('/', 1)[0] + '/',
                                    file=graph.get_file_path().rsplit('/', 1)[1])
    g_op = tg.Graph(file_path=g_path_op, is_directed=graph.get_is_directed(), latest_node=graph.get_latest_node())

    back_bfs = Bbfs.TemporalBackwardBFS(graph=g_op, start_node=i1)
    back_bfs.bfs()

    i2 = back_bfs.get_idx_farther_eat()
    d = -(back_bfs.get_eccentricity_eat())

    return r, i1, i2, d


def two_sweep_2_ldt(graph, r=None):
    """
    Return
    s: Starting node of longest path
    i: Arrival node of longest path
    d: distance of farther node find (our diameter estimate)
    """

    r, i1, i2, d1 = two_sweep_forward_ldt(graph, r)
    _, s, i, d = two_sweep_backward_ldt(graph, r)

    if d1 < d:
        s = i1
        i = i2
        d = d1
    return s, i, d


if __name__ == '__main__':
    g = tg.Graph(file_path='/home/marco/Coding/PycharmProjects/Temporal_graphs_diameter/graphs/imdb2/NOTcomputed/'
                           'imdb_all-sorted.txt', is_directed=False)
    degree_node, starting_node = g.get_max_deg_out(n=80)
    print('Starting node: ' + str(starting_node[0]))
    print('Degree node: ' + str(degree_node[0]))
    sp_dist = td.ShortestPath()
    diam_estimation = -1
    a = None
    b = None
    for nod in starting_node:
        a, b, diam_estimation_temp = two_sweep_2_fpsp(graph=g, fp_sp_distance=sp_dist, r=nod)
        print('1 2SW Done...')
        if diam_estimation < diam_estimation_temp:
            diam_estimation = diam_estimation_temp

    print('From: ' + str(a))
    print('To: ' + str(b))
    print('Diameter estimation: ' + str(diam_estimation))