limit_tree.hpp

// A single side (buy/sell) of the LimitOrderBook.
// Copyright 2020 Christian Kauten
//
// Author: Christian Kauten (kautenja@auburn.edu)
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
// You should have received a copy of the GNU General Public License
// along with this program.  If not, see <http://www.gnu.org/licenses/>.
//
 
#ifndef DATA_FEED_LIMIT_ORDER_BOOK_LIMIT_TREE_HPP
#define DATA_FEED_LIMIT_ORDER_BOOK_LIMIT_TREE_HPP
 
#include "structures.hpp"
#include "tsl/robin_map.h"
 
namespace DataFeed {
 
namespace LOB {
 
typedef tsl::robin_map<Price, Limit*> PriceLimitMap;
 
// ---------------------------------------------------------------------------
// MARK: set_best
// ---------------------------------------------------------------------------
 
template<Side side>
void set_best(Limit** best, Limit* limit);
 
template<>
inline void set_best<Side::Buy>(Limit** highest_buy, Limit* limit) {
    if (*highest_buy == nullptr) *highest_buy = limit;
    else if (limit->key > (*highest_buy)->key) *highest_buy = limit;
}
 
template<>
inline void set_best<Side::Sell>(Limit** lowest_sell, Limit* limit) {
    if (*lowest_sell == nullptr) *lowest_sell = limit;
    else if (limit->key < (*lowest_sell)->key) *lowest_sell = limit;
}
 
// ---------------------------------------------------------------------------
// MARK: find_best
// ---------------------------------------------------------------------------
 
template<Side side>
void find_best(Limit** best);
 
template<>
inline void find_best<Side::Buy>(Limit** highest_buy) {
    if ((*highest_buy)->parent == nullptr)  // removing root node
        // set left because if right existed it would be a better limit already
        *highest_buy = static_cast<Limit*>((*highest_buy)->left);
    else  // removing non-root node
        *highest_buy = static_cast<Limit*>((*highest_buy)->parent);
    if (*highest_buy != nullptr)  // highest buy exists
        *highest_buy = static_cast<Limit*>(BST::max(*highest_buy));
}
 
template<>
inline void find_best<Side::Sell>(Limit** lowest_sell) {
    if ((*lowest_sell)->parent == nullptr)  // removing root node
        // set right because if left existed it would be a better limit already
        *lowest_sell = static_cast<Limit*>((*lowest_sell)->right);
    else  // removing non-root node
        *lowest_sell = static_cast<Limit*>((*lowest_sell)->parent);
    if (*lowest_sell != nullptr)  // lowest sell exists
        *lowest_sell = static_cast<Limit*>(BST::min(*lowest_sell));
}
 
// ---------------------------------------------------------------------------
// MARK: can_match
// ---------------------------------------------------------------------------
 
template<Side side>
bool can_match(Price limit, Price market);
 
template<>
inline bool can_match<Side::Buy>(Price limit, Price market) {
    // short circuit on price > 0: 0 is sentinel for no limit
    // the price should be less than or equal to the best on the buy side.
    // i.e., the submitted order is a sell limit with a lower price
    return market == 0 || market <= limit;
}
 
template<>
inline bool can_match<Side::Sell>(Price limit, Price market) {
    // short circuit on price > 0: 0 is sentinel for no limit
    // the price should be greater than or equal to the best on the sell side.
    // i.e., the submitted order is a buy limit with a higher price
    return market == 0 || market >= limit;
}
 
template<Side side>
struct LimitTree {
    Limit* root = nullptr;
    PriceLimitMap limits;
    Limit* best = nullptr;
    Price last_best_price = 0;
    Count count = 0;
    Volume volume = 0;
 
    void clear() {
        // delete all the limits
        for(auto item = limits.begin(); item != limits.end(); item++)
            delete item->second;
        // clear the pairs from the map
        limits.clear();
        // set remaining tracers to 0
        root = nullptr;
        best = nullptr;
        count = 0;
        volume = 0;
    }
 
    void limit(Order* order) {
        if (limits.count(order->price) == 0) {  // first order at limit price
            // create the limit and set the order's limit to the limit
            order->limit = new Limit(order);
            // the limit price is new, add it to the limit tree
            BST::insert(
                reinterpret_cast<BST::Node<Price>**>(&root),
                static_cast<BST::Node<Price>*>(order->limit)
            );
            // set the best price
            set_best<side>(&best, order->limit);
            // put the limit into the price to limit mapping
            limits.emplace(order->limit->key, order->limit);
        } else {  // push to existing queue of orders at limit price
            // set the order's limit to the limit node for the order's price
            order->limit = limits.at(order->price);
            // increment the count of the orders at this limit node
            ++order->limit->count;
            // increment the volume of the orders at this limit node
            order->limit->volume += order->quantity;
            // add the order to the queue of orders for the limit node
            DLL::append(
                reinterpret_cast<DLL::Node**>(&order->limit->order_tail),
                static_cast<DLL::Node*>(order)
            );
        }
        // update the count and volume for the entire tree
        ++count;
        volume += order->quantity;
        // set the last best price
        if (best != nullptr) last_best_price = best->key;
    }
 
    // TODO: use object pool for limit reuse?
    void cancel(Order* order) {
        // unwrap the limit for the order
        auto limit_ = order->limit;
        if (order->prev == nullptr && order->next == nullptr) {  // last Order
            // remove the limit from the tree
            BST::remove(
                reinterpret_cast<BST::Node<Price>**>(&root),
                static_cast<BST::Node<Price>*>(limit_)
            );
            // replace the best limit if necessary
            if (best == limit_)
                find_best<side>(&best);
            // remove the limit from the price map
            limits.erase(limit_->key);
            delete limit_;
        } else {  // at least 1 other Order in queue
            --limit_->count;
            limit_->volume -= order->quantity;
            // remove the order from the queue (update head and tail)
            DLL::remove(
                reinterpret_cast<DLL::Node**>(&limit_->order_head),
                reinterpret_cast<DLL::Node**>(&limit_->order_tail),
                static_cast<DLL::Node*>(order)
            );
        }
        // update the count and volume for the entire tree
        --count;
        volume -= order->quantity;
        // set the last best price
        if (best != nullptr) last_best_price = best->key;
    }
 
    template<typename Callback>
    void market(Order* order, Callback did_fill) {
        // find orders until there are none
        while (best != nullptr && can_match<side>(best->key, order->price)) {
            // get the next match as the front of the best price
            auto match = best->order_head;
            if (match->quantity >= order->quantity) {  // current match can fill
                if (match->quantity == order->quantity) {  // limit order filled
                    // remove the current match from the book
                    cancel(match);
                    did_fill(match->uid);
                } else {  // limit order partially filled
                    // remove the market order quantity from the limit quantity
                    match->quantity -= order->quantity;
                    // update the match's limit volume
                    match->limit->volume -= order->quantity;
                    // update the volume for the entire tree
                    volume -= order->quantity;
                }
                // clear the remaining quantity for the order
                order->quantity = 0;
                return;
            }  // else: current match can NOT fill
            // decrement the remaining quantity of the market order
            order->quantity -= match->quantity;
            // remove the current match from the book
            cancel(match);
            did_fill(match->uid);
        }
 
    }
 
    inline Volume volume_at(Price price) const {
        if (limits.count(price)) return limits.at(price)->volume;
        return 0;
    }
 
    inline Count count_at(Price price) const {
        if (limits.count(price)) return limits.at(price)->count;
        return 0;
    }
};
 
}  // namespace LOB
 
}  // namespace DataFeed
 
#endif  // DATA_FEED_LIMIT_ORDER_BOOK_LIMIT_TREE_HPP