Top-of-Book Ticker

You are building the ticker component of a market data feed: after every order book event, it must publish the current top of book (best bid and best ask).

You receive a sequence of events. Each event is one of:

• an add event with an order_id, a side, a price and a qty: a new limit order enters the book. side is B for a bid (buy) or S for an ask (sell). Prices are integer ticks. order_id values of add events are unique.
• a cancel event with an order_id: the order leaves the book. A cancel may reference an id that was never added or was already cancelled; treat that as a no-op.

Implement top_of_book(events) returning one entry per event: the pair (best_bid, best_ask) immediately after applying that event. The best bid is the highest live bid price, the best ask is the lowest live ask price. A side with no live orders has no price. Order quantity never changes and does not affect the top of book in this problem.

def top_of_book(
    events: list[tuple[str, int, str, int, int] | tuple[str, int]],
) -> list[tuple[int | None, int | None]]: ...

An add is ("add", order_id, side, price, qty) with side as "B" or "S", and a cancel is ("cancel", order_id). Use None for a side with no live orders.

Orders are never matched against each other. A bid at or above the best ask does not trade: both orders stay live until they are cancelled, so the book can be crossed (best bid greater than or equal to best ask).

Example

events = [
    ("add", 1, "B", 100, 5),
    ("add", 2, "S", 102, 3),
    ("add", 3, "B", 101, 2),
    ("cancel", 3),
]
top_of_book(events)
# [(100, None), (100, 102), (101, 102), (100, 102)]

Constraints

• Up to \(10^5\) events.
• Prices are positive integers; multiple live orders may share a price.
• Your solution must handle the event volume comfortably: recomputing the best price by scanning every live order on every event will not finish in time.