<gh_stars>0
from queue import PriorityQueue

from pathfinder.constants import GRID_X, GRID_Y
from pathfinder.utils import cache
from .adjacent_nodes import adjacent_nodes


@cache
def dijkstra(start, end, wall, grid_size, weight_li):
    """
    The famous Dijkstra's Algorithm invented by <NAME> and
    implemented with a priority queue.
    Non-weighted nodes have a default weight of 1 and diagonal nodes
    have a weight of square root of 2 when diagonals are enabled.
    """
    grid = {(x, y): float("inf") for y in range(GRID_Y) for x in range(GRID_X) if (x, y) not in wall}
    prev = {start: None}
    queue = PriorityQueue()

    queue.put((0, start))
    grid[start] = 0
    visited = []
    while not queue.empty():
        curr_dist, curr = queue.get()

        if curr is None or curr == end:
            break

        adj_nodes = adjacent_nodes(curr, wall, grid_size)

        for adj in adj_nodes:
            pot_dist = curr_dist + weight_li[adj]
            pot_dist += adj_nodes[adj]  # diagonal weight
            if pot_dist < grid[adj]:
                grid[adj] = pot_dist
                prev[adj] = curr
            if adj not in visited:
                visited.append(adj)
                queue.put((pot_dist, adj))

    return grid, prev, visited


if __name__ == "__main__":
    print(dijkstra((0, 0), (6, 6), [], (10 - 1, 10 - 1), {(i, j): 1 for j in range(10) for i in range(10)}))
