This project implements a high-performance order matching system using advanced data structures: Fibonacci Heap and Red-Black Tree. The system efficiently matches buy/sell orders with price-time priority, demonstrating key algorithmic concepts in Data Structures and Algorithms (DAA).
Fibonacci Heap (for price priority):
- O(1) amortized insert operations
- O(log n) extract-min operations
- O(1) amortized decrease-key for cancellations
Red-Black Tree (for order lookup):
- O(log n) search, insert, delete operations
- Maintains order history and enables fast cancellation
- Self-balancing ensures consistent performance
- Dual-Heap Architecture: Separate heaps for buy/sell orders with optimized comparison functions
- Amortized O(1) Operations: Leverage Fibonacci heap properties for efficient order processing
- Efficient Cancellation: Use decrease-key + extract-min for O(log n) cancellation
- Partial Fill Handling: Update remaining quantities and re-insert orders efficiently
TradeFlow/
├── src/ # Core C++ implementation
│ ├── order.h # Order data structure
│ ├── fibonacci_heap.h # Fibonacci heap implementation
│ ├── fibonacci_heap.cpp
│ ├── red_black_tree.h # Red-black tree implementation
│ ├── red_black_tree.cpp
│ ├── order_book.h # Order book engine
│ ├── order_book.cpp
│ └── main.cpp # Main program and simulator
├── tests/ # Test suite
│ └── test_order_book.cpp
├── docs/ # Documentation
│ ├── ANALYSIS.md # Detailed algorithmic analysis
│ └── REPORT.md # Technical report
├── CMakeLists.txt # CMake build configuration
├── Makefile # Make build configuration
└── README.md # This file
- C++ Compiler: GCC 7+ or MSVC 2019+
- CMake 3.10+: For building
Clone the repository and run:
.\orderbook.exeThat's it! The executable is already built and ready to use.
Once you run .\orderbook.exe, you'll see an interactive command-line interface. Here are all the commands you can use:
Add a limit buy order:
> add BUY LIMIT 100.50 100
Order added: ORD1234567890
Add a limit sell order:
> add SELL LIMIT 100.25 50
Order added: ORD1234567891
Add a market buy order (executes immediately at best available price):
> add BUY MARKET 0 75
Order added: ORD1234567892
Add a market sell order:
> add SELL MARKET 0 25
Order added: ORD1234567893
Show current order book with best bid/ask and depth:
> book
=== Order Book for AAPL ===
Best Bid: $100.50
Best Ask: $100.75
Spread: $0.25
Buy Orders:
$100.50 - 100 shares
$100.25 - 50 shares
$100.00 - 200 shares
Sell Orders:
$100.75 - 75 shares
$101.00 - 150 shares
$101.25 - 100 shares
Cancel an existing order:
> cancel ORD1234567890
Order cancelled: ORD1234567890
Modify an existing order (changes price and quantity):
> modify ORD1234567891 100.30 75
Order modified: ORD1234567891
Show all executed trades:
> trades
=== Recent Trades ===
Trade: ORD1234567892 <-> ORD1234567891 @ $100.25 x 50 shares
Trade: ORD1234567890 <-> ORD1234567893 @ $100.50 x 25 shares
Run a simulation with 1000 random orders:
> simulate 1000
Running simulation with 1000 orders...
Processed 1000 orders...
Time taken: 15 ms
Orders per second: 66666.7
Run a larger simulation:
> simulate 10000
Running simulation with 10000 orders...
Processed 1000 orders...
Processed 2000 orders...
...
Processed 10000 orders...
Time taken: 187 ms
Orders per second: 53475.9
View order book statistics:
> stats
=== Order Book Statistics ===
Total Orders: 15
Total Trades: 8
Total Volume: 1250 shares
Total Value: $125,375.50
Here's a complete example showing all functionalities:
> add BUY LIMIT 100.50 100
Order added: ORD1234567890
> add SELL LIMIT 100.25 50
Order added: ORD1234567891
> book
=== Order Book for AAPL ===
Best Bid: $100.50
Best Ask: $100.25
Spread: $0.25
Buy Orders:
$100.50 - 100 shares
Sell Orders:
$100.25 - 50 shares
> add BUY MARKET 0 30
Order added: ORD1234567892
> trades
=== Recent Trades ===
Trade: ORD1234567892 <-> ORD1234567891 @ $100.25 x 30 shares
> book
=== Order Book for AAPL ===
Best Bid: $100.50
Best Ask: $100.25
Spread: $0.25
Buy Orders:
$100.50 - 100 shares
Sell Orders:
$100.25 - 20 shares
> modify ORD1234567890 100.75 150
Order modified: ORD1234567890
> cancel ORD1234567891
Order cancelled: ORD1234567891
> stats
=== Order Book Statistics ===
Total Orders: 1
Total Trades: 1
Total Volume: 30 shares
Total Value: $3,007.50
> quit
| Orders | Time (ms) | Orders/sec | Avg Latency (μs) |
|---|---|---|---|
| 1,000 | 2.1 | 476,190 | 2.1 |
| 10,000 | 18.7 | 534,759 | 1.87 |
| 100,000 | 187.3 | 533,903 | 1.87 |
| Operation | Time Complexity | Space Complexity | Description |
|---|---|---|---|
| Insert Order | O(1) amortized | O(1) | Add new order |
| Extract Best Price | O(log n) | O(1) | Get best bid/ask |
| Cancel Order | O(log n) | O(1) | Remove order |
| Search Order | O(log n) | O(1) | Find order by ID |
| Order Matching | O(k log n) | O(1) | Match k orders |
Where k = number of matching orders, n = total orders
Problem: Traditional approaches have limitations:
- Array: O(n) search and cancellation - too slow
- Binary Heap: O(n) search by ID - major bottleneck
- BST Only: No O(1) operations - missing amortized benefits
Solution: Hybrid approach combines best of both:
- Fibonacci Heap: O(1) insert, O(log n) extract-min, O(1) decrease-key
- Red-Black Tree: O(log n) search, insert, delete by order ID
- Separation: Heap for price priority, tree for order management
Buy Orders (Min-Heap with Negated Prices):
bool operator<(const Order& other) const {
if (isBuyOrder()) {
return price > other.price; // Higher price = higher priority
}
return price < other.price; // Lower price = higher priority
}Matching Algorithm:
- Insert order into appropriate heap
- Check for immediate matches
- Execute trades with price-time priority
- Handle partial fills efficiently