"""Pareto frontier (maximise y, minimise x) over labelled points. Pure Python, deterministic.

A point is *Pareto-efficient* when no other point has both a lower-or-equal x and a higher-or-equal y with at least one strict inequality.
Exact ties (same x and same y) are kept together on the frontier — we never break a tie by choosing one model over another."""
from __future__ import annotations

from typing import Any


def pareto_frontier(points: list[dict[str, Any]], *, x: str = "x", y: str = "y", key: str = "id", maximize_y: bool = True) -> list[Any]:
    """Return the `key`s of the Pareto-efficient points, ordered by increasing x. Points with a missing x or y are ignored."""
    valid = [p for p in points if p.get(x) is not None and p.get(y) is not None]
    if not valid:
        return []
    sign = 1.0 if maximize_y else -1.0
    # sort by x ascending, then by y descending (best first) so a sweep with the running best y finds the frontier
    ordered = sorted(valid, key=lambda p: (float(p[x]), -sign * float(p[y])))
    frontier: list[Any] = []
    best_y: float | None = None
    best_x: float | None = None
    for p in ordered:
        px, py = float(p[x]), sign * float(p[y])
        if best_y is None or py > best_y:
            frontier.append(p[key])
            best_y, best_x = py, px
        elif py == best_y and best_x is not None and px == best_x:
            frontier.append(p[key])  # exact tie: keep both
    return frontier


def is_dominated(p: dict[str, Any], others: list[dict[str, Any]], *, x: str = "x", y: str = "y", maximize_y: bool = True) -> bool:
    """True when some other point is at least as good on both axes and strictly better on one."""
    sign = 1.0 if maximize_y else -1.0
    px, py = float(p[x]), sign * float(p[y])
    for o in others:
        if o is p or o.get(x) is None or o.get(y) is None:
            continue
        ox, oy = float(o[x]), sign * float(o[y])
        if ox <= px and oy >= py and (ox < px or oy > py):
            return True
    return False


__all__ = ["is_dominated", "pareto_frontier"]