At a stock exchange, shares of publicly traded companies change hands. If you have an account with an online stock broker, you can participate in the trading over the Internet. Many banks offer their customers trading platforms where you can place bids for shares in certain companies, at the maximum price you are willing to pay.
Assume that you place a bid for Ericsson shares at a price of 70 SEK per share. This bid will be matched against the current lowest ask, i.e. the lowest price point at which a seller is currently willing to part with their shares in Ericsson. If there is currently an ask for 70 SEK or lower, your bid is accepted and you get to buy the shares at the that price. Placing a bid at a lower price than the current lowest ask is, of course, somewhat daft, but must be handled even so.
If the current selling price is higher than 70 SEK, your bid will be entered into the Ericsson order book, where all non-closed bids are recorded. If, at a later point in time, a seller should appear who is willing to part with their Ericsson shares at 70 SEK apiece, your bid will then be fetched from the order book and matched to this ask, and the trade will be completed.
Your task is to write a program to handle the kind of stock trading described above, either using Haskell or Java. For simplicity, your program only needs to deal with shares in a single company, and each bid is assumed to concern only a single share. It must, however, be able to handle an arbitrary number of buyers and sellers. Bids are given in units of whole SEK; no öre.
The order book consists of two priority queues: one containing all asks and one containing all bids. In the priority queue for asks, lower price means higher priority. In the priority queue for bids, on the other hand, higher price means higher priority. Since it's very important to maintain short turnaround times even at extremely large volumes of trade, these queues must be implemented as efficiently as possible; in this lab, you are going to implement them using the following data structures:
A user may take three different actions: buy, sell, and update an already existing bid or ask. The interface to perform these actions consist of a plain text file containing one bid, ask, or update per line. If, for instance, we write:
Ada K 70
This would indicate that Ada wants to buy a share at 70 SEK. Similarly, if we write:
Bengt S 71
This means that Bengt wants to sell a share at 71 SEK. To update this ask, we would write:
Bengt NS 71 70
...to lower Bengt's old 71 SEK ask to 70 SEK. To update Ada's bid, we would write:
Ada NK 70 72
...to raise Ada's old 70 SEK bid to 72 SEK.
Whenever a bid is accepted, your program shall print a notification to the command line. In the above example, Bengt changed his ask to 70 SEK, which matches Ada's bid. In this case, the program should print:
Ada köper från Bengt för 70 kr
After your program has printed all closed deals, it must print the remaining order book. Asks and bids must be listed in order of highest priority, as shown in the following example:
Orderbok: Säljare: Cecilia 70, Bengt 71, David 73, Erika 77 Köpare: Ada 69, Fredrik 68, Gustaf 68
In both binary and binomial heaps, insertion as well as removal of the element with the highest priority has a worst case time complexity of O(log n), where n is the size of the queue, and given that comparing two elements takes constant time. The time complexity of updating the priority of an element is O(n), as the worst case scenario involves traversing the entire heap to find the element to update.
If you choose to use Java: with a binary heap, it is possible to implement the update operation with a time complexity of O(log n) by using an auxiliary data structure to keep track of where in the heap any given element resides. One might for instance use a hash table for this purpose. By doing this, we can find any given element in the heap with time complexity O(1) (assuming a perfect O(1) hash function). We recommend that you implement the update operation in this way, but the less efficient method of looking up the element to update by traversing the entire heap is also accepted. Note, however, that this traversal must not have worse time complexity than O(n).
If you choose to use Haskell: finding the element to update by traversing the heap is the recommended solution. The traversal must have a worst case time complexity of O(n).
Your main program must be called Lab2.java or Lab2.hs. It must accept as an argument bids the path to a file containing a list of bids and asks as described above, like this:
Ada K 70 Bengt S 71 Cecilia S 70 Bengt NS 71 72 David K 72 Erik S 73 Frida S 71 Gustaf K 69 Hanna S 72
When running java Lab2 bids or runhaskell Lab2 bids, your program must print a list of closed deals, followed by the final state of the order book in the following format:
Ada köper från Cecilia för 70 kr David köper från Bengt för 72 kr Orderbok: Säljare: Frida 71, Hanna 72, Erik 73 Köpare: Gustaf 69
It must also be possible to run java Lab2 < bids or runhaskell Lab2 < bids to get the same result.
You may, if you wish, use the following templates for your submissions: Lab2.java or Lab2.hs.
Your program must report incorrect update commands, i.e. when a buyer or a seller attempts to modify a non-existing bid or ask, by printing an error message to the console. For more "unexpected" errors, throwing an unhandled exception is acceptable.
Write a few text files containing sequences of bids, asks, and updates to test your program. Run enough tests to make sure that all three actions work as expected. During your testing, it may be helpful to print the state of the order book after each command.
You should make use of the provided test suite to check your solution. Any solution which does not pass the test suite will be summarily rejected.
Your documentation must contain: