import time
import csv
from collections import defaultdict
from heapq import *
import copy
from multiprocessing import Process
from multiprocessing import Queue


def dijkstra(gg, starting_point, destinations, results):
    start = time.time()
    orig_destinations = copy.deepcopy(destinations)
    solution_list = list()
    solution_order = list()
    q, seen = [(0, starting_point, ())], set()
    while q:
        (cost, v1, path) = heappop(q)
        if v1 not in seen:
            seen.add(v1)
            path = (v1, path)
            if orig_destinations:
                if v1 in orig_destinations:
                    index = [i for i, e in enumerate(orig_destinations) if e == v1]
                    # index = orig_destinations.index(v1)
                    # solution_list.insert(index, (cost, path))
                    for ind in index:
                        solution_list.insert(ind, cost)
                        solution_order.insert(ind, v1)
                    # indux = sorted(index, reverse=True)
                    for ind in sorted(index, reverse=True):
                        orig_destinations.pop(ind)
            else:
                dummy = list()
                for i in destinations:
                    dummy.append(solution_list[solution_order.index(i)])
                # return solution_list, solution_order, dummy
                results.put([starting_point, destinations, dummy])
                print("Starting node:", starting_point, "ended in", time.time() - start, "seconds")
                return dummy

            for c, v2 in gg.get(v1, ()):
                if v2 not in seen:
                    heappush(q, (cost + c, v2, path))

    print("Starting node:", starting_point, "ended in", time.time() - start, "seconds")
    results.append([starting_point, destinations, float("inf")])
    return float("inf")


if __name__ == "__main__":
    print('Initializing...\n')
    results = Queue()
    NewYork_Edgelist = open("./NewYork_Edgelist.csv")

    reader = csv.reader(NewYork_Edgelist)

    next(reader, None)
    edges = list()
    for row in reader:
        edges.append(tuple((row[2], row[3], float(row[5]))))

    g = defaultdict(list)
    for l, r, c in edges:
        g[l].append((c, r))

    fromNode1 = '63897'
    toNode1 = ['530502', '865238', '1069005', '951981', '61481',
               '658516', '164716', '986147', '1148038', '1164216']
    fromNode2 = '730938'
    toNode2 = ['1098876', '514944', '1114686', '992999',
               '129039', '9993', '388307', '72051', '983766', '343466']
    fromNode3 = '989066'
    toNode3 = ['973564', '567699', '1013916', '251091', '181836',
               '1071879', '255966', '1053966', '553308', '799614']
    fromNode4 = '989055'
    toNode4 = ['971422', '573017', '1014169', '252555', '183338',
               '1071108', '256025', '1053896', '553490', '798696']
    fromNode5 = '1146036'
    toNode5 = ['753174', '1009285', '1007970', '946205', '1065244',
               '221882', '1002032', '747905', '44123', '137377']
    fromNode6 = '1146390'
    toNode6 = ['752513', '1007678', '1007806', '948255', '1064975',
               '222897', '1003072', '747508', '44122', '137055']
    fromNode7 = '356589'
    toNode7 = ['902114', '943364', '858599', '1221848', '1114953',
               '757203', '1117318', '814839', '799302', '753403']
    fromNode8 = '357784'
    toNode8 = ['901758', '943378', '861354', '1221768', '1115282',
               '757439', '1118651', '813347', '799198', '753163']

    print('Starting...\n')
    print('Dijkstra sequential')
    starting_time = time.time()
    dijkstra(g, fromNode1, toNode1, results)
    dijkstra(g, fromNode2, toNode2, results)
    dijkstra(g, fromNode3, toNode3, results)
    dijkstra(g, fromNode4, toNode4, results)
    dijkstra(g, fromNode5, toNode5, results)
    dijkstra(g, fromNode6, toNode6, results)
    dijkstra(g, fromNode7, toNode7, results)
    dijkstra(g, fromNode8, toNode8, results)

    for i in range(1, 9):
        result = results.get()
        print("Starting node:", result[0], "Result:", result[2])

    print('\n-------------------------------\n'
          'Total time: ', time.time() - starting_time,
          '\n-------------------------------')



    print('\n===============================\n===============================\n')



    print('Dijkstra multiprocess')
    starting_time = time.time()
    threads = list()

    threads.append(
        Process(target=dijkstra, args=(g, fromNode1, toNode1, results)))
    threads.append(
        Process(target=dijkstra, args=(g, fromNode2, toNode2, results)))
    threads.append(
        Process(target=dijkstra, args=(g, fromNode3, toNode3, results)))
    threads.append(
        Process(target=dijkstra, args=(g, fromNode4, toNode4, results)))
    threads.append(
        Process(target=dijkstra, args=(g, fromNode5, toNode5, results)))
    threads.append(
        Process(target=dijkstra, args=(g, fromNode6, toNode6, results)))
    threads.append(
        Process(target=dijkstra, args=(g, fromNode7, toNode7, results)))
    threads.append(
        Process(target=dijkstra, args=(g, fromNode8, toNode8, results)))

    for x in threads:
        x.start()

    for x in threads:
        x.join()

    for r in threads:
        result = results.get()
        print("Starting node:", result[0], "Result:", result[2])

    print('\n-------------------------------\n'
          'Total time: ', time.time() - starting_time,
          '\n-------------------------------')