COMP 9024, Assignment 3, 11s2
John Plaice
Fri Sep 23 14:23:04 EST 2011
You are to implement a Young tableau according to the specification given below. To
find out the details of how a Young tableau works, the description found in file
lyle.smu.edu/~saad/courses/cse3358/ps5/problemset5sol.pdf
is very well written.
You are to write two files, named Tableau.java and YoungTableau.java, and then
you will submit the using the following command.
give cs9024 assn3 Tableau.java YoungTableau.java
Because the assignment specification is one week late, the assignment due date has been
moved one week. The submission is due Tuesday, 27 September, 23:59:59.
All submitted Java files should begin with the line
package chapter8;
and should import the class6 types as needed.
You are provided with three files: EmptyTableauException.java, TableauInterface.
java, and TestYoungTableau.java.
The assignment is modeled on the implementation of the HeapPriorityQueue defined
in the book, pages 363–365. That setup there is:
• HeapPriorityQueue implements PriorityQueue.
• ArrayListCompleteBinaryTree implements CompleteBinaryTree.
In this assignment, the setup will be:
• YoungTableau implements PriorityQueue.
• Tableau implements TableauInterface.
1
1 Tableau.java
The Tableau class holds on to a square two-dimensional array of entries. Initially this
array is 1× 1, and as it fills up, it is grown by a factor of four, i.e., 2i× 2i is replaced with
2i+1 × 2i+1.
There are three fields:
protected int size;
protected int side;
protected Object[][] array;
where
• size keeps track of the number of actual entries currently in the tableau; it is ini-
tially 0.
• side keeps track of the number of times the array has been resized; it is initially 1.
• array is the actual two-dimensional array.
You will write a nested class as follows:
/** Nested class for a node holding on to the row and column. */
protected static class TPos implements Position {
E element; // element stored at this position
int row; // row index of this position in the array list
int col; // col index of this position in the array list
public TPos(E elt, int r, int c) { ... }
public E element() { ... }
public int row() { ... }
public int col() { ... }
public E setElement(E elt) { ... }
}
It is similar to the definition of MyPos on page 355.
The rest of the routines are inspired by the routines on pages 356–357.
In my implementation, the array is fully populated of TPos, and for each ∞ cells,
the element of the corresponding position is null.
2 YoungTableau.java
The YoungTableau class implements a Young tableau. Its declaration is as follows:
public class YoungTableau,V>
implements PriorityQueue { ... }
2
There are three fields:
protected Tableau> tableau; // underlying tableau
protected Comparator comp; // comparator for the keys
protected MyEntryComparator compEntry; // comparator for the entries
Because the tableau can have null elements in the positions, the comparator class cannot
simply be a comparator between keys. Rather, the entries need to be compared, and the
null pointers have to be propertly handled. The interface is as follows:
protected class MyEntryComparator
implements Comparator> {
public int compare(Entry a, Entry b)
throws ClassCastException { ... }
}
You will have to implement the routines of the PriorityQueue.
3 TestYoungTableau.java
I have written a program that allows you to test your code. It is in file TestYoungTableau.
java.
3
