project.cpp

#include <iostream>
#include <map>
#include <list>
#include <memory>
#include <vector>
#include <functional>
#include <algorithm>
#include <iomanip>

// Represents the side of an order.
enum class Side
{
    BUY,
    SELL
};

// Represents a single order in the book.
struct Order
{
    uint64_t id;
    Side side;
    double price;
    uint32_t quantity;
};

// Represents an executed trade.
struct Trade
{
    uint64_t buyOrderId;
    uint64_t sellOrderId;
    double price;
    uint32_t quantity;
};

class OrderBook
{

public:
    using BidsMap = std::map<double, std::list<Order>, std::greater<double>>;
    using AsksMap = std::map<double, std::list<Order>>;
    using MatchResult = std::pair<OrderBook, std::vector<Trade>>;

    // Default constructor for an empty order book.
    OrderBook()
        : bids_(std::make_shared<BidsMap>()),
          asks_(std::make_shared<AsksMap>()) {}

    OrderBook add(const Order &order) const
    {
        // 1. Create a shallow copy. This just copies the shared_ptrs, which is fast.
        OrderBook newBook = *this;

        if (order.side == Side::BUY)
        {
            // 2. Make a deep copy of the specific map we need to change.
            newBook.bids_ = std::make_shared<BidsMap>(*bids_);
            // 3. Modify the deep copy. The original remains untouched.
            (*newBook.bids_)[order.price].push_back(order);
        }
        else
        {
            newBook.asks_ = std::make_shared<AsksMap>(*asks_);
            (*newBook.asks_)[order.price].push_back(order);
        }
        return newBook;
    }

    MatchResult match() const
    {
        // If there's nothing to match, return the current state with no trades.
        if (bids_->empty() || asks_->empty())
        {
            return {*this, {}};
        }

        auto bestBidPrice = bids_->begin()->first;
        auto bestAskPrice = asks_->begin()->first;

        // If the highest bid is less than the lowest ask, there's no trade.
        if (bestBidPrice < bestAskPrice)
        {
            return {*this, {}};
        }

        // A trade is possible. We start with the current book's state.
        OrderBook currentBook = *this;
        std::vector<Trade> trades;

        // Loop as long as a match is possible.
        while (!currentBook.bids_->empty() && !currentBook.asks_->empty() &&
               currentBook.bids_->begin()->first >= currentBook.asks_->begin()->first)
        {
            // Create the next version of the book by deep-copying both maps.
            OrderBook nextBook = currentBook;
            nextBook.bids_ = std::make_shared<BidsMap>(*currentBook.bids_);
            nextBook.asks_ = std::make_shared<AsksMap>(*currentBook.asks_);

            auto &bidLevel = nextBook.bids_->begin()->second;
            auto &askLevel = nextBook.asks_->begin()->second;

            Order &bidOrder = bidLevel.front();
            Order &askOrder = askLevel.front();

            // Determine trade quantity.
            uint32_t tradeQuantity = std::min(bidOrder.quantity, askOrder.quantity);

            // Create a trade record. The trade price is the price of the resting order (the ask).
            trades.emplace_back(Trade{
                bidOrder.id,
                askOrder.id,
                askOrder.price,
                tradeQuantity});

            // Reduce quantities of the traded orders.
            bidOrder.quantity -= tradeQuantity;
            askOrder.quantity -= tradeQuantity;

            // If an order is fully filled, remove it.
            if (bidOrder.quantity == 0)
            {
                bidLevel.pop_front();
            }
            if (askOrder.quantity == 0)
            {
                askLevel.pop_front();
            }

            // If a price level is now empty, remove it from the map.
            if (bidLevel.empty())
            {
                nextBook.bids_->erase(nextBook.bids_->begin());
            }
            if (askLevel.empty())
            {
                nextBook.asks_->erase(nextBook.asks_->begin());
            }

            // The new state becomes the current state for the next loop iteration.
            currentBook = nextBook;
        }

        return {currentBook, trades};
    }

    /**
     * @brief Prints a visual representation of the order book.
     */
    void print() const
    {
        std::cout << "--- ORDER BOOK ---" << std::endl;
        std::cout << std::fixed << std::setprecision(2);

        // Print Asks (in reverse order to show lowest ask at the bottom)
        std::cout << "ASKS (Price | Quantity)" << std::endl;
        std::cout << "----------------------" << std::endl;
        for (auto it = asks_->rbegin(); it != asks_->rend(); ++it)
        {
            uint32_t totalQuantity = 0;
            for (const auto &order : it->second)
            {
                totalQuantity += order.quantity;
            }
            std::cout << it->first << "   | " << totalQuantity << std::endl;
        }

        std::cout << "----------------------" << std::endl;

        // Print Bids
        std::cout << "BIDS (Price | Quantity)" << std::endl;
        std::cout << "----------------------" << std::endl;
        for (const auto &pair : *bids_)
        {
            uint32_t totalQuantity = 0;
            for (const auto &order : pair.second)
            {
                totalQuantity += order.quantity;
            }
            std::cout << pair.first << "   | " << totalQuantity << std::endl;
        }
    }

private:
    // Use shared pointers for efficient, immutable copying.
    std::shared_ptr<BidsMap> bids_;
    std::shared_ptr<AsksMap> asks_;
};

int main() {
    uint64_t orderIdCounter = 1;

    // Start with a clean slate. This is Version 0.
    OrderBook book_v0;
    std::cout << "--- Initial State (v0) ---" << std::endl;
    book_v0.print();

    // Each 'add' call creates a new, independent version of the book.
    auto book_v1 = book_v0.add({orderIdCounter++, Side::BUY, 99.50, 100});
    auto book_v2 = book_v1.add({orderIdCounter++, Side::BUY, 99.75, 50});
    auto book_v3 = book_v2.add({orderIdCounter++, Side::SELL, 100.50, 200});
    auto book_v4 = book_v3.add({orderIdCounter++, Side::SELL, 100.25, 75});

    std::cout << "--- State after adding 4 orders (v4) ---" << std::endl;
    book_v4.print();

    // Let's prove immutability: the original book (v0) is still empty.
    std::cout << "--- Checking original state (v0) ---" << std::endl;
    book_v0.print();

    // --- Step 2: Add an order that will cause a match ---
    std::cout << "--- Adding a new BUY order at 100.25 ---" << std::endl;
    auto book_v5 = book_v4.add({orderIdCounter++, Side::BUY, 100.25, 150});
    std::cout << "--- State before matching (v5) ---" << std::endl;
    book_v5.print();

    // --- Step 3: Run the matching engine ---
    std::cout << "--- Running the matching engine... ---" << std::endl;
    auto matchResult = book_v5.match();
    OrderBook book_v6 = matchResult.first;
    std::vector<Trade> trades = matchResult.second;

    if (!trades.empty()) {
        std::cout << "Trades Executed!" << std::endl;
        for (const auto& trade : trades) {
            std::cout << "  - Matched Buy Order " << trade.buyOrderId
                      << " with Sell Order " << trade.sellOrderId
                      << ". Quantity: " << trade.quantity
                      << " @ Price: " << trade.price << std::endl;
        }
        std::cout << std::endl;
    } else {
        std::cout << "No trades were executed." << std::endl;
    }

    std::cout << "--- State after matching (v6) ---" << std::endl;
    book_v6.print();

    // Note that book_v5 is still unchanged because match() is also immutable.
    std::cout << "--- Checking pre-match state (v5) ---" << std::endl;
    book_v5.print();

    return 0;
}