| Pledge of Honor |
| 1 (30 pts) | 2 (30 pts) | 3.a ( 15 pts) | 3. b (13 pts) | 3.c (12 pts) | Total (100 pts) | |||
A tennis match between two players is divided into sets and a set is divided
into games. For this problem, you will design and implement a collection of
classes that model how a game of tennis is scored.
First, let us review how a game of tennis is scored. The first player to score
at least four points and outscore his or her opponent by at least two points wins the
game. Rather than keep a count of how many points each player has scored, the
score is kept as follows.
In essence, once either player has scored three or more points, only
the difference between the players' scores is remembered, rather than each
player's total number. This means that the "state" of a tennis game can be
represented by a finite number of possibilities, regardless of how many points
are scored in a game.
First, complete the following class that will be the public interface to your
design.
public class GameScoringMachine {
// student to fill in any necessary fields ...
public
void playerOneScores() {
// student to fill in ...
}
public
void playerTwoScores() {
// student to fill in ...
}
// student to fill in any necessary non-public methods ...
}
Now, write below any remaining classes that you need to complete your design for
the following game:
You do NOT need to write the classes necessary for games other than this, but your design must obviously (to us) accommodate all possible games.
Consider the following technique for sorting called a "Sink Sort" . (See the demo)
Initially: 4 5 1 3 2 ("top" is on the left at index 0, "bottom" is on the right at index 4)
Split all the array into one element arrays: 4 5 1 3 2
2 is already sorted: 4 5 1 3 2
Sink 3 until at right of 2: 4 5 1 2 3
Sink 1-already there : 4 5 1 2 3
Sink 5 until at right of 3: 4 1 5 2 3
4 1 2 5 3
4 1 2 3 5
Sink 4 until at right of 3: 1 4 2 3 5
1 2 4 3 5
1 2 3 4 5
Basically the idea is that the next number is "sunk" by swapping places with its adjacent number on the right until it is smaller than the number to its right. According to Merritt's split-sort-sort-join model of sorting, Sink sort is an easy split/hard join algorithm. Write the code for the join method of Sink sort as described in the above. For your convenience, we provide you with the code for the sort framework, the stub code for SinkSort and a JUnit test code.
protected int split(Object[] A, int lo, int hi){
// Students to write code
}
/**
* Given A[lo..s-1] and A[s..hi] sorted,
* merges the two sub-arrays so that A[lo..hi] is sorted.
* The merge should be done in such a way that the numbers
in A[lo..s-1]
* sink by swapping places with their adjacent right (higher
indexed) neighbors until each
* is smaller than the number to its right, or until hi is
encountered.
*/
protected void join(Object[] A, int lo, int s, int hi){
// Students to write code.
}
Consider the TreeN framework as discussed in lecture #32. The code for the complete framework and the GUI demo is provided here for your convenience. Click here for UML and javadoc of TreeN and visitor.
For a TreeN , each node can contain an arbitrary number of data elements. A TreeN node containing k data elements has k+1 subtrees. We mainly use TreeN as a balanced sorted tree structure. The key structural methods for TreeN are splitUpAt, splitDownAt, and spliceAt. Review the PowerPoint presentation given in lecture #32 to see how these operations work. The published paper (given in lecture #32) also provides detailed descriptions of these behaviors.
A sorted TreeN of order 1 is nothing but a binary search tree.
A 2-3-4 tree is a sorted TreeN of order 3, i.e. each node can contain a maximum of 3 sorted data elements.
A red-black tree (see lecture #38) is a sorted TreeN of order 1 (i.e. a binary search tree) with the following properties:
A 2-3-4 tree can be transformed into a red-black tree by the following process (see page 4 of the lecture note on Red-Black trees for pictures illustrating the process)::
Conversely, a red-black tree can be transformed into an equivalent 2-3-4 tree by collapsing each red node into its black node parent and removing the color of each of the nodes.
Run the following demo program (rbdemo.jar) for an illustration of the equivalence between 2-3-4 trees and red-black trees:
Your task in this problem is to write TreeN visitors to carry out the equivalent transformations between 2-3-4 trees and red-black trees as described in the above. To decorate a raw data Object as black or red, we use a union of classes, ARBObject, Red and Black, with the corresponding visitor interface, IRBVisitor; click here for UML and javadoc of the Red-Black decoration (Note: varargs is denoted by array notation). For your convenience, the stub code for these visitors are included in the above source code download.
3.a Write the ITreeNAlgo called From234ToRedBlack to transform a 2-3-4 tree to a red-black tree as specified in the stub code given below.
/**
* Converts a 2-3-4 tree to a Red-Black tree.
*/
public class From234ToRedBlack implements ITreeNAlgo {
public static final From234ToRedBlack Singleton = new From234ToRedBlack();
private From234ToRedBlack() {
}
/**
* Perform recursively the following operation from the bottom of the tree
* up towards the root:
* Splits a 3 children node into a 2 children node ( like a binary tree)
* whose root contains a Black decorated object, and whose left subtree
* has a root that contains a Red decorated object.
*
* Splits a 4 children node into a 2 children node ( like a binary tree)
* whose root contains a Black decorated object, and whose left and right
* subtrees with Red decorated object roots.
*
* See Page 4 of the lecture note on Red-Black Tree.
*/
public Object caseAt(int i, TreeN host, Object... nu) {
switch(i) {
case 0: {
return host;
}
case 1: {
// This is the case with 1 data and 2 children subtrees.
// Decorate the root data as Black and recurse down the left
// and right subtrees.
// STUDENT TO COMPLETE
return host;
}
case 2: {
// This is the case with 2 data and 3 children subtrees.
// Recurse down the subtrees and split up the root node
// as specified.
// STUDENT TO COMPLETE
return host;
}
case 3: {
// This is the case with 3 data and 4 children subtrees.
// Recurse down the subtrees and split up the root node
// as specified.
// STUDENT TO COMPLETE
return host;
}
default: {
return host;
}
}
}
}
You are given the following complete code for class CollapseRed, which serves as a utility visitor in the process of transforming a red-black tree to a 2-3-4 tree. Note that CollapseRed is a visitor for a RBObject and not a TreeN visitor.
/**
* Serves as a utility visitor in the process of transforming a red-black tree
* to a standard (unmarked) 2-3-4 tree.
* The RBObject host is the root data of the given child TreeN of a given
* red-black TreeN.
* Only when this host is Red that the child tree spliced to its given parent
* TreeN at a given index in order to transform the parent red-black tree
* to a 2-3-4 tree whose root should contain only the (unmarked) raw data.
*/
class CollapseRed implements IRBVisitor {
public static final CollapseRed Singleton = new CollapseRed();
private CollapseRed() {
}
/**
* Splices the given child tree to the given parent tree at the given
* index and remove the red marker from the host.
* @param r the root data of the child TreeN inp[1].
* @param inp inp[0] is the index to be spliced at,
* in[1] is the child TreeN to be spliced into inp[2],
* inp[2] is the parent red-black TreeN.
* @return TreeN inp[2].
*/
public Object redCase(Red r, Object... inp) {
TreeN child = (TreeN)inp[1];
child.setDat(0, r.getObject());
return ((TreeN)inp[2]).spliceAt((Integer)inp[0], child);
}
/**
* Removes the black marker from the host.
* @param r the root data of the child TreeN inp[1].
* @param inp inp[0] is the index to be spliced at,
* in[1] is the child TreeN to be spliced into inp[2],
* inp[2] is the parent red-black TreeN.
* @return TreeN inp[2].
*/
public Object blackCase(Black b, Object... inp) {
TreeN child = (TreeN)inp[1];
child.setDat(0, b.getObject());
return inp[2];
}
}
You are to write the code to transform a red-black tree into an equivalent 2-3-4 tree in two steps as prescribed by the following.
3.b Write the TreeN visitor called CollapseAll that traverses the host TreeN from top to bottom and collapses all the red nodes with their parent black nodes, as specified in the stub code below. Hint: use the above CollapseRed.
Note:
/**
* Serves as a helper visitor in the process of transforming a red-black tree
* to a standard (unmarked) 2-3-4 tree.
* Tries to collapse the host tree to its parent tree at a given index.
* Only trees whose root nodes are red are to be collapsed with their parents.
*
* FOR STUDENT TO COMPLETE
*/
class CollapseAll implements ITreeNAlgo {
public static final CollapseAll Singleton = new CollapseAll();
private CollapseAll() {
}
/**
* Only collapses the red host tree to the given parent tree at the given
* index, and recursively traverses down the right and left subtrees to perform
* the same operation.
* @param inp inp[0] the index for where to splice to the parent,
* inp[1] the parent tree.
* @return this.
*/
public Object caseAt(int i, TreeN host, Object... inp) {
switch (i) {
case 0: {
return host;
}
case 1: {
// Hint: since the host can mutate, hold on to its left and right
// subtree before trying to collapse the host to its parent.
// STUDENT TO COMPLETE
return host;
}
default: {
return host;
}
}
}
}
3.c Write the TreeN visitor called
RBto234 that mutates a red-black
tree (i.e. a sorted TreeN of order 1) to an equivalent 2-3-4 tree, as specified
by the stub code given below. Hint: use the above CollapseAll.
/**
* Converts a Red-Black tree to a 2-3-4 tree.
* The host is assumed to be a red-black tree whose data nodes contain RBObject.
* The root node is a black node.
*
* FOR STUDENT TO COMPLETE
*/
public class RBto234 implements ITreeNAlgo {
public static final RBto234 Singleton = new RBto234();
private RBto234() {
}
/**
* Converts this red-black to a corresponding 2-3-4 tree by collapsing the trees
* with red nodes with their (black) parents.
*
* FOR STUDENT TO COMPLETE
*/
public Object caseAt(int i, TreeN host, Object... nu) {
switch(i) {
case 0: {
return host;
}
case 1: {
// Hint: since the host can mutate, unwrap the root data and hold on
// to the left and right subtrees before trying to collapse them to the host.
// STUDENT TO COMPLETE
return host;
}
default: {
return host;
}
}
}
}