"""Token Lab synthetic scheduling lab. Python 3.11+, standard library only.
No model, API, tools, GPU or external environment is called.
Inference stages have fixed durations and unlimited parallel capacity.
This is an independently written teaching model, not the paper's evaluator.
"""
from dataclasses import dataclass
from heapq import heappush, heappop
from math import ceil, floor, isfinite

@dataclass(frozen=True)
class Trace:
    inference: tuple[float, ...]
    environment: tuple[float, ...]
    def __post_init__(self):
        assert len(self.inference) == len(self.environment) + 1
        assert all(isfinite(x) and x > 0 for x in self.inference + self.environment)


def run(traces, samples=4, environments=1, policy="fcfs", band=30.0, bucket=1.0):
    assert samples > 0 and environments > 0 and band > 0 and bucket > 0
    assert policy in {"fcfs", "caas"}
    events, pending, completed, spans = [], [], {}, []
    active = busy = next_task = serial = 0
    observed = [0.0] * len(traces)
    max_busy = 0
    def schedule(end, kind, task, turn):
        nonlocal serial
        serial += 1
        heappush(events, (end, serial, kind, task, turn))
    def admit(now):
        nonlocal active, next_task
        while active < samples and next_task < len(traces):
            task = next_task
            next_task += 1
            active += 1
            schedule(now + traces[task].inference[0], "inference", task, 0)
    admit(0.0)
    while events:
        now = events[0][0]
        # Process simultaneous completions before choosing the next environment job.
        while events and events[0][0] == now:
            _, _, kind, task, turn = heappop(events)
            trace = traces[task]
            if kind == "environment":
                busy -= 1
                schedule(now + trace.inference[turn + 1], "inference", task, turn + 1)
            else:
                observed[task] += trace.inference[turn]
                if turn == len(trace.environment):
                    completed[task] = now
                    active -= 1
                else:
                    serial += 1
                    key = (serial,) if policy == "fcfs" else (
                        floor(now / band), -(turn + 1),
                        ceil(observed[task] / (turn + 1) / bucket), serial)
                    heappush(pending, (key, task, turn, now))
        admit(now)
        while pending and busy < environments:
            _, task, turn, arrival = heappop(pending)
            end = now + traces[task].environment[turn]
            spans.append((task, turn, arrival, now, end))
            busy += 1
            max_busy = max(max_busy, busy)
            schedule(end, "environment", task, turn)
    assert len(completed) == len(traces) and not pending and busy == active == 0
    ordered = sorted(completed.values())
    t95 = ordered[ceil(.95 * len(ordered)) - 1] if ordered else 0
    end = ordered[-1] if ordered else 0
    return {"makespan": end, "tail5": end - t95,
            "mean_completion": sum(ordered) / len(ordered) if ordered else 0,
            "completed": completed, "spans": spans, "max_busy": max_busy}


def checks():
    short = Trace((1., 1.), (2.,))
    assert run([short], samples=1)["makespan"] == 4
    assert run([short] * 3, samples=1)["makespan"] == 12
    assert run([short] * 3, samples=3)["makespan"] == 8
    for policy in ["fcfs", "caas"]:
        r = run([short] * 3, samples=3, environments=2, policy=policy)
        assert r["max_busy"] <= 2 and r["makespan"] == 6
        assert sum(e-s for _, _, _, s, e in r["spans"]) == 6
    # Earlier arrival bands outrank later bands regardless of observed depth.
    assert (0, -1, 5, 1) < (1, -100, 1, 2)
    try:
        Trace((1.,), (2.,))
    except AssertionError:
        pass
    else:
        raise AssertionError("invalid dependency chain accepted")
    return short

if __name__ == "__main__":
    short = checks()
    print("checks=passed")
    for policy in ["fcfs", "caas"]:
        for capacity in [1, 3]:
            r = run([short] * 3, samples=capacity, policy=policy)
            print(f"{policy} C_S={capacity} C_E=1 makespan={r['makespan']:.1f}s")
    # A broader synthetic comparison, with identical traces for both policies.
    import random
    rng = random.Random(17)
    traces = []
    for _ in range(50):
        turns = rng.choice([1, 2, 8, 16])
        traces.append(Trace(tuple(float(rng.randint(1, 4)) for _ in range(turns+1)),
                            tuple(float(rng.randint(1, 6)) for _ in range(turns))))
    for policy in ["fcfs", "caas"]:
        r = run(traces, samples=20, environments=3, policy=policy)
        print(f"{policy} mixed makespan={r['makespan']:.1f}s tail5={r['tail5']:.1f}s "
              f"mean={r['mean_completion']:.2f}s")
