Implement Price-Time Order Matching

Problem Statement

Implement an in-memory matching engine for a limit order book operating under price-time priority (FIFO).

When a new limit order enters the market:

1. It attempts to cross against existing resting orders on the opposite side of the book.
   • A BUY order matches against resting SELL orders where resting_sell_price = incoming_sell_price, starting from the highest buy price.
2. Tie-breaking (Time Priority): If multiple resting orders have the same price, the order submitted earliest must be filled first.
3. Execution Price: The match executes at the price of the resting order (maker price), not the incoming order.
4. Partial Fills: An order can be partially filled across multiple counter-orders until its quantity reaches zero or no valid matches remain. Any remaining unfilled quantity is placed in the book as a resting order.

Implement the OrderMatcher class with the following methods:

class OrderMatcher:
    def __init__(self):
        pass

    def add_order(self, order_id: int, side: str, price: int, quantity: int) -> list[tuple[int, int, int, int]]:
        """
        Submits a new limit order.
        side is either 'BUY' or 'SELL'.
        Returns a list of executed trades in the order they occur:
        [(buy_order_id, sell_order_id, match_price, match_quantity), ...]
        """
        pass

    def cancel_order(self, order_id: int) -> bool:
        """
        Cancels a resting order if it exists on the book.
        Returns True if the order was found and removed, False otherwise.
        """
        pass

Example

m = OrderMatcher()

# 1. Add BUY order 1: price 100, qty 10
m.add_order(1, "BUY", 100, 10)
# Output: [] (rests in book)

# 2. Add BUY order 2: price 101, qty 5
m.add_order(2, "BUY", 101, 5)
# Output: [] (rests in book)

# 3. Add SELL order 3: price 99, qty 8
# Best buy is order 2 (price 101, qty 5), followed by order 1 (price 100, needs 3)
m.add_order(3, "SELL", 99, 8)
# Output: [
#   (2, 3, 101, 5),  # Order 2 fully filled at resting price 101
#   (1, 3, 100, 3)   # Order 1 partially filled (7 left) at resting price 100
# ]

# 4. Cancel order 1
m.cancel_order(1)
# Output: True (remaining 7 qty removed)

# 5. Cancel non-existent / filled order 2
m.cancel_order(2)
# Output: False

Constraints

• 1 <= order_id <= 10^9 (unique across all add_order calls)
• side in ("BUY", "SELL")
• 1 <= price <= 10^6
• 1 <= quantity <= 10^6
• Up to 20,000 total calls to add_order and cancel_order.

Edge Cases

• Incoming order matches against multiple price levels and multiple orders at the same price level.
• Orders that match completely vs. orders that leave residual quantities.
• Canceling an order that has already been fully matched or never existed.