engine.cpp

#include "engine.hpp"

#include <vector>
#include <unordered_map>
#include <optional>
#include <stdexcept>
#include <cstdint>
#include <algorithm>
#include <functional>

// Core matching helper: walk through price levels in ordersMap and fill order
// until quantity reaches zero or no more qualifying price levels remain
template <typename OrderMap, typename Condition>
static uint32_t process_orders(Order &order,
                               OrderMap &ordersMap,
                               std::unordered_map<Id, OrderLocation> &orderIndex,
                               Condition cond) {
    uint32_t matchCount = 0;
    auto it = ordersMap.begin();
    while (it != ordersMap.end() && order.quantity > 0 && cond(it->first, order.price)) {
        auto &priceLevel = it->second;
        auto &ordersAtPrice = priceLevel.orders;
        
        size_t idx = 0;
        while (idx < ordersAtPrice.size() && order.quantity > 0) {
            Order &matchedOrder = ordersAtPrice[idx];
            Quantity trade = std::min<Quantity>(order.quantity, matchedOrder.quantity);
            order.quantity -= trade;
            matchedOrder.quantity -= trade;
            priceLevel.cachedVolume -= trade;
            ++matchCount;

            if (matchedOrder.quantity == 0) {
                // swap with last and pop (O(1) removal)
                Id removedId = matchedOrder.id;
                if (idx < ordersAtPrice.size() - 1) {
                    // swap with last element
                    std::swap(ordersAtPrice[idx], ordersAtPrice.back());
                    Id swappedId = ordersAtPrice[idx].id;
                    auto &swappedLoc = orderIndex[swappedId];
                    swappedLoc.index = idx;
                }
                orderIndex.erase(removedId);
                ordersAtPrice.pop_back();
            } else {
                ++idx;
            }
        }
        if (ordersAtPrice.empty()) {
            it = ordersMap.erase(it);
        } else {
            ++it;
        }
    }
    return matchCount;
}

// modify or cancel an order using index (O(1) lookup)
static bool modify_order_using_index(Orderbook &orderbook,
                                     Id order_id,
                                     Quantity new_quantity) {
    auto indexIt = orderbook.orderIndex.find(order_id);
    if (indexIt == orderbook.orderIndex.end()) {
        return false;
    }
    
    OrderLocation &loc = indexIt->second;
    PriceLevel *priceLevel = nullptr;
    
    if (loc.side == Side::BUY) {
        auto mapIt = orderbook.buyOrders.find(loc.price);
        if (mapIt == orderbook.buyOrders.end()) return false;
        priceLevel = &mapIt->second;
    } else {
        auto mapIt = orderbook.sellOrders.find(loc.price);
        if (mapIt == orderbook.sellOrders.end()) return false;
        priceLevel = &mapIt->second;
    }
    
    if (loc.index >= priceLevel->orders.size()) return false;
    
    Order &order = priceLevel->orders[loc.index];
    if (order.id != order_id) return false;
    
    int32_t volumeDelta = static_cast<int32_t>(new_quantity) - static_cast<int32_t>(order.quantity);
    
    if (new_quantity == 0) {
        // remove order: swap with last and pop
        priceLevel->cachedVolume -= order.quantity;
        if (loc.index < priceLevel->orders.size() - 1) {
            // swap with last element
            std::swap(priceLevel->orders[loc.index], priceLevel->orders.back());
            // update index for the swapped order
            Id swappedId = priceLevel->orders[loc.index].id;
            orderbook.orderIndex[swappedId].index = loc.index;
        }
        priceLevel->orders.pop_back();
        orderbook.orderIndex.erase(indexIt);
        
        if (priceLevel->orders.empty()) {
            if (loc.side == Side::BUY) {
                orderbook.buyOrders.erase(loc.price);
            } else {
                orderbook.sellOrders.erase(loc.price);
            }
        }
    } else {
        order.quantity = new_quantity;
        priceLevel->cachedVolume += volumeDelta;
    }
    
    return true;
}

// lookup an order by ID using the index (O(1) lookup)
static std::optional<Order> lookup_order_using_index(const Orderbook &orderbook,
                                                      Id order_id) {
    auto indexIt = orderbook.orderIndex.find(order_id);
    if (indexIt == orderbook.orderIndex.end()) {
        return std::nullopt;
    }
    
    const OrderLocation &loc = indexIt->second;
    
    if (loc.side == Side::BUY) {
        auto mapIt = orderbook.buyOrders.find(loc.price);
        if (mapIt == orderbook.buyOrders.end()) return std::nullopt;
        const auto &priceLevel = mapIt->second;
        if (loc.index >= priceLevel.orders.size()) return std::nullopt;
        return priceLevel.orders[loc.index];
    } else {
        auto mapIt = orderbook.sellOrders.find(loc.price);
        if (mapIt == orderbook.sellOrders.end()) return std::nullopt;
        const auto &priceLevel = mapIt->second;
        if (loc.index >= priceLevel.orders.size()) return std::nullopt;
        return priceLevel.orders[loc.index];
    }
}

extern "C" {

// match an incoming order against the book
uint32_t match_order(Orderbook &orderbook, const Order &incoming) {
    Order order = incoming;
    uint32_t matchCount = 0;

    if (order.side == Side::BUY) {
        // match sell orders priced <= limit
        matchCount = process_orders(order,
                                    orderbook.sellOrders,
                                    orderbook.orderIndex,
                                    [](Price p, Price limit) { return p <= limit; });
        if (order.quantity > 0) {
            // add remaining order to book
            PriceLevel &priceLevel = orderbook.buyOrders[order.price];
            size_t index = priceLevel.orders.size();
            priceLevel.orders.push_back(order);
            priceLevel.cachedVolume += order.quantity;
            orderbook.orderIndex[order.id] = {Side::BUY, order.price, index};
        }
    } else {
        // match buy orders priced >= limit
        matchCount = process_orders(order,
                                    orderbook.buyOrders,
                                    orderbook.orderIndex,
                                    [](Price p, Price limit) { return p >= limit; });
        if (order.quantity > 0) {
            // add remaining order to book
            PriceLevel &priceLevel = orderbook.sellOrders[order.price];
            size_t index = priceLevel.orders.size();
            priceLevel.orders.push_back(order);
            priceLevel.cachedVolume += order.quantity;
            orderbook.orderIndex[order.id] = {Side::SELL, order.price, index};
        }
    }

    return matchCount;
}

// modify or cancel an existing order by ID
void modify_order_by_id(Orderbook &orderbook,
                        Id order_id,
                        Quantity new_quantity) {
    modify_order_using_index(orderbook, order_id, new_quantity);
}

// get total quantity at a given price level (O(1) using cached volume)
uint32_t get_volume_at_level(Orderbook &orderbook,
                             Side side,
                             Price price) {
    if (side == Side::BUY) {
        auto it = orderbook.buyOrders.find(price);
        if (it != orderbook.buyOrders.end()) {
            return it->second.cachedVolume;
        }
    } else {
        auto it = orderbook.sellOrders.find(price);
        if (it != orderbook.sellOrders.end()) {
            return it->second.cachedVolume;
        }
    }
    return 0;
}
Order lookup_order_by_id(Orderbook &orderbook, Id order_id) {
    if (auto opt = lookup_order_using_index(orderbook, order_id)) {
        return *opt;
    }
    throw std::runtime_error("Order not found");
}

bool order_exists(Orderbook &orderbook, Id order_id) {
    return orderbook.orderIndex.find(order_id) != orderbook.orderIndex.end();
}

Orderbook *create_orderbook() {
    return new Orderbook();
}

}