from __future__ import annotations

import heapq
from typing import Dict, List, Tuple

from .data_loader import load_edges


def _build_graph() -> Dict[str, List[Tuple[str, int]]]:
    graph: Dict[str, List[Tuple[str, int]]] = {}
    for edge in load_edges():
        a = edge["from"]
        b = edge["to"]
        d = int(edge["distance_m"])
        graph.setdefault(a, []).append((b, d))
        graph.setdefault(b, []).append((a, d))
    return graph


GRAPH_CACHE: Dict[str, List[Tuple[str, int]]] | None = None


def get_graph() -> Dict[str, List[Tuple[str, int]]]:
    global GRAPH_CACHE
    if GRAPH_CACHE is None:
        GRAPH_CACHE = _build_graph()
    return GRAPH_CACHE


def shortest_path_distance(start: str, goal: str) -> int:
    if start == goal:
        return 0
    graph = get_graph()
    dist: Dict[str, int] = {start: 0}
    pq: List[Tuple[int, str]] = [(0, start)]

    while pq:
        cur_dist, node = heapq.heappop(pq)
        if node == goal:
            return cur_dist
        if cur_dist > dist.get(node, float("inf")):
            continue
        for neighbor, weight in graph.get(node, []):
            nd = cur_dist + weight
            if nd < dist.get(neighbor, float("inf")):
                dist[neighbor] = nd
                heapq.heappush(pq, (nd, neighbor))
    return 0


def order_by_nearest_neighbor(
    attraction_ids: List[str],
    node_lookup: Dict[str, str],
    start_node: str = "HUB",
) -> List[str]:
    """Order attractions by geography: nearest-neighbor from start_node to minimize walking."""
    current = start_node
    to_visit = [a for a in attraction_ids if node_lookup.get(a)]
    ordered: List[str] = []
    while to_visit:
        best_id: str | None = None
        best_dist = float("inf")
        for aid in to_visit:
            node = node_lookup[aid]
            d = shortest_path_distance(current, node)
            if d < best_dist:
                best_dist = d
                best_id = aid
        if best_id is None:
            break
        ordered.append(best_id)
        to_visit.remove(best_id)
        current = node_lookup[best_id]
    return ordered


def greedy_schedule(
    attractions_order: List[str],
    start_time_minutes: int,
    walking_weight: float,
    wait_time_lookup: Dict[str, int],
    node_lookup: Dict[str, str],
) -> Tuple[List[Dict], int, int]:
    from .data_loader import walking_distance_between, load_attractions

    attractions = load_attractions()
    current_node = "HUB"
    current_time = start_time_minutes
    total_wait = 0
    total_walk = 0
    stops: List[Dict] = []

    for attr_id in attractions_order:
        attr = attractions[attr_id]
        target_node = node_lookup[attr_id]
        walk = walking_distance_between(current_node, target_node)
        wait = wait_time_lookup.get(attr_id, 10)
        total_walk += walk
        total_wait += wait

        start_time_str = f"{current_time // 60:02d}:{current_time % 60:02d}"
        current_time += walk // 80
        current_time += wait
        end_time_str = f"{current_time // 60:02d}:{current_time % 60:02d}"

        stops.append(
            {
                "attraction_id": attr.id,
                "attraction_name": attr.name,
                "node_id": attr.node_id,
                "start_time": start_time_str,
                "end_time": end_time_str,
                "estimated_wait_minutes": wait,
                "walking_distance_m": walk,
            }
        )
        current_node = target_node

    return stops, total_wait, total_walk