Implementiere einen deterministischen Limit-Order-Book-Simulator

from itertools import count

def _is_pos_int(v):
return isinstance(v, int) and not isinstance(v, bool) and v > 0

def process_events(events):
trades = []
rejected = []

# Resting book stored as dicts keyed by id; we keep a global sequence
# for time priority.
seq = count()

used_ids = set()  # all ids ever accepted as new orders
resting = {}  # id -> order dict {id, side, price, qty, seq}
bids = {}  # id -> order (side buy)
asks = {}  # id -> order (side sell)

def reject(idx, event, reason):
    rejected.append({"input_index": idx, "event": event, "reason": reason})

def sorted_asks():
    # ascending price, then seq
    return sorted(asks.values(), key=lambda o: (o["price"], o["seq"]))

def sorted_bids():
    # descending price, then seq
    return sorted(bids.values(), key=lambda o: (-o["price"], o["seq"]))

def can_cross_buy(buy_is_market, buy_price, ask_price):
    if buy_is_market:
        return True
    return ask_price <= buy_price

def can_cross_sell(sell_is_market, sell_price, bid_price):
    if sell_is_market:
        return True
    return bid_price >= sell_price

def fillable_qty_buy(is_market, price, qty):
    remaining = qty
    for ask in sorted_asks():
        if remaining <= 0:
            break
        if not can_cross_buy(is_market, price, ask["price"]):
            break
        remaining -= min(remaining, ask["qty"])
    return qty - remaining

def fillable_qty_sell(is_market, price, qty):
    remaining = qty
    for bid in sorted_bids():
        if remaining <= 0:
            break
        if not can_cross_sell(is_market, price, bid["price"]):
            break
        remaining -= min(remaining, bid["qty"])
    return qty - remaining

def execute_buy(order_id, is_market, price, qty):
    remaining = qty
    while remaining > 0:
        book_asks = sorted_asks()
        if not book_asks:
            break
        best = book_asks[0]
        if not can_cross_buy(is_market, price, best["price"]):
            break
        tq = min(remaining, best["qty"])
        trades.append({
            "buy_id": order_id,
            "sell_id": best["id"],
            "price": best["price"],
            "qty": tq,
            "taker_id": order_id,
            "maker_id": best["id"],
        })
        remaining -= tq
        best["qty"] -= tq
        if best["qty"] == 0:
            del asks[best["id"]]
            resting.pop(best["id"], None)
    return remaining

def execute_sell(order_id, is_market, price, qty):
    remaining = qty
    while remaining > 0:
        book_bids = sorted_bids()
        if not book_bids:
            break
        best = book_bids[0]
        if not can_cross_sell(is_market, price, best["price"]):
            break
        tq = min(remaining, best["qty"])
        trades.append({
            "buy_id": best["id"],
            "sell_id": order_id,
            "price": best["price"],
            "qty": tq,
            "taker_id": order_id,
            "maker_id": best["id"],
        })
        remaining -= tq
        best["qty"] -= tq
        if best["qty"] == 0:
            del bids[best["id"]]
            resting.pop(best["id"], None)
    return remaining

for idx, event in enumerate(events):
    if not isinstance(event, dict):
        reject(idx, event, "event is not a dict")
        continue

    etype = event.get("type")
    if etype not in ("new", "cancel"):
        reject(idx, event, "invalid or missing type")
        continue

    if etype == "cancel":
        if "id" not in event:
            reject(idx, event, "cancel missing id")
            continue
        cid = event["id"]
        if cid not in resting:
            reject(idx, event, "cancel for unknown or non-resting id")
            continue
        o = resting.pop(cid)
        if o["side"] == "buy":
            bids.pop(cid, None)
        else:
            asks.pop(cid, None)
        continue

    # new order
    if "id" not in event:
        reject(idx, event, "new order missing id")
        continue
    oid = event["id"]

    side = event.get("side")
    order_type = event.get("order_type")
    qty = event.get("qty")

    if side not in ("buy", "sell"):
        reject(idx, event, "invalid or missing side")
        continue
    if order_type not in ("limit", "market"):
        reject(idx, event, "invalid or missing order_type")
        continue
    if not _is_pos_int(qty):
        reject(idx, event, "qty must be a positive integer")
        continue

    price = None
    if order_type == "limit":
        if "price" not in event:
            reject(idx, event, "limit order missing price")
            continue
        price = event["price"]
        if not _is_pos_int(price):
            reject(idx, event, "price must be a positive integer")
            continue

    # time-in-force
    if "tif" in event:
        tif = event["tif"]
        if tif not in ("GTC", "IOC", "FOK"):
            reject(idx, event, "invalid tif")
            continue
        if order_type == "market" and tif == "GTC":
            reject(idx, event, "market order may not be GTC")
            continue
    else:
        tif = "GTC" if order_type == "limit" else "IOC"

    # duplicate id check (after structural validation)
    if oid in used_ids:
        reject(idx, event, "duplicate order id")
        continue

    # Accept the order: register its id now.
    used_ids.add(oid)

    is_market = order_type == "market"

    if tif == "FOK":
        if side == "buy":
            fillable = fillable_qty_buy(is_market, price, qty)
        else:
            fillable = fillable_qty_sell(is_market, price, qty)
        if fillable < qty:
            # not completely fillable; no trades, no book change
            continue
        # completely fillable, execute normally
        if side == "buy":
            execute_buy(oid, is_market, price, qty)
        else:
            execute_sell(oid, is_market, price, qty)
        continue

    # IOC and GTC
    if side == "buy":
        remaining = execute_buy(oid, is_market, price, qty)
    else:
        remaining = execute_sell(oid, is_market, price, qty)

    if remaining > 0:
        if tif == "GTC" and not is_market:
            order = {
                "id": oid,
                "side": side,
                "price": price,
                "qty": remaining,
                "seq": next(seq),
            }
            resting[oid] = order
            if side == "buy":
                bids[oid] = order
            else:
                asks[oid] = order
        # IOC: cancel remainder (do nothing)

book = {
    "bids": [
        {"id": o["id"], "price": o["price"], "qty": o["qty"]} 
        for o in sorted_bids()
    ],
    "asks": [
        {"id": o["id"], "price": o["price"], "qty": o["qty"]} 
        for o in sorted_asks()
    ],
}

return {"trades": trades, "rejected": rejected, "book": book}

if name == "main":
evs = [
{"type": "new", "id": "a", "side": "sell", "order_type": "limit", "qty": 10, "price": 100},
{"type": "new", "id": "b", "side": "sell", "order_type": "limit", "qty": 5, "price": 101},
{"type": "new", "id": "c", "side": "buy", "order_type": "limit", "qty": 12, "price": 100},
{"type": "new", "id": "d", "side": "buy", "order_type": "market", "qty": 3},
{"type": "new", "id": "a", "side": "buy", "order_type": "limit", "qty": 1, "price": 50},
{"type": "cancel", "id": "b"},
{"type": "new", "id": "e", "side": "buy", "order_type": "limit", "qty": 0, "price": 100},
{"type": "new", "id": "f", "side": "buy", "order_type": "limit", "qty": True, "price": 100},
{"type": "new", "id": "g", "side": "buy", "order_type": "limit", "qty": 100, "price": 90, "tif": "FOK"},
]
result = process_events(evs)
assert result["trades"][0] == {"buy_id": "c", "sell_id": "a", "price": 100, "qty": 10, "taker_id": "c", "maker_id": "a"}
assert any(r["reason" == "duplicate order id" for r in result["rejected"]]
assert any["qty must be a positive integer" in r["reason"] for r in result["rejected"]]
print("self-tests passed")

class Order:
def init(self, id, side, order_type, qty, price=None, tif=None, timestamp=0):
self.id = id
self.side = side
self.order_type = order_type
self.qty = qty
self.price = price
self.tif = tif
self.timestamp = timestamp

def to_book_entry(self):
    return {"id": self.id, "price": self.price, "qty": self.qty}

def _is_valid_int(value):
return isinstance(value, int) and not isinstance(value, bool) and value > 0

def _reject_event(rejected_list, input_index, event, reason):
rejected_list.append({"input_index": input_index, "event": event, "reason": reason})

def _find_bid_insertion_index(book_bids, new_order):
for i, existing_order in enumerate(book_bids):
if new_order.price > existing_order.price:
return i
if new_order.price == existing_order.price and new_order.timestamp < existing_order.timestamp:
return i
return len(book_bids)

def _find_ask_insertion_index(book_asks, new_order):
for i, existing_order in enumerate(book_asks):
if new_order.price < existing_order.price:
return i
if new_order.price == existing_order.price and new_order.timestamp < existing_order.timestamp:
return i
return len(book_asks)

def _add_order_to_book(order, book_bids, book_asks, active_orders):
if order.side == "buy":
idx = _find_bid_insertion_index(book_bids, order)
book_bids.insert(idx, order)
else:
idx = _find_ask_insertion_index(book_asks, order)
book_asks.insert(idx, order)
active_orders[order.id] = order

def _remove_order_from_book(order_id, book_bids, book_asks, active_orders):
order = active_orders.pop(order_id, None)
if order:
if order.side == "buy":
if order in book_bids:
book_bids.remove(order)
else:
if order in book_asks:
book_asks.remove(order)

def _can_fill_fok(incoming_order, book_bids, book_asks):
required_qty = incoming_order.qty
fillable_qty = 0
if incoming_order.side == "buy":
maker_candidates = sorted(book_asks, key=lambda x: (x.price, x.timestamp))
def can_cross_fok(taker_price, maker_price):
if incoming_order.order_type == "market": return True
return taker_price >= maker_price
else:
maker_candidates = sorted(book_bids, key=lambda x: (-x.price, x.timestamp))
def can_cross_fok(taker_price, maker_price):
if incoming_order.order_type == "market": return True
return taker_price <= maker_price
for maker_order in maker_candidates:
if maker_order.qty == 0:
continue
if can_cross_fok(incoming_order.price, maker_order.price):
fillable_qty += maker_order.qty
if fillable_qty >= required_qty:
return True
else:
break
return False

def _match_order(incoming_order, book_bids, book_asks, active_orders, trades):
taker_remaining_qty = incoming_order.qty
if incoming_order.side == "buy":
maker_candidates = sorted(book_asks, key=lambda x: (x.price, x.timestamp))
def can_cross(taker_price, maker_price):
if incoming_order.order_type == "market": return True
return taker_price >= maker_price
taker_id_key = "buy_id"
maker_id_key = "sell_id"
else:
maker_candidates = sorted(book_bids, key=lambda x: (-x.price, x.timestamp))
def can_cross(taker_price, maker_price):
if incoming_order.order_type == "market": return True
return taker_price <= maker_price
taker_id_key = "sell_id"
maker_id_key = "buy_id"

if incoming_order.tif == "FOK":
    if not _can_fill_fok(incoming_order, book_bids, book_asks):
        return 0

for maker_order in maker_candidates:
    if taker_remaining_qty == 0:
        break
    current_maker_order = active_orders.get(maker_order.id)
    if not current_maker_order or current_maker_order.qty == 0:
        continue

    if can_cross(incoming_order.price, current_maker_order.price):
        trade_qty = min(taker_remaining_qty, current_maker_order.qty)
        trade_price = current_maker_order.price
        trade_record = {
            taker_id_key: incoming_order.id,
            maker_id_key: current_maker_order.id,
            "price": trade_price,
            "qty": trade_qty,
            "taker_id": incoming_order.id,
            "maker_id": current_maker_order.id
        }
        trades.append(trade_record)

        taker_remaining_qty -= trade_qty
        current_maker_order.qty -= trade_qty

        if current_maker_order.qty == 0:
            _remove_order_from_book(current_maker_order.id, book_bids, book_asks, active_orders)
    else:
        break

return taker_remaining_qty

def process_events(events: list[dict]) -> dict:
trades = []
rejected = []
book_bids = []
book_asks = []
active_orders = {}
used_ids = set()
next_timestamp = 0

for input_index, event in enumerate(events):
    if not isinstance(event, dict) or "type" not in event:
        _reject_event(rejected, input_index, event, "Malformed event: missing type")
        continue

    event_type = event["type"]

    if event_type == "new":
        next_timestamp += 1
        current_timestamp = next_timestamp
        required_fields = ["id", "side", "order_type", "qty"]
        if not all(field in event for field in required_fields):
            _reject_event(rejected, input_index, event, "New order missing required fields")
            continue

        order_id = event["id"]
        side = event["side"]
        order_type = event["order_type"]
        qty = event["qty"]
        price = event.get("price")
        tif = event.get("tif")

        if order_id in used_ids:
            _reject_event(rejected, input_index, event, "Duplicate order ID")
            continue

        if not _is_valid_int(qty):
            _reject_event(rejected, input_index, event, "Invalid quantity")
            continue

        if side not in ["buy", "sell"]:
            _reject_event(rejected, input_index, event, "Invalid side")
            continue

        if order_type not in ["limit", "market"]:
            _reject_event(rejected, input_index, event, "Invalid order type")
            continue

        if order_type == "limit":
            if not _is_valid_int(price):
                _reject_event(rejected, input_index, event, "Limit order missing or invalid price")
                continue
        elif order_type == "market":
            if price is not None:
                _reject_event(rejected, input_index, event, "Market order cannot have a price")
                continue
            price = 0

        if tif is None:
            tif = "GTC" if order_type == "limit" else "IOC"

        if tif not in ["GTC", "IOC", "FOK"]:
            _reject_event(rejected, input_index, event, "Invalid time-in-force")
            continue

        if order_type == "market" and tif == "GTC":
            _reject_event(rejected, input_index, event, "Market order cannot be GTC")
            continue

        used_ids.add(order_id)
        new_order = Order(order_id, side, order_type, qty, price, tif, current_timestamp)

        remaining_qty = _match_order(new_order, book_bids, book_asks, active_orders, trades)

        if remaining_qty > 0:
            if new_order.tif == "GTC" and new_order.order_type == "limit":
                new_order.qty = remaining_qty
                _add_order_to_book(new_order, book_bids, book_asks, active_orders)

    elif event_type == "cancel":
        required_fields = ["id"]
        if not all(field in event for field in required_fields):
            _reject_event(rejected, input_index, event, "Cancel event missing required fields")
            continue
        order_id = event["id"]
        if order_id not in active_orders:
            _reject_event(rejected, input_index, event, "Cancel order ID not found or not resting")
            continue
        _remove_order_from_book(order_id, book_bids, book_asks, active_orders)
    else:
        _reject_event(rejected, input_index, event, "Unknown event type")
        continue

final_book = {
    "bids": [order.to_book_entry() for order in book_bids],
    "asks": [order.to_book_entry() for order in book_asks]
}

return {"trades": trades, "rejected": rejected, "book": final_book}

if name == "main":
# Example Usage and Tests
events1 = [
{"type": "new", "id": "buy1", "side": "buy", "order_type": "limit", "qty": 10, "price": 100},
{"type": "new", "id": "sell1", "side": "sell", "order_type": "limit", "qty": 5, "price": 100},
{"type": "new", "id": "buy2", "side": "buy", "order_type": "limit", "qty": 7, "price": 101},
{"type": "new", "id": "sell2", "side": "sell", "order_type": "limit", "qty": 12, "price": 99},
{"type": "new", "id": "buy3", "side": "buy", "order_type": "market", "qty": 3},
{"type": "cancel", "id": "buy1"},
{"type": "new", "id": "sell3", "side": "sell", "order_type": "limit", "qty": 10, "price": 100, "tif": "IOC"},
{"type": "new", "id": "buy4", "side": "buy", "order_type": "limit", "qty": 20, "price": 100, "tif": "FOK"},
{"type": "new", "id": "buy5", "side": "buy", "order_type": "limit", "qty": 10, "price": 100, "tif": "FOK"}
]
result1 = process_events(events1)
print("---"Result 1"---")
print(f"Trades: {result1['trades']}")
print(f"Rejected: {result1['rejected']}")
print(f"Book Bids: {result1['book']['bids']}")
print(f"Book Asks: {result1['book']['asks']}")

# Expected:
# Trades:
# 1. sell2 (maker) matches buy2 (taker): price 99, qty 7. sell2 remaining 5.
# 2. sell2 (maker) matches buy3 (taker): price 99, qty 3. sell2 remaining 2.
# 3. sell1 (maker) matches sell3 (taker): price 100, qty 5. sell1 filled. sell3 filled.
# Rejected:
# 1. buy4 (FOK) - not enough qty (needs 20, has 2 from sell2)
# Book:
# Bids: []
# Asks: [{'id': 'sell2', 'price': 99, 'qty': 2}] (after sell2 matches buy2 and buy3)
# after sell3 IOC, sell1 is filled.
# buy1 is cancelled.
# buy5 FOK needs 10, has 2, so rejected.
# Let's trace manually:
# 1. buy1 (10@100) -> book_bids: [buy1]
# 2. sell1 (5@100) -> book_asks: [sell1]
# 3. buy2 (7@101) -> Matches sell1 (5@100). Trade: buy2-sell1, 100, 5. sell1 filled. buy2 remaining 2. buy2 (2@101) -> book_bids: [buy2(2@101), buy1(10@100)]
# 4. sell2 (12@99) -> Matches buy2 (2@101). Trade: buy2-sell2, 101, 2. buy2 filled. sell2 remaining 10. sell2 (10@99) -> Matches buy1 (10@100). Trade: buy1-sell2, 100, 10. buy1 filled. sell2 remaining 0. sell2 filled. Book empty.
#    Wait, my manual trace is wrong. Price-time priority.
#    buy2 (7@101) is a new order. It matches resting asks. Current asks: [sell1 (5@100)].
#    buy2 (taker) vs sell1 (maker). buy2.price (101) >= sell1.price (100). Match.
#    Trade: buy_id=buy2, sell_id=sell1, price=100, qty=5, taker_id=buy2, maker_id=sell1.
#    sell1 filled. buy2 remaining 2.
#    Book: bids: [], asks: [] (sell1 removed). buy2 (2@101) rests. book_bids: [buy2(2@101)]
# 4. sell2 (12@99) -> Matches resting bids. Current bids: [buy2(2@101)].
#    sell2 (taker) vs buy2 (maker). sell2.price (99) <= buy2.price (101). Match.
#    Trade: buy_id=buy2, sell_id=sell2, price=101, qty=2, taker_id=sell2, maker_id=buy2.
#    buy2 filled. sell2 remaining 10.
#    Book: bids: [], asks: []. sell2 (10@99) rests. book_asks: [sell2(10@99)]
# 5. buy3 (market, 3) -> Matches resting asks. Current asks: [sell2(10@99)].
#    buy3 (taker) vs sell2 (maker). Market order crosses any. Match.
#    Trade: buy_id=buy3, sell_id=sell2, price=99, qty=3, taker_id=buy3, maker_id=sell2.
#    buy3 filled. sell2 remaining 7.
#    Book: bids: [], asks: [sell2(7@99)]
# 6. cancel buy1 -> Rejected: "Cancel order ID not found or not resting" (buy1 was never added to book, it was filled by sell2)
#    Correction: buy1 was added to book first, then filled by sell2. So it's not resting. Correct rejection.
# 7. sell3 (10@100, IOC) -> Matches resting bids. None. Matches resting asks. None.
#    It's a sell order, matches bids. No bids. So it rests? No, IOC. It executes as much as possible, then cancels.
#    So, no trades, no remainder. Book unchanged.
# 8. buy4 (20@100, FOK) -> Needs 20. Current asks: [sell2(7@99)]. Only 7 available. FOK fails. Rejected.
# 9. buy5 (10@100, FOK) -> Needs 10. Current asks: [sell2(7@99)]. Only 7 available. FOK fails. Rejected.
# Final Book: bids: [], asks: [sell2(7@99)]
# Final Trades:
# 1. buy_id=buy2, sell_id=sell1, price=100, qty=5, taker_id=buy2, maker_id=sell1
# 2. buy_id=buy2, sell_id=sell2, price=101, qty=2, taker_id=sell2, maker_id=buy2
# 3. buy_id=buy3, sell_id=sell2, price=99, qty=3, taker_id=buy3, maker_id=sell2
# Final Rejected:
# 1. cancel buy1: "Cancel order ID not found or not resting"
# 2. buy4: FOK failed
# 3. buy5: FOK failed
# This matches my manual trace.
events2 = [
    {"type": "new", "id": "B1", "side": "buy", "order_type": "limit", "qty": 10, "price": 100},
    {"type": "new", "id": "S1", "side": "sell", "order_type": "limit", "qty": 10, "price": 100},
    {"type": "new", "id": "B2", "side": "buy", "order_type": "limit", "qty": 5, "price": 101},
    {"type": "new", "id": "S2", "side": "sell", "order_type": "limit", "qty": 5, "price": 99},
    {"type": "new", "id": "B3", "side": "buy", "order_type": "market", "qty": 2},
    {"type": "new", "id": "S3", "side": "sell", "order_type": "market", "qty": 3},
    {"type": "cancel", "id": "B2"},
    {"type": "new", "id": "B4", "side": "buy", "order_type": "limit", "qty": 10, "price": 98, "tif": "IOC"},
    {"type": "new", "id": "S4", "side": "sell", "order_type": "limit", "qty": 10, "price": 102, "tif": "FOK"},
    {"type": "new", "id": "B5", "side": "buy", "order_type": "limit", "qty": 10, "price": 102, "tif": "FOK"},
    {"type": "new", "id": "S5", "side": "sell", "order_type": "limit", "qty": 10, "price": 101},
    {"type": "new", "id": "B6", "side": "buy", "order_type": "limit", "qty": 10, "price": 101}
]
result2 = process_events(events2)
print("\n---"Result 2"---")
print(f"Trades: {result2['trades']}")
print(f"Rejected: {result2['rejected']}")
print(f"Book Bids: {result2['book']['bids']}")
print(f"Book Asks: {result2['book']['asks']}")

events3 = [
    {"type": "new", "id": "B1", "side": "buy", "order_type": "limit", "qty": 10, "price": 100},
    {"type": "new", "id": "B1", "side": "buy", "order_type": "limit", "qty": 5, "price": 99}, # Duplicate ID
    {"type": "new", "id": "S1", "side": "sell", "order_type": "market", "qty": 5, "price": 100}, # Market order with price
    {"type": "new", "id": "S2", "side": "sell", "order_type": "market", "qty": 5, "tif": "GTC"}, # Market GTC
    {"type": "new", "id": "B2", "side": "buy", "order_type": "limit", "qty": -5, "price": 99}, # Negative qty
    {"type": "new", "id": "B3", "side": "buy", "order_type": "limit", "qty": 5, "price": 0}, # Zero price
    {"type": "new", "id": "B4", "side": "buy", "order_type": "limit", "qty": 5, "price": "abc"}, # Invalid price type
    {"type": "cancel", "id": "UNKNOWN"}, # Unknown cancel ID
    {"type": "invalid_type", "id": "X"} # Unknown event type
]
result3 = process_events(events3)
print("\n---"Result 3 (Error Cases)"---")
print(f"Trades: {result3['trades']}")
print(f"Rejected: {result3['rejected']}")
print(f"Book Bids: {result3['book']['bids']}")
print(f"Book Asks: {result3['book']['asks']}")