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.

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

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 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 replace it, then restore the heap invariant because the new value may have (and typically has) a different priority. 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 (but not strictly required in this lab) 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.