"""Two rate-limiting algorithms, side by side: token bucket and sliding
window log. Both expose the same interface: allow(now) -> bool, where `now`
is a caller-supplied timestamp (seconds), so behavior is deterministic and
testable without real clocks or sleeps.
"""

from collections import deque


class TokenBucket:
    """Allows bursts up to `capacity`, then throttles to `refill_rate`
    tokens/sec steady state.
    """

    def __init__(self, capacity, refill_rate):
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.tokens = capacity
        self.last_refill = 0.0

    def allow(self, now):
        elapsed = now - self.last_refill
        self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
        self.last_refill = now

        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False


class SlidingWindowLog:
    """Allows at most `max_requests` in any trailing `window` seconds,
    tracked exactly via a log of request timestamps (no averaging/bucketing
    error, at the cost of O(window) memory per client).
    """

    def __init__(self, max_requests, window):
        self.max_requests = max_requests
        self.window = window
        self.log = deque()

    def allow(self, now):
        cutoff = now - self.window
        while self.log and self.log[0] <= cutoff:
            self.log.popleft()

        if len(self.log) < self.max_requests:
            self.log.append(now)
            return True
        return False