from __future__ import annotations

import heapq
from abc import ABC, abstractmethod
from collections import deque
from dataclasses import dataclass
from itertools import count

from .models import Cell, Maze


@dataclass(frozen=True)
class PathResult:
    path: list[Cell]
    visited_count: int


class PathFindingStrategy(ABC):
    name = "abstract"

    @abstractmethod
    def find_path(self, maze: Maze, start: Cell, exit: Cell) -> PathResult:
        raise NotImplementedError

    def findPath(self, maze: Maze, start: Cell, exit: Cell) -> PathResult:
        return self.find_path(maze, start, exit)


class BFSStrategy(PathFindingStrategy):
    name = "BFS"

    def find_path(self, maze: Maze, start: Cell, exit: Cell) -> PathResult:
        queue: deque[Cell] = deque([start])
        parents: dict[Cell, Cell | None] = {start: None}
        visited = {start}

        while queue:
            current = queue.popleft()
            if current == exit:
                return PathResult(_reconstruct_path(parents, exit), len(visited))

            for neighbor in maze.get_neighbors(current):
                if neighbor not in visited:
                    visited.add(neighbor)
                    parents[neighbor] = current
                    queue.append(neighbor)

        return PathResult([], len(visited))


class DFSStrategy(PathFindingStrategy):
    name = "DFS"

    def find_path(self, maze: Maze, start: Cell, exit: Cell) -> PathResult:
        stack = [start]
        parents: dict[Cell, Cell | None] = {start: None}
        visited = {start}

        while stack:
            current = stack.pop()
            if current == exit:
                return PathResult(_reconstruct_path(parents, exit), len(visited))

            for neighbor in reversed(maze.get_neighbors(current)):
                if neighbor not in visited:
                    visited.add(neighbor)
                    parents[neighbor] = current
                    stack.append(neighbor)

        return PathResult([], len(visited))


class DijkstraStrategy(PathFindingStrategy):
    name = "Dijkstra"

    def find_path(self, maze: Maze, start: Cell, exit: Cell) -> PathResult:
        tie_breaker = count()
        heap: list[tuple[int, int, Cell]] = [(0, next(tie_breaker), start)]
        distances: dict[Cell, int] = {start: 0}
        parents: dict[Cell, Cell | None] = {start: None}
        visited: set[Cell] = set()

        while heap:
            current_distance, _, current = heapq.heappop(heap)
            if current in visited:
                continue
            visited.add(current)

            if current == exit:
                return PathResult(_reconstruct_path(parents, exit), len(visited))

            for neighbor in maze.get_neighbors(current):
                new_distance = current_distance + neighbor.weight
                if new_distance < distances.get(neighbor, 10**12):
                    distances[neighbor] = new_distance
                    parents[neighbor] = current
                    heapq.heappush(heap, (new_distance, next(tie_breaker), neighbor))

        return PathResult([], len(visited))


class AStarStrategy(PathFindingStrategy):
    name = "A*"

    def find_path(self, maze: Maze, start: Cell, exit: Cell) -> PathResult:
        tie_breaker = count()
        start_heuristic = _manhattan(start, exit)
        heap: list[tuple[int, int, int, Cell]] = [
            (start_heuristic, start_heuristic, next(tie_breaker), start)
        ]
        g_score: dict[Cell, int] = {start: 0}
        parents: dict[Cell, Cell | None] = {start: None}
        visited: set[Cell] = set()

        while heap:
            _, _, _, current = heapq.heappop(heap)
            if current in visited:
                continue
            visited.add(current)

            if current == exit:
                return PathResult(_reconstruct_path(parents, exit), len(visited))

            for neighbor in maze.get_neighbors(current):
                tentative_score = g_score[current] + neighbor.weight
                if tentative_score < g_score.get(neighbor, 10**12):
                    g_score[neighbor] = tentative_score
                    parents[neighbor] = current
                    heuristic = _manhattan(neighbor, exit)
                    priority = tentative_score + heuristic
                    heapq.heappush(
                        heap,
                        (priority, heuristic, next(tie_breaker), neighbor),
                    )

        return PathResult([], len(visited))


def _reconstruct_path(parents: dict[Cell, Cell | None], end: Cell) -> list[Cell]:
    path: list[Cell] = []
    current: Cell | None = end
    while current is not None:
        path.append(current)
        current = parents[current]
    path.reverse()
    return path


def _manhattan(first: Cell, second: Cell) -> int:
    return abs(first.x - second.x) + abs(first.y - second.y)
