from __future__ import annotations

from itertools import repeat
from typing import Generic, TYPE_CHECKING

from typing_extensions import Self

from rene import hints
from rene._utils import permute, to_arg_min, to_contour_orientation
from rene.enums import Location, Orientation

from .edge import Edge
from .leaf import Leaf
from .x_node import XNode
from .y_node import YNode

if TYPE_CHECKING:
    from collections.abc import Sequence

    from rene._hints import Orienteer

    from .node import Node
    from .trapezoid import Trapezoid


class Trapezoidation(Generic[hints.ScalarT]):
    @classmethod
    def from_multisegment(
        cls,
        multisegment: hints.Multisegment[hints.ScalarT],
        seed: int,
        orienteer: Orienteer[hints.ScalarT],
        /,
    ) -> Self:
        assert seed >= 0, f'Seed should be non-negative, but got {seed}.'
        endpoints: list[hints.Point[hints.ScalarT]] = []
        edges: list[Edge[hints.ScalarT]] = []
        for segment in multisegment.segments:
            start, end = segment.start, segment.end
            start_index = len(endpoints)
            endpoints.append(start)
            end_index = len(endpoints)
            endpoints.append(end)
            edges.append(
                Edge.from_endpoints(
                    start_index,
                    end_index,
                    interior_to_left=False,
                    orienteer=orienteer,
                )
                if start < end
                else Edge.from_endpoints(
                    end_index,
                    start_index,
                    interior_to_left=False,
                    orienteer=orienteer,
                )
            )
        permute(edges, seed)
        return cls._from_box(
            multisegment.bounding_box, edges, endpoints, orienteer
        )

    @classmethod
    def from_polygon(
        cls,
        polygon: hints.Polygon[hints.ScalarT],
        seed: int,
        orienteer: Orienteer[hints.ScalarT],
        /,
    ) -> Self:
        edges: list[Edge[hints.ScalarT]] = []
        endpoints: list[hints.Point[hints.ScalarT]] = []
        _populate_from_contour(
            polygon.border,
            Orientation.COUNTERCLOCKWISE,
            edges,
            endpoints,
            orienteer,
        )
        for hole in polygon.holes:
            _populate_from_contour(
                hole, Orientation.CLOCKWISE, edges, endpoints, orienteer
            )
        permute(edges, seed)
        return cls._from_box(polygon.bounding_box, edges, endpoints, orienteer)

    @property
    def height(self, /) -> int:
        return self._root.to_height(self._nodes)

    def locate(self, point: hints.Point[hints.ScalarT], /) -> Location:
        return self._root.locate(
            point, self._edges, self._endpoints, self._nodes
        )

    @classmethod
    def _from_box(
        cls,
        box: hints.Box[hints.ScalarT],
        edges: list[Edge[hints.ScalarT]],
        endpoints: list[hints.Point[hints.ScalarT]],
        orienteer: Orienteer[hints.ScalarT],
        /,
    ) -> Self:
        nodes: list[Node[hints.ScalarT]] = []
        edges_count = len(edges)
        _add_edge_to_single_trapezoid(
            0,
            _box_to_trapezoid(box, edges, endpoints, nodes, orienteer),
            edges,
            endpoints,
            nodes,
        )
        for edge_index in range(1, edges_count):
            _add_edge(edge_index, edges, endpoints, nodes)
        return cls(edges, endpoints, nodes)

    @property
    def _root(self, /) -> Node[hints.ScalarT]:
        return self._nodes[0]

    _edges: Sequence[Edge[hints.ScalarT]]
    _endpoints: Sequence[hints.Point[hints.ScalarT]]
    _nodes: Sequence[Node[hints.ScalarT]]

    __slots__ = '_edges', '_endpoints', '_nodes'

    def __new__(
        cls,
        edges: Sequence[Edge[hints.ScalarT]],
        endpoints: Sequence[hints.Point[hints.ScalarT]],
        nodes: Sequence[Node[hints.ScalarT]],
        /,
    ) -> Self:
        self = super().__new__(cls)
        self._edges, self._endpoints, self._nodes = edges, endpoints, nodes
        return self

    def __contains__(self, point: hints.Point[hints.ScalarT]) -> bool:
        return (
            self._root.locate(point, self._edges, self._endpoints, self._nodes)
            is not Location.EXTERIOR
        )


def _add_edge(
    edge_index: int,
    edges: Sequence[Edge[hints.ScalarT]],
    endpoints: Sequence[hints.Point[hints.ScalarT]],
    nodes: list[Node[hints.ScalarT]],
    /,
) -> None:
    trapezoids = _find_intersecting_trapezoids(
        edge_index, edges, endpoints, nodes
    )
    if len(trapezoids) == 1:
        _add_edge_to_single_trapezoid(
            edge_index, trapezoids[0], edges, endpoints, nodes
        )
    else:
        prev_above, prev_below = _add_edge_to_first_trapezoid(
            edge_index, trapezoids[0], edges, endpoints, nodes
        )
        for middle_trapezoid in trapezoids[1:-1]:
            prev_above, prev_below = _add_edge_to_middle_trapezoid(
                edge_index,
                middle_trapezoid,
                prev_above,
                prev_below,
                edges,
                nodes,
            )
        _add_edge_to_last_trapezoid(
            edge_index,
            trapezoids[-1],
            prev_above,
            prev_below,
            edges,
            endpoints,
            nodes,
        )


def _add_edge_to_first_trapezoid(
    edge_index: int,
    trapezoid: Trapezoid,
    edges: Sequence[Edge[hints.ScalarT]],
    endpoints: Sequence[hints.Point[hints.ScalarT]],
    nodes: list[Node[hints.ScalarT]],
    /,
) -> tuple[Trapezoid, Trapezoid]:
    edge = edges[edge_index]
    above, below = (
        _create_trapezoid(
            edge.left_point_index,
            trapezoid.right_point_index,
            edge_index,
            trapezoid.above_edge_index,
            edges,
            nodes,
        ),
        _create_trapezoid(
            edge.left_point_index,
            trapezoid.right_point_index,
            trapezoid.below_edge_index,
            edge_index,
            edges,
            nodes,
        ),
    )
    replacement_node_index = _create_y_node(
        edge_index, below.leaf_index, above.leaf_index, nodes
    )
    # set pairs of trapezoid neighbours
    if (
        endpoints[edge.left_point_index]
        == endpoints[trapezoid.left_point_index]
    ):
        _maybe_set_as_upper_left(above, trapezoid.upper_left_node_index, nodes)
        _maybe_set_as_lower_left(below, trapezoid.lower_left_node_index, nodes)
    else:
        left = _create_trapezoid(
            trapezoid.left_point_index,
            edge.left_point_index,
            trapezoid.below_edge_index,
            trapezoid.above_edge_index,
            edges,
            nodes,
        )
        _maybe_set_as_lower_left(left, trapezoid.lower_left_node_index, nodes)
        _maybe_set_as_upper_left(left, trapezoid.upper_left_node_index, nodes)
        left.set_as_lower_right(below)
        left.set_as_upper_right(above)
        replacement_node_index = _create_x_node(
            edge.left_point_index,
            left.leaf_index,
            replacement_node_index,
            nodes,
        )
    _maybe_set_as_upper_right(above, trapezoid.upper_right_node_index, nodes)
    _maybe_set_as_lower_right(below, trapezoid.lower_right_node_index, nodes)
    _replace_node(trapezoid.leaf_index, replacement_node_index, nodes)
    return above, below


def _add_edge_to_last_trapezoid(
    edge_index: int,
    trapezoid: Trapezoid,
    prev_above: Trapezoid,
    prev_below: Trapezoid,
    edges: Sequence[Edge[hints.ScalarT]],
    endpoints: Sequence[hints.Point[hints.ScalarT]],
    nodes: list[Node[hints.ScalarT]],
    /,
) -> None:
    edge = edges[edge_index]
    if prev_above.above_edge_index is trapezoid.above_edge_index:
        above = prev_above
        above.right_point_index = edge.right_point_index
    else:
        above = _create_trapezoid(
            trapezoid.left_point_index,
            edge.right_point_index,
            edge_index,
            trapezoid.above_edge_index,
            edges,
            nodes,
        )
        above.set_as_lower_left(prev_above)
        _maybe_set_as_upper_left(above, trapezoid.upper_left_node_index, nodes)
    if prev_below.below_edge_index is trapezoid.below_edge_index:
        below = prev_below
        below.right_point_index = edge.right_point_index
    else:
        below = _create_trapezoid(
            trapezoid.left_point_index,
            edge.right_point_index,
            trapezoid.below_edge_index,
            edge_index,
            edges,
            nodes,
        )
        below.set_as_upper_left(prev_below)
        _maybe_set_as_lower_left(below, trapezoid.lower_left_node_index, nodes)
    replacement_node_index = _create_y_node(
        edge_index, below.leaf_index, above.leaf_index, nodes
    )
    # set pairs of trapezoid neighbours
    if (
        endpoints[edge.right_point_index]
        == endpoints[trapezoid.right_point_index]
    ):
        _maybe_set_as_upper_right(
            above, trapezoid.upper_right_node_index, nodes
        )
        _maybe_set_as_lower_right(
            below, trapezoid.lower_right_node_index, nodes
        )
    else:
        right = _create_trapezoid(
            edge.right_point_index,
            trapezoid.right_point_index,
            trapezoid.below_edge_index,
            trapezoid.above_edge_index,
            edges,
            nodes,
        )
        _maybe_set_as_lower_right(
            right, trapezoid.lower_right_node_index, nodes
        )
        _maybe_set_as_upper_right(
            right, trapezoid.upper_right_node_index, nodes
        )
        right.set_as_lower_left(below)
        right.set_as_upper_left(above)
        replacement_node_index = _create_x_node(
            edge.right_point_index,
            replacement_node_index,
            right.leaf_index,
            nodes,
        )
    _replace_node(trapezoid.leaf_index, replacement_node_index, nodes)


def _add_edge_to_middle_trapezoid(
    edge_index: int,
    trapezoid: Trapezoid,
    prev_above: Trapezoid,
    prev_below: Trapezoid,
    edges: Sequence[Edge[hints.ScalarT]],
    nodes: list[Node[hints.ScalarT]],
    /,
) -> tuple[Trapezoid, Trapezoid]:
    if prev_above.above_edge_index == trapezoid.above_edge_index:
        above = prev_above
        above.right_point_index = trapezoid.right_point_index
    else:
        above = _create_trapezoid(
            trapezoid.left_point_index,
            trapezoid.right_point_index,
            edge_index,
            trapezoid.above_edge_index,
            edges,
            nodes,
        )
        above.set_as_lower_left(prev_above)
        _maybe_set_as_upper_left(above, trapezoid.upper_left_node_index, nodes)
    if prev_below.below_edge_index == trapezoid.below_edge_index:
        below = prev_below
        below.right_point_index = trapezoid.right_point_index
    else:
        below = _create_trapezoid(
            trapezoid.left_point_index,
            trapezoid.right_point_index,
            trapezoid.below_edge_index,
            edge_index,
            edges,
            nodes,
        )
        below.set_as_upper_left(prev_below)
        _maybe_set_as_lower_left(below, trapezoid.lower_left_node_index, nodes)
    _maybe_set_as_upper_right(above, trapezoid.upper_right_node_index, nodes)
    _maybe_set_as_lower_right(below, trapezoid.lower_right_node_index, nodes)
    replacement_node_index = _create_y_node(
        edge_index, below.leaf_index, above.leaf_index, nodes
    )
    _replace_node(trapezoid.leaf_index, replacement_node_index, nodes)
    return above, below


def _add_edge_to_single_trapezoid(
    edge_index: int,
    trapezoid: Trapezoid,
    edges: Sequence[Edge[hints.ScalarT]],
    endpoints: Sequence[hints.Point[hints.ScalarT]],
    nodes: list[Node[hints.ScalarT]],
    /,
) -> None:
    edge = edges[edge_index]
    above, below = (
        _create_trapezoid(
            edge.left_point_index,
            edge.right_point_index,
            edge_index,
            trapezoid.above_edge_index,
            edges,
            nodes,
        ),
        _create_trapezoid(
            edge.left_point_index,
            edge.right_point_index,
            trapezoid.below_edge_index,
            edge_index,
            edges,
            nodes,
        ),
    )
    replacement_node_index = _create_y_node(
        edge_index, below.leaf_index, above.leaf_index, nodes
    )
    if (
        endpoints[edge.right_point_index]
        == endpoints[trapezoid.right_point_index]
    ):
        _maybe_set_as_upper_right(
            above, trapezoid.upper_right_node_index, nodes
        )
        _maybe_set_as_lower_right(
            below, trapezoid.lower_right_node_index, nodes
        )
    else:
        right = _create_trapezoid(
            edge.right_point_index,
            trapezoid.right_point_index,
            trapezoid.below_edge_index,
            trapezoid.above_edge_index,
            edges,
            nodes,
        )
        _maybe_set_as_lower_right(
            right, trapezoid.lower_right_node_index, nodes
        )
        _maybe_set_as_upper_right(
            right, trapezoid.upper_right_node_index, nodes
        )
        right.set_as_lower_left(below)
        right.set_as_upper_left(above)
        replacement_node_index = _create_x_node(
            edge.right_point_index,
            replacement_node_index,
            right.leaf_index,
            nodes,
        )
    if (
        endpoints[edge.left_point_index]
        == endpoints[trapezoid.left_point_index]
    ):
        _maybe_set_as_upper_left(above, trapezoid.upper_left_node_index, nodes)
        _maybe_set_as_lower_left(below, trapezoid.lower_left_node_index, nodes)
    else:
        left = _create_trapezoid(
            trapezoid.left_point_index,
            edge.left_point_index,
            trapezoid.below_edge_index,
            trapezoid.above_edge_index,
            edges,
            nodes,
        )
        _maybe_set_as_lower_left(left, trapezoid.lower_left_node_index, nodes)
        _maybe_set_as_upper_left(left, trapezoid.upper_left_node_index, nodes)
        left.set_as_lower_right(below)
        left.set_as_upper_right(above)
        replacement_node_index = _create_x_node(
            edge.left_point_index,
            left.leaf_index,
            replacement_node_index,
            nodes,
        )
    _replace_node(trapezoid.leaf_index, replacement_node_index, nodes)


def _box_to_trapezoid(
    box: hints.Box[hints.ScalarT],
    edges: list[Edge[hints.ScalarT]],
    endpoints: list[hints.Point[hints.ScalarT]],
    nodes: list[Node[hints.ScalarT]],
    orienteer: Orienteer[hints.ScalarT],
    /,
) -> Trapezoid:
    min_x, min_y, max_x, max_y = box.min_x, box.min_y, box.max_x, box.max_y
    delta_x, delta_y = (max_x - min_x) or 1, (max_y - min_y) or 1
    min_x, min_y, max_x, max_y = (
        min_x - delta_x,
        min_y - delta_y,
        max_x + delta_x,
        max_y + delta_y,
    )
    point_cls = type(endpoints[0])
    above_edge_left_point_index = len(endpoints)
    endpoints.append(point_cls(min_x, max_y))
    above_edge_right_point_index = len(endpoints)
    endpoints.append(point_cls(max_x, max_y))
    above_edge_index = len(edges)
    edges.append(
        Edge.from_endpoints(
            above_edge_left_point_index,
            above_edge_right_point_index,
            interior_to_left=True,
            orienteer=orienteer,
        )
    )
    below_edge_left_point_index = len(endpoints)
    endpoints.append(point_cls(min_x, min_y))
    below_edge_right_point_index = len(endpoints)
    endpoints.append(point_cls(max_x, min_y))
    below_edge_index = len(edges)
    edges.append(
        Edge.from_endpoints(
            below_edge_left_point_index,
            below_edge_right_point_index,
            interior_to_left=False,
            orienteer=orienteer,
        )
    )
    return _create_trapezoid(
        below_edge_left_point_index,
        below_edge_right_point_index,
        below_edge_index,
        above_edge_index,
        edges,
        nodes,
    )


def _create_trapezoid(
    left_point_index: int,
    right_point_index: int,
    below_edge_index: int,
    above_edge_index: int,
    edges: Sequence[Edge[hints.ScalarT]],
    nodes: list[Node[hints.ScalarT]],
    /,
) -> Trapezoid:
    is_component = (
        edges[below_edge_index].interior_to_left
        and not edges[above_edge_index].interior_to_left
    )
    leaf: Leaf[hints.ScalarT] = Leaf(
        is_component=is_component,
        left_point_index=left_point_index,
        right_point_index=right_point_index,
        below_edge_index=below_edge_index,
        above_edge_index=above_edge_index,
        index=len(nodes),
    )
    nodes.append(leaf)
    return leaf.trapezoid


def _create_x_node(
    point_index: int,
    left_node_index: int,
    right_node_index: int,
    nodes: list[Node[hints.ScalarT]],
    /,
) -> int:
    result = len(nodes)
    nodes.append(XNode(point_index, left_node_index, right_node_index))
    return result


def _create_y_node(
    edge_index: int,
    below_index: int,
    above_index: int,
    nodes: list[Node[hints.ScalarT]],
    /,
) -> int:
    result = len(nodes)
    nodes.append(YNode(edge_index, below_index, above_index))
    return result


def _find_intersecting_trapezoids(
    edge_index: int,
    edges: Sequence[Edge[hints.ScalarT]],
    endpoints: Sequence[hints.Point[hints.ScalarT]],
    nodes: Sequence[Node[hints.ScalarT]],
    /,
) -> list[Trapezoid]:
    edge = edges[edge_index]
    cursor = nodes[0]
    for _ in repeat(None, len(nodes) - 1):
        candidate = cursor.search_edge_node(edge, edges, endpoints, nodes)
        if candidate is cursor:
            break
        cursor = candidate
    assert isinstance(cursor, Leaf), cursor
    trapezoid = cursor.trapezoid
    result = [trapezoid]
    right = endpoints[edge.right_point_index]
    while endpoints[trapezoid.right_point_index] < right:
        candidate_index = (
            (
                trapezoid.upper_right_node_index
                or trapezoid.lower_right_node_index
            )
            if (
                edge.orientation_of(
                    endpoints[trapezoid.right_point_index], endpoints
                )
                is Orientation.CLOCKWISE
            )
            else (
                trapezoid.lower_right_node_index
                or trapezoid.upper_right_node_index
            )
        )
        assert candidate_index is not None, (
            'Expected neighbour trapezoid, but none found.'
        )
        trapezoid = _get_trapezoid(candidate_index, nodes)
        result.append(trapezoid)
    return result


def _get_trapezoid(
    index: int, nodes: Sequence[Node[hints.ScalarT]], /
) -> Trapezoid:
    node = nodes[index]
    assert isinstance(node, Leaf), node
    return node.trapezoid


def _maybe_set_as_lower_left(
    trapezoid: Trapezoid,
    maybe_node_index: int | None,
    nodes: Sequence[Node[hints.ScalarT]],
    /,
) -> None:
    if maybe_node_index is None:
        trapezoid.reset_lower_left()
    else:
        trapezoid.set_as_lower_left(_get_trapezoid(maybe_node_index, nodes))


def _maybe_set_as_lower_right(
    trapezoid: Trapezoid,
    maybe_node_index: int | None,
    nodes: Sequence[Node[hints.ScalarT]],
    /,
) -> None:
    if maybe_node_index is None:
        trapezoid.reset_lower_right()
    else:
        trapezoid.set_as_lower_right(_get_trapezoid(maybe_node_index, nodes))


def _maybe_set_as_upper_left(
    trapezoid: Trapezoid,
    maybe_node_index: int | None,
    nodes: Sequence[Node[hints.ScalarT]],
    /,
) -> None:
    if maybe_node_index is None:
        trapezoid.reset_upper_left()
    else:
        trapezoid.set_as_upper_left(_get_trapezoid(maybe_node_index, nodes))


def _maybe_set_as_upper_right(
    trapezoid: Trapezoid,
    maybe_node_index: int | None,
    nodes: Sequence[Node[hints.ScalarT]],
    /,
) -> None:
    if maybe_node_index is None:
        trapezoid.reset_upper_right()
    else:
        trapezoid.set_as_upper_right(_get_trapezoid(maybe_node_index, nodes))


def _populate_from_contour(
    contour: hints.Contour[hints.ScalarT],
    correct_orientation: Orientation,
    edges: list[Edge[hints.ScalarT]],
    endpoints: list[hints.Point[hints.ScalarT]],
    orienteer: Orienteer[hints.ScalarT],
    /,
) -> None:
    contour_vertices = contour.vertices
    is_contour_correctly_oriented = (
        to_contour_orientation(
            contour_vertices, to_arg_min(contour_vertices), orienteer
        )
        is correct_orientation
    )
    first_start = start = contour_vertices[0]
    first_start_index = start_index = len(endpoints)
    endpoints.extend(contour_vertices)
    for end_index, end in enumerate(
        contour_vertices[1:], start=first_start_index + 1
    ):
        edges.append(
            Edge.from_endpoints(
                start_index,
                end_index,
                interior_to_left=is_contour_correctly_oriented,
                orienteer=orienteer,
            )
            if start < end
            else Edge.from_endpoints(
                end_index,
                start_index,
                interior_to_left=not is_contour_correctly_oriented,
                orienteer=orienteer,
            )
        )
        start, start_index = end, end_index
    last_end_index, last_end = len(endpoints) - 1, endpoints[-1]
    assert last_end_index == first_start_index + len(contour.vertices) - 1
    edges.append(
        Edge.from_endpoints(
            first_start_index,
            last_end_index,
            interior_to_left=is_contour_correctly_oriented,
            orienteer=orienteer,
        )
        if first_start < last_end
        else Edge.from_endpoints(
            last_end_index,
            first_start_index,
            interior_to_left=not is_contour_correctly_oriented,
            orienteer=orienteer,
        )
    )


def _replace_node(
    original_index: int,
    replacement_index: int,
    nodes: list[Node[hints.ScalarT]],
    /,
) -> None:
    assert replacement_index == len(nodes) - 1, (
        replacement_index,
        len(nodes) - 1,
    )
    nodes[original_index] = nodes.pop()
