"""Reference solution — Token-Level Streaming Differ with Rollback.

DO NOT READ BEFORE YOU HAVE RUN THE PROBLEM UNDER THE CLOCK.

--------------------------------------------------------------------------
The representation that survives all four gates
--------------------------------------------------------------------------

Gate 1 tempts you into keeping only a cursor. That is enough for gates 1 and
2 and collapses at gate 3, because rollback needs to know how much of the
event log to unwind.

Gate 3 then tempts you into snapshotting state per checkpoint. That is enough
for gate 3 and collapses at gate 4's memory bound, because undo needs
per-FEED granularity and there are far more feeds than checkpoints.

The representation that survives everything is a per-feed DELTA:

    history[i] = (cursor_before, n_events_emitted, token)

Three machine words per feed. From it:

    undo      pop the entry, truncate `events` by n_events, restore cursor
    redo      re-apply the recorded token
    checkpoint  remember (len(events), cursor, len(history)) -- O(1)
    rollback    truncate all three to the remembered lengths

Every operation is O(1) except the truncation, which is O(number of events
actually removed) and is therefore paid for by the work being undone.

The general lesson, which is the point of the gated format: when a problem
is going to grow undo-like requirements, store the DELTA, not the STATE.
Deltas compose (checkpoints are just delta-log positions); snapshots do not.
You cannot know gate 4 exists when you write gate 1 -- but you can ask "what
would break first if this needed to be reversible?" and let the answer pick
the representation.
"""

from __future__ import annotations

from typing import Iterable, Sequence

Event = tuple  # ("keep" | "insert" | "delete", token)


class StreamDiffer:
    """Incremental diff of a token stream against a known baseline."""

    __slots__ = (
        "baseline",
        "lookahead",
        "_cursor",
        "_events",
        "_history",
        "_redo",
        "_checkpoints",
        "_ckpt_order",
        "_closed",
    )

    def __init__(self, baseline: Sequence[str], lookahead: int = 8) -> None:
        self.baseline = tuple(baseline)
        if lookahead < 0:
            raise ValueError("lookahead must be non-negative")
        self.lookahead = lookahead
        self._cursor = 0
        self._events: list[Event] = []
        # (cursor_before, n_events_emitted, token) -- one per feed. O(1) each.
        self._history: list[tuple[int, int, str]] = []
        self._redo: list[str] = []
        self._checkpoints: dict[str, tuple[int, int, int]] = {}
        self._ckpt_order: list[str] = []
        self._closed = False

    # --- introspection -----------------------------------------------------

    @property
    def events(self) -> list[Event]:
        return list(self._events)

    @property
    def cursor(self) -> int:
        return self._cursor

    @property
    def closed(self) -> bool:
        return self._closed

    def stats(self) -> dict:
        counts = {"keep": 0, "insert": 0, "delete": 0}
        for kind, _ in self._events:
            counts[kind] += 1
        return {**counts, "feeds": len(self._history), "cursor": self._cursor}

    # --- gate 1 / gate 2 ---------------------------------------------------

    def _match_within_window(self, token: str) -> int | None:
        """Smallest j in (cursor, cursor+lookahead] with baseline[j] == token."""
        if self.lookahead <= 0:
            return None
        end = min(self._cursor + self.lookahead, len(self.baseline) - 1)
        for j in range(self._cursor + 1, end + 1):
            if self.baseline[j] == token:
                return j
        return None

    def _apply(self, token: str) -> list[Event]:
        """Apply one token and record the delta. Shared by feed() and redo()."""
        cursor_before = self._cursor
        emitted: list[Event] = []

        if self._cursor < len(self.baseline) and self.baseline[self._cursor] == token:
            emitted.append(("keep", token))
            self._cursor += 1
        else:
            j = self._match_within_window(token)
            if j is None:
                emitted.append(("insert", token))
            else:
                # The stream skipped baseline[cursor:j] -- those are deletions.
                for index in range(self._cursor, j):
                    emitted.append(("delete", self.baseline[index]))
                emitted.append(("keep", token))
                self._cursor = j + 1

        self._events.extend(emitted)
        self._history.append((cursor_before, len(emitted), token))
        return emitted

    def feed(self, token: str) -> list[Event]:
        if self._closed:
            raise RuntimeError("stream is closed")
        self._redo.clear()  # a new edit invalidates the redo branch
        return self._apply(token)

    def feed_all(self, tokens: Iterable[str]) -> list[Event]:
        out: list[Event] = []
        for token in tokens:
            out.extend(self.feed(token))
        return out

    def close(self) -> list[Event]:
        if self._closed:
            return []
        trailing = [
            ("delete", self.baseline[index])
            for index in range(self._cursor, len(self.baseline))
        ]
        self._events.extend(trailing)
        self._cursor = len(self.baseline)
        self._closed = True
        return trailing

    # --- gate 3 ------------------------------------------------------------

    def checkpoint(self, label: str) -> None:
        if self._closed:
            raise RuntimeError("stream is closed")
        if label in self._ckpt_order:
            self._ckpt_order.remove(label)
        self._checkpoints[label] = (len(self._events), self._cursor, len(self._history))
        self._ckpt_order.append(label)

    def labels(self) -> list[str]:
        return list(self._ckpt_order)

    def rollback(self, label: str) -> None:
        if self._closed:
            raise RuntimeError("stream is closed")
        if label not in self._checkpoints:
            raise KeyError(f"no live checkpoint {label!r}")
        n_events, cursor, n_history = self._checkpoints[label]
        del self._events[n_events:]
        del self._history[n_history:]
        self._cursor = cursor
        self._redo.clear()
        # Checkpoints taken after this one describe a history that no longer
        # exists, so they are invalidated rather than left dangling.
        position = self._ckpt_order.index(label)
        for later in self._ckpt_order[position + 1 :]:
            self._checkpoints.pop(later, None)
        del self._ckpt_order[position + 1 :]

    # --- gate 4 ------------------------------------------------------------

    def _drop_stale_checkpoints(self) -> None:
        stale = [
            label
            for label, (_, _, n_history) in self._checkpoints.items()
            if n_history > len(self._history)
        ]
        for label in stale:
            self._checkpoints.pop(label, None)
            if label in self._ckpt_order:
                self._ckpt_order.remove(label)

    def undo(self, n: int = 1) -> list[str]:
        if self._closed:
            raise RuntimeError("stream is closed")
        if n < 0:
            raise ValueError("n must be non-negative")
        if n > len(self._history):
            raise IndexError(
                f"cannot undo {n} feed(s); only {len(self._history)} in history"
            )
        undone: list[str] = []
        for _ in range(n):
            cursor_before, n_events, token = self._history.pop()
            if n_events:
                del self._events[len(self._events) - n_events :]
            self._cursor = cursor_before
            undone.append(token)
        self._redo.extend(undone)  # most-recently-undone ends up last
        self._drop_stale_checkpoints()
        return undone

    def redo(self, n: int = 1) -> list[str]:
        if self._closed:
            raise RuntimeError("stream is closed")
        if n < 0:
            raise ValueError("n must be non-negative")
        if n > len(self._redo):
            raise IndexError(f"cannot redo {n}; only {len(self._redo)} available")
        redone: list[str] = []
        for _ in range(n):
            token = self._redo.pop()
            self._apply(token)
            redone.append(token)
        return redone