"""A busy server and a crowd of clients that retry. Python standard library only.

This is a toy, not a model of any real provider. Time moves in whole ticks (think of a tick as one second).
The server answers at most LIMIT calls in a tick; every other call that tick gets "too many requests" (HTTP 429).
All clients make their first call at tick 0. A refused client waits, then calls again, until it is served or has
used up its tries. The four rules differ only in how long the wait is. The same seed always gives the same run.
"""
from dataclasses import dataclass

CLIENTS = 20  # clients that all call at tick 0
LIMIT = 3  # calls the server answers per tick
TRIES = 6  # a client gives up after this many calls
FIXED = 4  # the fixed-wait rule: ticks between calls
BASE = 4  # backoff: the wait after the first refusal, in ticks
CAP = 16  # backoff: the longest wait, in ticks
SEED = 1  # the seed of the run the lesson shows
RULES = (("once", "Retry at once"), ("fixed", "Fixed wait"), ("backoff", "Backoff"), ("jitter", "Backoff with jitter"))

MASK = 0xFFFFFFFF


def random_numbers(seed):
    """Endless numbers in [0, 1), the same on every machine (the mulberry32 generator; widget.html has the same code)."""
    state = seed & MASK
    while True:
        state = (state + 0x6D2B79F5) & MASK
        t = ((state ^ (state >> 15)) * (state | 1)) & MASK
        t ^= (t + (((t ^ (t >> 7)) * (t | 61)) & MASK)) & MASK
        yield ((t ^ (t >> 14)) & MASK) / 4294967296


def wait_after(rule, refusals, draw):
    """Ticks to wait before the next call, after this many refusals so far (1 after the first)."""
    if rule == "once":
        return 1
    if rule == "fixed":
        return FIXED
    longest = min(CAP, BASE * 2 ** (refusals - 1))
    if rule == "backoff":
        return longest
    return 1 + int(draw() * longest)  # jitter: any whole number of ticks from 1 up to the longest wait


@dataclass(frozen=True)
class Run:
    rule: str
    served: tuple  # per tick: calls the server answered
    refused: tuple  # per tick: calls that got "too many requests"
    gave_up: int  # clients that used up their tries without being served

    @property
    def finished(self):
        """The tick of the last call anyone made."""
        return len(self.served) - 1

    @property
    def refused_calls(self):
        return sum(self.refused)

    @property
    def busiest_retry_tick(self):
        """The most calls in one tick after the first tick: the biggest wave of retries."""
        return max((s + r for s, r in zip(self.served[1:], self.refused[1:])), default=0)


def simulate(rule, seed=SEED, clients=CLIENTS, limit=LIMIT, tries=TRIES):
    draw = random_numbers(seed).__next__
    due = [0] * clients  # the tick of each client's next call; None once it is served or has given up
    refusals = [0] * clients
    served, refused, gave_up, tick = [], [], 0, 0
    while any(d is not None for d in due):
        calling = [c for c in range(clients) if due[c] == tick]
        for c in calling[:limit]:
            due[c] = None
        for c in calling[limit:]:
            refusals[c] += 1
            if refusals[c] == tries:
                due[c] = None
                gave_up += 1
            else:
                due[c] = tick + wait_after(rule, refusals[c], draw)
        served.append(min(len(calling), limit))
        refused.append(max(len(calling) - limit, 0))
        tick += 1
    return Run(rule, tuple(served), tuple(refused), gave_up)