Match Limit Orders with Price-Time Priority

Problem Statement

Design and implement an in-memory limit order matching engine. The engine receives a sequence of limit orders and matches them based on standard price-time priority.

Each order has:

• order_id: A unique string identifier.
• side: Either "BUY" or "SELL".
• price: An integer representing the limit price.
• quantity: A positive integer representing the number of units to trade.

Matching Rules

1. Price-Time Priority:
   • Buy orders (Bids): Prioritize highest price first. For matching prices, prioritize earlier arrival time (FIFO).
   • Sell orders (Asks): Prioritize lowest price first. For matching prices, prioritize earlier arrival time (FIFO).
2. Crossing Conditions:
   • An incoming BUY order matches with resting SELL orders if buy_price >= sell_price.
   • An incoming SELL order matches with resting BUY orders if sell_price <= buy_price.
3. Execution Price:
   • Trades always execute at the price of the resting order (the passive maker order already in the book), never the incoming taker order's price.
4. Partial Fills & Residuals:
   • An order matches as much quantity as possible against eligible resting orders.
   • If the resting order is partially filled, it remains at the top of its price level with its remaining quantity and its original arrival priority.
   • Any unmatched remaining quantity of the incoming order rests in the book.

Interface

Implement the following function:

def match_orders(orders: list[tuple[str, str, int, int]]) -> tuple[
    list[tuple[str, str, int, int]], 
    list[tuple[str, int, int]], 
    list[tuple[str, int, int]]
]:
    """
    Processes a list of orders in arrival order.
    
    Args:
        orders: List of (order_id, side, price, quantity) where side is 'BUY' or 'SELL'.
        
    Returns:
        A tuple of (trades, remaining_bids, remaining_asks):
          - trades: List of (maker_order_id, taker_order_id, trade_price, trade_quantity)
                    in chronological order of execution.
          - remaining_bids: List of (order_id, price, quantity) sorted by best bid first
                            (highest price, then earliest arrival).
          - remaining_asks: List of (order_id, price, quantity) sorted by best ask first
                            (lowest price, then earliest arrival).
    """
    pass

Constraints

• 1 <= len(orders) <= 10^5
• 1 <= price <= 10^9
• 1 <= quantity <= 10^9
• order_id consists of alphanumeric characters and is unique per order.
• Total execution time should scale efficiently (logarithmic insertion and matching per order level).

Example

orders = [
    ("B1", "BUY", 100, 10),
    ("B2", "BUY", 102, 5),
    ("S1", "SELL", 103, 10),
    ("S2", "SELL", 101, 8)
]

trades, bids, asks = match_orders(orders)

Step-by-step Trace:

1. B1 rests: Bids: [B1: (100, 10)]
2. B2 rests: Bids: [B2: (102, 5), B1: (100, 10)]
3. S1 arrives (Ask 103): Does not cross (103 > 102). Asks: [S1: (103, 10)]
4. S2 arrives (Ask 101, qty 8): Crosses with B2 (`101 100, so no further match.
   • Remaining S2 quantity (3) rests in book.

Output:

trades = [("B2", "S2", 102, 5)]
remaining_bids = [("B1", 100, 10)]
remaining_asks = [("S2", 101, 3), ("S1", 103, 10)]