Deadlines: first deadline 28th November, final deadline 12th December. Submissions by Fire.

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

Your task is to implement a program in Java 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 a binary heap.

Making bids

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), and

Ada NK 70 72

if Ada changes her bid from 70 to 72kr (NK = ny köpkurs).

Reporting transactions

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 Bengt changed his price to 70kr, which matches Ada’s bid. So the program should print out:

Ada buys a share from Bengt for 70kr

If Ada had changed her bid before Bengt changed his, then instead it would say:

Ada buys a share from Bengt for 72kr

because Ada was willing to pay 72kr.

Printing the order book

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

Format of input data and output

Your program should be called Lab2.java. 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, 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. The sample code you can download from this page already deals with this.

Testing

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 code (the .class files or executable program). Then start a terminal and in that same directory run:

java -ea -jar testing.jar lab2test.Lab2GenTest Lab2

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:

java -ea -jar testing.jar -v 5 lab2test.Lab2GenTest Lab2

The last test case printed is the one that makes the program hang.

Other ways to run the test program

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:

java -ea -jar testing.jar -s 2000000 lab2test.Lab2GenTest Lab2

Step 1: writing the program

Your program should consist of the following classes:

Lab2

This class contains the main program. Start from Lab2.java. Try to understand what the existing code does, and what the missing parts should do, before you continue. You can wait until you have started on your priority queue before filling in the missing bits. You may change the existing code however much you want.

Bid (a class for bids)

This class describes a bid. Start from Bid.java.

The class is nearly complete, but you need to define equals and toString. Don’t implement Comparable, but use a separate comparator to compare bids (see below).

Two comparators

Write two comparators to help with inserting bids into your two priority queues. You need one for sellers and one for buyers.

compare should be compatible with equals, so that compare gives 0 if and only if equals gives true.

Here is a nice explanation about how comparators work.

A priority queue

You also need a class that implements a priority queue using a binary heap. If you want, you can start from PriorityQueue.java, or you can write your own. The example code implements deletion but not insertion. Read it and make sure you understand it before you go on.

Your priority queue should use an ArrayList with generic elements (don’t use a raw array). The constructor of your priority queue should take a Comparator as parameter. You use the comparator to decide the priority ordering of the elements in the heap.

You will need to make sure you understand how a binary heap works before you start implementing it. You might want to look at chapter 6.3 of Weiss, or at the slides, or at Wikipedia's description of binary heaps. You can also find detailed pseudocode at opendatastructures.org, which might help if you get stuck. You can also start from Weiss’s code if you like, but make sure to change it to use an ArrayList.

There’s no specific interface you have to implement, but you must at least support the following operations…

  • removal of the smallest element

  • insertion

  • an inefficient update operation — this should take the old and new elements as parameters

…since your main program will need these three.

You should use private helper methods siftDown and siftUp (or whatever names you choose) to do the sifting. You can then use these methods when implementing the heap operations.

Changing the priority

By issuing an NK or NS bid, the user can change a bid that is already in the orderbook. Hence in your priority queue class, you must be able to change the priority of an existing element.

You can do this in two steps: first find the element in the heap and change its priority, then restore the heap invariant. After modifying the heap, to restore the heap invariant, you should either sift the element up (if the priority increased) or down (if the priority decreased).

For the inefficient update you will search through the whole heap to find the updated element. Decide what you want to do if you don’t find the element. If you do find it, switch out the old element for the new and then sift down or sift up as appropriate to restore the heap invariant, as described above.

Changing the priority of an existing element will take O(n) time, since you must search through the whole heap to find the element whose priority has changed, before you can sift it. In step 3, below, you will fix this.

Step 2: making sure your program is correct

A class invariant

It’s a good idea to write down the class invariant that your priority queue satisfies, and test that it holds at the beginning and end of every call to a public method. Use assertions to test the class invariant. To test the assertions, when you run your program, you must give the flag -ea, otherwise they will be ignored.

An example of testing the invariant:

public void add(E x){
         assert invariant() : showHeap();

         ... // inserting the element and restoring the invariant

         assert invariant() : showHeap();
}

private boolean invariant(){
        // TODO: return true if and only if the heap invariant is true.
}

private String showHeap(){
        // TODO: return description of heap contents.
}

invariant checks the invariant that you have for your priority queue.

In the code above, showHeap will be called when the invariant doesn’t hold. You should implement this method so that it shows how the heap looks. This makes it easier to see what’s gone wrong.

Testing

Write a file with input data to your program and check that it works. Then use the test program to make sure that your program works. If the test program finds input data for which your program gives the wrong output, throws an exception, or where the class invariant doesn’t hold, then you must work out what has gone wrong.

Debugging

You can add print statements for debugging wherever you like in your code, but use System.err, not System.out. The test program prints everything out after every test. If you have trouble tracking down a bug that the test program found, save the input data that the test program used in a file and run your program on that file. If you use Eclipse you can give the filename as an argument, and use Eclipse’s debugger to step through the program if you like.

Step 3: efficient updates

Next you have to make updates work efficiently. The expensive part of updating an element is finding the element in the heap. The trick is to use a Map<E,Integer> to keep track of the index where each element is in the heap. That way, you can easily find the updated element in order to modify it.

You should use a HashMap for this because it gives (amortised) O(1) time complexity for all the map operations. When you update you just need to check in the Map where the old element is, instead of searching through the whole heap to find it. Each time you move an element in the heap you should update the Map accordingly.

Since you have to keep the Map up-to-date when you modify the heap, that means there should be an invariant relating the Map to the heap. Specifically, every key in your Map must be in the heap at the position that the Map thinks it is, and every element in the heap must be present in the Map. Update your class invariant so that it checks this — it will catch any places where you forget to update the Map.

After you have done this, changing the priority of an element will take O(log n) time (the cost of sifting).

Submission

Before you upload your code to Fire, make sure that it passes at least 2 million tests running the test program (you don’t need to write your own tests — running the test program is enough). The code should also meet the following requirements:

  • Your program should consist of: the main class, the priority queue (which should be generic over the type of elements), two comparators, and one class for bids. Each class should be in its own file. Don’t use package declarations in your code —  it makes it harder for us to mark.

  • Your code should be of reasonable quality. Make sure that it compiles without warnings, and is indented sensibly. Do not use SuppressWarnings to hide warnings. Comment any code that you think needs explaining. Think about whether each method should be private or public.

  • Documentation: make sure that each instance variable is documented, and write down an explanation of the class invariant. Document each method, including the meaning of the parameters, and write down the time complexity. (You may assume that all comparisons and hash table operations take O(1) time.)

  • Miscellaneous requirements: use an ArrayList and not a raw array in your priority queue class. use helper methods siftDown/siftUp or similar for insertion, removal and update to move elements in the heap. The method for updating an element must take two parameters: the old element and the new one. Only your main class may print anything. Finally, don’t call System.exit.

Extra tasks

Here is an optional extra task for those who want to learn more.

If you insert mutable elements in the priority queue, what problem can occur if an element is changed after it’s been inserted?

To solve this problem we can separate the priority from the inserted element. When we insert the element, we give the element and the priority separately, and when we update we give the element and the new priority. Implement a priority queue that does that.

Can you find a way to build this new priority queue on top of your existing class instead of modifying your existing code? Hint: consider defining an inner class that contains both a (mutable) element and an (immutable) priority. Your inner class will need to define the hashCode method correctly for the HashMap to work (as well as equals and compareTo), so you may want to read up on how to define hashCode in Java.