Design an Order Matching Engine: Order Book, Price-Time Priority and Order Types

from collections import deque
import heapq, itertools

class Book:
    """One instrument's limit order book: price-time priority, one thread."""
    def __init__(self):
        self.levels = {"buy": {}, "sell": {}}   # price -> deque of [id, owner, qty]
        self.prices = {"buy": [], "sell": []}   # heaps of prices (buy stored negative)
        self.where = {}                         # order id -> (side, price), for O(1) cancel
        self.seq = itertools.count(1)

    def best(self, side):
        heap = self.prices[side]
        while heap:                             # drop prices whose queue is empty
            p = -heap[0] if side == "buy" else heap[0]
            if self.levels[side].get(p):
                return p
            heapq.heappop(heap)
            self.levels[side].pop(p, None)
        return None

    def submit(self, owner, side, qty, price=None, tif="GTC"):
        oid, other = next(self.seq), ("sell" if side == "buy" else "buy")
        crosses = lambda p: price is None or (p <= price if side == "buy" else p >= price)
        if tif == "FOK":                        # fill or kill: check depth first, change nothing
            avail = sum(o[2] for p, q in self.levels[other].items() if q and crosses(p) for o in q)
            if avail < qty:
                return oid, [], "killed"
        fills = []
        while qty and (p := self.best(other)) is not None and crosses(p):
            queue = self.levels[other][p]
            maker = queue[0]
            if maker[1] == owner:               # self-trade prevention: cancel the newer order
                return oid, fills, "cancelled (self-trade)"
            n = min(qty, maker[2])
            fills.append((maker[0], oid, p, n))  # trades at the resting order's price
            maker[2] -= n
            qty -= n
            if maker[2] == 0:
                queue.popleft()
                del self.where[maker[0]]
        if qty and price is not None and tif == "GTC":  # the rest waits in the book
            queue = self.levels[side].setdefault(price, deque())
            if not queue:
                heapq.heappush(self.prices[side], -price if side == "buy" else price)
            queue.append([oid, owner, qty])
            self.where[oid] = (side, price)
            return oid, fills, f"resting {qty}"
        return oid, fills, "done" if not qty else f"{qty} unfilled, dropped"

    def cancel(self, oid):
        side, price = self.where.pop(oid)
        queue = self.levels[side][price]
        queue.remove(next(o for o in queue if o[0] == oid))


book = Book()
print(book.submit("ana", "sell", 100, price=101))
print(book.submit("ben", "sell", 50, price=100))
print(book.submit("cy", "sell", 70, price=100))
print(book.submit("dev", "buy", 200, price=101, tif="FOK"))
print(book.submit("eve", "buy", 90, price=100))
print(book.submit("ana", "buy", 10, price=102))
print(book.submit("fay", "buy", 500, tif="IOC"))
book.cancel(5)
print(book.best("buy"), book.best("sell"))