In a stock exchange people can buy and sell shares in companies. There are online services where you can bid to buy or sell a certain stock and give the price you are willing to pay.
Suppose you want to buy shares in Ericsson for 70kr each. Your bid will then be compared against the asking price, that is the lowest price some seller is willing to accept for their shares. If the asking price is 70kr or less your bid is accepted and you get the shares for 70kr. (If the asking price is less than 70kr you still get charged the full 70kr.) The completed bid is then called a transaction. If the asking price is higher than 70kr, your bid will be added to Ericsson’s order book, where all uncompleted bids are registered. Your bid will then be completed when a seller appears who is willing to sell for 70kr.
Your task is to implement a program in Java or Haskell for a stock exchange following the description above. To simplify things it will only deal with one company. However, there will be many buyers and sellers. Bids will be given in whole kronor.
The order book consists of two priority queues, one for sellers and one for buyers. You will need to be able to compare a new bid against the lowest uncompleted sell-bid or the highest uncompleted buy-bid. Therefore, in the sellers' priority queue a lower price will get higher priority (be removed earlier from the priority queue), while in the buyers' priority queue a higher price will get higher priority. If the stock exchange is big it’s important that the priority queues work efficiently, so you will implement them using either:
a binary heap (if your solution is in Java)
a skew heap (if your solution is in Haskell)
A user can do three things: offer to buy, or to sell, or change an earlier bid. We write
Ada K 70
(K for köpa) if Ada wants to buy a share for 70kr. Likewise, we write
Bengt S 71
if Bengt wants to sell his share for 71kr,
Bengt NS 71 70
if Bengt changes his bid from 71 to 70kr (NS = ny säljkurs), or
Ada NK 70 72
if Ada changes her bid from 70 to 72kr (NK = ny köpkurs).
You can assume that the input data is such that each person has at most a single bid in the priority queue.
When a bid is accepted your program should report the purchase by printing it out. In the above example if Bengt changed his price to 70kr, it matches Ada’s bid. So the program should print out:
Ada buys a share from Bengt for 70kr
If Ada had instead changed her bid, then instead it would say:
Ada buys a share from Bengt for 72kr
because Ada was willing to pay 72kr.
Note that when either of the persons change their bid to the amounts above, a transaction will take place and there will no longer be any bid to change.
After your program has printed out all completed transactions, it should finally print out the book of uncompleted orders. The willing buyers and sellers should be listed in order of priority, for example:
Order book: Sellers: Cecilia 70, Bengt 71, David 73, Erika 77 Buyers: Ada 69, Fredrik 68, Gustaf 68
Your program should be called Lab2.java or Lab2.hs. It takes a command-line parameter which is a filename. That file will contain a list of bids, one bid per line, in the following format:
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 you run java Lab2 name-of-bid-file (for Java) or ./Lab2 name-of-bid-file (for Haskell), your program should print a list of transactions followed by the final order book in the following format:
Ada buys from Cecilia for 70kr David buys from Bengt for 72kr Order book: Sellers: Frida 71, Hanna 72, Erik 73 Buyers: Gustaf 69
It should also work to run java Lab2 < name-of-bid-file (for Java) or ./Lab2 < name-of-bid-file (for Haskell). The sample code you can download from this page already deals with this.
Although the full sequence of bids can be provided in a file, the program should perform a transaction if possible after each bid in the list. It should not add all the bids to the order book first and then start looking for transactions.
There is a test program which generates input data for your program. Please use it to test your program after every step before you move on!
Your program must pass at least 2 million test cases to make sure it works. The reason why you must run so many tests is that the test program builds increasingly long lists of bids where the number of generated test cases grows exponentially with the length of the list. So the more tests, the longer the priority queues that your program builds. If you run few test cases, you might miss bugs that only happen with longer priority queues.
Bear in mind that the test program is not guaranteed to find all the bugs in your code. So you should think carefully about your code and not just guess at things until the test program doesn’t find any mistakes.
Save the test program (testing.jar) in the same directory where you have your compiled Java or Haskell code (the .class files or executable program). Then start a terminal and in that same directory run either:
(for Java) java -ea -jar testing.jar lab2test.Lab2GenTest Lab2 (for Haskell) java -ea -jar testing.jar lab2test.Lab2GenTest Lab2External
If the test program goes into a loop and doesn’t print anything, you probably have an infinite loop in your program. In that case run:
(for Java) java -ea -jar testing.jar -v 5 lab2test.Lab2GenTest Lab2 (for Haskell) java -ea -jar testing.jar -v 5 lab2test.Lab2GenTest Lab2External
The last test case printed is the one that makes the program hang.
There are a number of flags you can use if you want. To see them, run:
java -ea -jar testing.jar --help java -ea -jar testing.jar lab2test.Lab2GenTest "Lab2 --help"
For example, you can skip earlier test cases with:
(for Java) java -ea -jar testing.jar -s 2000000 lab2test.Lab2GenTest Lab2 (for Haskell) java -ea -jar testing.jar -s 2000000 lab2test.Lab2GenTest Lab2External