Fills Against a Resting Book

The first thing any matching engine does: take an incoming order, walk the resting side of the book, and work out what it trades against.

Implement fill_order(levels, qty, limit_price, side).

• levels is the resting opposite side, already in book order, best price first. Each entry is (price, available) with integer ticks and lots. For a buy these are asks in ascending price; for a sell they are bids in descending price.
• qty is the incoming quantity, a non-negative integer.
• limit_price bounds what the order will accept: a buy will not pay above it, a sell will not accept below it.
• side is 'B' or 'S'.

Walk the levels in order, consuming as much as the incoming order still needs at each. A level may be consumed partially, leaving the rest resting.

Return (fills, remaining) where fills is the list of (price, quantity) actually traded, in the order they occurred, and remaining is the unfilled quantity.

Examples

fill_order([(100, 5), (101, 10), (102, 7)], 12, 101, "B")
# ([(100, 5), (101, 7)], 0)

fill_order([(100, 5), (101, 10)], 20, 100, "B")
# ([(100, 5)], 15)

The first fills 5 at the touch and 7 of the 10 at the next level, leaving 3 resting there. The second cannot pay 101, so it stops after the first level with 15 lots unfilled.

Constraints

• 0 <= len(levels) <= 2 * 10^5, quantities and prices are positive integers.
• Levels are monotone in price, so once a level is out of reach of the limit price, every later one is too. Stop rather than skipping.
• A zero-quantity order fills nothing and an empty book fills nothing; neither is an error.
• Do not emit zero-quantity fills.