use crate::mathx;
pub const MAX_DEPTH_PER_SIDE: usize = 32;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Side {
Buy,
Sell,
}
pub type OwnerId = std::borrow::Cow<'static, str>;
pub fn owner_id(owner: &str) -> OwnerId {
match owner {
"mm" => OwnerId::Borrowed("mm"),
"depth" => OwnerId::Borrowed("depth"),
"flow" => OwnerId::Borrowed("flow"),
"range" => OwnerId::Borrowed("range"),
other => OwnerId::Owned(other.to_string()),
}
}
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub enum OrderId {
Given(String),
Sequenced,
}
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub struct BookOrder {
pub id: OrderId,
pub piece: u32,
pub side: Side,
pub price: f64,
pub quantity: f64,
pub remaining: f64,
pub sequence: u64,
pub owner_id: OwnerId,
}
impl BookOrder {
pub fn id_in(&self, company_id: &str) -> String {
let base = match &self.id {
OrderId::Given(id) => id.clone(),
OrderId::Sequenced => sequenced_id(company_id, self.sequence),
};
if self.piece == 0 {
base
} else {
format!("{base}.{}", self.piece)
}
}
pub fn piece(&self, k: u32, price: f64, shares: f64, company_id: &str) -> BookOrder {
let id = if self.piece == 0 {
self.id.clone()
} else {
OrderId::Given(self.id_in(company_id))
};
BookOrder {
id,
piece: k,
side: self.side,
price,
quantity: shares,
remaining: shares,
sequence: self.sequence,
owner_id: self.owner_id.clone(),
}
}
}
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub struct Fill {
pub price: f64,
pub quantity: f64,
pub maker_order_id: String,
pub maker_id: OwnerId,
pub taker_id: OwnerId,
pub taker_side: Side,
}
pub fn is_house_owner(owner: &str) -> bool {
matches!(owner, "mm" | "depth" | "flow" | "range")
}
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub struct MatchResult {
pub fills: Vec<Fill>,
pub unfilled: f64,
pub average_price: Option<f64>,
pub resting: Option<BookOrder>,
}
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub struct PriceLevel {
pub price: f64,
pub quantity: f64,
pub orders: u32,
}
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub struct SweepCost {
pub average_price: f64,
pub worst_price: f64,
pub filled: f64,
}
#[derive(Debug, Clone, Default)]
#[non_exhaustive]
pub struct SubmitOptions {
pub limit_price: Option<f64>,
pub post_remainder: bool,
pub order_id: Option<String>,
pub skip_own: bool,
pub house_ids: bool,
}
#[derive(Debug, Clone, PartialEq)]
#[non_exhaustive]
pub struct OrderBook {
pub company_id: String,
pub bids: Vec<BookOrder>,
pub asks: Vec<BookOrder>,
pub last_price: Option<f64>,
pub sequence: u64,
pub cap: usize,
}
impl OrderBook {
pub fn new(company_id: impl Into<String>, last_price: Option<f64>) -> Self {
Self {
company_id: company_id.into(),
bids: Vec::new(),
asks: Vec::new(),
last_price,
sequence: 0,
cap: MAX_DEPTH_PER_SIDE,
}
}
pub fn reset(&mut self, company_id: &str, last_price: Option<f64>) {
let OrderBook {
company_id: id,
bids,
asks,
last_price: last,
sequence,
cap,
} = self;
id.clear();
id.push_str(company_id);
bids.clear();
asks.clear();
*last = last_price;
*sequence = 0;
*cap = MAX_DEPTH_PER_SIDE;
}
pub fn with_cap(mut self, cap: usize) -> Self {
self.cap = cap;
self
}
pub fn best_bid(&self) -> Option<f64> {
self.bids.first().map(|o| o.price)
}
pub fn best_ask(&self) -> Option<f64> {
self.asks.first().map(|o| o.price)
}
pub fn mid_price(&self) -> Option<f64> {
match (self.best_bid(), self.best_ask()) {
(Some(b), Some(a)) => Some((b + a) / 2.0),
_ => None,
}
}
pub fn spread(&self) -> Option<f64> {
match (self.best_bid(), self.best_ask()) {
(Some(b), Some(a)) => Some(a - b),
_ => None,
}
}
pub fn depth(&self, side: Side) -> f64 {
let mut total = 0.0;
for o in self.side(side) {
total += o.remaining;
}
total
}
fn side(&self, side: Side) -> &Vec<BookOrder> {
match side {
Side::Buy => &self.bids,
Side::Sell => &self.asks,
}
}
fn side_mut(&mut self, side: Side) -> &mut Vec<BookOrder> {
match side {
Side::Buy => &mut self.bids,
Side::Sell => &mut self.asks,
}
}
pub fn price_levels(&self, side: Side, max_levels: usize) -> Vec<PriceLevel> {
let mut levels: Vec<PriceLevel> = Vec::new();
for o in self.side(side) {
if let Some(last) = levels.last_mut() {
if last.price == o.price {
last.quantity += o.remaining;
last.orders += 1;
continue;
}
}
if levels.len() >= max_levels {
break;
}
levels.push(PriceLevel {
price: o.price,
quantity: o.remaining,
orders: 1,
});
}
levels
}
fn insert_resting(&mut self, order: BookOrder) {
let is_buy = order.side == Side::Buy;
let price = order.price;
let cap = self.cap;
let side = self.side_mut(order.side);
let mut i = 0;
while i < side.len() {
let better = if is_buy {
price > side[i].price
} else {
price < side[i].price
};
if better {
break;
}
i += 1;
}
side.insert(i, order);
if side.len() > cap {
side.truncate(cap);
}
}
fn crosses(side: Side, taker_price: Option<f64>, resting_price: f64) -> bool {
match taker_price {
None => true,
Some(p) => match side {
Side::Buy => p >= resting_price,
Side::Sell => p <= resting_price,
},
}
}
pub fn submit(
&mut self,
side: Side,
quantity: f64,
taker_id: &str,
options: SubmitOptions,
) -> MatchResult {
let mut fills: Vec<Fill> = Vec::new();
let (unfilled, resting) = self.match_into(side, quantity, taker_id, options, &mut fills);
let average_price = if fills.is_empty() {
None
} else {
let mut notional = 0.0;
let mut shares = 0.0;
for f in &fills {
notional += f.price * f.quantity;
shares += f.quantity;
}
Some(notional / shares)
};
MatchResult {
fills,
unfilled,
average_price,
resting,
}
}
pub(crate) fn match_into(
&mut self,
side: Side,
quantity: f64,
taker_id: &str,
options: SubmitOptions,
fills: &mut Vec<Fill>,
) -> (f64, Option<BookOrder>) {
let limit_price = options.limit_price;
if !(quantity > 0.0) {
return (0.0, None);
}
let mut remaining = quantity;
let opposite_side = match side {
Side::Buy => Side::Sell,
Side::Sell => Side::Buy,
};
let mut at = 0;
while remaining > 0.0 && at < self.side(opposite_side).len() {
let maker_price = self.side(opposite_side)[at].price;
if !Self::crosses(side, limit_price, maker_price) {
break;
}
if options.skip_own && self.side(opposite_side)[at].owner_id == taker_id {
at += 1;
continue;
}
let (traded, exhausted, maker_order_id, maker_id) = {
let company = &self.company_id;
let maker = match opposite_side {
Side::Buy => &mut self.bids[at],
Side::Sell => &mut self.asks[at],
};
let traded = mathx::min(remaining, maker.remaining);
maker.remaining -= traded;
let id = if options.house_ids || !is_house_owner(&maker.owner_id) {
maker.id_in(company)
} else {
String::new()
};
(traded, maker.remaining <= 0.0, id, maker.owner_id.clone())
};
remaining -= traded;
fills.push(Fill {
price: maker_price,
quantity: traded,
maker_order_id,
maker_id,
taker_id: owner_id(taker_id),
taker_side: side,
});
self.last_price = Some(maker_price);
if exhausted {
self.side_mut(opposite_side).remove(at);
}
}
let mut resting: Option<BookOrder> = None;
if remaining > 0.0 {
if let (true, Some(limit)) = (options.post_remainder, limit_price) {
let order = BookOrder {
id: options.order_id.map_or(OrderId::Sequenced, OrderId::Given),
piece: 0,
side,
price: limit,
quantity,
remaining,
sequence: self.sequence,
owner_id: owner_id(taker_id),
};
self.sequence += 1;
self.insert_resting(order.clone());
resting = Some(order);
remaining = 0.0;
}
}
(remaining, resting)
}
pub fn post_limit(
&mut self,
side: Side,
price: f64,
quantity: f64,
owner_id: &str,
order_id: Option<String>,
) -> Option<BookOrder> {
if !(quantity > 0.0) || !(price > 0.0) {
return None;
}
let order = self.resting_order(side, price, quantity, owner_id, order_id);
self.insert_resting(order.clone());
Some(order)
}
pub fn rest_limit(&mut self, side: Side, price: f64, quantity: f64, owner_id: &str) {
if !(quantity > 0.0) || !(price > 0.0) {
return;
}
let order = self.resting_order(side, price, quantity, owner_id, None);
self.insert_resting(order);
}
fn resting_order(
&mut self,
side: Side,
price: f64,
quantity: f64,
owner_id: &str,
order_id: Option<String>,
) -> BookOrder {
let order = BookOrder {
id: order_id.map_or(OrderId::Sequenced, OrderId::Given),
piece: 0,
side,
price,
quantity,
remaining: quantity,
sequence: self.sequence,
owner_id: self::owner_id(owner_id),
};
self.sequence += 1;
order
}
pub fn cancel_order(&mut self, order_id: &str) -> bool {
for side in [Side::Buy, Side::Sell] {
let company = &self.company_id;
let orders = match side {
Side::Buy => &mut self.bids,
Side::Sell => &mut self.asks,
};
if let Some(idx) = orders.iter().position(|o| o.id_in(company) == order_id) {
orders.remove(idx);
return true;
}
}
false
}
pub fn cancel_all_for(&mut self, owner_id: &str) -> u32 {
let mut removed = 0;
for side in [Side::Buy, Side::Sell] {
let orders = self.side_mut(side);
let before = orders.len();
orders.retain(|o| o.owner_id != owner_id);
removed += (before - orders.len()) as u32;
}
removed
}
pub fn sweep_cost(&self, side: Side, quantity: f64) -> Option<SweepCost> {
let opposite = match side {
Side::Buy => Side::Sell,
Side::Sell => Side::Buy,
};
let mut remaining = quantity;
let mut notional = 0.0;
let mut worst_price = 0.0;
for o in self.side(opposite) {
if remaining <= 0.0 {
break;
}
let traded = mathx::min(remaining, o.remaining);
notional += o.price * traded;
remaining -= traded;
worst_price = o.price;
}
let filled = quantity - remaining;
if filled <= 0.0 {
return None;
}
Some(SweepCost {
average_price: notional / filled,
worst_price,
filled,
})
}
pub fn append_maker_level(
&mut self,
side: Side,
price: f64,
quantity: f64,
owner_id: &str,
) -> Option<BookOrder> {
if self.push_maker_level(side, price, quantity, owner_id) {
self.side(side).last().cloned()
} else {
None
}
}
pub fn push_maker_level(
&mut self,
side: Side,
price: f64,
quantity: f64,
owner_id: &str,
) -> bool {
if !(quantity > 0.0) || !(price > 0.0) {
return false;
}
if self.side(side).len() >= self.cap {
return false;
}
let order = BookOrder {
id: OrderId::Sequenced,
piece: 0,
side,
price,
quantity,
remaining: quantity,
sequence: self.sequence,
owner_id: self::owner_id(owner_id),
};
self.sequence += 1;
self.side_mut(side).push(order);
true
}
}
fn sequenced_id(company_id: &str, sequence: u64) -> String {
let mut digits = [0u8; 20];
let mut i = digits.len();
let mut n = sequence;
loop {
i -= 1;
digits[i] = b'0' + (n % 10) as u8;
n /= 10;
if n == 0 {
break;
}
}
let mut id = String::with_capacity(company_id.len() + 1 + (digits.len() - i));
id.push_str(company_id);
id.push('-');
id.push_str(std::str::from_utf8(&digits[i..]).unwrap_or("0"));
id
}
#[cfg(test)]
mod tests {
use super::*;
fn book() -> OrderBook {
OrderBook::new("TEST", None)
}
#[test]
fn bids_rank_by_descending_price_then_arrival() {
let mut b = book();
b.post_limit(Side::Buy, 100.0, 10.0, "a", None);
b.post_limit(Side::Buy, 101.0, 10.0, "b", None);
b.post_limit(Side::Buy, 100.0, 10.0, "c", None); let owners: Vec<&str> = b.bids.iter().map(|o| &*o.owner_id).collect();
assert_eq!(
owners,
vec!["b", "a", "c"],
"equal prices must keep arrival order"
);
}
#[test]
fn asks_rank_by_ascending_price_then_arrival() {
let mut b = book();
b.post_limit(Side::Sell, 101.0, 10.0, "a", None);
b.post_limit(Side::Sell, 100.0, 10.0, "b", None);
b.post_limit(Side::Sell, 101.0, 10.0, "c", None);
let owners: Vec<&str> = b.asks.iter().map(|o| &*o.owner_id).collect();
assert_eq!(owners, vec!["b", "a", "c"]);
}
#[test]
fn trades_print_at_the_makers_price() {
let mut b = book();
b.post_limit(Side::Sell, 100.0, 10.0, "maker", None);
let r = b.submit(
Side::Buy,
10.0,
"taker",
SubmitOptions {
limit_price: Some(105.0),
..Default::default()
},
);
assert_eq!(r.fills.len(), 1);
assert_eq!(
r.fills[0].price, 100.0,
"should fill at 100, not the 105 bid"
);
assert_eq!(b.last_price, Some(100.0));
}
#[test]
fn skip_own_passes_over_the_takers_own_orders() {
let mut b = book();
b.post_limit(Side::Sell, 100.0, 10.0, "me", Some("me-0".into()));
b.post_limit(Side::Sell, 100.0, 4.0, "other", None);
b.post_limit(Side::Sell, 101.0, 10.0, "me", Some("me-1".into()));
b.post_limit(Side::Sell, 102.0, 10.0, "other", None);
let r = b.submit(
Side::Buy,
20.0,
"me",
SubmitOptions { limit_price: Some(101.5), skip_own: true, ..Default::default() },
);
let got: Vec<_> = r.fills.iter().map(|f| (f.price, f.quantity, &*f.maker_id)).collect();
assert_eq!(got, vec![(100.0, 4.0, "other")]);
assert_eq!(r.unfilled, 16.0);
let left: Vec<_> = b.asks.iter().map(|o| (o.id_in(&b.company_id), o.remaining)).collect();
assert_eq!(left[..2], [("me-0".to_string(), 10.0), ("me-1".to_string(), 10.0)]);
let mut plain = book();
plain.post_limit(Side::Sell, 100.0, 10.0, "me", None);
let r = plain.submit(Side::Buy, 5.0, "me", SubmitOptions::default());
assert_eq!(r.fills[0].maker_id, "me", "off, the reference matches the queue as it stands");
}
#[test]
fn sweeping_multiple_levels_pays_a_worse_average() {
let mut b = book();
b.post_limit(Side::Sell, 100.0, 10.0, "m1", None);
b.post_limit(Side::Sell, 101.0, 10.0, "m2", None);
b.post_limit(Side::Sell, 102.0, 10.0, "m3", None);
let r = b.submit(Side::Buy, 25.0, "taker", SubmitOptions::default());
assert_eq!(r.fills.len(), 3);
assert_eq!(r.unfilled, 0.0);
assert_eq!(r.average_price, Some((1000.0 + 1010.0 + 510.0) / 25.0));
}
#[test]
fn a_market_order_never_rests() {
let mut b = book();
b.post_limit(Side::Sell, 100.0, 5.0, "m", None);
let r = b.submit(
Side::Buy,
20.0,
"taker",
SubmitOptions {
post_remainder: true,
..Default::default()
},
);
assert_eq!(r.unfilled, 15.0);
assert!(r.resting.is_none());
assert!(b.bids.is_empty());
}
#[test]
fn a_posted_remainder_counts_as_filled() {
let mut b = book();
b.post_limit(Side::Sell, 100.0, 5.0, "m", None);
let r = b.submit(
Side::Buy,
20.0,
"taker",
SubmitOptions {
limit_price: Some(100.0),
post_remainder: true,
order_id: None,
skip_own: false,
house_ids: false,
},
);
assert_eq!(r.unfilled, 0.0);
assert_eq!(r.resting.as_ref().unwrap().remaining, 15.0);
assert_eq!(b.bids.len(), 1);
}
#[test]
fn a_non_crossing_limit_does_not_trade() {
let mut b = book();
b.post_limit(Side::Sell, 100.0, 10.0, "m", None);
let r = b.submit(
Side::Buy,
10.0,
"taker",
SubmitOptions {
limit_price: Some(99.0),
..Default::default()
},
);
assert!(r.fills.is_empty());
assert_eq!(r.unfilled, 10.0);
}
#[test]
fn nan_and_nonpositive_sizes_are_rejected() {
let mut b = book();
b.post_limit(Side::Sell, 100.0, 10.0, "m", None);
for q in [0.0, -5.0, f64::NAN] {
let r = b.submit(Side::Buy, q, "taker", SubmitOptions::default());
assert!(r.fills.is_empty(), "quantity {q} should not trade");
assert_eq!(r.unfilled, 0.0);
}
assert!(b
.post_limit(Side::Buy, 100.0, f64::NAN, "x", None)
.is_none());
assert!(b.post_limit(Side::Buy, f64::NAN, 10.0, "x", None).is_none());
}
#[test]
fn depth_is_capped_and_trimmed_from_the_worst_end() {
let mut b = book();
for i in 0..(MAX_DEPTH_PER_SIDE + 10) {
b.post_limit(Side::Buy, 100.0 + i as f64, 1.0, "m", None);
}
assert_eq!(b.bids.len(), MAX_DEPTH_PER_SIDE);
assert_eq!(b.bids[0].price, 100.0 + (MAX_DEPTH_PER_SIDE + 9) as f64);
}
#[test]
fn sequenced_id_matches_format() {
for &n in &[0u64, 1, 9, 10, 99, 100, 12345, u64::MAX] {
assert_eq!(sequenced_id("ACME", n), format!("{}-{}", "ACME", n));
}
assert_eq!(sequenced_id("", 7), "-7");
}
#[test]
fn append_maker_level_refuses_past_the_cap() {
let mut b = book();
for i in 0..MAX_DEPTH_PER_SIDE {
assert!(b
.append_maker_level(Side::Buy, 100.0 - i as f64, 1.0, "mm")
.is_some());
}
assert!(b.append_maker_level(Side::Buy, 1.0, 1.0, "mm").is_none());
}
#[test]
fn cancel_all_for_removes_both_sides() {
let mut b = book();
b.post_limit(Side::Buy, 99.0, 1.0, "mm", None);
b.post_limit(Side::Sell, 101.0, 1.0, "mm", None);
b.post_limit(Side::Buy, 98.0, 1.0, "other", None);
assert_eq!(b.cancel_all_for("mm"), 2);
assert_eq!(b.bids.len(), 1);
assert!(b.asks.is_empty());
}
#[test]
fn sweep_cost_reports_none_when_the_book_is_empty() {
let b = book();
assert!(b.sweep_cost(Side::Buy, 10.0).is_none());
}
#[test]
fn sweep_cost_reports_a_partial_fill() {
let mut b = book();
b.post_limit(Side::Sell, 100.0, 5.0, "m", None);
let s = b.sweep_cost(Side::Buy, 20.0).unwrap();
assert_eq!(s.filled, 5.0);
assert_eq!(s.average_price, 100.0);
assert_eq!(s.worst_price, 100.0);
}
#[test]
fn matching_conserves_shares() {
let mut b = book();
b.post_limit(Side::Sell, 100.0, 7.0, "m1", None);
b.post_limit(Side::Sell, 101.0, 9.0, "m2", None);
let before = b.depth(Side::Sell);
let r = b.submit(Side::Buy, 12.0, "taker", SubmitOptions::default());
let traded: f64 = r.fills.iter().map(|f| f.quantity).sum();
assert_eq!(traded + b.depth(Side::Sell), before);
assert_eq!(traded, 12.0);
}
}