CS 101 (Spring 2000) Lab 7: Abstract Data Types: Stacking the Deck Authored by Amar and Cytron

Lab Assigned
Design Due
(In class)

10 AM
Implement
(In Lab)
Demo
(In Lab)
Lab Due
(In class)
Friday
10 AM
13 Mar None 14-15 Mar 21-22 Mar 27 Mar

Goals:

By the end of this lab, you should
• Understand the concept of an ADT, in particular a `Stack`
• Understand how ADTs can nest to produce intuitive and powerful data structures
• Understand more about object/reference manipulation in list structures
• Understand how an object like a deck of cards might be represented

Before starting:

• Read over this entire document before you start.
• Study the examples in class and in the notes.
• Run the sample solution.

1. Problem Statement

This lab is the first of a two-week sequence that will culminate in the creation of a working game of CloneLike Solitaire, a look-alike to Klondike, one of the most famous one-person card games. It is the same Solitaire game that comes with the Windows operating system.

During this first week, you will create the abstraction of a pile of cards. These piles will form the basis for our game. Our notion of a pile of cards is similar to that of the `Stack` you have been learning about in class. The "last" card in a pile is whatever card was last added to it, and cards are removed from this pile from last to first; the pile is last-in, first-out (LIFO), like a Stack. You will first implement a `CardStack`, which we will then use to implement a `CardPile`.

In fact, the `CardPile` is-a `CardStack`, but with some extra functionality. So, just like `Mass` extends `Rect` in Lab 6, so can `CardPile` extend `CardStack` in this lab.
2. Design

All methods below are `public` unless otherwise stated.

1. The `Card` class represents a card in our game. This class is modeled after the notion of a two-dimensional sequence, as discussed in class. The API for `Card` does not disclose its representation. While this is considered good design, you will have to become acquainted with treating a card's rank and suit abstractly---so that each card is positioned with respect to two orthogonal sequences. A `Card` also "knows" whether it is visible (face-up) or not (face-down). Here is the API for `Card`.

Constructor(s)
There is but one public constructor. However, you might choose to make a private constructor that is aware of the internal representation of a `Card`.
`Card()`
Constructs a `Card` with base rank and suit. For our purposes, this is the Ace of Clubs. By default, the card is visible.
Accessors
`boolean isVisible()`
Returns true if the card is face-up.
Mutators
`void setVisibility(boolean visibility)`
Sets the visibility of the `Card` according to the parameter.
Other methods
Your code will be graded on the exent to which you phrase one method in terms of other methods in the API, instead of writing the code for each method "from scratch".

`Card genNextRank()`
returns a new `Card` with the same suit as this one, but with the next higher rank. This method cannot generate an error.
`Card genPrevRank()`
returns a new `Card` with the same suit as this one, but with the next lower rank. This method cannot generate an error.
`Card genNextSuit()`
returns a new `Card` with the same rank as this one, but with the next higher suit. This method cannot generate an error.
`Card genPrevSuit()`
returns a new `Card` with the same rank as this one, but with the next lower suit. This method cannot generate an error.
`int rankDiff(Card other)`
returns the numerical difference in rank between the `other Card` and `this Card`.
`int suitDiff(Card other)`
returns the numerical difference in suit between the `other Card` and `this Card`.
`boolean sameRankAs(Card other)`
returns true iff `this Card` has the same rank as the `other Card`.
`boolean sameSuitAs(Card other)`
returns true iff `this Card` has the same suit as the `other Card`.
`boolean isRankPrevOf(Card other)`
returns true iff `this Card` has rank one lower than that of the `other Card`.
`boolean isRankSuccOf(Card other)`
returns true iff `this Card` has the rank one higher than that of the `other Card`.
`boolean isAlternateSuitOf(Card other)`
returns true iff `this Card`'s "color" is opposite that of the `other Card`.
`String toString()`
Forms a `String` representation of this card.
`String loadFilename()`
Returns the `String` filename (with respect to the current directory) of where the image representing this card is expected to be found. The details for this are discussed in class.

2. The `CardListItem` class represents a placeholder in a singly-linked list that holds Card objects. The code is patterned after `ListItem`. Instead of holding a (primitive) `int` type, each `CardListItem` can hold a `Card`. We provide this code for you, because it is practically identical to `ListItem`.
Constructor(s)
`CardListItem(Card c, CardListItem next)`
Constructs a new `CardListItem` that holds the given `Card` and initially points to the `CardListItem` specified as the `next` parameter.
Accessors
`Card getCard()`
Returns the `Card` reference currently held in this item.
`CardListItem getNext()`
Returns a reference to the next item in the list.
Mutators
`void setCard(Card c)`
Change the card currently in this item to the one specified as parameter `c`.
`void setNext(CardListItem c)`
Change the next pointer in this item to point to the specified item `c`.
Other methods
`String toString()`
Returns a `String` representation of the list starting at this CardListItem. Each element in the list is printed, separated by spaces.

3. The `ListOfCards` class represents a list of `Card` objects, but it is built using the `CardListItem` class. The code is patterned after `ListOfInts`. Because of its similarity to the material discussed in class, we provide this code for you.
Constructor(s)
`ListOfCards()`
Constructs an empty list.
Methods
`boolean isEmpty()`
returns true iff the list is empty.
`boolean atEnd()`
returns true iff the "current" item is past the end of the list.
`Card getItem()`
returns the current `Card`. An error is thrown if the list is empty, or if the current item is beyond the end of the list.
`ListOfCards prepend(Card c)`
places the `Card` at the beginning of the list. For convenience, a referece to the list is returned.
`ListOfCards append(Card c)`
places the `Card` at the end of the list. For convenience, a referece to the list is returned.
`void setItem(Card c)`
Changes the contents of the current item to the specified `Card`. An error is thrown if the list is empty, or if the current item is beyond the end of the list.
`void reset()`
resets the current item to be the first item in the list.
`void next()`
advances the current item by one list element.
`void insert(Card n)`
inserts the `Card` just before the current item, and makes the inserted item the current one.
`Card delete()`
deletes and returns the current item
`String toString()`
Returns a `String` representation of the entire list.

4. The `StackOfCards` is a simple class, but is really the lifeblood of this lab. Because `ListOfCards` seems similar to `StackOfCards`, it may be tempting to implement `StackOfCards` by extending `ListOfCards`. However, this is not the right thing to do. A list has many operations, such as insert, delete, next, and reset, that are inappropriate for a stack. If we extended `ListOfCards`, then the resulting `StackOfCards` would inherit all those methods, which are not formally part of its API. A better approach is to implement `StackOfCards` by ensuring that it "has-a" `ListOfCards` as its underlying implementation.
Constructor(s)
`StackOfCards()`
This should construct an initially empty `StackOfCards`.
Accessors
`boolean isEmpty()`
This should return `true` if there are no elements in this `StackOfCards`, and false otherwise.
`Card peek()`
This should return the topmost `Card` on this `StackOfCards`. Try to implement this method in terms of the other methods in this API.
Mutators
`void push(Card c)`
This should push the specified `Card` on top of the stack.
`Card pop()`
This should remove the topmost `Card` from the stack and return it. An attempt to `pop` an empty stack should result in an error.
Other methods
`String toString()`
This should print out in a String all the elements in the stack. Write them from left to right, bottom-to-top. Just as you did in Lab 6, you may be able to leverage existing toString( ) methods.

5. In order to have a card game at all, we must have the `CardPile` class, which you must complete according to the API below. Also, you must implement this class by extending `StackOfCards`. Our `CardPile` supports at least the following operations are supported.
• Getting the topmost or bottommost card in the pile
• Getting the nth-card-from-the-top of the pile
• Transferring a portion of the pile to another `CardPile` by specifying the point at which the pile should be "cut" and then transferring the "top" portion to the other pile.
• Verifying that the `CardPile` can receive a given card. (For this lab, we'll always accept the move; for the game, we will be more selective.)
• Shuffling the `CardPile` via a perfect shuffle (exactly interleaving the cards in the deck)
• Turning the `CardPile` over (by reversing its elements and inverting the visibility of each card)
The `CardPile` extends the functionality of your `StackOfCards` class. Thus, it does make sense for `CardPile` to extend `StackOfCards`. Note, however, that `CardPile` is an abstract data type which may be implemented in many different ways.

Here's the API for `CardPile`:
Constructor(s)
`CardPile()`
creates an empty `CardPile`.
Accessors
`boolean isEmpty()`
This should return `true` if this CardPile currently has no cards, otherwise false. This method can be inherited for-free from `StackOfCards`
`int getSize()`
This should return the number of cards currently in this CardPile (0 if empty). Note that `StackOfCards` has no notion of the size of its stack; you'll have to implement the notion of size in the extended class.
`Card getTop()`
This should return the topmost `Card` in this `CardPile`. You can write this method in terms of `peek`, inherited from `StackOfCards`. Or, you can write it in terms of `getNthFromTop`.
`Card getBottom()`
This should return the bottommost `Card` in this `CardPile`. You can write this method in terms of `getNthFromTop`.
`Card getNthFromTop(int n)`
returns the specified `Card` in this `CardPile`. Here, 0 represents the topmost card and `(getSize() - 1)` is the index of the bottommost card. This method is tricky, because the `StackOfCards` object does not give access to anything but its topmost element. You'll have to use at temporary `StackOfCards` to help you do this, as discussed in class.
Mutators
`boolean transferTo(CardPile destination, Card splitAt)`
This should transfer all the cards on the top of this `CardPile`, up to and including the card specified in the `splitAt` parameter. The cards are transferred to the TOP of the `destination CardPile`, specified as a parameter. The order of the cards in the portion transferred should remain the same; be careful not to reverse them.

The transfer should take place if and only if the `destination` `CardPile` accepts the cards. This can be determined by calling the `desination`'s `okToAdd` method. If the transfer is rejected by the `destination`, then the cards should be left as they were. If the `splitAt` `Card` is not found in this `CardPile`, then an error should be thrown. Upon success, return true; otherwise, return false.
`boolean addCard(Card c)`
tests whether it is `okToAdd(c)` and then adds the `Card` and returns true if OK; otherwise, the card is not added and false is returned.
`Card removeTop()`
operates like `pop()` of `StackOfCards`, except that here we return null if the stack is empty.
`void flipCards()`
This should reverse the order of every `Card` in this `CardPile`, and inverts the visibility of each `Card`.
`void shuffle()`
This should perform (one pass of) a "Perfect Shuffle". A perfect shuffle is one that splits the deck exactly in half and then interleaves the portions of the deck exactly (one card from one half, then another card from the other half, and back and forth).

You must implement this method using only the `CardPile` at hand, along with as many `StackOfCards` objects as you want.
Other methods
`String toString()`
You should print out all the cards in this pile between square brackets [ ] (e.g. "[ace-of-hearts ace-of-diamonds four-of-spades ]"). Again, the toString( ) in some of the smaller classes may help.

6. The `PileViz` class is provided to you as means of testing and demonstration. You will use it to help you do testing on the `CardPile` objects. You use it by associating it with a `CardPile` in the constructor call, and then you call `redraw` on it every time the CardPile changes. It has the following API:
Constructor(s)
`PileViz(String name, CardPile cp)`
Creates a PileViz object with the given name (which serves as a title for the window in which the PileViz draws) and associates it with the specified CardPile.
Accessor(s)
None.
Mutator(s)
None.
Other method(s)
`void redraw()`
Redraws the PileViz object to reflect the new contents of the associated CardPile.
`void sleep(int howLong)`
Specifies for the program to pause for `howLong` milliseconds (thus, calling `sleep(2000)` causes a two-second sleep. Use this method to prevent your tests from going by too fast.

3. Implementation

Read the following carefully, and be sure to complete all parts below.

1. You must implement the classes described in the design. For this lab, you are constrained to following this design. Specific implementation steps are given at the end of this document; the files you download repeat those suggestions.

2. You must thoroughly test `StackOfCards` and show your test output in the terminal window. Do this by completing the `testStack( )` method in `Startup.java`. Your code grade for this lab will be adversely affected by poor testing. Be sure to submit a transcript of your tests.

3. The demonstration for this lab requires that you show all your methods in the class are working. Use the `PileViz` class to show us the status of some test CardPile objects after you test each of the methods in the CardPile API. Complete your tests in the `testPile( )` method of `Startup.java`. Your demo grade for this lab will be adversely affected by poor testing. You must ALSO submit a transcript of your CardPile tests, so you should also provide terminal tests and output (probably in conjunction with the PileViz tests).

What to turn in:

1. Complete a code cover sheet.
2. Provide a printout of any files you have modified (see approach below).
3. Provide transcript(s) from the tests on `StackOfCards` and `CardPile`.

Suggested implementation approach:

1. Implement `StackOfCards` fully according to the API. Fill in the `testStack()` method in `Startup` and test to be sure that your class works. Until `Card` is working, the only card you can create is the base card (Ace of Clubs), but you can still test your stack.
2. Implement `Card`.
3. Re-test `StackOfCards`
4. Implement `CardPile` one method at a time. The order in which the methods are listed is the suggested order of implementation. Write some test procedures in `Startup` using the provided PileViz class to be sure that your class works. Test as you go -- don't write the whole class and then try to test it. Test in one-method increments.