"""Set diff between two snapshots of WoW global function names.

`removed` and `added` are exact set differences. `renamed` is a heuristic
that pairs items in `removed` with similarly-named items in `added` when
edit distance is within `MAX_RENAME_DISTANCE`. The heuristic is best-effort
and intended for human review, not auto-fix.
"""
from dataclasses import dataclass, field

MAX_RENAME_DISTANCE = 3


@dataclass
class Diff:
    removed: set[str] = field(default_factory=set)
    added: set[str] = field(default_factory=set)
    renamed: list[tuple[str, str]] = field(default_factory=list)


def _levenshtein(a: str, b: str) -> int:
    if a == b:
        return 0
    if not a:
        return len(b)
    if not b:
        return len(a)
    prev = list(range(len(b) + 1))
    for i, ca in enumerate(a, start=1):
        curr = [i] + [0] * len(b)
        for j, cb in enumerate(b, start=1):
            curr[j] = min(
                prev[j] + 1,
                curr[j - 1] + 1,
                prev[j - 1] + (0 if ca == cb else 1),
            )
        prev = curr
    return prev[-1]


def compute_diff(old: set[str], new: set[str]) -> Diff:
    removed = old - new
    added = new - old
    renamed: list[tuple[str, str]] = []
    paired: set[str] = set()
    for r in sorted(removed):
        best = None
        best_dist = MAX_RENAME_DISTANCE + 1
        for a in added:
            if a in paired:
                continue
            d = _levenshtein(r, a)
            if d <= MAX_RENAME_DISTANCE and d < best_dist:
                best_dist = d
                best = a
        if best is not None:
            renamed.append((r, best))
            paired.add(best)
    return Diff(removed=removed, added=added, renamed=renamed)
