def __lt__(self, other): if self.order_type == 'buy': # For buy orders, higher prices have priority; if prices are equal, earlier orders have priority return (self.price, -self.timestamp) > (other.price, -other.timestamp) else: # For sell orders, lower prices have priority; if prices are equal, earlier orders have priority return (self.price, self.timestamp) < (other.price, other.timestamp)
class OrderBook: def __init__(self): self.buy_orders = [] # Max-heap for buy orders (negative prices for max-heap) self.sell_orders = [] # Min-heap for sell orders self.timestamp_counter = 0
while buy_prices and sell_prices: highest_buy_price = buy_prices[0] lowest_sell_price = sell_prices[0]
if highest_buy_price >= lowest_sell_price: buy_orders_at_price = self.buy_orders[highest_buy_price] sell_orders_at_price = self.sell_orders[lowest_sell_price]
# Calculate total buy and sell quantities at this price total_buy_quantity = sum(order.quantity for order in buy_orders_at_price) total_sell_quantity = sum(order.quantity for order in sell_orders_at_price)
# Determine the amount to trade based on the smaller side quantity_to_trade = min(total_buy_quantity, total_sell_quantity)
# Pro-rata allocation for buy and sell orders for order in buy_orders_at_price: proportion = order.quantity / total_buy_quantity traded_quantity = quantity_to_trade * proportion matches.append((order.order_id, lowest_sell_price, traded_quantity)) order.quantity -= traded_quantity
for order in sell_orders_at_price: proportion = order.quantity / total_sell_quantity traded_quantity = quantity_to_trade * proportion matches.append((order.order_id, highest_buy_price, traded_quantity)) order.quantity -= traded_quantity
# Remove fully matched orders self.buy_orders[highest_buy_price] = [o for o in buy_orders_at_price if o.quantity > 0] self.sell_orders[lowest_sell_price] = [o for o in sell_orders_at_price if o.quantity > 0]
if not self.buy_orders[highest_buy_price]: del self.buy_orders[highest_buy_price] buy_prices.pop(0)
if not self.sell_orders[lowest_sell_price]: del self.sell_orders[lowest_sell_price] sell_prices.pop(0) else: break
while buy_prices and sell_prices: highest_buy_price = buy_prices[0] lowest_sell_price = sell_prices[0]
if highest_buy_price >= lowest_sell_price: buy_orders_at_price = self.buy_orders[highest_buy_price] sell_orders_at_price = self.sell_orders[lowest_sell_price]
# Calculate total buy and sell quantities at this price total_buy_quantity = sum(order.quantity for order in buy_orders_at_price) total_sell_quantity = sum(order.quantity for order in sell_orders_at_price)
# Determine the amount to trade based on the smaller side quantity_to_trade = min(total_buy_quantity, total_sell_quantity)
# Priority based matching and then pro-rata allocation while quantity_to_trade > 0 and buy_orders_at_price and sell_orders_at_price: buy_order = buy_orders_at_price[0] sell_order = sell_orders_at_price[0]
