from __future__ import annotations

import math
from dataclasses import dataclass, field
from typing import Any, Callable, Protocol, TypeVar


MAX_LINES = 4


class PointLike(Protocol):
    uid: int
    x: float
    y: float
    row: int
    col: int


PointT = TypeVar("PointT", bound=PointLike)
TypeVarT = TypeVar("TypeVarT")


@dataclass(frozen=True)
class UnfoldingSpec:
    max_lines: int = MAX_LINES
    neighbor_mode: str = "grid-8"
    direction: str = "clockwise"


@dataclass(frozen=True)
class UnfoldingLineSummary:
    line_id: int
    led_count: int
    block_count: int


@dataclass
class UnfoldingDescription:
    max_lines: int = MAX_LINES
    line_order: str = "clockwise"
    block_order: str = "clockwise"
    led_index_scope: str = "line"
    block_size: int | None = None
    block_counts: list[UnfoldingLineSummary] = field(default_factory=list)

    @classmethod
    def from_payload(cls, payload: Any) -> "UnfoldingDescription":
        if not isinstance(payload, dict):
            return cls()

        max_lines = max(1, min(int(payload.get("max_lines", MAX_LINES)), MAX_LINES))
        block_size = payload.get("block_size")
        block_counts: list[UnfoldingLineSummary] = []
        for item in payload.get("block_counts", []):
            if isinstance(item, dict):
                block_counts.append(
                    UnfoldingLineSummary(
                        line_id=int(item.get("line_id", 0)),
                        led_count=int(item.get("led_count", 0)),
                        block_count=int(item.get("block_count", 0)),
                    )
                )

        return cls(
            max_lines=max_lines,
            line_order=str(payload.get("line_order", "clockwise")),
            block_order=str(payload.get("block_order", "clockwise")),
            led_index_scope=str(payload.get("led_index_scope", "line")),
            block_size=None if block_size is None else int(block_size),
            block_counts=block_counts,
        )

    def to_payload(self) -> dict[str, Any]:
        payload: dict[str, Any] = {
            "max_lines": max(1, min(self.max_lines, MAX_LINES)),
            "line_order": self.line_order,
            "block_order": self.block_order,
            "led_index_scope": self.led_index_scope,
            "block_counts": [
                {
                    "line_id": item.line_id,
                    "led_count": item.led_count,
                    "block_count": item.block_count,
                }
                for item in self.block_counts
            ],
        }
        if self.block_size is not None:
            payload["block_size"] = self.block_size
        return payload

    def expected_block_count(self, led_count: int) -> int:
        if led_count <= 0:
            return 0
        if self.block_size is None or self.block_size <= 0:
            return 1
        return math.ceil(led_count / self.block_size)


@dataclass(frozen=True)
class BlockDescriptor:
    id: int
    name: str
    led_count: int
    start_index: int
    end_index: int


@dataclass(frozen=True)
class LineDescriptor:
    id: int
    name: str
    block_count: int
    led_count: int
    blocks: list[BlockDescriptor] = field(default_factory=list)


@dataclass(frozen=True)
class UnfoldingSummary:
    spec: UnfoldingSpec
    lines: list[LineDescriptor]


def connected_groups(points: list[PointT]) -> list[list[PointT]]:
    remaining = set(point.uid for point in points)
    by_id = {point.uid: point for point in points}
    groups: list[list[PointT]] = []
    while remaining:
        start = remaining.pop()
        queue = [start]
        group = [by_id[start]]
        while queue:
            current = by_id[queue.pop()]
            for candidate_id in list(remaining):
                candidate = by_id[candidate_id]
                if are_neighbors(current, candidate):
                    remaining.remove(candidate_id)
                    queue.append(candidate_id)
                    group.append(candidate)
        groups.append(group)
    return sorted(groups, key=lambda group: min(point_sort_key(point) for point in group))


def order_points_clockwise(points: list[PointT]) -> list[PointT]:
    if len(points) <= 2:
        return sorted(points, key=point_sort_key)

    center_x = sum(point.x for point in points) / len(points)
    center_y = sum(point.y for point in points) / len(points)
    ordered = sorted(
        points,
        key=lambda point: (
            clockwise_angle(point, center_x, center_y),
            distance_to_center(point, center_x, center_y),
            point_sort_key(point),
        ),
    )
    ordered = ensure_clockwise(ordered)
    return rotate_to_stable_start(ordered)


def order_blocks_clockwise(block_point_ids: list[list[int]], points_by_id: dict[int, PointT]) -> list[list[int]]:
    non_empty = [block for block in block_point_ids if block]
    if len(non_empty) <= 1:
        return non_empty

    line_points = [points_by_id[point_id] for block in non_empty for point_id in block]
    center_x = sum(point.x for point in line_points) / len(line_points)
    center_y = sum(point.y for point in line_points) / len(line_points)

    def block_key(block: list[int]) -> tuple[float, float, int]:
        block_points = [points_by_id[point_id] for point_id in block]
        block_x = sum(point.x for point in block_points) / len(block_points)
        block_y = sum(point.y for point in block_points) / len(block_points)
        angle = (-math.atan2(block_y - center_y, block_x - center_x)) % math.tau
        radius = math.hypot(block_x - center_x, block_y - center_y)
        return angle, radius, min(block)

    return sorted(non_empty, key=block_key)


def clockwise_sort(items: list[TypeVarT], points_for_item: Callable[[TypeVarT], list[PointLike]]) -> list[TypeVarT]:
    if len(items) <= 1:
        return items[:]

    items_with_points = [(item, points_for_item(item), index) for index, item in enumerate(items)]
    non_empty = [(item, points, index) for item, points, index in items_with_points if points]
    empty = [(item, index) for item, points, index in items_with_points if not points]
    if len(non_empty) <= 1:
        return [item for item, _, _ in non_empty] + [item for item, _ in empty]

    all_points = [point for _, points, _ in non_empty for point in points]
    center_x = sum(point.x for point in all_points) / len(all_points)
    center_y = sum(point.y for point in all_points) / len(all_points)

    def item_key(item_data: tuple[TypeVarT, list[PointLike], int]) -> tuple[float, float, int]:
        _, points, index = item_data
        item_x = sum(point.x for point in points) / len(points)
        item_y = sum(point.y for point in points) / len(points)
        angle = (-math.atan2(item_y - center_y, item_x - center_x)) % math.tau
        radius = math.hypot(item_x - center_x, item_y - center_y)
        return angle, radius, index

    return [item for item, _, _ in sorted(non_empty, key=item_key)] + [item for item, _ in empty]


def are_neighbors(a: PointLike, b: PointLike) -> bool:
    return abs(a.row - b.row) <= 1 and abs(a.col - b.col) <= 1


def point_sort_key(point: PointLike) -> tuple[int, int, float, float, int]:
    return point.row, point.col, point.x, point.y, point.uid


def clockwise_angle(point: PointLike, center_x: float, center_y: float) -> float:
    return (-math.atan2(point.y - center_y, point.x - center_x)) % math.tau


def distance_to_center(point: PointLike, center_x: float, center_y: float) -> float:
    return math.hypot(point.x - center_x, point.y - center_y)


def signed_area(points: list[PointLike]) -> float:
    area = 0.0
    for index, point in enumerate(points):
        next_point = points[(index + 1) % len(points)]
        area += point.x * next_point.y - next_point.x * point.y
    return area / 2.0


def ensure_clockwise(points: list[PointT]) -> list[PointT]:
    if len(points) < 3 or signed_area(points) <= 0:
        return points
    return [points[0], *reversed(points[1:])]


def rotate_to_stable_start(points: list[PointT]) -> list[PointT]:
    start = min(range(len(points)), key=lambda index: point_sort_key(points[index]))
    return [*points[start:], *points[:start]]