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
(In Lab)
(In Lab)
Lab Due
(In class)
10 AM
13 Mar None 14-15 Mar 21-22 Mar 27 Mar


By the end of this lab, you should

Before starting:

[[[ Download PC zip ]]]

Lab7.java Startup.java Card.java CardListItem.java
ListOfCards.java StackOfCards.java CardPile.java PileViz.java

  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.

      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.
      Constructs a Card with base rank and suit. For our purposes, this is the Ace of Clubs. By default, the card is visible.
      boolean isVisible()
      Returns true if the card is face-up.
      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.
      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.
      Card getCard()
      Returns the Card reference currently held in this item.
      CardListItem getNext()
      Returns a reference to the next item in the list.
      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.
      Constructs an empty list.
      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.
      This should construct an initially empty StackOfCards.
      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.
      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:
      creates an empty CardPile.
      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.
      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:
      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.
      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.

Last modified 15:05:07 CST 27 March 2000 by Ron K. Cytron