"""
p98 — Design Circular Queue (LC 622)

INVARIANT (ring representation): the queue's logical elements live at indices
  [front, front+1, ..., front+size-1] mod k. Rear = (front + size - 1) mod k.
  Next-write slot = (front + size) mod k.

INVARIANT (no ambiguity): `size` disambiguates full (size == k) from empty
  (size == 0); we never have to compare front and rear.
"""
from __future__ import annotations

import random
from collections import deque
from typing import List, Tuple


class MyCircularQueue:
    """Ring buffer using front + size. All ops O(1)."""

    def __init__(self, k: int):
        self.arr: List[int] = [0] * k
        self.k = k
        self.front = 0
        self.size = 0

    def enQueue(self, value: int) -> bool:
        if self.size == self.k:
            return False
        self.arr[(self.front + self.size) % self.k] = value
        self.size += 1
        return True

    def deQueue(self) -> bool:
        if self.size == 0:
            return False
        self.front = (self.front + 1) % self.k
        self.size -= 1
        return True

    def Front(self) -> int:
        if self.size == 0:
            return -1
        return self.arr[self.front]

    def Rear(self) -> int:
        if self.size == 0:
            return -1
        return self.arr[(self.front + self.size - 1) % self.k]

    def isEmpty(self) -> bool:
        return self.size == 0

    def isFull(self) -> bool:
        return self.size == self.k


class MyCircularQueueDeque:
    """Brute oracle using deque(maxlen=k)."""

    def __init__(self, k: int):
        self.k = k
        self.dq: deque = deque(maxlen=k)

    def enQueue(self, value: int) -> bool:
        if len(self.dq) == self.k:
            return False
        self.dq.append(value)
        return True

    def deQueue(self) -> bool:
        if not self.dq:
            return False
        self.dq.popleft()
        return True

    def Front(self) -> int:
        return self.dq[0] if self.dq else -1

    def Rear(self) -> int:
        return self.dq[-1] if self.dq else -1

    def isEmpty(self) -> bool:
        return len(self.dq) == 0

    def isFull(self) -> bool:
        return len(self.dq) == self.k


def edge_cases() -> None:
    q = MyCircularQueue(3)
    assert q.enQueue(1) is True
    assert q.enQueue(2) is True
    assert q.enQueue(3) is True
    assert q.enQueue(4) is False  # full
    assert q.Rear() == 3
    assert q.isFull() is True
    assert q.deQueue() is True
    assert q.enQueue(4) is True  # wrap
    assert q.Rear() == 4
    assert q.Front() == 2

    # Empty.
    q2 = MyCircularQueue(2)
    assert q2.Front() == -1
    assert q2.Rear() == -1
    assert q2.deQueue() is False
    assert q2.isEmpty() is True

    # k == 1.
    q3 = MyCircularQueue(1)
    assert q3.enQueue(7) is True
    assert q3.enQueue(8) is False
    assert q3.Front() == 7
    assert q3.Rear() == 7
    assert q3.deQueue() is True
    assert q3.isEmpty() is True


def _run_sequence(q, ops: List[Tuple[str, int]]) -> List:
    results = []
    for op, v in ops:
        if op == "enQ":
            results.append(q.enQueue(v))
        elif op == "deQ":
            results.append(q.deQueue())
        elif op == "Front":
            results.append(q.Front())
        elif op == "Rear":
            results.append(q.Rear())
        elif op == "isEmpty":
            results.append(q.isEmpty())
        elif op == "isFull":
            results.append(q.isFull())
    return results


def stress_test() -> None:
    rng = random.Random(42)
    ops_pool = ["enQ", "deQ", "Front", "Rear", "isEmpty", "isFull"]
    for _ in range(200):
        k = rng.randint(1, 6)
        n_ops = rng.randint(1, 40)
        ops: List[Tuple[str, int]] = []
        for _ in range(n_ops):
            op = rng.choice(ops_pool)
            v = rng.randint(0, 100) if op == "enQ" else 0
            ops.append((op, v))
        a = _run_sequence(MyCircularQueue(k), ops)
        b = _run_sequence(MyCircularQueueDeque(k), ops)
        assert a == b, (k, ops, a, b)


if __name__ == "__main__":
    edge_cases()
    stress_test()
    print("ALL TESTS PASSED")