# examples/online-softmax/online_softmax.py
"""Educational online softmax with standard-library CPU correctness checks.

Run with Python 3.10+: python examples/online-softmax/online_softmax.py
Use --json to emit a deterministic trace. This is not a GPU benchmark.
"""

import argparse
import heapq
import json
import math
import random


def finite_values(values):
    """Materialize a nonempty finite sequence for the two-pass references."""
    result = tuple(float(value) for value in values)
    if not result or not all(math.isfinite(value) for value in result):
        raise ValueError("A nonempty sequence of finite logits is required")
    return result


# region: stable
def stable_softmax(values):
    """Subtract the final maximum before exponentiation."""
    values = finite_values(values)
    maximum = max(values)
    denominator = math.fsum(math.exp(x - maximum) for x in values)
    return [math.exp(x - maximum) / denominator for x in values]
# endregion: stable


# region: online
def online_normalizer(values):
    """Consume finite logits once, keeping just a maximum and shifted sum."""
    maximum, denominator = -math.inf, 0.0
    for value in values:
        if not math.isfinite(value):
            raise ValueError("Finite logits required")
        next_maximum = max(maximum, value)
        denominator = (
            denominator * math.exp(maximum - next_maximum)
            + math.exp(value - next_maximum)
        )
        maximum = next_maximum
    return maximum, denominator
# endregion: online


# region: merge
def merge(left, right):
    """Merge summaries; (-inf, 0) is the empty-chunk identity."""
    left_max, left_sum = left
    right_max, right_sum = right
    if left_sum == 0:
        return right
    if right_sum == 0:
        return left
    maximum = max(left_max, right_max)
    denominator = (
        left_sum * math.exp(left_max - maximum)
        + right_sum * math.exp(right_max - maximum)
    )
    return maximum, denominator
# endregion: merge


# region: output
def online_softmax(values):
    """The final probabilities still require access to every input logit."""
    values = finite_values(values)
    maximum, denominator = online_normalizer(values)
    return [math.exp(x - maximum) / denominator for x in values]
# endregion: output


# region: topk
def online_topk(values, k):
    """Read once; retain k logits and normalize with the ALL-logit sum."""
    if not isinstance(k, int) or isinstance(k, bool) or k < 1:
        raise ValueError("A positive integer k is required")
    maximum, denominator = -math.inf, 0.0
    selected = []
    for index, value in enumerate(values):
        if not math.isfinite(value):
            raise ValueError("Finite logits required")
        maximum, denominator = merge((maximum, denominator), (value, 1.0))
        # Smaller original indices win ties in this teaching reference.
        heapq.heappush(selected, (value, -index))
        if len(selected) > k:
            heapq.heappop(selected)
    if len(selected) < k:
        raise ValueError("k must not exceed the input length")
    return [(-index, math.exp(value - maximum) / denominator)
            for value, index in sorted(selected, reverse=True)]
# endregion: topk


def trace(values):
    """Record the authored trace for browser/reference agreement checks."""
    maximum, denominator = -math.inf, 0.0
    rows = []
    for value in finite_values(values):
        next_maximum = max(maximum, value)
        correction = math.exp(maximum - next_maximum)
        incoming = math.exp(value - next_maximum)
        denominator = denominator * correction + incoming
        maximum = next_maximum
        rows.append({"maximum": maximum, "denominator": denominator,
                     "correction": correction, "incoming": incoming})
    return rows


def check_close(actual, expected):
    """Compare independent reductions with floating-point tolerances."""
    assert len(actual) == len(expected)
    for result, reference in zip(actual, expected):
        assert math.isclose(result, reference, rel_tol=2e-12, abs_tol=1e-14)


def self_check():
    """Check shifts, partitions, empty identities, ties, and extreme logits."""
    rng = random.Random(180502867)
    cases = [[0.0], [3.0] * 7, [1000.0, 1001.0, 999.0],
             [-1000.0, 0.0, 1000.0], [2.0, 1.0, 4.0, 0.0, 5.0, 3.0]]
    cases.extend([rng.uniform(-30, 30) for _ in range(size)]
                 for size in [2, 7, 31, 127])
    for values in cases:
        expected = stable_softmax(values)
        check_close(online_softmax(values), expected)
        check_close(online_softmax([x + 1024 for x in values]), expected)
        for split in range(len(values) + 1):
            maximum, denominator = merge(online_normalizer(values[:split]),
                                         online_normalizer(values[split:]))
            check_close([math.exp(x - maximum) / denominator for x in values],
                        expected)
        k = min(3, len(values))
        selected = online_topk(iter(values), k)
        indices = sorted(range(len(values)), key=lambda i: (-values[i], i))[:k]
        assert [i for i, _ in selected] == indices
        check_close([p for _, p in selected], [expected[i] for i in indices])
    assert merge((-math.inf, 0.0), (-math.inf, 0.0)) == (-math.inf, 0.0)
    for invalid in [[], [math.inf], [-math.inf], [math.nan]]:
        try:
            online_softmax(invalid)
        except ValueError:
            continue
        raise AssertionError("Invalid input was accepted")


def main():
    parser = argparse.ArgumentParser(description=__doc__)
    parser.add_argument('--json', action='store_true')
    args = parser.parse_args()
    self_check()
    values = [2.0, 1.0, 4.0, 0.0, 5.0, 3.0]
    if args.json:
        print(json.dumps({"trace": trace(values), "output": online_softmax(values),
                          "topk": online_topk(iter(values), 2)}))
    else:
        print("CPU correctness checks passed (no timing measurements).")
        print("Input:", values)
        print("Online softmax:", online_softmax(values))
        print("Top 2 original probabilities:", online_topk(iter(values), 2))


if __name__ == '__main__':
    main()
