Lesson 3 — The Book struct and the Reverse<Price> trick

Question

The Book is a BTreeMap<Price, VecDeque<Order>> for bids and asks. The Reverse<Price> trick makes the bid side sort descending (best bid first) while keeping the ask side ascending. One BTreeMap variant; two opposite orderings.

Principle (minimum model)

• Book struct. bids: BTreeMap<Reverse<Price>, VecDeque<Order>> + asks: BTreeMap<Price, VecDeque<Order>>. Both keyed by price; bids reversed.
• Reverse<Price>. Standard library std::cmp::Reverse — wraps a value so Ord is reversed. Reverse(Price(10)) > Reverse(Price(20)). Best bid = first entry in bids.
• Asks ascending. Best ask = first entry in asks (lowest price = best for buyer).
• VecDeque for FIFO. At each price level, orders are FIFO; VecDeque lets us push_back on submit and pop_front on match.
• current_best_bid / current_best_ask. O(log n) lookup via bids.first_key_value(). The matching engine uses these constantly.
• Memory layout. BTreeMap<Reverse<Price>, _> stores the same way as BTreeMap<Price, _>; just the Ord impl differs. No extra cost.
• Why this matters. Standard textbook CLOB uses a sorted skiplist or a min-heap. BTreeMap is simpler, fast enough, and gives O(log n) operations everywhere.

Worked example + steps

Lesson 3 — The Book struct and the Reverse<Price> trick

Goal

Concepts you'll grasp in this lesson:

• Two BTreeMaps are the entire matching-engine state — no order-id index, no best-price cache, no per-side counters. Everything else is derived. Optimizations layer on top later without changing the core model.
• Reverse<Price> makes the iterator walk bids highest-first — by flipping Ord::cmp at the key type, both sides can use BTreeMap::iter().next() uniformly. One type asymmetry buys symmetric matching code.
• RestingOrder trims Order to make impossible states unrepresentable — a resting order has no side (we know it from which map it's in) and no order_type (Market never rests). Type design as constraint engineering.
• VecDeque over Vec for FIFO queues — Vec::remove(0) shifts every element (O(n)); VecDeque::pop_front() is O(1). Price-time priority requires fast pop-front and fast push-back.

Verification:

cargo check -p openhl-clob

…still compiles.

Specific changes:

You'll have a new file crates/clob/src/book.rs containing:

• Book struct — two BTreeMaps (bids + asks), each mapping a price level to a VecDeque of resting orders.
• RestingOrder struct — what a single order looks like once it's resting on the book (trimmed from Order).
• new() constructor + 4 read-only accessors (best_bid, best_ask, depth_bid, depth_ask).

No matching logic yet — submit lands in Lesson 4 + Lesson 5, cancel in Lesson 6. This lesson is about building the data structure correctly so the matching logic can be a few lines on top of it.

Recap

After Lesson 2, your crates/clob/src/types.rs is complete (~109 lines): 4 newtypes, Side, OrderType, Order, Fill, FillResult, Display impls.

crates/clob/src/lib.rs re-exports all of those via pub use types::*. There is no book module yet — this lesson creates it.

Plan

Five things:

1. Create crates/clob/src/book.rs.
2. Write the Book struct with bids: BTreeMap<Reverse<Price>, VecDeque<RestingOrder>> and asks: BTreeMap<Price, VecDeque<RestingOrder>>.
3. Write the RestingOrder struct — trimmed from Order (no side, no order_type, no qty growth).
4. Add Book::new() + the 4 accessor methods.
5. Wire pub mod book; into lib.rs.

The accessors return Option<Price> or usize — pure read operations against the BTreeMap shape. The interesting design choices are the map key types and what RestingOrder keeps vs. drops from Order.

The completed Book's logical structure is a 2-level nest:

bids (BTreeMap<Reverse<Price>, VecDeque<RestingOrder>>) — iterate highest first:
  Reverse(Price(102)) → [O3]              ← best bid: keys().next()
  Reverse(Price(100)) → [O1, O2]
  Reverse(Price(99))  → [O5, O6]

asks (BTreeMap<Price, VecDeque<RestingOrder>>) — iterate lowest first:
  Price(103) → [O7, O8]                   ← best ask: keys().next()
  Price(105) → [O9]
  Price(107) → [O10, O11]

The outer BTreeMap gives price priority (sorted keys); the inner VecDeque gives time priority (FIFO order) — that's the structure of a price-time-priority CLOB. Only the bid side's Reverse<Price> key type is asymmetric, and that's the load-bearing trick that makes keys().next() return the best bid on both sides.

Walk-through

Step 1: Create book.rs with module doc and imports

touch crates/clob/src/book.rs (or just create the file in your editor). Top of the file:

//! Price-time priority orderbook + matching engine.
//!
//! Bids are stored with a `Reverse<Price>` key so `BTreeMap` natural-order
//! iteration walks them best-first (highest price first). Asks are stored
//! with `Price` directly so they also walk best-first (lowest price first).
//! Within each price level, orders are queued FIFO — that's the "time
//! priority" half of price-time priority.

use core::cmp::Reverse;
use std::collections::{BTreeMap, VecDeque};

use crate::types::{
    AccountId, Fill, FillResult, Order, OrderId, OrderType, Price, Qty, Side,
};

A few things to scan:

• core::cmp::Reverse — the wrapper that flips the ordering of any Ord type. Reverse(Price(100)) compares greater than Reverse(Price(200)), because Reverse inverts the underlying comparison.
• BTreeMap — a sorted map. Iteration walks keys in ascending order (= natural order = whatever Ord::cmp says is "smaller goes first"). Insert/remove/lookup are all O(log n).
• VecDeque — a double-ended queue. We use it for the "time priority" inside each price level: push_back for new orders (they go to the back of the line), pop_front for matched orders (front of the line gets filled first).
• Mechanical-sympathy note — VecDeque is not exactly one flat contiguous region like Vec, but as a ring buffer it keeps O(1) operations at both ends while preserving strong locality. At the "hundreds to low-thousands per level" scale, scans are close to sequential access, so CPU cache lines and prefetching usually work in your favor. In wall-clock terms that often beats pointer-chasing hash structures.
• All the types from Lessons 1 + 2 — even ones we don't use directly in this lesson (Fill, FillResult, Side, etc.). We're importing them now to match the final imports list; they'll all be used by Lessons 4–6's matching code.

Step 2: Write the Book struct

Continue:

#[derive(Debug, Default)]
pub struct Book {
    /// Bids: `Reverse<Price>` key gives best-first iteration (highest first).
    bids: BTreeMap<Reverse<Price>, VecDeque<RestingOrder>>,
    /// Asks: `Price` key gives best-first iteration (lowest first).
    asks: BTreeMap<Price, VecDeque<RestingOrder>>,
}

The whole matching engine's state is two BTreeMaps. That's it. No order-id index (we'll do O(n) cancel in Lesson 6 and address that trade-off explicitly), no separate "best price" cache (the BTreeMap already gives us best in O(1)), no tick-size tables.

The asymmetry between bids and asks — Reverse<Price> vs. Price — looks weird, but it's the load-bearing trick:

• Asks: BTreeMap<Price, _>. Natural-order keys means iteration goes Price(99), Price(100), Price(101), ... A buy-taker that wants the cheapest ask reads asks.keys().next() → Price(99). Best-first.
• Bids: BTreeMap<Reverse<Price>, _>. Natural order on Reverse<Price>(p) is descending in p: Reverse(Price(101)) comes before Reverse(Price(100)) comes before Reverse(Price(99)). A sell-taker that wants the highest bid reads bids.keys().next() → Reverse(Price(101)). Best-first.

Both sides use keys().next() to get the best price. That's the API symmetry that justifies the type asymmetry. Without Reverse, bid lookup would have to be keys().next_back() (the BTreeMap iterator's reverse direction), and the matching code would be asymmetric across sides — easy to confuse, easy to write wrong.

#[derive(Default)] is here so Book::new() (next step) can just be Self::default() — no need to write BTreeMap::new() four times in a constructor. Default for BTreeMap is an empty map; same for Default on Book overall.

Step 3: Write the RestingOrder struct

Below Book:

/// An order resting on the book. Trimmed from `Order` — side and `order_type`
/// are implicit from which side of the book it's resting on, and `qty` shrinks
/// as fills consume it.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
struct RestingOrder {
    id: OrderId,
    account: AccountId,
    qty: Qty,
}

3 fields, not pub (this is an internal type — callers never touch RestingOrder directly).

What's missing from Order:

• side — gone. We know what side a RestingOrder is on by which map it lives in (bids vs. asks). Storing it twice would be redundant + error-prone.
• order_type — gone. Resting orders are always Limit orders by definition (Market orders never rest — they fill what they can and discard the rest). Storing order_type would let us construct a RestingOrder with OrderType::Market, which is meaningless.
• qty stays — but it shrinks over time as the order gets partially filled. The submit code in Lesson 4 will mutate RestingOrder.qty directly when a maker eats less than 100% of a taker's quantity.

Step 4: Add new() and the 4 accessors

Append to book.rs:

impl Book {
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }

    #[must_use]
    pub fn best_bid(&self) -> Option<Price> {
        self.bids.keys().next().map(|rp| rp.0)
    }

    #[must_use]
    pub fn best_ask(&self) -> Option<Price> {
        self.asks.keys().next().copied()
    }

    #[must_use]
    pub fn depth_bid(&self) -> usize {
        self.bids.values().map(VecDeque::len).sum()
    }

    #[must_use]
    pub fn depth_ask(&self) -> usize {
        self.asks.values().map(VecDeque::len).sum()
    }
}

5 methods, all #[must_use]:

• new() — Self::default(). We could write Book { bids: BTreeMap::new(), asks: BTreeMap::new() } but #[derive(Default)] handles that uniformly.
• best_bid() — keys().next() returns the smallest natural-order key. Because bids use Reverse<Price>, that key wraps the highest price. We unwrap with .map(|rp| rp.0) — the rp.0 peels off the Reverse wrapper.
• best_ask() — same pattern, but the key is Price directly. keys().next() returns the smallest Price, and we .copied() to get a Price value (without that, we'd get Option<&Price>).
• depth_bid() / depth_ask() — sum of queue lengths across all price levels. Inspection-only methods, used by tests and debugging.

Why Option<Price> for best? When the book is empty, there's no best price. Option::None is the right answer; returning Price(0) or Price(u64::MAX) would let callers accidentally treat them as real prices. The type forces the empty case to be handled.

Step 5: Wire into lib.rs

Open crates/clob/src/lib.rs. Lessons 1 + 2's content is:

//! Pure-Rust CLOB (central limit order book) matching engine for openhl.
//!
//! No I/O. No allocation beyond fill output. Deterministic by construction.
//! See [`book::Book`] for the matching state machine (Lesson 3+).

pub mod types;

pub use types::*;

Add one line for the new module, and one re-export for the public Book type:

//! Pure-Rust CLOB (central limit order book) matching engine for openhl.
//!
//! No I/O. No allocation beyond fill output. Deterministic by construction.
//! See [`book::Book`] for the matching state machine.

pub mod book;
pub mod types;

pub use book::Book;
pub use types::*;

The order is intentional: book first alphabetically, types second. Imports in Rust crates generally read better when crate-level modules are alphabetized.

Only Book is re-exported, not RestingOrder. RestingOrder is the internal queue element; nothing outside the matching engine should construct or read it. Keeping it struct (not pub struct) inside book.rs makes that explicit. The compiler enforces "no one outside this module touches RestingOrder."

Test

cargo check -p openhl-clob

Expected: clean compile, no warnings.

You might see a warning about unused imports — that's because book.rs imports Fill, FillResult, Order, OrderType, Qty, Side but Lesson 3 doesn't use them yet:

warning: unused import: `Fill, FillResult, Order, OrderType, Qty, Side`
 --> crates/clob/src/book.rs:11:5

Two options for how to handle this:

1. Tolerate the warning for now — move on; each import gets used in Lessons 4–6 and the warning disappears naturally. If the compile-time noise bothers you, temporarily add #[allow(unused_imports)] above the use statement (remove in Lesson 4).
2. Comment out the unused imports for now, uncomment as you need them in Lessons 4–6.

This course recommends option 1. The reference at SHA 55a9dff keeps all imports (the file is complete at that SHA), so the build-along's per-step code lines up byte-for-byte with the reference. The warning is transient noise — it goes away naturally from Lesson 4 onward.

A quick sanity test that the structure compiles correctly:

cat > /tmp/book_test.rs <<'EOF'
use openhl_clob::Book;
use openhl_clob::Price;

fn main() {
    let b = Book::new();
    assert_eq!(b.best_bid(), None);
    assert_eq!(b.best_ask(), None);
    assert_eq!(b.depth_bid(), 0);
    assert_eq!(b.depth_ask(), 0);
    let _: Option<Price> = b.best_bid();
}
EOF

You don't need to run this; the types just have to compile. If cargo check -p openhl-clob is clean, you're good.

Common errors and fixes:

• error[E0277]: 'BTreeMap<Reverse<Price>, ...>' is not 'Default' — BTreeMap<K, V> requires K: Ord, and Reverse<T> requires T: Ord. Since Price: Ord from Lesson 1, this works. If you forgot to derive Ord on Price in Lesson 1, that derive chain breaks here.
• **error[E0599]: no method named 'len' for VecDeque<RestingOrder>** — typo in depth_bid/depth_ask. The method is VecDeque::len, accessed as .len()directly or asVecDeque::len(deque_ref)`.
• **error[E0382]: borrow of moved value: rp** in best_bid— using.map(|rp| rp.0)on a&Reverse<Price>reference: the closure receivesrp: &Reverse<Price>, and rp.0isPriceby value becauseReverse<Price>: Copy(sincePrice: Copy). If this errors, Priceisn'tCopy` — check Lesson 1's derive list.
• error: cannot find type 'RestingOrder' in module 'book' from outside — RestingOrder is private. That's intentional.

Design reflection

Three load-bearing decisions encoded here:

1. The state of the matching engine is two BTreeMaps. No order-id index, no best-price cache, no per-side counters. Everything else is derived from those two maps. Future optimizations (e.g., HashMap<OrderId, (Side, Price)> for O(1) cancel) can be added without changing the core data model. Start with the simplest representation that supports the operations; optimize when profiling demands it.

2. Reverse<Price> for bids is a type-level trick that saves matching-code complexity. Without it, every place that walks the book would have to branch: "if asks, use next; if bids, use next_back." With Reverse<Price> on bids, both sides use next uniformly. One symmetric API at the call site is worth one type asymmetry in the data definition.

3. RestingOrder is trimmed from Order to encode invariants. A resting order doesn't have a side (we know its side from which map it's in) and doesn't have an order_type (Market orders never rest). Removing those fields from RestingOrder makes the impossible states unrepresentable. Type design = constraint engineering.

Answer key

cd ~/code/openhl-reference
git checkout 55a9dff
diff -u ~/code/my-openhl/crates/clob/src/book.rs ./crates/clob/src/book.rs
diff -u ~/code/my-openhl/crates/clob/src/lib.rs ./crates/clob/src/lib.rs

After Lesson 3, your book.rs is approximately the first ~45 lines of the reference (struct definitions + new() + 4 accessors). The reference at this SHA also contains submit (~100 LOC, Lesson 4 + Lesson 5), cancel (~25 LOC, Lesson 6), and match_at_level helper (~30 LOC, Lesson 4). Those will land in subsequent lessons.

Return:

git checkout main

Common questions

Q: Why VecDeque and not Vec? Because we need fast push-back and fast pop-front. Vec::remove(0) shifts every element left — O(n). VecDeque::pop_front() is O(1). FIFO queues should always use VecDeque (or a real ringbuffer) — never Vec shifted from the front.

Q: What's Reverse actually doing under the hood? It flips the Ord::cmp direction. Reverse(a).cmp(&Reverse(b)) == b.cmp(&a). That's all. BTreeMap queries the key's Ord impl when sorting; by wrapping the key in Reverse, we make BTreeMap think Reverse(higher) is "smaller" than Reverse(lower) and walks accordingly.

Q: Couldn't RestingOrder just be Order? You could — but you'd carry the side and order_type fields uselessly (we already know the side from the map, and a resting Market order is a contradiction). The trim is small, but the type-level guarantee "you can't construct a resting Market order" comes for free.

Q: Why are the BTreeMap fields private? Because callers shouldn't directly modify the maps — they should go through submit / cancel (Lesson 4+ / Lesson 6) which maintain invariants like "an empty queue is never left in the map." If someone called book.asks.insert(price, VecDeque::new()), they'd create a phantom empty price level that best_ask() would return. The encapsulation prevents that.

Next lesson (Lesson 4)

You have the data structure. Lesson 4 puts the first matching logic on top of it — submit for Limit Buy orders. Reader writes the Buy branch that walks asks from cheapest, matches at-or-below the limit, and rests the unfilled remainder. ~60 LOC of body + a match_at_level helper that Lessons 4–5 both use. After Lesson 4, your matching engine produces real Fills for the most common scenario (limit buy crossing a resting ask).

Summary (3 lines)

• Book = BTreeMap<Reverse<Price>, VecDeque<Order>> bids + BTreeMap<Price, VecDeque<Order>> asks. Reverse trick = best bid first.
• VecDeque at each price level for FIFO. current_best_bid / current_best_ask are O(log n).
• No extra memory vs raw BTreeMap. Next: submit for Limit orders + match_at_level.