A web service lets each client make requests in bursts, but not too many over time. It keeps a bucket of tokens: the bucket holds at most capacity tokens and starts full at time 0. A new token arrives at every time that is a positive multiple of every (at every, 2 * every, ...); a token that arrives when the bucket is full is lost. A request at time t first receives the tokens that have arrived up to and including t; then it is served if there is a token, which it uses up. Otherwise it is refused, and the client is told how long to wait for the next token: the time from t to the next multiple of every after t.
Write a generator function limiter(capacity, every) that the service talks to with send. When started with next(gate) it yields None. After that, every gate.send(t) passes in the time of a request, and the value yielded back is the answer: 0 when the request is served, or the positive waiting time when it is refused.
Setup helpers you can use with Run: decide(limiter, capacity, every, times) starts your generator and sends each time; gateway(limiter, capacity, every, requests) runs one limiter per client for a list of (client, time) requests and returns the served count per client and the total waiting time quoted; traffic(seed, n, clients=3) generates requests.
Examples
Input: decide(limiter, 2, 5, [0, 0, 0, 3, 5, 5, 12, 20, 20, 20])
Output: [0, 0, 5, 2, 0, 5, 0, 0, 0, 5]
Explanation: two tokens at the start; the third request at time 0 waits 5. The token of time 5 serves one request; at 12 the token of time 10 has arrived; by 20 the tokens of 15 and 20 have filled the bucket again.
Input: gateway(limiter, 1, 10, [("ana", 0), ("bo", 1), ("ana", 4), ("ana", 10)])
Output: ([("ana", 2), ("bo", 1)], 6)
Constraints
1 <= capacity <= 1000,1 <= every <= 1000.- Request times are non-negative integers that never decrease for one limiter; up to 100,000 requests.
Goals
- Receive values inside a generator with `value = yield answer` and answer each one
- Keep a small state machine's state in a generator's local variables instead of a class
- Prime a generator with `next()` and understand why the first `send` must wait for it