Implement an in-memory order book API

Problem

Implement an in-memory limit order book for a single trading symbol. You do not need to implement order matching/execution—only store and maintain orders and provide book queries.

The order book has two sides:

• BUY (bid) : higher price has higher priority.
• SELL (ask) : lower price has higher priority.

Within the same price level, orders follow FIFO (earlier timestamp first).

Order model

Each order has:

• order_id (unique string or integer)
• side ∈ {BUY, SELL}
• price (positive integer)
• qty (positive integer)
• ts (monotonic integer timestamp assigned at insertion; used for FIFO)

Required API

Design and implement a class (or module) with the following operations:

1. add(order_id, side, price, qty)
   • Inserts a new order.
   • Assume order_id does not already exist.
2. cancel(order_id)
   • Removes an existing order by id.
   • If the order does not exist, do nothing.
3. modify(order_id, new_qty)
   • Updates the quantity of an existing order.
   • If new_qty == 0 , treat it as cancel(order_id) .
   • If the order does not exist, do nothing.
4. best_bid() and best_ask()
   • Return the current best price and total quantity at that price level, e.g. (price, total_qty) .
   • If the side is empty, return None .
5. top_of_book()
   • Return both best bid and best ask (or None for a missing side).

Constraints / expectations

• Up to 2×10^5 operations .
• Target time complexity around O(log M) per operation, where M is the number of distinct price levels on a side.
• Memory should be O(N) in the number of live orders.

Notes

• No matching means adding a BUY order does not trade against existing SELL orders; both sides simply coexist.
• You may assume single-threaded execution unless you explicitly design for concurrency.