[Bug Report] `sell_orders` orders asks highest-price-first, so a marketable buy can skip a better offer and cross the book

[OPTIONPOOL]

Found while integrating vincurious/ordermatchingengine into an open matching-engine benchmark, the Matching Engine Performance Challenge — it cross-checks engines against the byte-identical consensus of other open-source engines. The matcher is otherwise clean; this is a latent defect in the sell_orders priority queue's comparator that surfaces the moment more than one ask is resting and a buy crosses, and it reproduces with three orders driven straight through OrderBook.addOrderHelper().

Pinned at current master (e244231).

Environment

• Commit: e244231d90b2a44828167bf7a23d06a693e3a6e1
• Language/toolchain: Java (any JDK 8+); only the matcher classes are needed — no file/Swing/CSV layer.
• Build (matcher only):

  javac -d out src/OrderInterface.java src/Order.java \
               src/OrderBookInterface.java src/OrderBook.java Repro.java
  java -cp out Repro

What happens

The ask book (sell_orders) keeps the highest-priced ask at its head instead of the lowest. The matcher always peeks the head as the best contra offer, so two things go wrong for an incoming buy:

1. When the buy does cross, it is matched against the highest resting ask first (the worst available offer) rather than the lowest.
2. More seriously, when the buy's limit sits below the highest ask but at or above a lower resting ask, the cross test against the (highest) head fails, so addOrder() stops and rests the buy — even though a lower, marketable ask is sitting right there. The book is left crossed: a resting bid priced at or above a resting ask.

The bid book (buy_orders) uses the same descending-price ordering, which is correct for bids (the highest bid belongs at the head). That symmetry is what makes the sell-side copy easy to miss — only the ask book needs the opposite (lowest ask at the head).

Minimal reproduction

Rest two asks (100 and 102), then send a marketable BUY @ 101:

import java.util.Date;

public class Repro {
    static int seq = 0;
    static Order ord(int id, double px, String side, int qty) {
        return new Order(id, new Date(1000 + (seq++)), "AAPL", px, side, qty);
    }
    public static void main(String[] a) {
        OrderBook book = new OrderBook("AAPL");
        book.addOrderHelper(ord(1, 100, "SELL", 50));   // resting ask 100
        book.addOrderHelper(ord(2, 102, "SELL", 50));   // resting ask 102
        System.out.println("best ask (sell head) = " + book.sell_orders.peek().order_price);

        book.addOrderHelper(ord(3, 101, "BUY", 50));    // marketable vs the ask at 100
        double lowestAsk = Double.POSITIVE_INFINITY;
        for (Order o : book.sell_orders) lowestAsk = Math.min(lowestAsk, o.order_price);
        double bestBid = book.buy_orders.isEmpty() ? Double.NEGATIVE_INFINITY
                                                   : book.buy_orders.peek().order_price;
        System.out.println("buyer traded?  " + book.filled_orders.containsKey(3));
        System.out.println("best bid = " + bestBid + ", lowest ask = " + lowestAsk
                           + ", crossed? " + (bestBid >= lowestAsk));
    }
}

Output:

best ask (sell head) = 102.0
buyer traded?  false
best bid = 101.0, lowest ask = 100.0, crossed? true

Expected: the best ask is 100.0, the buy trades at 100, and the book is not crossed. (The mirror is correct: a SELL crossing two resting bids hits the highest bid first, because the bid book's descending order is right for bids — which is why the same ordering on the ask book is easy to overlook.)

Mechanism / root cause

The sell_orders comparator in the OrderBook constructor returns the values for a descending price order — the same as the bid book — so the lowest ask compares as the "greatest" element and the highest ask ends up at the PriorityQueue head:

// src/OrderBook.java:75-78  (sell_orders comparator)
if (o1.order_price < o2.order_price) {
    return 1;
} else if (o1.order_price > o2.order_price) {
    return -1;
}

A PriorityQueue keeps the least element at the head, so these return values place the highest ask there. addOrder() then peeks that head as the best contra order and tests it against the incoming buy (src/OrderBook.java:183, :186: placed_order.order_price >= currentOrderFromQueue.order_price). With the highest ask at the head, a buy that should lift a lower resting ask instead compares against the highest one — matching at the wrong price when it crosses, or failing the test and resting (crossing the book) when it does not. The bid book's identical block (:54-57) is correct because bids do want the highest price first.

Suggested fix

Invert the price comparison for the ask book so the lowest ask sits at the head (mirroring how the bid book keeps the highest bid). The time tiebreak just below it already orders earliest-first and needs no change:

--- a/src/OrderBook.java
+++ b/src/OrderBook.java
@@ public int compare(Order o1, Order o2) {   // sell_orders
-				if (o1.order_price < o2.order_price) {
-					return 1;
-				} else if (o1.order_price > o2.order_price) {
-					return -1;
+				if (o1.order_price < o2.order_price) {
+					return -1;            // lowest ask at the head (best offer first)
+				} else if (o1.order_price > o2.order_price) {
+					return 1;
 				} else {

With this applied, the reproduction prints best ask = 100.0, buyer traded? true, and crossed? false. Only the ask ordering changes; matching order on the bid side, fill quantities, counterparties, and the rest of the book state are untouched.

---

This is a reproducible, time-stamped snapshot of e244231, offered back in case it's useful — not a comment on the project. I didn't find an existing issue covering the ask ordering, and the lines are unchanged on master. Thanks for sharing the engine; happy to provide the failing case or a small harness.

Respectfully submitted.