Limit Order Book

A stock exchange keeps an order book of buy and sell orders. Each order offers to trade some quantity at a limit price, and new orders are matched like this:

• A buy order with limit price p trades with resting sell orders whose price is at most p, cheapest first. Among sell orders at the same price, the one that arrived first trades first.
• A sell order with limit price p trades with resting buy orders whose price is at least p, highest first, and again the earliest first at the same price.
• Each trade happens at the resting order's price, for as much quantity as both orders still have. The new order keeps trading until it is filled or nothing else matches, and whatever is left of it then rests in the book.

Build an OrderBook class:

• OrderBook() starts with an empty book.
• buy(order_id, price, quantity) and sell(order_id, price, quantity) place a new order and return the list of trades it made, in the order they happened, as (resting_order_id, price, quantity) tuples. An empty list means no trade.
• cancel(order_id) removes what is left of a resting order and returns the quantity removed. If that order is not resting in the book (it was filled, already cancelled, or never existed), it returns 0.
• best_bid() returns the highest price of a resting buy order, and best_ask() the lowest price of a resting sell order; each returns None when that side of the book is empty.

Examples

ob = OrderBook()
ob.sell(1, 101, 5)     # returns []
ob.sell(2, 100, 3)     # returns []
ob.sell(3, 101, 4)     # returns []
ob.buy(4, 101, 10)     # returns [(2, 100, 3), (1, 101, 5), (3, 101, 2)]
ob.best_ask()          # returns 101    (order 3 has 2 left)
ob.cancel(3)           # returns 2
ob.best_ask()          # returns None
ob.buy(5, 99, 7)       # returns []
ob.sell(6, 98, 10)     # returns [(5, 99, 7)]
ob.best_ask()          # returns 98     (order 6 rests with 3 left)

The buy order 4 first takes the cheapest sell order (2, at 100), then the two at 101 in the order they arrived. The sell order 6 trades at 99, the resting buy order's price.

Constraints

• Up to 100,000 calls; order ids are different positive whole numbers, and prices and quantities are whole numbers from 1 to 10^9
• With tens of thousands of resting orders, searching the whole book for the best price on every call is too slow.