The Limit-Order Book

First, let us define some objects which will correspond to orders. A limit-order contains three key pieces of information - whether the order is a buy or a sell, the price and the posted quantity. Let us call whether the limit-order is a buy or a sell the OrderSide. To construct an OrderSide object, we will inherit the Enum class which is built in to Python. The Enum class is suited to objects which are a set of symbolic names (members) bound to unique values.

from enum import Enum


class OrderSide(Enum):
    BUY: str = "buy"
    SELL: str = "sell"

We can select an order type with the syntax OrderType.BUY or OrderType.SELL .

Let's define an Order abstract base class. We will not specify anything in this class at this stage, but we will inherit the Order class in LimitOrder and MarketOrder so that it is clear that these are valid orders. We will use the Order class as a type hint in the LimitOrderBook class to ensure that only valid order classes are submitted into the book.

Next, let's define the limit order itself. We use dataclasses, which are classes that only contain data values. The primary difference between dataclasses and regular classes is that dataclass tend to contain few or no functions. The dataclass decorator provides us with a convenient syntax for defining such classes. Without it, we would need to define the constructor __init__() function and manually assign the attributes inside the class.

from abc import ABC
from dataclasses import dataclass

class Order(ABC):
    pass

@dataclass
class LimitOrder(Order):
    side: OrderSide
    price: float
    quantity: int

Next, let's define a class for market orders. Recall that a market order will immediately execute a trade to buy or sell a certain quantity for the best available price. As a result, we only need to include the order type and quantity.

@dataclass
class MarketOrder(Order):
    side: OrderSide
    quantity: int

Now, we can create a LimitOrderBook object to receive these order objects and update the limit order book accordingly. Firstly, we need some way of storing the posted quantity of some asset as a function of price for bids and for asks. A simple way to implement this is by means of a dictionary, with the prices as keys and the posted quantity as values. We will create a dictionary to store bids and one to store asks. We will use the built-in Python class `defaultdict`, which will automatically assign any key we try to access to some default value. In this case, it will be the default value of integers which is zero. Using defaultdict will simply our code, since we do not need to manually add new prices to the limit order book.

from typing import DefaultDict
from collections import defaultdict


class LimitOrderBook:
    
    def __init__(
        self, 
    ) -> None:
        self.bids = defaultdict(int)
        self.asks = defaultdict(int)

Now, let's define a generic submit_order function in our class, which will accept an order and update the limit order book correctly, depending on the type of the order. Implementing the code this way enables us to easily extend the code to accept more order types later on.

def submit_order(
    self,
    order: Order,
) -> Dict[str, Any]:
    if isinstance(order, MarketOrder):
        return self.submit_market_order(order)
    elif isinstance(order, LimitOrder):
        return self.submit_limit_order(order)
    else:
        raise NotImplementedError(f"Order {order.__class__} not recognised.")

Next, we must implement self.submit_limit_order(order) and self.submit_market_order(order). In our submit_limit_order() function, we must take into account several conditions. Firstly, let us make some preliminary checks that the limit order is valid. A valid limit order at the least should have a positive price and quantity. Then, the state of the order book will determine how our limit order behaves. Suppose we want to place a bid limit order to the book. We need to take into account two conditions.

1. There are ask limit orders in the book at our order price. In this case, we immediately trade the available quantity. If the posted ask quantity is greater than or equal to our order quantity, then we can trade the full order immediately, subtracting our order from the ask quantity. If the posted ask order is less than our order quantity, then we trade the available quantity immediately and post the remaining quantity.
2. There are no ask limit orders in the book at our order price. In this case, we can simply add the bid limit order to the book.

quantity_matched = min(self.asks[order.price], order.quantity)
remaining_quantity = order.quantity - quantity_matched
self.asks[order.price] -= quantity_matched
self.bids[order.price] += remaining_quantity

A nonzero quantity_matched indicates that there are ask orders in the book with the same price as our bid order. In this case, our bid order is subtracted from the ask orders and the trade is executed immediately for our posted price. If our bid order is not fully executed, then the remaining quantity is then posted to the bids. Likewise, if no ask orders exist in the book, then quantity_matched == 0 and we simply add order.quantity to the bids in the book.

We only need to implement this logic for both buy and sell orders to complete the submit_limit_order() function. When an order is submitted we will return some information to the user, indicating the quantity posted and the quantity immediately traded.

def submit_limit_order(
    self, 
    order: LimitOrder
) -> Dict[str, Any]:
    if order.price < 0 or order.quantity < 0:
        return {
            "quantity posted": 0, 
            "quantity immediately traded": 0,
        }

    active_book, passive_book = (
        self.bids, self.asks
        if order.side == OrderSide.BUY 
        else self.asks, self.bids
    )

    quantity_matched = min(passive_book[order.price], order.quantity)
    quantity_remaining = order.quantity - quantity_matched
    passive_book[order.price] -= quantity_matched
    active_book[order.price] += quantity_remaining

    return {
        "quantity posted": quantity_remaining,
        "quantity immediately traded": quantity_matched,
    }

Next, let's implement the submit_market_order() function. Here, we need to take the available quantity from the book starting from the best price until the order is fulfilled or until we exhaust the available limit orders in the book. If the market order is to buy, we begin at the lowest ask and iterate towards higher prices. If the market order is to sell, we begin at the largest bid and iterate towards lower prices. As a result we need to sort the dictionary keys before we iterate through them according to whether we buy or sell. At each price we either trade the remaining order quantity or the posted quantity, whichever is smaller. Similarly, we return some trade information to the user - the quantity traded and the average price of the asset traded.

def submit_market_order(self, order: MarketOrder) -> Dict[str, Any]:
    if order.quantity <= 0:
        return {
            "quantity immediately traded": 0, 
            "traded price": 0,
        }

    remaining_quantity = order.quantity
    total_cost = 0
    order_book = self.asks if order.side == OrderSide.BUY else self.bids

    for price, quantity in sorted(order_book.items(), reverse=order.side == OrderSide.SELL):
        trade_quantity = min(quantity, remaining_quantity)
        total_cost += trade_quantity * price
        order_book[price] -= trade_quantity
        remaining_quantity -= trade_quantity

        if remaining_quantity == 0:
            break

    quantity_matched = order.quantity - remaining_quantity
    average_traded_price = total_cost / quantity_matched if quantity_matched else 0

    return {
        "quantity immediately traded": quantity_matched,
        "traded price": average_traded_price,
    }

def show(self, save=False) -> None:

    # Get tick_size for bar widths
    all_prices = np.concatenate(
        [
            list(prices) for prices in
            (lob.bids.keys(), lob.asks.keys())
        ],
    )
    all_prices.sort()
    tick_size = np.round(
        np.diff(all_prices).min(),
        4,
    )

    fig, ax = plt.subplots(figsize=(10,6))
    fig.tight_layout()
    ax.bar(self.bids.keys(), self.bids.values(), color='g', width=tick_size * 0.9, label="bids")
    ax.bar(self.asks.keys(), self.asks.values(), color='r', width=tick_size * 0.9, label="asks")
    ax.legend(fontsize=12)
    ax.set_ylabel("Quantity", fontsize=15)
    ax.set_xlabel("Price", fontsize=15)
    ax.tick_params(labelsize=12)

    if save:
        fig.savefig("limit_order_book.png", dpi=72,  transparent=True, bbox_inches='tight')

@dataclass
class IOCOrder(Order):
    side: OrderSide
    price: float
    quantity: int

def submit_order(
    self,
    order: Order,
) -> Dict[str, Any]:
    if isinstance(order, MarketOrder):
        return self.submit_market_order(order)
    elif isinstance(order, LimitOrder):
        return self.submit_limit_order(order)
    elif isinstance(order, IOCOrder):
        return self.submit_ioc_order(order)
    else:
        raise NotImplementedError(f"Order {order.__class__} not recognised.")

def submit_ioc_order(
    self, 
    order: IOCOrder,
) -> Dict[str, Any]:
    if order.quantity <= 0:
        return {
            "quantity immediately traded": 0, 
            "traded price": 0,
        }

    order_book = self.asks if order.side == OrderSide.BUY else self.bids
    quantity_matched = min(order_book[order.price], order.quantity)
    order_book[order.price] -= quantity_matched

    return {
        "quantity immediately traded": quantity_matched,
    }

@dataclass
class NewLimitOrder(Order):
    id: int
    side: OrderSide
    price: float
    quantity: int

bids={
    100.2: {5:1},  # values are {order id: quantity}
    100.1: {6:3, 7:2},
    100.0: {8:3, 9:7},
}

def execute_trade(
    self,
    trade_quantity: int,
    price: float,
    order_book: DefaultDict[float, Dict[int, int]], 
) -> None:

    order_ids_to_remove = []

    for order_id, order_quantity in order_book[price].items():

        matched_quantity = min(trade_quantity, order_quantity)
        trade_quantity -= matched_quantity
        order_book[price][order_id] -= matched_quantity

        if order_book[price][order_id] == 0:
            order_ids_to_remove.append(order_id)

    for order_id in order_ids_to_remove:
        del order_book[price][order_id]

def submit_limit_order(
    self, 
    order: NewLimitOrder,
) -> Dict[str, Any]:
    if order.price < 0 or order.quantity < 0:
        return {
            "quantity posted": 0, 
            "quantity immediately traded": 0,
        }

    active_book, passive_book = (
        (self.bids, self.asks)
        if order.side == OrderSide.BUY 
        else (self.asks, self.bids)
    )

    passive_book_quantity_at_price = sum(passive_book[order.price].values())
    quantity_matched = min(passive_book_quantity_at_price, order.quantity)
    quantity_remaining = order.quantity - quantity_matched
    self.execute_trade(
        trade_quantity=quantity_matched,
        price=order.price,
        order_book=passive_book,
    )

    if quantity_remaining:
        active_book[order.price][order.id] = quantity_remaining

    return {
        "quantity posted": quantity_remaining,
        "quantity immediately traded": quantity_matched,
    }

def submit_market_order(
    self, 
    order: MarketOrder,
) -> Dict[str, Any]:
    if order.quantity <= 0:
        return {
            "quantity immediately traded": 0, 
            "traded price": 0,
        }

    remaining_quantity = order.quantity
    total_cost = 0
    order_book = self.asks if order.side == OrderSide.BUY else self.bids

    for price, quantity in sorted(order_book.items(), reverse=order.side == OrderSide.SELL):
        trade_quantity = min(quantity, remaining_quantity)
        total_cost += trade_quantity * price

        self.exeecute_trade(
            trade_quantity=trade_quantity,
            price=price,
            order_book=order_book,
        )
        remaining_quantity -= trade_quantity

        if remaining_quantity == 0:
            break

    quantity_matched = order.quantity - remaining_quantity
    average_traded_price = total_cost / quantity_matched if quantity_matched else 0

    return {
        "quantity immediately traded": quantity_matched,
        "traded price": average_traded_price,
    }

def cancel_limit_order(
    self,
    order_id: int,
) -> None:
    for order_book in [self.bids, self.asks]:
        for price, orders in order_book.items():
            if order_id in orders:
                del orders[order_id]
                return