#!/usr/bin/env python3
# Source: q4-ml-coding.html
import numpy as np


def rankdata_avg(a: np.ndarray) -> np.ndarray:
    """1-based ranks. Tied values share the average of their ranks."""
    order = np.argsort(a, kind="mergesort")
    s = a[order]
    # Start index of each run of equal values.
    starts = np.flatnonzero(np.r_[True, s[1:] != s[:-1]])
    ends = np.r_[starts[1:], len(s)]
    avg = (starts + ends + 1) / 2.0                 # mean of ranks starts+1 .. ends
    ranks = np.empty(len(a))
    ranks[order] = np.repeat(avg, ends - starts)
    return ranks


def roc_auc_rank(y: np.ndarray, s: np.ndarray) -> float:
    """AUC = P(score of random positive > random negative), ties count 1/2."""
    y = y.astype(bool)
    n_pos, n_neg = y.sum(), (~y).sum()
    if n_pos == 0 or n_neg == 0:
        raise ValueError("AUC needs both classes")
    r = rankdata_avg(s)
    u = r[y].sum() - n_pos * (n_pos + 1) / 2.0      # Mann-Whitney U
    return float(u / (n_pos * n_neg))


def roc_curve(y: np.ndarray, s: np.ndarray) -> tuple[np.ndarray, np.ndarray]:
    """Sweep the threshold from high to low. One point per distinct score."""
    order = np.argsort(-s, kind="mergesort")
    s, y = s[order], y[order].astype(float)
    last = np.r_[s[1:] != s[:-1], True]             # last index of each tied group
    tp = np.cumsum(y)[last]
    fp = np.cumsum(1.0 - y)[last]
    tpr = np.r_[0.0, tp / tp[-1]]
    fpr = np.r_[0.0, fp / fp[-1]]
    return fpr, tpr


def roc_auc_sweep(y: np.ndarray, s: np.ndarray) -> float:
    fpr, tpr = roc_curve(y, s)
    return float(np.sum(np.diff(fpr) * (tpr[1:] + tpr[:-1]) / 2.0))  # trapezoids


if __name__ == "__main__":
    y = np.array([0, 0, 1, 1, 0, 1])
    s = np.array([0.1, 0.4, 0.35, 0.8, 0.4, 0.4])
    brute = np.mean([(sp > sn) + 0.5 * (sp == sn) for sp in s[y == 1] for sn in s[y == 0]])
    assert np.isclose(roc_auc_rank(y, s), brute)
    assert np.isclose(roc_auc_sweep(y, s), brute)
    rng = np.random.default_rng(4)
    y2 = rng.integers(0, 2, 1000)
    s2 = np.round(rng.normal(size=1000) + y2, 1)    # rounding makes many ties
    assert np.isclose(roc_auc_rank(y2, s2), roc_auc_sweep(y2, s2))
    print("ok", round(brute, 4))
