"""
p102 — Design Hit Counter (LC 362)

Window: trailing 300 seconds, inclusive, i.e., hits in [ts - 299, ts].

Designs:
 1. HitCounter        — deque of timestamps. O(1) amortized hit; O(n_stale) getHits.
 2. HitCounterBucket  — circular array of 300 (ts, count) buckets. Both ops O(300).
 3. HitCounterBrute   — list of all hits (oracle, unbounded).

INVARIANT (bucket design): a bucket's stored ts indicates which 300-window it counts toward.
If bucket.ts <= query_ts - 300, the bucket is stale and contributes 0 to the query.
"""
from __future__ import annotations
from collections import deque
from typing import Deque, List, Tuple
import random


WINDOW = 300


class HitCounter:
    """Deque of monotonic timestamps."""

    def __init__(self) -> None:
        self.q: Deque[int] = deque()

    def hit(self, ts: int) -> None:
        self.q.append(ts)

    def getHits(self, ts: int) -> int:
        # Evict timestamps <= ts - WINDOW (window is inclusive [ts-299, ts]).
        cutoff = ts - WINDOW
        while self.q and self.q[0] <= cutoff:
            self.q.popleft()
        return len(self.q)


class HitCounterBucket:
    """Circular array of WINDOW slots."""

    def __init__(self) -> None:
        self.bucket_ts: List[int] = [0] * WINDOW
        self.bucket_count: List[int] = [0] * WINDOW

    def hit(self, ts: int) -> None:
        i = ts % WINDOW
        if self.bucket_ts[i] == ts:
            self.bucket_count[i] += 1
        else:
            # Stale or empty -- overwrite.
            self.bucket_ts[i] = ts
            self.bucket_count[i] = 1

    def getHits(self, ts: int) -> int:
        cutoff = ts - WINDOW  # bucket.ts must be > cutoff to count
        total = 0
        for i in range(WINDOW):
            if self.bucket_ts[i] > cutoff and self.bucket_ts[i] <= ts:
                total += self.bucket_count[i]
        return total


class HitCounterBrute:
    """List of every hit; O(n) per query oracle."""

    def __init__(self) -> None:
        self.hits: List[int] = []

    def hit(self, ts: int) -> None:
        self.hits.append(ts)

    def getHits(self, ts: int) -> int:
        return sum(1 for t in self.hits if ts - WINDOW < t <= ts)


def edge_cases() -> None:
    # LC example
    c = HitCounter()
    c.hit(1)
    c.hit(2)
    c.hit(3)
    assert c.getHits(4) == 3
    c.hit(300)
    assert c.getHits(300) == 4
    assert c.getHits(301) == 3   # hit at ts=1 drops

    b = HitCounterBucket()
    b.hit(1); b.hit(2); b.hit(3)
    assert b.getHits(4) == 3
    b.hit(300)
    assert b.getHits(300) == 4
    assert b.getHits(301) == 3

    # Burst at same second
    b = HitCounterBucket()
    for _ in range(1000):
        b.hit(100)
    assert b.getHits(100) == 1000
    assert b.getHits(399) == 1000
    assert b.getHits(400) == 0

    # Bucket recycling across the wrap
    b = HitCounterBucket()
    b.hit(5)
    assert b.getHits(5) == 1
    # ts = 5 + 300 = 305 shares bucket index with 5
    b.hit(305)
    assert b.getHits(305) == 1   # the old hit at ts=5 must not be counted

    # Long quiet gap
    b = HitCounterBucket()
    b.hit(1)
    assert b.getHits(10_000) == 0

    print("edge_cases OK")


def stress_test(trials: int = 200, ops: int = 400) -> None:
    rng = random.Random(42)
    for t in range(trials):
        a = HitCounter()
        b = HitCounterBucket()
        c = HitCounterBrute()
        cur_ts = 1
        for _ in range(ops):
            # Monotonic: ts can stay the same or advance by 0..50
            cur_ts += rng.randint(0, 5)
            if rng.random() < 0.65:
                a.hit(cur_ts)
                b.hit(cur_ts)
                c.hit(cur_ts)
            else:
                qa, qb, qc = a.getHits(cur_ts), b.getHits(cur_ts), c.getHits(cur_ts)
                assert qa == qb == qc, (t, cur_ts, qa, qb, qc)
    print(f"stress_test OK ({trials} trials)")


if __name__ == "__main__":
    edge_cases()
    stress_test()