Deadlines: first deadline 19th May, final deadline 29th May.

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.

To make your job a bit easier there is a description of how to go about solving the lab.

Your task

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 leftist heap (if your solution is in Haskell)

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

Changing the priority

In a binary or leftist heap, inserting an element and deleting the minimum element take O(log n) time in the worst case (where n is the size of the priority queue, assuming that comparisons take O(1) time and the underlying array doesn’t need to be expanded).

We can also change the priority of an existing element in a heap. After modifying the heap, to restore the heap invariant, we have to either sift the element up (if the priority increased) or down (if the priority decreased). Changing the priority of an existing element takes O(n) time, since we must search through the whole heap to find the element whose priority has changed, before we can sift it.

For the stock exchange to work efficiently, you must also have O(log n) complexity when changing existing elements in the heap. You can achieve this by using an updateable heap. In an updateable heap, we maintain alongside the heap a map which remembers the index where each element can be found. You should use a hash table to remember each element’s position in the heap. In this way we can find a given element in the heap with O(1) complexity. Changing the priority of an element will then take O(log n) time (the cost of sifting).

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

That is, if you run your program with no command-line arguments, it should read from System.in instead.

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). 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

You can also optionally do

java -ea -jar testing.jar -t -1 lab2test.Lab2GenTest "Lab2 -p"

for parallel testing. This runs several tests in parallel, which might be faster. Parallel testing assumes that you have a method String pureMain(String[]) which takes an array with all commands and returns a string with all output data instead of writing to System.out. If you use parallel testing, you should avoid System.out and System.err entirely, because several test cases will be mixed up in the output.

Step 1: getting started

Now we move on to how to solve the lab. 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.

A priority queue

You also need a class that implements a priority queue. 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.

Read through chapter 20.2 (other editions: 21.2) before you implement the priority queue. You can also read about heaps on Wikipedia. Start from the code in the course book if you like. You don’t need to write out the code, you can download it from the companion website, in the file weiss/util/PriorityQueue.java, but remember to change the package name, class names, author, and so on.

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.

For the inefficient update you will search through the whole heap for the element which is going to be changed. Decide what you want to do when 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 (see section Changing the priority for how to do this). You should use helper methods siftDown and siftUp (or whatever names you choose) to do the sifting — the book uses the name percolateDown instead of siftDown. You can then use these methods when implementing the heap operations.

Step 2: class invariant, testing and debugging

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, as described in section Changing the priority. Use a Map<E,Integer> to keep track of the index where each element is in the heap. 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.

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. 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 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 task

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.