"""A circuit breaker (closed/open/half-open) and two dependencies to wrap.

Both dependencies expose the same interface: call(now, k) -> (ok, failed),
where `k` calls are offered at integer tick `now`. The breaker exposes
allow(now) -> bool and record(ok, now) -> None, with `now` supplied by the
caller. No clock, no sleeping, no randomness: a run is a pure function of
its arrival trace.

The point of the pairing: DeadDependency fails for reasons unrelated to how
much traffic it gets, and OverloadedDependency fails for no other reason.
The breaker cannot tell them apart, because the only measurement it ever
takes is a single call.
"""

from collections import deque, namedtuple

# One row of a simulation. `state` is the breaker's state *during* the tick:
# after admission was decided, before this tick's outcomes were recorded.
Tick = namedtuple(
    "Tick",
    "now arrivals state offered admitted ok failed pending dropped trips"
)


class CircuitBreaker:
    """Trips when the rolling error rate over the last `window` outcomes
    reaches `error_rate`, stays open for `cooldown` ticks, then admits at
    most `probes` calls per tick until one succeeds (close) or one fails
    (open again).
    """

    def __init__(self, window=20, min_calls=10, error_rate=0.5, cooldown=5,
                 probes=1):
        self.window = window
        self.min_calls = min_calls
        self.error_rate = error_rate
        self.cooldown = cooldown
        self.probes = probes
        self.state = "closed"
        self.outcomes = deque(maxlen=window)
        self.opened_at = None
        self.probe_tick = None
        self.probes_used = 0

    def allow(self, now):
        """Gate one call. The only place open -> half_open happens."""
        if self.state == "open":
            if now - self.opened_at < self.cooldown:
                return False
            self.state = "half_open"
            self.probe_tick = now
            self.probes_used = 0

        if self.state == "half_open":
            if now != self.probe_tick:      # a fresh tick gets a fresh budget
                self.probe_tick = now
                self.probes_used = 0
            if self.probes_used >= self.probes:
                return False
            self.probes_used += 1
            return True

        return True

    def record(self, ok, now):
        """Feed back the outcome of a call that allow() admitted."""
        if self.state == "half_open":
            # A probe is a verdict on the whole dependency, either way.
            if ok:
                self.state = "closed"
                self.outcomes.clear()
            else:
                self._trip(now)
            return

        self.outcomes.append(ok)
        if len(self.outcomes) < self.min_calls:
            return
        if self.outcomes.count(False) / len(self.outcomes) >= self.error_rate:
            self._trip(now)

    def _trip(self, now):
        self.state = "open"
        self.opened_at = now
        self.outcomes.clear()


class NoBreaker:
    """The control. Same interface, no opinion — every call goes through."""
    state = "closed"

    def allow(self, now):
        return True

    def record(self, ok, now):
        pass


class DeadDependency:
    """Fails every call between tick `down` and tick `up`, and succeeds
    every call outside that interval. `k` is ignored: how much load it is
    offered has no bearing on whether it works.
    """

    def __init__(self, down, up):
        self.down, self.up = down, up

    def call(self, now, k):
        if self.down <= now < self.up:
            return 0, k
        return k, 0


class OverloadedDependency:
    """Serves `capacity` calls per tick and rejects the rest. `now` is
    ignored: the offered load `k` is the only thing that decides whether a
    call fails. It is never "down" — at k <= capacity it is perfect.
    """

    def __init__(self, capacity):
        self.capacity = capacity

    def call(self, now, k):
        ok = min(k, self.capacity)
        return ok, k - ok


def simulate(dependency, breaker, arrivals, max_attempts=None):
    """Drive `dependency` through `breaker` with one request per arrival.

    A request shed by the breaker or failed by the dependency is retried on
    the next tick — until it succeeds if `max_attempts` is None, otherwise
    dropped after that many attempts. This retry loop is not decoration: it
    is what turns a shed request into a herd waiting at the door for the
    moment the breaker closes.
    """
    pending = []                       # attempts already spent, per request
    rows = []
    dropped = 0
    trips = 0

    for now, arriving in enumerate(arrivals):
        queue = pending + [0] * arriving
        pending = []
        admitted = []

        for attempts in queue:
            if breaker.allow(now):
                admitted.append(attempts)
            elif max_attempts is not None and attempts + 1 >= max_attempts:
                dropped += 1
            else:
                pending.append(attempts + 1)

        state = breaker.state          # the state these calls were made under
        ok, failed = dependency.call(now, len(admitted))

        for _ in range(ok):
            breaker.record(True, now)
        for _ in range(failed):
            breaker.record(False, now)

        # Counted here, not inferred from `state` later: a short cooldown can
        # carry open -> half_open inside the next allow(), leaving no row.
        if state != "open" and breaker.state == "open":
            trips += 1

        for attempts in admitted[ok:]:
            if max_attempts is not None and attempts + 1 >= max_attempts:
                dropped += 1
            else:
                pending.append(attempts + 1)

        rows.append(Tick(now, arriving, state, len(queue), len(admitted),
                         ok, failed, len(pending), dropped, trips))

    return rows


def totals(rows):
    """Summary of a run: what got through, what was spent getting there."""
    return {
        "completed": sum(r.ok for r in rows),
        "calls": sum(r.admitted for r in rows),
        "failed_calls": sum(r.failed for r in rows),
        "shed": sum(r.offered - r.admitted for r in rows),
        "trips": rows[-1].trips,
        "backlog": rows[-1].pending,
        "dropped": rows[-1].dropped,
    }


def drained_at(rows, after):
    """First tick at or after `after` with nothing queued and nothing
    failing — when the incident is genuinely over. None if never.
    """
    for r in rows:
        if r.now >= after and r.pending == 0 and r.failed == 0:
            return r.now
    return None