.
General Structure:
As suggested by WK Selph:
The idea is to have a binary tree of Limit objects sorted by limitPrice,
each of which is itself a doubly linked list of Order objects. Each side
of the book, the buy Limits and the sell Limits, should be in separate trees
so that the inside of the book corresponds to the end and beginning of the
buy Limit tree and sell Limit tree, respectively. Each order is also an
entry in a map keyed off idNumber, and each Limit is also an entry in a
map keyed off limitPrice.
With this structure you can easily implement these key operations with
good performance:
Add – O(log M) for the first order at a limit, O(1) for all others
Cancel – O(1)
Execute – O(1)
GetVolumeAtLimit – O(1)
GetBestBid/Offer – O(1)