from __future__ import annotations

from collections import deque
from itertools import chain, groupby
from operator import attrgetter
from typing import Generic, TYPE_CHECKING

from typing_extensions import Self

from rene import hints
from rene._relating import segment_endpoints
from rene._utils import locate_point_in_point_point_point_circle
from rene.enums import Location, Orientation, Relation

from .mesh import Mesh, build_delaunay_triangulation, orient_point_to_edge
from .quad_edge import QuadEdge, UNDEFINED_EDGE, to_opposite_edge
from .vertices import ContourVertex, PolygonVertexPosition

if TYPE_CHECKING:
    from collections.abc import Container, Iterable, Sequence

    from rene._hints import Orienteer

BORDER_CONTOUR_INDEX = 0


class ConstrainedDelaunayTriangulation(Generic[hints.ScalarT]):
    @classmethod
    def from_polygon(
        cls,
        polygon: hints.Polygon[hints.ScalarT],
        orienteer: Orienteer[hints.ScalarT],
        /,
    ) -> Self:
        contours_vertices = [
            polygon.border.vertices,
            *[hole.vertices for hole in polygon.holes],
        ]
        vertices = list(
            chain.from_iterable(
                (
                    ContourVertex(index, vertex_index, vertex)
                    for vertex_index, vertex in zip(
                        range(len(contour_vertices) - 1),
                        contour_vertices[:-1],
                        strict=True,
                    )
                )
                for index, contour_vertices in enumerate(contours_vertices)
            )
        ) + [
            ContourVertex(
                index, len(contour_vertices) - 1, contour_vertices[-1]
            )
            for index, contour_vertices in enumerate(contours_vertices)
        ]
        vertices.sort()
        polygon_vertices_positions: list[list[PolygonVertexPosition]] = []
        points: list[hints.Point[hints.ScalarT]] = []
        for point, same_point_vertices in groupby(
            vertices, key=attrgetter('point')
        ):
            points.append(point)
            polygon_vertices_positions.append(
                [
                    PolygonVertexPosition(vertex.contour_index, vertex.index)
                    for vertex in same_point_vertices
                ]
            )
        mesh = Mesh.from_points(points)
        left_side, right_side = build_delaunay_triangulation(mesh, orienteer)
        contours_sizes = [
            len(contour_vertices) for contour_vertices in contours_vertices
        ]
        triangular_holes_indices = [
            hole_index
            for hole_index, hole_size in enumerate(contours_sizes[1:], start=1)
            if hole_size == 3
        ]
        self = cls(
            left_side,
            right_side,
            mesh,
            polygon_vertices_positions,
            triangular_holes_indices,
            orienteer,
        )
        self.constrain(contours_sizes, contours_vertices)
        self.bound(contours_sizes)
        self.cut(contours_vertices)
        return self

    @property
    def left_side(self, /) -> QuadEdge:
        return self._left_side

    @property
    def mesh(self, /) -> Mesh[hints.ScalarT]:
        return self._mesh

    @property
    def right_side(self, /) -> QuadEdge:
        return self._right_side

    def bound(self, contours_sizes: list[int], /) -> None:
        mesh = self.mesh
        boundary_edges = self.to_unique_boundary_edges()
        extraneous_mouths = [
            edge
            for edge in boundary_edges
            if not is_polygon_edge(
                mesh, edge, contours_sizes, self._polygon_vertices_positions
            )
        ]
        while extraneous_mouths:
            mouth = extraneous_mouths.pop()
            first_candidate, second_candidate = mouth_edge_to_incidents(
                mesh, mouth, self._orienteer
            )
            self.delete_edge(mouth)
            if not is_polygon_edge(
                mesh,
                first_candidate,
                contours_sizes,
                self._polygon_vertices_positions,
            ):
                extraneous_mouths.append(first_candidate)
            if not is_polygon_edge(
                mesh,
                second_candidate,
                contours_sizes,
                self._polygon_vertices_positions,
            ):
                extraneous_mouths.append(second_candidate)

    def constrain(
        self,
        contours_sizes: list[int],
        contours_vertices: list[Sequence[hints.Point[hints.ScalarT]]],
        /,
    ) -> None:
        mesh = self.mesh
        contours_constraints_flags = to_contours_constraints_flags(
            mesh, contours_sizes, self._polygon_vertices_positions
        )
        for edge in mesh.to_edges():
            vertex_start_index = mesh.to_start_index(edge)
            vertex_point = mesh.endpoints[vertex_start_index]
            vertex_positions = self._polygon_vertices_positions[
                vertex_start_index
            ]
            for vertex_position in vertex_positions:
                contour_index, vertex_index = (
                    vertex_position.contour_index,
                    vertex_position.index,
                )
                contour_size = contours_sizes[contour_index]
                next_vertex_index = (vertex_index + 1) % contour_size
                constraint_index = to_constraint_index(
                    vertex_index, next_vertex_index
                )
                if not contours_constraints_flags[contour_index][
                    constraint_index
                ]:
                    next_vertex_point = contours_vertices[contour_index][
                        next_vertex_index
                    ]
                    angle_base_edge = to_angle_containing_constraint_base(
                        mesh, edge, next_vertex_point, self._orienteer
                    )
                    crossings = detect_crossings(
                        mesh,
                        angle_base_edge,
                        vertex_point,
                        next_vertex_point,
                        self._orienteer,
                    )
                    if crossings:
                        set_constraint(
                            mesh,
                            vertex_point,
                            next_vertex_point,
                            crossings,
                            self._orienteer,
                        )
                    contours_constraints_flags[contour_index][
                        constraint_index
                    ] = True

    def cut(
        self, contours_vertices: list[Sequence[hints.Point[hints.ScalarT]]], /
    ) -> None:
        mesh = self.mesh
        for edge in mesh.to_unique_edges():
            if is_edge_inside_hole(
                mesh,
                edge,
                contours_vertices,
                self._polygon_vertices_positions,
                self._orienteer,
            ):
                self.delete_edge(edge)

    def delete_edge(self, edge: QuadEdge, /) -> None:
        if (
            edge == self.right_side
            or to_opposite_edge(edge) == self.right_side
        ):
            self._right_side = to_opposite_edge(
                self.mesh.to_right_from_end(self.right_side)
            )
        if edge == self.left_side or to_opposite_edge(edge) == self.left_side:
            self._left_side = self.mesh.to_left_from_start(self.left_side)
        self.mesh.delete_edge(edge)

    def to_boundary_points(self, /) -> list[hints.Point[hints.ScalarT]]:
        edge_to_start = self.mesh.to_start
        return [
            edge_to_start(edge) for edge in self.to_unique_boundary_edges()
        ]

    def to_unique_boundary_edges(self, /) -> list[QuadEdge]:
        if self:
            result = []
            start = self.left_side
            edge = start
            while True:
                result.append(edge)
                candidate = self.mesh.to_right_from_end(edge)
                if candidate == start:
                    break
                edge = candidate
            return result
        return list(self.mesh.to_unique_edges())

    def triangles_vertices(
        self,
    ) -> list[
        tuple[
            hints.Point[hints.ScalarT],
            hints.Point[hints.ScalarT],
            hints.Point[hints.ScalarT],
        ]
    ]:
        mesh = self.mesh
        result = []
        for edge in mesh.to_edges():
            first_vertex = mesh.to_start(edge)
            second_vertex = mesh.to_end(edge)
            third_vertex = mesh.to_end(mesh.to_left_from_start(edge))
            if (
                first_vertex < second_vertex
                and first_vertex < third_vertex
                and third_vertex
                == mesh.to_end(
                    mesh.to_right_from_start(to_opposite_edge(edge))
                )
                and orient_point_to_edge(
                    mesh, edge, third_vertex, self._orienteer
                )
                is Orientation.COUNTERCLOCKWISE
                and not (
                    self._triangular_holes_indices
                    and are_triangular_hole_vertices(
                        self._polygon_vertices_positions[
                            mesh.to_start_index(edge)
                        ],
                        self._polygon_vertices_positions[
                            mesh.to_end_index(edge)
                        ],
                        self._polygon_vertices_positions[
                            mesh.to_end_index(mesh.to_left_from_start(edge))
                        ],
                        self._triangular_holes_indices,
                    )
                )
            ):
                result.append((first_vertex, second_vertex, third_vertex))
        return result

    __slots__ = (
        '_left_side',
        '_mesh',
        '_orienteer',
        '_polygon_vertices_positions',
        '_right_side',
        '_triangular_holes_indices',
    )

    def __init__(
        self,
        left_side: QuadEdge,
        right_side: QuadEdge,
        mesh: Mesh[hints.ScalarT],
        polygon_vertices_positions: list[list[PolygonVertexPosition]],
        triangular_holes_indices: Container[int],
        orienteer: Orienteer[hints.ScalarT],
        /,
    ) -> None:
        (
            self._left_side,
            self._mesh,
            self._orienteer,
            self._polygon_vertices_positions,
            self._right_side,
            self._triangular_holes_indices,
        ) = (
            left_side,
            mesh,
            orienteer,
            polygon_vertices_positions,
            right_side,
            triangular_holes_indices,
        )

    def __bool__(self, /) -> bool:
        result = bool(self.mesh)
        assert result is (self.left_side != UNDEFINED_EDGE)
        assert result is (self.right_side != UNDEFINED_EDGE)
        return result


def angle_contains_point(
    vertex: hints.Point[hints.ScalarT],
    first_ray_point: hints.Point[hints.ScalarT],
    second_ray_point: hints.Point[hints.ScalarT],
    angle_orientation: Orientation,
    point: hints.Point[hints.ScalarT],
    orienteer: Orienteer[hints.ScalarT],
    /,
) -> bool:
    assert angle_orientation is not Orientation.COLLINEAR
    first_half_orientation = orienteer(vertex, first_ray_point, point)
    second_half_orientation = orienteer(second_ray_point, vertex, point)
    return (
        first_half_orientation is Orientation.COLLINEAR
        or first_half_orientation is angle_orientation
    ) and (
        second_half_orientation is Orientation.COLLINEAR
        or second_half_orientation is angle_orientation
    )


def are_polygon_edge_indices(
    first: int, second: int, contour_size: int, /
) -> bool:
    return (
        abs(first - second) == 1
        or (first == 0 and second == contour_size - 1)
        or (first == contour_size - 1 and second == 0)
    )


def are_triangular_hole_vertices(
    first_positions: list[PolygonVertexPosition],
    second_positions: list[PolygonVertexPosition],
    third_positions: list[PolygonVertexPosition],
    triangular_holes_indices: Container[int],
    /,
) -> bool:
    first_contours_indices = [
        position.contour_index for position in first_positions
    ]
    second_contours_indices = [
        position.contour_index for position in second_positions
    ]
    third_contours_indices = [
        position.contour_index for position in third_positions
    ]
    return any(
        (
            contour_index != BORDER_CONTOUR_INDEX
            and contour_index in second_contours_indices
            and contour_index in third_contours_indices
            and contour_index in triangular_holes_indices
        )
        for contour_index in first_contours_indices
    )


def detect_crossings(
    mesh: Mesh[hints.ScalarT],
    base_edge: QuadEdge,
    constraint_start: hints.Point[hints.ScalarT],
    constraint_end: hints.Point[hints.ScalarT],
    orienteer: Orienteer[hints.ScalarT],
    /,
) -> list[QuadEdge]:
    candidate = mesh.to_left_from_end(base_edge)
    result = []
    while mesh.to_start(candidate) != constraint_end:
        last_crossing = candidate
        assert (
            segment_endpoints.relate_to_segment_endpoints(
                mesh.to_start(last_crossing),
                mesh.to_end(last_crossing),
                constraint_start,
                constraint_end,
                orienteer,
            )
            is Relation.CROSS
        )
        result.append(last_crossing)
        candidate = mesh.to_right_from_start(last_crossing)
        if (
            orient_point_to_edge(mesh, candidate, constraint_end, orienteer)
            is not Orientation.CLOCKWISE
        ) or (
            orienteer(constraint_start, constraint_end, mesh.to_end(candidate))
            is Orientation.CLOCKWISE
        ):
            candidate = to_opposite_edge(mesh.to_right_from_end(last_crossing))
    assert all(to_opposite_edge(edge) not in result for edge in result)
    assert all(
        edge in result or to_opposite_edge(edge) in result
        for edge in mesh.to_unique_edges()
        if (
            segment_endpoints.relate_to_segment_endpoints(
                mesh.to_start(edge),
                mesh.to_end(edge),
                constraint_start,
                constraint_end,
                orienteer,
            )
            is Relation.CROSS
        )
    )
    return result


def intersect_polygon_vertices_positions(
    first: list[PolygonVertexPosition],
    second: list[PolygonVertexPosition],
    *,
    with_border: bool,
) -> list[tuple[PolygonVertexPosition, PolygonVertexPosition]]:
    return list(
        _intersect_polygon_vertices_positions(
            first, second, reverse=False, with_border=with_border
        )
        if len(first) < len(second)
        else _intersect_polygon_vertices_positions(
            second, first, reverse=True, with_border=with_border
        )
    )


def _intersect_polygon_vertices_positions(
    first: list[PolygonVertexPosition],
    second: list[PolygonVertexPosition],
    /,
    *,
    reverse: bool,
    with_border: bool,
) -> Iterable[tuple[PolygonVertexPosition, PolygonVertexPosition]]:
    assert len(first) <= len(second)
    for first_position in first:
        if with_border or first_position.contour_index != BORDER_CONTOUR_INDEX:
            try:
                second_position = next(
                    candidate
                    for candidate in second
                    if (
                        candidate.contour_index == first_position.contour_index
                    )
                )
            except StopIteration:
                pass
            else:
                yield (
                    (second_position, first_position)
                    if reverse
                    else (first_position, second_position)
                )


def is_edge_inside_hole(
    mesh: Mesh[hints.ScalarT],
    edge: QuadEdge,
    contours_vertices: list[Sequence[hints.Point[hints.ScalarT]]],
    polygon_vertices_positions: list[list[PolygonVertexPosition]],
    orienteer: Orienteer[hints.ScalarT],
    /,
) -> bool:
    start_index, end_index = mesh.to_start_index(edge), mesh.to_end_index(edge)
    start, end = mesh.endpoints[start_index], mesh.endpoints[end_index]
    common_holes_positions = intersect_polygon_vertices_positions(
        polygon_vertices_positions[start_index],
        polygon_vertices_positions[end_index],
        with_border=False,
    )
    assert len(common_holes_positions) <= 1
    return bool(common_holes_positions) and is_segment_inside_hole(
        start, end, *common_holes_positions[0], contours_vertices, orienteer
    )


def is_segment_inside_hole(
    start: hints.Point[hints.ScalarT],
    end: hints.Point[hints.ScalarT],
    start_position: PolygonVertexPosition,
    end_position: PolygonVertexPosition,
    contours_vertices: list[Sequence[hints.Point[hints.ScalarT]]],
    orienteer: Orienteer[hints.ScalarT],
    /,
) -> bool:
    assert start_position.contour_index == end_position.contour_index
    hole_vertices = contours_vertices[start_position.contour_index]
    hole_size = len(hole_vertices)
    start_vertex_index = start_position.index
    end_vertex_index = end_position.index
    if are_polygon_edge_indices(
        start_vertex_index, end_vertex_index, hole_size
    ):
        return False
    prior_to_start_point = hole_vertices[start_vertex_index - 1]
    prior_to_end_point = hole_vertices[end_vertex_index - 1]
    next_to_start_point = hole_vertices[(start_vertex_index + 1) % hole_size]
    next_to_end_point = hole_vertices[(end_vertex_index + 1) % hole_size]
    start_angle_orientation = orienteer(
        start, prior_to_start_point, next_to_start_point
    )
    end_angle_orientation = orienteer(
        end, prior_to_end_point, next_to_end_point
    )
    return (
        (end_angle_orientation is Orientation.COUNTERCLOCKWISE)
        is angle_contains_point(
            end,
            prior_to_end_point,
            next_to_end_point,
            end_angle_orientation,
            start,
            orienteer,
        )
    ) and (
        (start_angle_orientation is Orientation.COUNTERCLOCKWISE)
        is angle_contains_point(
            start,
            prior_to_start_point,
            next_to_start_point,
            start_angle_orientation,
            end,
            orienteer,
        )
    )


def mouth_edge_to_incidents(
    mesh: Mesh[hints.ScalarT],
    edge: QuadEdge,
    orienteer: Orienteer[hints.ScalarT],
    /,
) -> tuple[QuadEdge, QuadEdge]:
    left_from_start = mesh.to_left_from_start(edge)
    assert (
        orient_point_to_edge(
            mesh, edge, mesh.to_end(left_from_start), orienteer
        )
        is Orientation.COUNTERCLOCKWISE
    )
    return left_from_start, mesh.to_right_from_end(left_from_start)


def to_contours_constraints_flags(
    mesh: Mesh[hints.ScalarT],
    contours_sizes: list[int],
    polygon_vertices_positions: list[list[PolygonVertexPosition]],
    /,
) -> list[list[bool]]:
    result = [[False] * contour_size for contour_size in contours_sizes]
    for edge in mesh.to_unique_edges():
        common_positions = intersect_polygon_vertices_positions(
            polygon_vertices_positions[mesh.to_start_index(edge)],
            polygon_vertices_positions[mesh.to_end_index(edge)],
            with_border=True,
        )
        for start_position, end_position in common_positions:
            assert start_position.contour_index == end_position.contour_index
            contour_index = start_position.contour_index
            start_index, end_index = (start_position.index, end_position.index)
            if are_polygon_edge_indices(
                start_index, end_index, contours_sizes[contour_index]
            ):
                result[contour_index][
                    to_constraint_index(start_index, end_index)
                ] = True
    return result


def edge_should_be_swapped(
    mesh: Mesh[hints.ScalarT],
    edge: QuadEdge,
    orienteer: Orienteer[hints.ScalarT],
    /,
) -> bool:
    return is_convex_quadrilateral_diagonal(mesh, edge, orienteer) and (
        locate_point_in_point_point_point_circle(
            mesh.to_end(mesh.to_right_from_start(edge)),
            mesh.to_start(edge),
            mesh.to_end(edge),
            mesh.to_end(mesh.to_left_from_start(edge)),
        )
        is Location.INTERIOR
        or (
            locate_point_in_point_point_point_circle(
                mesh.to_end(mesh.to_left_from_start(edge)),
                mesh.to_end(edge),
                mesh.to_start(edge),
                mesh.to_end(mesh.to_right_from_start(edge)),
            )
            is Location.INTERIOR
        )
    )


def is_convex_quadrilateral_diagonal(
    mesh: Mesh[hints.ScalarT],
    edge: QuadEdge,
    orienteer: Orienteer[hints.ScalarT],
    /,
) -> bool:
    return (
        orient_point_to_edge(
            mesh, mesh.to_left_from_end(edge), mesh.to_start(edge), orienteer
        )
        is orient_point_to_edge(
            mesh, mesh.to_right_from_start(edge), mesh.to_end(edge), orienteer
        )
        is Orientation.COUNTERCLOCKWISE
        is orient_point_to_edge(
            mesh,
            to_opposite_edge(mesh.to_right_from_end(edge)),
            mesh.to_end(mesh.to_left_from_start(edge)),
            orienteer,
        )
        is orient_point_to_edge(
            mesh,
            to_opposite_edge(mesh.to_left_from_start(edge)),
            mesh.to_end(mesh.to_right_from_start(edge)),
            orienteer,
        )
    )


def is_polygon_edge(
    mesh: Mesh[hints.ScalarT],
    edge: QuadEdge,
    contours_sizes: list[int],
    polygon_vertices_positions: list[list[PolygonVertexPosition]],
    /,
) -> bool:
    common_positions = intersect_polygon_vertices_positions(
        polygon_vertices_positions[mesh.to_start_index(edge)],
        polygon_vertices_positions[mesh.to_end_index(edge)],
        with_border=True,
    )
    return any(
        are_polygon_edge_indices(
            start_position.index,
            end_position.index,
            contours_sizes[start_position.contour_index],
        )
        for start_position, end_position in common_positions
    )


def resolve_crossings(
    mesh: Mesh[hints.ScalarT],
    constraint_start: hints.Point[hints.ScalarT],
    constraint_end: hints.Point[hints.ScalarT],
    crossings: list[QuadEdge],
    orienteer: Orienteer[hints.ScalarT],
    /,
) -> list[QuadEdge]:
    result = []
    crossings_queue = deque(crossings, maxlen=len(crossings))
    while crossings_queue:
        crossing = crossings_queue.popleft()
        if is_convex_quadrilateral_diagonal(mesh, crossing, orienteer):
            mesh.swap_diagonal(crossing)
            relation = segment_endpoints.relate_to_segment_endpoints(
                mesh.to_start(crossing),
                mesh.to_end(crossing),
                constraint_start,
                constraint_end,
                orienteer,
            )
            if relation is Relation.CROSS:
                crossings_queue.append(crossing)
            elif relation is not Relation.EQUAL:
                result.append(crossing)
        else:
            crossings_queue.append(crossing)
    return result


def restore_delaunay_criterion(
    mesh: Mesh[hints.ScalarT],
    candidates: list[QuadEdge],
    orienteer: Orienteer[hints.ScalarT],
    /,
) -> None:
    while True:
        next_target_edges: list[QuadEdge] = []
        edges_to_swap: list[QuadEdge] = []
        for edge in candidates:
            (
                edges_to_swap
                if edge_should_be_swapped(mesh, edge, orienteer)
                else next_target_edges
            ).append(edge)
        if not edges_to_swap:
            break
        for edge in edges_to_swap:
            mesh.swap_diagonal(edge)
        candidates = next_target_edges


def set_constraint(
    mesh: Mesh[hints.ScalarT],
    constraint_start: hints.Point[hints.ScalarT],
    constraint_end: hints.Point[hints.ScalarT],
    crossings: list[QuadEdge],
    orienteer: Orienteer[hints.ScalarT],
    /,
) -> None:
    new_edges = resolve_crossings(
        mesh, constraint_start, constraint_end, crossings, orienteer
    )
    restore_delaunay_criterion(mesh, new_edges, orienteer)


def to_angle_containing_constraint_base(
    mesh: Mesh[hints.ScalarT],
    edge: QuadEdge,
    constraint_end: hints.Point[hints.ScalarT],
    orienteer: Orienteer[hints.ScalarT],
    /,
) -> QuadEdge:
    if mesh.to_end(edge) != constraint_end:
        orientation = orient_point_to_edge(
            mesh, edge, constraint_end, orienteer
        )
        if orientation is Orientation.COUNTERCLOCKWISE:
            while True:
                candidate = mesh.to_left_from_start(edge)
                orientation = orient_point_to_edge(
                    mesh, candidate, constraint_end, orienteer
                )
                if orientation is Orientation.CLOCKWISE:
                    break
                edge = candidate
        else:
            while True:
                edge = mesh.to_right_from_start(edge)
                orientation = orient_point_to_edge(
                    mesh, edge, constraint_end, orienteer
                )
                if orientation is not Orientation.CLOCKWISE:
                    break
    return edge


def to_constraint_index(
    first_vertex_index: int, second_vertex_index: int, /
) -> int:
    return (
        max(first_vertex_index, second_vertex_index)
        if abs(second_vertex_index - first_vertex_index) == 1
        else 0
    )
