levels.hpp

#pragma once
 
#include <cstddef>
#include <cstdint>
#include <optional>
#include <vector>
 
#include <order_book/feed.hpp>
 
namespace order_book {

struct Level {
    Price price;       
    Quantity quantity; 
    friend bool operator==(const Level&, const Level&) = default;
};

struct Bbo {
    std::optional<Level> bid; 
    std::optional<Level> ask; 
    friend bool operator==(const Bbo&, const Bbo&) = default;
};

struct LevelRecord {
    Quantity total;       
    std::uint32_t orders; 
    std::uint16_t locate; 
    Side side;            
};

struct LevelEntry {
    Price price;         
    std::uint32_t level; 
};

struct BookLevels {
    std::vector<LevelEntry> bids; 
    std::vector<LevelEntry> asks; 
};

class LevelPool {
public:
    struct Added {
        std::uint32_t level; 
        bool changed;        
    };

    Added add(BookLevels& book, const AddOrder& order, std::uint16_t locate = 0);
    bool reduce(BookLevels& book, std::uint32_t level, Shares quantity, bool removed);
    [[nodiscard]] Bbo bbo(const BookLevels& book) const;

    [[nodiscard]] const LevelRecord& operator[](std::uint32_t level) const
    {
        return m_records[level];
    }

    [[nodiscard]] std::size_t size() const { return m_records.size() - 1 - m_free.size(); }
 
private:
    // Make a level for `order` and insert it into `levels` at `index`. Kept out of line, so that
    // add() stays small enough to inline: most adds join a level that exists.
    Added create(std::vector<LevelEntry>& levels, std::size_t index, const AddOrder& order,
                 std::uint16_t locate);
    // Whether `lhs` is a worse price than `rhs` on `side`: lower for bids, higher for asks
    [[nodiscard]] static bool worse(Side side, Price lhs, Price rhs)
    {
        return side == Side::Buy ? lhs < rhs : lhs > rhs;
    }
    // Where the level at `price` is in `levels`, worst first, or where it would be inserted:
    // levels[result - 1] is the first from the best that is not better than `price`
    [[nodiscard]] static std::size_t position(const std::vector<LevelEntry>& levels, Side side,
                                              Price price);
 
    std::vector<LevelRecord> m_records = std::vector<LevelRecord>(1);
    std::vector<std::uint32_t> m_free;
};
 
inline LevelPool::Added LevelPool::add(BookLevels& book, const AddOrder& order,
                                       std::uint16_t locate)
{
    auto& levels = order.side == Side::Buy ? book.bids : book.asks;
    const auto index = position(levels, order.side, order.price);
    if (index == 0 || levels[index - 1].price != order.price) {
        return create(levels, index, order, locate);
    }
    const auto handle = levels[index - 1].level;
    auto& level = m_records[handle];
    level.total += order.shares;
    ++level.orders;
    return {.level = handle, .changed = index == levels.size() && order.shares != 0};
}
 
// A handle and a quantity, which the check sees as swappable
// NOLINTNEXTLINE(bugprone-easily-swappable-parameters)
inline bool LevelPool::reduce(BookLevels& book, std::uint32_t level, Shares quantity, bool removed)
{
    auto& record = m_records[level];
    auto& levels = record.side == Side::Buy ? book.bids : book.asks;
    const auto best = levels.back().level == level;
    // Only the best level shows in the BBO, and only if its total changes or it goes away
    auto changed = best && quantity != 0;
    record.total -= quantity;
    if (removed && --record.orders == 0) {
        changed = best;
        if (best) {
            levels.pop_back();
        }
        else {
            // Found by handle from the end, which takes as many steps as position() would, so the
            // record needs no copy of the price
            auto index = levels.size() - 2;
            while (levels[index].level != level) {
                --index;
            }
            levels.erase(levels.begin() + static_cast<std::ptrdiff_t>(index));
        }
        m_free.push_back(level);
    }
    return changed;
}
 
inline Bbo LevelPool::bbo(const BookLevels& book) const
{
    Bbo bbo;
    if (!book.bids.empty()) {
        const auto& best = book.bids.back();
        bbo.bid = Level{.price = best.price, .quantity = m_records[best.level].total};
    }
    if (!book.asks.empty()) {
        const auto& best = book.asks.back();
        bbo.ask = Level{.price = best.price, .quantity = m_records[best.level].total};
    }
    return bbo;
}
 
inline std::size_t LevelPool::position(const std::vector<LevelEntry>& levels, Side side,
                                       Price price)
{
    // Most adds and removals are near the top of the book, which is the end of the vector
    auto index = levels.size();
    while (index > 0 && worse(side, price, levels[index - 1].price)) {
        --index;
    }
    return index;
}
 
} // namespace order_book