Working in Groups on this Assignment

As on Problem Set 1, you are encouraged to work in groups of up to three people on this assignment. The times reported on PS1 indicate that this is a good idea. The average time to complete PS1 was about 7 hours for group members but over 9 hours for individuals working alone. Moreover, all but one group finished the assignment in 8 hours or less, while over half of those working alone took 9 or more hours. If you are in this latter category, you should definitely consider joining a group for PS2, since it is likely to save you lots of time. This is especially important considering that PS2 is a bit more challenging than PS1.

On this assignment, I recommend that you work with different team members than you did on Problem Set 1, just to get to know more of your fellow students. But I realize it is difficult to find partners with similar schedules, so if you've already formed a compatible group, you may stick together for this assignment. If you're in a group of two, I hope you will consider "adopting" a third member who is not yet associated with a group. The CS111-Fall99 Q&A folder is an excellent place to seek group members.

Because I am posting this problem set late (the afternoon of Saturday, Sep. 18), I have extended the due date of the assignment from Thursday, Sep. 23 to Friday, Sep. 24.

Because I will be away at a conference between Sep 25 -- Oct 2, I will not be able to return your graded PS2s until I return.

Your team should submit a single softcopy (electronic) and
hardcopy (paper) solution packet to these problems. For the softcopy
solution, submit the solution folder for each of the problems to the
drop folder of *one* of your team members. For the hardcopy
solution, submit a printout of the relevant code for each problem.
Your hardcopy solution should begin with a cover sheet that can be
found here. The cover sheet asks you to
list the names of your team members, the location of the dropped
softcopy solution, and the time you took on each problem.

Problem 1: Object Diagrams

In this problem, you will draw some object diagrams to illustrate your understanding of the Java Object Model and the important notion of sharing. Study the following code for the Pair class:

publicclass Pair {// Instance variables:publicint left;publicint right;publicPair (int l, int r) { left = l; right = r; }publicbooleanequals (Pair p) {return(left == p.left) && (right == p.right); }publicstaticboolean[ ] comparisons (Pair [ ] [ ] pairArrays) {boolean[ ] bools = new boolean [8];for(int i = 0; i < 4; i++) { bools[i] = (pairArrays[i][0] == pairArrays[i][1]); }for(int j = 0; j < 4; j++) { bools[j+4] = (pairArrays[j][0].equals(pairArrays[j][1])); }returnbools; }publicstaticvoidtest() {// Note: new Pair [4] [ ] creates a 4-slot array // whose slots hold objects of type Pair [ ].Pair [ ] [ ] pairss =newPair [4] [ ]; Pair [ ] a =newPair [3]; a[0] =newPair (1,2); a[1] = a[0]; a[2] =newPair (3,4); pairss[0] = a; pairss[1] = a; pairss[2] =newPair[3]; pairss[2][0] =newPair(1,2); pairss[2][1] = pairss[0][1]; pairss[2][2] = pairss[1][2]; pairss[3] = pairss[2]; boolean [ ] bools1 = comparisons(pairss);// *** Object Diagram #1 should depict this point ***pairss[1][1] = a[2]; pairss[3][0] = pairss[3][1]; boolean [ ] bools2 = comparisons(pairss);// *** Object Diagram #2 should depict this point ***}publicstaticvoidmain (String [ ] args) { test(); } }

For this problem, you are asked to draw object diagrams that are "snapshots" of the state of the Pair application at two "snapshots" during its execution:

- Draw an object diagram that depicts the state of the program immediately after the statement

is executed.

- Draw an object diagram that depicts the state of the program immediately after the statement

is executed.

Recall that an object diagram shows the state of the objects in ObjectLand. There are two kinds of objects: (1) class instances, which are drawn as boxes labelled by their class name that contain instance variables labelled by their names and (2) array objects, which are drawn as boxes labelled by their array type that contain variables labelled by their index. Variables themselves are drawn as boxes that contain either primitive data (e.g., numbers, booleans, characters) or references (pointers) to other objects. Sharing is indicated by having two pointers that point to the same object. For sample object diagrams, see the object diagrams in Problem 4 of this assignment.

Your object diagrams should **not** show execution frames, but
they should include the following local variables of the test method: pairss, a, bools1, and bools2.
These variables may be shown "floating" in the object diagrams. The
diagrams should also show all objects that are reachable from these
four variables. All such objects (both instances and arrays) should
be labelled with their type, and should be drawn as boxes that
contain labelled variables.

Notes:

- The equality operator
*a*==*b*is true for objects*a*and*b*if and only if*a*and*b*are the exact same object -- i.e., they were created by the same call to**new**. In an object diagram, two object references are == if and only if they they point to the same instance or array on the page.

- The equals method for pairs returns true if and only if they are structurally equivalent -- i.e., they have the same left and right components. Two pairs may be equals without being ==, but two pairs that are == are guaranteed to be equals.

For this problem, you should submit only a harcopy version of your two object diagrams. You can use pencil and paper for your diagrams -- you need not format them on a computer! (Unless you are very adept with drawing software, formatting the diagrams on the computer will take you much longer than drawing them by hand.)

Problem 2: Blackjack Backtrack

In Problem 3 of Problem Set 1, you implemented a simplified version of a Blackjack game in which aces always counted as 11 points. But, as explained in that problem, aces can count as either 1 or 11 in a real game of Blackjack. In this problem, you will modify the Blackjack game from Problem 3 of Problem Set 1 to count aces as either 1 or 11.

To see how this can be done, let's consider a concrete example: the hand [AC 5S AD 3H]. The handPoints() method of the BlackjackGame class you implemented in PS1 would count 30 points for this hand, which is a clear bust. But other possibilities point values for this hand are 10 (if both aces count as 1) and 20 (if one ace counts as 1 and the other as 11). We would like handPoints() to return the largest of these values that is less than or equal to 21 (20, in this case). If none of the values meets this criterion, we would like the handPoints() to return the smallest of the values, which will necessarily be greater than 21.

Solving this problem amounts to exploring a decision tree in which there is a two-way branch for every ace: one branch indicates that the ace counts as 11, while the other branch indicates that the ace counts as 1. Here is such a tree for our sample hand:

The top node of the tree is called the *root*, while the
bottommost nodes (the black dots) are called *leaves*. The lines
connecting two nodes are called *edges*. The tree assumes that
we explore the cards from the highest index of the hand down, so 3H
is at the root. Each edge of the tree is labelled with a
*weight* that is the number of points charged for traversing an
edge. Any path from the root down to a leaf corresponds to one way of
counting the points in the hand. The point value associated with each
root-to-leaf path is shown below each leaf. We will call a path from
a node to leaf *successful* if the point value at the leaf is
<= 21.

Conceptually, we would like to explore this tree as follows, using a strategy we'll call maxPointsLEQ. Assume that as it descends the tree, maxPointsLEQ keeps track of the maximum point value maxval that can be allocated to the as-yet-unexplored cards. When maxPointsLEQ starts at the root of the tree, maxval is initially 21. At every node it encounters, maxPointsLEQ will return the maximum number of points less than or equal to maxval for the unexplored cards (i.e., the cards at or below the node being encountered); if there is no such point value, it returns the smallest number of points greater than maxval. Since maxval is 21 at the root of the tree, invoking maxPointsLEQ at the root will yield a solution to our Blackjack problem.

Any time maxPointsLEQ encounters a
non-ace card *c* with Blackjack value *v*, we know that
*v* must be subtracted from maxval
to yield the maximum value for the remainder of the unexplored cards.
We also know that the value returned by maxPointsLEQ at *c* will
be *v* more than the value returned for the remainder of the
unexplored cards.

But when maxPointsLEQ encounters an
ace, there is a decision to be made: is it counted as an 11 or as a
1? Since we're looking for the largest value <= maxval, we will first assume that it counts as
11 (i.e., take the left branch) and see how this decision pans out.
If the value result returned by maxPointsLEQ for the remainder of the hand is
<= (maxval - 11), then we
*succeed*; there is a successful path from the ace to a leaf
that has value result + 11. However, if
the value result returned by maxPointsLEQ for the remainder of the hand is
> (maxval - 11), then we *fail*;
there is no successful path to a leaf based on the assumption that
the ace counts as 11 points. So instead we *backtrack* (i.e.,
change our decision at a choice point) and instead assume that the
ace counts as 1. Again we can either succeed (the value result returned for the rest of the hand is
<= (maxval - 1)) or fail (the value
result returned for the rest of the hand
is > (maxval - 1). But this time, if
we fail, there are no more choices to be tried, so maxPointsLEQ must return result + 1 in either case. (In the success
case, this is the largest number <= maxval, and in the failure case, it is the
smallest value > maxval.)

To give you a better sense how maxPointsLEQ processes a hand, here is the decision tree from above where every node is annotated with the value of the parameter maxval at that node and the returned value result for that node:

Note in this case that the maxPointsLEQ strategy only explores two root-to-leaf paths in the tree before it succeeds.

As another example, here is the annotated decision tree for the hand [AC 7S AD 3H]:

Here, the maxPointsLEQ strategy must explore all four root-to-leaf paths in the tree before it succeeds. It is also possible for maxPointsLEQ to fail on a hand. Indeed, in the above example, it fails for the subhands [7S AC] and [AC] in the left half of the tree, as well as for the empty subhand [ ] at the leaf labelled 22 on the right hand side of the tree. In all these cases, result is greater than maxval.

The strategy described above can be encoded as a recursive function (static method) maxPointsLEQ that takes two parameters (the hand of unexplored cards and maxval) and returns the largest point value for the cards <= maxval (if it exists) or the smallest point value for the cards > maxval (otherwise). For simplicity, we will assume that maxPointsLEQ behaves non-destructively; that is, the state of the hand parameter when a particular invocation of maxPointsLEQ is made should be the same as the state of the hand parameter when this invocation returns. Thus, any caller of maxPointsLEQ may assume that maxPointsLEQ does not change the state of its hand parameter.

The initial call to maxPointsLEQ is made from handPoints(), where 21 is supplied as the initial maxval:

publicstaticinthandPoints (Hand h) {returnmaxPointsLEQ(h, 21); }publicstaticintmaxPointsLEQ (Hand h,intmaxval) {Flesh out the details of this method.}

To begin this problem, download the Cards folder from the CS230 download folder. This folder contains all the code you will need to do Problems 2, 3, and 4 of this assignment. The BlackjackGame.java file contains a complete implementation of the BlackjackGame class except for the missing body of the maxPointsLEQ method, which you must flesh out.

Notes:

- Although this problem has a concise solution, it is tricky.
You need not do it first. You may well want to attack Problems 3
and 4 before solving this problem.

- maxPointsLEQ should
*not*construct any sort of tree data structure. The nodes in the decision trees drawn above should instead be encoded by the execution frames of maxPointsLEQ. That is, a node labelled with card*c*, maxval value*m*and return value*r*corresponds to an execution frame whose h parameter is a hand whose last card is*c*, whose maxval parameter is*m*, and whose return value is*r*. A decision point at an ace is encoded by calling maxPointsLEQ twice on the rest of the hand, with different assumptions for maxval. Note that execution frames need to be constructed only for the part of the decision tree that is actually explored.

- In order to make maxPointsLEQ
behave non-destructively, you will probably want to take one of
two approaches:
- Make sure that all side effects (e.g., remove()) that you
perform are on a
*copy*of the hand parameter. - Perform side effects directly on the hand parameter, but
remember to undo these side effects later before returning from
maxPointsLEQ. (You used the same
idea in CS111 whenever you wrote Buggle routines that returned
to their starting position in addition to returning a value.) .
Study the function discardRecNonTail in HandFunctions.java (also in the Cards folder) for an example of a
function that undoes side effects in this manner.

- Make sure that all side effects (e.g., remove()) that you
perform are on a
- As in Problem Set 1, you should make use of the provided cardPoints() method to determine the point
value associated with a card.

- You are extremley unlikely to succeed on your first try! It is
therefore essential that you use good debugging techniques to
determine why your code doesn't work as expected. To help you out,
I have provided some auxiliary methods in Blackjack class for
printing out so-called trace information. You should use the
following two methods in your implementation of maxPointsLEQ:
- MPLEnter(): Make the invocation MPLEnter(h,maxval); the first statement in the body of maxPointsLEQ. This will display the argument information every time maxPointsLEQ is invoked, and will display the information for nested calls at an indentation level that indicates the nesting level.
- MPLExit(): Where you would
normally write
**return***result-exp*to return the value of the expression

*result-exp*, you should instead write**return**MPLExit(h, maxval,*result-exp*)This will display, at an appropriate indentation level, the argument and returned value information every time an invocation of maxPointsLEQ returns.

For example, the debugging information that should be displayed when invoking handPoints() on the hand [AC, 5S, AD, 3H] should be:

Enter maxPointsLEQ(Hand[AC,5S,AD,3H], 21) | Enter maxPointsLEQ(Hand[AC,5S,AD], 18) | | Enter maxPointsLEQ(Hand[AC,5S], 7) | | | Enter maxPointsLEQ(Hand[AC], 2) | | | | Enter maxPointsLEQ(Hand[], -9) | | | | Exit maxPointsLEQ(Hand[], -9) => 0 | | | | Enter maxPointsLEQ(Hand[], 1) | | | | Exit maxPointsLEQ(Hand[], 1) => 0 | | | Exit maxPointsLEQ(Hand[AC], 2) => 1 | | Exit maxPointsLEQ(Hand[AC,5S], 7) => 6 | Exit maxPointsLEQ(Hand[AC,5S,AD], 18) => 17 Exit maxPointsLEQ(Hand[AC,5S,AD,3H], 21) => 20

Note how nested calls are indented and how the vertical bars line each entry point up with the corresponding exit point. As another example, here is the debugging information that should be displayed when invoking handPoints() on the hand [AC, 7S, AD, 3H]:

Enter maxPointsLEQ(Hand[AC,7S,AD,3H], 21) | Enter maxPointsLEQ(Hand[AC,7S,AD], 18) | | Enter maxPointsLEQ(Hand[AC,7S], 7) | | | Enter maxPointsLEQ(Hand[AC], 0) | | | | Enter maxPointsLEQ(Hand[], -11) | | | | Exit maxPointsLEQ(Hand[], -11) => 0 | | | | Enter maxPointsLEQ(Hand[], -1) | | | | Exit maxPointsLEQ(Hand[], -1) => 0 | | | Exit maxPointsLEQ(Hand[AC], 0) => 1 | | Exit maxPointsLEQ(Hand[AC,7S], 7) => 8 | | Enter maxPointsLEQ(Hand[AC,7S], 17) | | | Enter maxPointsLEQ(Hand[AC], 10) | | | | Enter maxPointsLEQ(Hand[], -1) | | | | Exit maxPointsLEQ(Hand[], -1) => 0 | | | | Enter maxPointsLEQ(Hand[], 9) | | | | Exit maxPointsLEQ(Hand[], 9) => 0 | | | Exit maxPointsLEQ(Hand[AC], 10) => 1 | | Exit maxPointsLEQ(Hand[AC,7S], 17) => 8 | Exit maxPointsLEQ(Hand[AC,7S,AD], 18) => 9 Exit maxPointsLEQ(Hand[AC,7S,AD,3H], 21) => 12

- One way to test your maxPointsLEQ
method is to play lots of games of Blackjack. A better way to test
your method is to write a main()
method for the BlackjackGame class
that calls handPoints() on a
representative collection of hands.

- When we discuss linked-list data structures this coming week,
we will see that the above backtracking algorithm can be expressed
more simply and elegantly using lists.

- There is a simpler algorithm for solving this problem that
does not require recursion or backtracking. Suppose you first
count every ace to be 11 points, giving a point value of 30 to the
sample hand [AC 5S AD 3H]. Observe that switching an ace from
counting as 11 to counting as 1 will reduce the point value of the
hand by 10. To see how many times we can subtract 10, we just need
to count the number of aces in the hand (2 in this case). Then we
can take our original maximal point value and keep subtracting one
10 for each ace until we get to a value less than or equal to 21,
which we return. If we run out of aces before reaching such a
value, then we return the final point total, which must be the
smallest point value for the hand greater than 21.

This alternative algorithm can easily be implemented with a few loops. In fact, you will receive**extra credit**if you implement this alternative algorithm**in addition to**the backtracking version.

It's worth noting that the alternative algorithm takes advantage of special features of the problem and is not easily generalizable. For instance, suppose we change the rules of the game so that Jacks count as either 10 or 1, Queens count as either 10 or 2, and Kings count as either 10 or 3. Then it is easy to extend the backtracking solution to handle the new rules, but it is not easy to modify the non-backtracking algorithm to do so.

For this problem, your hardcopy submission should be your final version of BlackjackGame.java. Your softcopy submission for this problem (as well as for Problems 3 and 4) should be the Cards folder as modified in Problems 2, 3 and 4.

Problem 3: Data Abstraction -- Cards

The Contendo game company is attempting to implement a number of card games in Java on a hand-held computer with a small amount of memory. Because memory is such a limited resource, they are looking for any way they can to reduce the amount of memory their program uses. They hire Abby Stracksen, one of the world's top data abstraction experts, to improve the memory usage of their implementation.

One of the files they show to Abby is their implementation of the Card abstraction, which is shown in Appendix A. You should study this appendix now.

Abby notes that every Card instance requires space for two variables: one to hold a pointer to the card's value, and another to hold a pointer to the card's suit. Abby observes that the amount of space per Card instance can be reduced from two variables to one by using a single integer variable whose contents ranges between 0 and 51 to encode which of the 52 cards in a deck is denoted by the card. In particular, she settles on the following correspondence between integers and cards:

0 : 2C 1 : 2D 2 : 2H 3 : 2S 4 : 3C 5 : 3D 6 : 3H 7 : 3S ... 44 : KC 45 : KD 46 : KH 47 : KS 48 : AC 49 : AD 50 : AH 51 : AS

In this problem, you will use Abby's idea as the basis for a new implementation of the Card class that will replace the one shown above.

To begin this problem, download the Cards folder from the CS230 download folder. This folder contains implementations of all of the card abstractions discussed in class, plus the Blackjack program from Problem Set 1 and the video poker program mentioned in class. Before you make any modifications, do the following:

- Study the main() method and the other class methods within the Card class in the file Card.java. (These are not shown above, but are in the file.) These methods are used to test if the implementation of the Card class is correct. Invoke the main() method of the Card class by double-clicking on Card.class . Study the output and make sure you understand why it is the correct output. (You will be using this main() method later in this problem to test your changes to the Card class.)
- Make a copy of Card.java (call it Card-orig.java, say) so that you will always have the original version to refer to if you should need it.

You should begin by removing the instance variables value and suit from the Card class and replacing them by a single integer instance variable named num:

private int num; // New instance var for Card. Should be in range 0--51.

Next, modify the definitions of the constructor method and all the
instance methods (but not the class methods) of the Card class so that they work correctly with the
new num instance variable in place of the
old ones. **You should not change the interfaces to any of these
methods; you should just change their implementations! **What you
are doing is changing the internals of the Card black-box abstraction in such a way that
it still appears to work as it did before from the outside world.
This is the essence of data abstraction.

For instance, the Card constructor should still take two arguments: a Value v and a Suit s. Your job is to figure out how to generate a number between 0 and 51 that corresponds to the card that has Value v and Suit s. Similarly the value() and suit() methods should return the value and suit of the card, just as before.

When you have changed the implementations of the constructor and instance methods in Card to be consistent with your new representation, test your changes by executing the main() method you studied above. (Be sure to quit out of the Applet Viewer and launch a new Applet Viewer before performing this test.) You have succeeded when the test behaves exactly as it did for the original implementation. If the test does not behave correctly, you need to fix your new implementation of the Card class.

Once you are satisfied that your new Card class works, rename it to be Card-num.java, and rename Card-orig.java back to Card.java. (You could use your new class throughout the rest of the assignment, but it might contain subtle bugs that could complicate the other problems, so its best to use the original implementation just in case.)

*Notes/Hints:*

- To implement the constructor method Card(Value v, Suit s), combine v.toInt() and s.toInt() in an appropriate way.
- When implementing the value() and suit() methods, you will find the following methods handy: Value.intToValue and Suit.intToSuit.
- If n and d are integers, (n / d) finds the integer quotient of n divided by d, while (n % d) finds the integer remainder. That is, n is equal to ((d * (n / d)) + (n % d)). Study the main() method to see how / and % can be used to convert between numbers and cards.
- Even though num is a private instance variable, the instance method of one Card instance can examine the num of another Card instance.
- All of your method bodies except for compare can be one-liners.
- The string representation of Value.TEN has changed from "10" on the last assignment to "T" on this assignment. It turns out that having one character for all values simplifies the testing code.

For this problem, your hardcopy submission should be Card-num.java. Your softcopy submission for this problem (as well as for Problems 2 and 4) should be the Cards folder as modified in Problems 2, 3 and 4.

Problem 4: Data Abstraction -- Hands

An obvious implementation of the Hand class uses an array of
*n* cards to represent a hand with *n* cards. For example,
the object diagram corresponding to the hand [6S, AC, JD] would be:

Appendix B contains implementation based on this representation. This implementation appears in the Hand.java file within the Cards folder. We will study it in class on Tuesday, September 21, but it is worth looking at before then.

One drawback of this representation is that a new array must be created and filled every time a new card is added or removed. This means that it can be expensive to add a large number of cards in sequence to a hand. For instance, if k cards are added in sequence to an initially empty hand, then:

- adding the first card creates and fills an array of length 1;
- adding the second card creates and fills an array of length 2;
- adding the third card creates and fills an array of length 3.
- ...
- adding the
*k*th card creates and fills an array of length*k*.

In total, *k* arrays are created, and the number of array
slots filled is 1 + 2 + 3 + ... + *k* = *k(k+1)/2. *This
implies that the time to create a hand with *k* cards is
*quadratic* in *k*. As noted in the first lecture,
quadratic is usually considered "bad", and we would like to do
better.

There is a cleverer representation for a sequence of elements that
requires less copying than the naive representation considered above.
The idea is this: we will represent a sequence of length elements
using two instance variables: an instance variable size which holds the number of cards *n*,
and an instance variable elts with
*capacity* slots, where *n <= capacity*. Slots 0 through
size - 1 of elts will be filled with the
*n* elements of the sequence; slots size through *capacity - 1* can be filled
arbitrarily (we will never look at them). For example, here is an
object diagram depicting the representation of the sample hand [6S,
AC, JD] assuming a capacity of 4 (which is encoded as the length of
the array):

The "?" in slot 3 indicates "don't care". The advantage of such a
representation is that it is easy to add cards. Adding a new card
*c* requires filling the slot at index size with *c* and
incrementing size. For example, adding 2H
to the hand represented above should yield:

But what happens when an add is performed when the array is already filled to capacity? In this case it is necessary to increase the length of the array. It turns out that a good strategy is to create a new array that is double the length of the existing array, and copy the elements from the existing array into the new one. For instance, adding 9C to the hand in our running example should yield:

The main advantage of this new representation is that it is much
cheaper to add k elements in sequence to an empty array. Suppose the
initial capacity of the empty array is 1 element. Then when adding k
elements, it is only necessary to create new arrays when adding
elements whose (0-based) index is of the form 2^{i }: e.g.,
elements 1, 2, 4, 8, 16, 32, etc. Thus only log_{2}(k) arrays
are created. Furthemore, it turns out that the total number of array
slots filled when adding k elements is less than 2k, so that the time
for adding k elements to an empty hand is *linear*, which is
considered "good" in this context.

What about removing a card? Removing a
card at index *i* requires shifting all elements at indices *i
+ 1* through size - 1 to the left by
one unit, and decrementing size. While
elements must be shifted, a new array never needs to be created (we
never shrink the size of an array). For instance, removing JD from
index 2 in our running example yields:

In this problem, you will modify Hand.java to implement the more efficient representation described above. You will use the same Cards folder that you downloaded for Problems 2 and 3. Before you make any modifications, do the following:

- Study Deck.java which implements the Deck class, a subclass of Hand. The Deck class includes a main() method that is useful for testing the correctness of Hands (since a Deck is a kind of Hand, and Decks won't work if Hands don't). Invoke the main() method of the Deck class by double-clicking on Deck.class . Study the output and make sure you understand why it is the correct output. (You will be using this main() method later in this problem to test your changes to the Hand class.)
- Make a copy of Hand.java (call it Hand-orig.java, say) so that you will always have the original version to refer to if you should need it.

In Hand.java, first remove the instance variable cards and replace it by the following two instance variables:

privateCard [ ] elts;privateint size;

You should also add the following new class variable:

privatestaticint initialCapacity = 1;

Then you should change the constructor methods and all the instance methods of the Hand class to be consistent with this new representation. You should assume that the capacity of an empty hand is the value of initialCapacity. Referring to this class variable rather than a "magical" constant makes it more apparent how to change the initial capacity for an empty array.

You can test your changes by executing the main() method in the Deck class that you studied above. (Be sure to quit out of the Applet Viewer and launch a new Applet Viewer before performing this test.) You have succeeded when the test behaves exactly as it did for the original implementation. If the test does not behave correctly, you need to fix your new implementation of the Hand class.

Notes:

- The capacity of the elts array is
just its length, elts.length.

- An attempt to get, set, or remove an element at an
out-of-range index is unspecified. This means you can do whatever
you want (and is convenient) in these situations. The initial
implementation of Hand that you are provided with defers to Java's
array routines, which raise exceptions when indices are out of
bounds. We have not studied exceptions, so you are not required to
raise them.

- You should verify that a new array is created only when
attempting to add a new card to an existing elts array filled to capacity. The easiest
way to do this is to insert a call to System.out.println in the spot where a new
array is created that indicates the size of the new array. When
you test your code, make sure that new arrays are created exactly
when you expect them to be. For instance, when creating a new
Deck() with initialCapacity = 1, new arrays should be
created for the following lengths: 1, 2, 4, 8, 16, 32, 64. If you
change initialCapacity to 3, new
arrays should be created at the following lengths: 3, 6, 12, 24,
48, 96. If you change initialCapacity
to 52, only one array (of length 52) should be created.

- Many of the methods in the new representation will be quite
similar to methods in the old representation. This is especially
true for the sort(), insert() and toString() methods.

- You will have to change the interface of the private
constructor method Hands(Card [] cs)
to Hand(Card [] cs, int s). This
private constructor method is used to make copies of hands.

- As always, you should consult the
JDK
1.0.2 API for any Java library classes or methods with which
you are unfamiliar.

- This representation for a hand of cards will of course work for any sequence of objects. Indeed, it is a standard implementation of the Java Vector class that we will be studying (and using frequently) in CS230.

For this problem, your hardcopy submission should be your final version of Hand.java. Your softcopy submission for this problem (as well as for Problems 2 and 3) should be the Cards folder as modified in Problems 2, 3 and 4.

Appendix A: A Simple Implementation of the Card Abstraction

// The following code can be found in the file Card.java within the Card folder.publicclassCard {// Instance Variables:privateValue value;// The value of this card.privateSuit suit;// The suit of this card.// Constructor Method:publicCard (Value v, Suit s) {// Returns a new card with the given value and suit.value = v; suit = s; }// Instance Methods:publicValue value() {// Returns the value of this card.return value; }publicSuit suit() {// Returns the suit of this card.returnsuit; }publicboolean equals (Card c) {// Returns true if c has the same value and suit as this card; false otherwise.return((value.equals(c.value)) && (suit.equals(c.suit))); }publicint compare (Card c) {// Returns -1 if this card precedes c in the card ordering; // 0 if this card is equal to c in the card ordering; // and 1 if this card follows c in the card ordering.if(value.equals(c.value)) {returnsuit.compare(c.suit); } else {returnvalue.compare(c.value); } }publicString toString() {// Returns a string representation of this card.returnvalue.toString() + suit.toString(); }// Various testing methods not shown}

Appendix B: A Simple Implementation of the Hand Abstraction

// The following code can be found in the file Hand.java within the Card folder.publicclass Hand {// Instance Variables:privateCard [ ] cards;// Constructor Methods:publicHand () { // Returns an empty hand (i.e., a hand without cards). cards = new Card[0]; }privateHand (Card [ ] cs) {// Used by the copy() methodcards = cs; }// Instance Methods:publicintsize () {// Returns the number of cards in the hand.returncards.length; }publicvoidadd (Card c) {// Adds the card c to the hand so that it is at the last index.// Create a new array one slot longer than old:Card [ ] newcards =newCard[cards.length + 1];// Copy cards from old array to new:for(inti = 0; i < cards.length; i++) { newcards[i] = cards[i]; }// Put c in last slot of new array:newcards[cards.length] = c;// Update instance variable:cards = newcards; }publicCard remove (inti) {// Removes the card at index i from the hand and returns it. // The indices of all cards whose index was initially greater than i are decremented by 1. // The behavior is unspecified for indices out of range.Card c =null;// This is how you write the null pointer in Java.if((i >= 0) && (i < cards.length)) { c = cards[i];// Create a new array one slot shorter than old:Card [ ] newcards = new Card[cards.length - 1];// Copy cards from old array to new, skipping index i:for(intless = 0; less < i ; less++) { newcards[less] = cards[less]; }for(intgreater = i+1; greater < cards.length ; greater++) { newcards[greater-1] = cards[greater]; }// Update instance variable:cards = newcards; }returnc; }publicCard get (inti) {// Returns the card at index i in the hand. // The behavior is unspecified for indices out of range.return cards[i]; }publicvoidset (inti, Card c) {// Replaces the card at index i with c. // The behavior is unspecified for indices out of range.cards[i] = c; }publicvoidsort () {// Rearrange the cards in the hand to be in card sorted order by index, // from low value to high value. // For simplicity, use insertion sort. Quadratic behavior won't be too bad // since hands will never be very large.for(inti = 1; i < cards.length; i++) { insert(i); } }privatevoidinsert (int i) {// Assume that cards[0..i-1] is sorted. Insert card at i into sorted order // from low oto hi.Card c = cards[i];intj = i; // j is the insertion point.while((j > 0) && (cards[j-1].compare(c) == 1)) { cards[j] = cards[j-1]; j = j - 1; } cards[j] = c; }publicHand copy () {// Return a new hand that has the same cards as this hand.Card [ ] newcards = new Card [cards.length];for(int i = 0; i < cards.length; i++) { newcards[i] = cards[i]; }returnnew Hand(newcards); }publicString toString() {// Returns a string representation of this hand.StringBuffer sb = new StringBuffer(); sb.append(this.type() + "[");if(cards.length > 0) { sb.append(cards[0].toString());for(inti = 1; i < cards.length; i++) { sb.append(","); sb.append(cards[i].toString()); } } sb.append("]");returnsb.toString(); }protectedString type() {return"Hand";// Can be overridden by subclasses, Deck in particular.} }