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


def impurity(counts: np.ndarray, kind: str = "gini") -> np.ndarray:
    """counts: (..., C) class counts. Returns impurity per row. Empty rows give 0."""
    tot = counts.sum(-1, keepdims=True)
    p = np.divide(counts, tot, out=np.zeros_like(counts, dtype=float), where=tot > 0)
    if kind == "gini":
        return 1.0 - (p * p).sum(-1)
    logp = np.log2(p, out=np.zeros_like(p), where=p > 0)   # 0 log 0 = 0
    return -(p * logp).sum(-1)


def best_split(X: np.ndarray, y: np.ndarray, kind: str = "gini",
               min_leaf: int = 1) -> tuple[int, float, float]:
    """Find the (feature, threshold) that most reduces weighted impurity.

    X: (n, d) numeric. y: (n,) ints 0..C-1. Rule: go left if x <= threshold.
    Returns (feature, threshold, gain). feature is -1 if no valid split.
    """
    n, d = X.shape
    C = int(y.max()) + 1
    parent = impurity(np.bincount(y, minlength=C).astype(float), kind)
    best = (-1, np.nan, 0.0)
    for f in range(d):
        order = np.argsort(X[:, f], kind="stable")       # O(n log n)
        xs, ys = X[order, f], y[order]
        left = np.cumsum(np.eye(C)[ys], axis=0)[:-1]     # (n-1, C): counts left of cut i
        right = left[-1] + np.eye(C)[ys[-1]] - left      # total minus left
        n_left = np.arange(1, n)
        w_imp = (n_left * impurity(left, kind) + (n - n_left) * impurity(right, kind)) / n
        valid = xs[1:] > xs[:-1]                         # never cut between equal values
        valid &= (n_left >= min_leaf) & (n - n_left >= min_leaf)
        if not valid.any():
            continue
        w_imp = np.where(valid, w_imp, np.inf)
        i = int(w_imp.argmin())
        gain = parent - w_imp[i]
        if gain > best[2]:
            best = (f, (xs[i] + xs[i + 1]) / 2.0, float(gain))  # midpoint threshold
    return best


if __name__ == "__main__":
    X = np.array([[2.0, 7.0], [3.0, 1.0], [10.0, 5.0], [11.0, 3.0], [12.0, 9.0]])
    y = np.array([0, 0, 1, 1, 1])
    f, t, g = best_split(X, y)
    assert f == 0 and t == 6.5 and np.isclose(g, 0.48), (f, t, g)
    f2, t2, g2 = best_split(X, y, kind="entropy")
    assert f2 == 0 and np.isclose(g2, 0.97095, atol=1e-4)
    assert best_split(np.ones((4, 1)), np.array([0, 1, 0, 1]))[0] == -1
    print("ok", f, t, round(g, 3))
