==> Order.hpp <==
struct Order {
[Code redacted] int id;
int quantity; // hiddenQuantity needs to be >= peakSize
int peakSize;
int hiddenQuantity;
short price; // we don't really need this, cause price is the index
Order(int id = 0, int quantity = 0, int peakSize = 0, int hiddenQuantity = 0, short price = 0) :
id(id),
quantity(quantity),
peakSize(peakSize),
hiddenQuantity(hiddenQuantity),
price(price) { }
};
==> OrderBook.cpp <==
#include "OrderBook.hpp"
template<Side side>
inline bool OrderBook::compare(const int &top, const int &bottom) {
if constexpr (side == Side::Bid)
return top >= bottom;
else
return top <= bottom;
}
template<Side side>
inline void OrderBook::findNextPrice() {
Book &bookSide{books[side]};
while (compare<side>(bookSide.top, bookSide.bottom) and bookSide.orders[bookSide.top].empty())
if constexpr (side == Side::Bid)
--bookSide.top;
else
++bookSide.top;
if (not compare<side>(bookSide.top, bookSide.bottom))
bookSide.makeDefault();
}
inline void OrderBook::replenishIcebergOrder(Order &order) {
if (order.quantity == 0 and order.hiddenQuantity > 0) {
order.quantity = std::min(order.peakSize, order.hiddenQuantity);
order.hiddenQuantity -= order.quantity;
}
}
template<Side side>
void OrderBook::processOrder(Order &order) {
constexpr Side otherSide = (side == Side::Bid) ? Side::Ask : Side::Bid;
matchOrders<side, otherSide>(order);
displayOrderBook();
}
template<Side side, Side otherSide>
void OrderBook::matchOrders(Order &order) {
auto &otherBook{books[otherSide]};
while (compare<otherSide>(otherBook.top, order.price) and order.quantity > 0) {
auto &other = otherBook.orders[otherBook.top].front();
if constexpr (side == Side::Bid)
std::cout << order.id << ',' << other.id;
else
std::cout << other.id << ',' << order.id;
std::cout << ',' << otherBook.top << ',' << std::min(other.quantity, order.quantity) << '\n';
int change = other.quantity - order.quantity;
other.quantity = std::max(0, change);
order.quantity = std::max(0, -change);
replenishIcebergOrder(other);
replenishIcebergOrder(order);
if (other.quantity == 0) {
otherBook.orders[otherBook.top].pop_front();
if (otherBook.orders[otherBook.top].empty())
findNextPrice<otherSide>();
}
}
if (order.quantity > 0)
addOrder<side>(order);
}
template<Side side>
void OrderBook::addOrder(Order &order) {
Book &bookSide{books[side]};
if constexpr (side == Side::Bid) {
bookSide.top = std::max(bookSide.top, static_cast<int>(order.price));
bookSide.bottom = std::min(bookSide.bottom, static_cast<int>(order.price));
} else {
bookSide.top = std::min(bookSide.top, static_cast<int>(order.price));
bookSide.bottom = std::max(bookSide.bottom, static_cast<int>(order.price));
}
bookSide.orders[order.price].push_back(std::move(order));
}
// TODO: is there a better way to do this?
void OrderBook::displayOrderBook() {
std::cout << "+-----------------------------------------------------------------+\n";
std::cout << "| BUY | SELL |\n";
std::cout << "| Id | Volume | Price | Price | Volume | Id |\n";
std::cout << "+----------+-------------+-------+-------+-------------+----------+\n";
std::vector<std::pair<Order, Order>> orders;
unsigned long int bidIndex{0}, askIndex{0};
for (int i = books[Side::Bid].top; i >= books[Side::Bid].bottom; --i) {
for (auto &order: books[Side::Bid].orders[i]) {
if (bidIndex >= orders.size()) {
orders.push_back({order, Order{}});
++bidIndex;
} else {
orders[bidIndex++].first = order;
}
}
}
for (int i = books[Side::Ask].top; i <= books[Side::Ask].bottom; ++i) {
for (auto &order: books[Side::Ask].orders[i]) {
if (askIndex >= orders.size()) {
orders.push_back({Order{}, order});
++askIndex;
} else {
orders[askIndex++].second = order;
}
}
}
auto displayField = [](const int &value) {
return value == 0 ? "" : std::to_string(value);
};
for (const auto &[bidOrder, askOrder]: orders) {
std::cout << '|' << std::setw(10) << displayField(bidOrder.id) << '|'
<< std::setw(13) << formatWithCommas(bidOrder.quantity) << '|'
<< std::setw(7) << formatWithCommas(bidOrder.price) << '|'
<< std::setw(7) << formatWithCommas(askOrder.price) << '|'
<< std::setw(13) << formatWithCommas(askOrder.quantity) << '|'
<< std::setw(10) << displayField(askOrder.id) << "|\n";
}
std::cout << "+-----------------------------------------------------------------+\n";
}
std::string OrderBook::formatWithCommas(const int &value) {
if (value == 0)
return "";
std::string numberString = std::to_string(value);
for (int i = numberString.size() - 3; i > 0; i -= 3)
numberString.insert(i, ",");
return numberString;
}
==> OrderBook.hpp <==
#include <array>
#include <vector>
#include <deque>
#include <iostream>
#include <iomanip>
#include "Order.hpp"
#define BOOK_TOP 32768 // one level above SHRT_MAX
#define BOOK_BOTTOM -1 // one level blow bottom of book
#define BOOK_SIZE 32767 // SHRT_MAX
enum Side { Bid = 0, Ask = 1 };
struct Book {
/*
could use a ring buffer/circular queue instead of a deque
if you know the max possible level depth/width of the orderbook,
to avoid expensive allocations and deallocations,
but I decided to keep things simple.
I chose deque over a doubly linked since it's semi contiguous
*/
std::vector<std::deque<Order>> orders;
int top;
int bottom;
int defaultTop;
int defaultBottom;
Book (long unsigned int size, int top, int bottom) :
orders{size},
top{top},
bottom{bottom},
defaultTop(top),
defaultBottom(bottom) { }
void makeDefault() {
top = defaultTop;
bottom = defaultBottom;
}
};
class OrderBook {
public:
OrderBook() :
books{{Book{BOOK_SIZE, BOOK_BOTTOM, BOOK_TOP},
Book{BOOK_SIZE, BOOK_TOP, BOOK_BOTTOM}}} { }
~OrderBook() = default;
template<Side side>
inline bool compare(const int &top, const int &bottom);
template<Side side>
inline void findNextPrice();
inline void replenishIcebergOrder(Order &order);
template<Side side>
void processOrder(Order &order);
template<Side side, Side otherSide>
void matchOrders(Order &order);
template<Side side>
void addOrder(Order &order);
void displayOrderBook();
std::string formatWithCommas(const int &value);
private:
std::array<Book, 2> books; // bids, asks
};
==> main.cpp <==
#include "OrderBook.cpp"
int main() {
OrderBook orderbook;
std::string line;
while (std::getline(std::cin, line)) {
if (line.empty() or line[0] == '#' or line[0] == ' ')
continue;
std::istringstream iss{line};
std::string item;
std::vector<std::string> items;
while (getline(iss, item, ','))
items.push_back(item);
char side{items[0][0]};
int id{stoi(items[1])};
short price{static_cast<short>(std::stoi(items[2]))};
int quantity{std::stoi(items[3])};
int peakSize{0};
int hiddenQuantity{0};
// error checking
if ((side != 'B' and side != 'S') or id <= 0 or price <= 0 or quantity <= 0) {
std::cerr << "Invalid input: " << line << '\n';
continue;
}
// IceBerg order
if (items.size() == 5) {
peakSize = stoi(items[4]);
if (peakSize <= 0 or peakSize > quantity) {
std::cerr << "Invalid input: " << line << '\n';
continue;
}
hiddenQuantity = quantity - peakSize;
quantity = peakSize;
}
Order order{id, quantity, peakSize, hiddenQuantity, price};
if (side == 'B')
orderbook.processOrder<Side::Bid>(order);
else
orderbook.processOrder<Side::Ask>(order);
}
return 0;
}
Here is an example test
B,100321,5103,7500
B,100322,5101,7500
B,100323,5103,7500
S,100324,5103,7500
S,100345,5103,100000,10000
# this is a test
# this is another test
# this is going to be invalid
S,1,5103,100,10000
B,2,5103,100
B,3,5103,1000,90
S,4,5103,100,100
S,5,5104,100,100
S,6,5103,100,100
B,7,5105,300,300
S,8,5105,300,100
B,1234567890,32503,1234567890
S,1234567890,32505,1234567890
which ofc can be tested by doing something like cat test | ./order_book
