CS 101 (Fall 2000)
Lab 7: Stacking the Deck

Authors: Nate Bayless and Sergey Klibanov
Lab Assigned Design Due
(In class)

1 PM
(In Lab)
(In Lab)
Lab Due
(In class)
1 PM
23 Oct None 25-26 Oct 1-2 Nov 3 Nov


The stack abstract data type (ADT) is fundamental to many things in computer science. For example, Java itself (as well as many other languages, including C and C++) uses a stack to execute your code. When a method goo() calls a method foo() , what goes on behind the scenes is that at the moment the call is made, foo()'s local variables are pushed onto Java's runtime stack. When foo() returns, they are all popped and goo() regains control where it left off. Recursive algorithms make extensive use of this process for obvious reasons. Some calculators, like the HP48G, use a stack as the user interface. We will use a stack for the less serious and more entertaining task of making a card game.


By the end of this lab, you should

Before starting:

[[[ Download PC zip ]]]
Zip contains:
  1. Problem Statement

    This lab is the first of a two-week sequence that will culminate in the creation of a working card game.

    During this first week, you will create the abstraction of a stack of cards. Our notion of a stack 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 StackOfCards, which we will then use to implement a Deck.

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

    You will need to create your own .java files for the classes that we have not provided. You will probably also need to make your own Startup.java to test your code, but you will not need to turn that file in. All grading will be done with the provided Startup.java file.

    All methods below are public. You may not add other public methods. All methods you add must be private. You are encouraged to add private methods where you see fit. **See the JavaDoc for the same information presented differently**

    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.

      Constructs a Card with base rank and suit. By default, the card is invisible.
      boolean isVisible()
      Returns true if the card is face-up.
      PictureComponent getPicture()
      Returns the PictureComponent that holds the Card's image. ** The SAME object must be returned every time! **
      void setVisible(boolean visibility)
      Sets the visibility of the Card according to the parameter. If the Card's image changes because its visibility is altered, do not construct a new PictureComponent. Instead, use the PictureComponent's setImage(String filename) on the existing PictureComponent.
      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. If the maximum rank is reached and passed, a card of the lowest rank is returned.
      Card genPrevRank()
      returns a new Card with the same suit as this one, but with the next lower rank. If the minimum rank has been reached and passed, a card of the highest rank is returned.
      Card genNextSuit()
      returns a new Card with the same rank as this one, but with the next higher suit. If the maximum suit has been reached and passed, a card of the lowest suit is returned.
      Card genPrevSuit()
      returns a new Card with the same rank as this one, but with the next lower suit. If the minimum suit has been reached and passed, a card of the highest suit is returned.
      int rankDiff(Card other)
      returns the numerical difference in rank between the other Card and this Card (i.e. other - this; **all diff methods are this way).
      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. The Ace is the previous rank of a Two.
      boolean isRankSuccOf(Card other)
      returns true iff this Card has the rank one higher than that of the other Card. The Two is the successor of the Ace.
      boolean isAlternateSuitOf(Card other)
      returns true iff this Card's "color" is opposite that of the other Card.
      String suitToString()
      Returns the suit of the card as a String, for example "Spades"
      String ranktoString()
      Returns the rank of the card as a String, for example "Ace"
      String toString()
      Returns a String containing the rank and suit of this card, for example "Ace of Spades"

      In order to make grading easier, we will constrain your implementation of Card somewhat. The following conditions are required. The card created by the default constructor must be a Two of Clubs. If genNextRank is called on a Two of Clubs, a Three of Clubs should be created. If a genNextRank should be called on a Three of Clubs, a Four of Clubs should be returned, and so on up through Ace. If genNextRank is called on an Ace, a Two should be returned. The suits are ordered as follows: Clubs, Diamonds, Hearts, Spades. Therefore, if genNextSuit is called on a Two of Clubs, a Two of Diamonds should be returned, and so forth. genPrevRank and genPrevSuit should behave in a similar way.

    2. The ListOfCards class represents a list of Card objects. 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 he 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.

    3. 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. We do not want this. A better approach is to implement StackOfCards by ensuring that it "has-a" ListOfCards as its underlying implementation. Another way to implement a stack might have been with an array, but we chose to use a linked list. This is why the stack is an abstract data type -- to the user of the StackOfCards class, it does not matter how it was implemented as long as it works as expected. Having said that, you are nonetheless required to use ListOfCards in your 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 print an error message and return null.
      Other methods
      String toString()
      Returns a string containing the cards on the stack, in order, starting with the most recently-pushed. You should probably use the ListOfCards's toString() method here.

    4. In order to have a card game at all, we must have the Deck class, which you must complete according to the API below. The Deck is an abstract data type, so as with StackOfCards, it can be implemented in many ways. Our implementation of the Deck will extend StackOfCards.
      Deck must have the following methods:
      Creates a regular 52-card deck, not randomized.
      int getSize()
      Returns the number of cards currently in the deck.
      Card getTop()
      Returns (does not delete) the top card on the deck -- equivalent to Card peek() in StackOfCards.
      Card getBottom()
      Returns (does not delete) the bottom card.
      Card getNthFromTop(int n)
      Returns (does not delete) the nth card from the top of the deck. The top card is 0th from top.
      Some mutators may modify the number of cards in the deck. The value returned by int getSize() must be updated in this case.
      void push(Card c)
      Overrides the push method in StackOfCards. The Deck keeps track of the number of cards it contains, while StackOfCards does not. This method should appropriately adjust the value to be returned by getSize(), as well as performing the push() from StackOfCards.
      Card pop()
      Overrides the pop method in StackOfCards. Look at void push(Card c) for more detail on method function.
      Card removeTop()
      Equivalent to Card pop()
      Card removeBottom()
      Returns and deletes from the deck the bottom card
      Card removeNthFromTop()
      Returns and deletes from the deck the nth card from the top. The top card is 0th from the top.
      void perfectShuffle()
      Performs one pass of the Perfect Shuffle algorithm. This works as follows: The deck is split into two equal halves, then reconstructed by interleaving the two halves. Specifically, the deck is cut equally into two halves. One card is taken from the first half (the half that used to be on top of the deck) and pushed onto the deck, then one is taken from the second half and pushed on, then one from the first and so on until the deck is fully reconstructed. About twenty passes of this This approach to shuffling will not randomize the deck. In fact, after a computable number of perfect shuffles, the deck will return to its original order! Even more specifically, let's assume the deck holds cards (3, 4, 5, 6, 7, 8). The first half would contain (3, 4, 5) and the second half would contain (6, 7, 8) in that order. Then a 3 would be taken from the first half, and pushed onto the now-empty deck. Then the 6 would be chosen. The final product should be a deck that holds (8, 5, 7, 4, 6, 3). If the number of cards is odd, let the second half contain the extra card.
      void selectionShuffle()
      Performs one pass of the "Selection Shuffle" algorithm, which works as follows: A random card is chosen and removed from the deck. This card is placed on top of the deck. Another randomly chosen card, but one that has not yet been touched by the algorithm, is removed and placed on top. This process is run until all cards have been touched by the algorithm. The result is a fairly randomized deck.

      While writing your code, consider carefully what methods Deck inherited from StackOfCards. These include push and pop which have been overridden. Other inherited methods are Card peek(), boolean isEmpty(), String toString. As with Card, for grading purposes, we will constrain your implementation of the Deck. When the deck is constructed, the cards in it must be in the following order, from the top of the stack down: Ace of Spades, Ace of Hearts, Ace of Diamonds, Ace of Clubs, King of Spades, Hearts, Diamonds, Clubs, etc. The bottom 4 cards should be Two of Spades, Two of Hearts, Two of Diamonds, Two of Clubs.

    5. The last item that is essential to any card game is a Hand. It is the hand of cards that is actually used to play the game, and not user as a source of cards (like the Deck is). Our Hand class has-a ListOfCards that keeps track of all the Card objects currently in the hand. Here's the API for Hand:
      creates an empty Hand with an empty DrawingPane and ListOfCards. Cards in the hand are invisible (face down) by default.
      DrawingPane getDrawingPane()
      returns the DrawingPane on which the Hand draws itself.
      int getSize()
      returns how many cards are in the hand.
      boolean isEmpty()
      Returns whether or not the hand is empty (has 0 cards)
      boolean isVisible()
      Returns whether or not the cards in the hand are visible (face up)
      boolean getCard(int n)
      Returns the nth card in the hand. 0 is the first card.
      void add(Card c)
      adds the specified Card to the Hand. This constitutes adding both to the ListOfCards and to the Hand's DrawingPane. More recently added cards go to the end of the hand.
      void remove(Card c)
      removes the specified Card from the Hand and the Card's PictureComponent the DrawingPane. Prints an error message if the card is not in the hand or if the hand is empty.
      Card remove(int n)
      Removes the nth card in the hand. 0 is the first card.
      void setVisible(boolean visible)
      sets each Card's visibility to the specified visibility.
      void clear()
      Removes all images from the Hand's DrawingPane and empties its ListOfCards.
      void sort()
      sorts the Hand by rank (i.e. from high to low, with Aces high). Changes in order are reflected both visually and internally.

      This method is worth 5 lab points of extra credit. It is tested from Startup, so you must include at least a stub for this method if not the actual implementation.

      Other method(s)
      String toString()
      Prints out all the cards in the hand. Same format as specified above, using parentheses and commas.

    6. Finally, you will need the Startup class to demonstrate that your classes work. To ease grading, this class is provided for you. Ideally, the transcript generated by the reference implementation and your code will be identical. You should not, however, rely solely on our Startup code entirely during your own testing. After, for example, you finish the Card class, you should make completely sure that it works as expected before moving on.
      Creates a Startup object which tests the other classes in this lab.


    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.
    2. Do not expect the given Startup.java file to compile until you are finished with the lab.
    3. Once you have the Startup.java file compiling, compare the behavior of your implementation with the behavior of the reference implemenation. Any output that does not use the selectionShuffle method should be *exactly* the same between the two implementations.

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 the transcript from the tests on StackOfCards, Deck, and Hand generated by the given Startup.java

Suggested implementation approach:

  1. Implement Card. Try commenting out the calls to testStack(), testDeck() and testHand() in the given Startup's constructor and comparing the behavior of your card class to the reference implemenation.
  2. Implement StackOfCards. Test it similarly.
  3. Implement Deck.
  4. Implement Hand

Test as you go. The wrong approach is to write all of one class, then to try to get it to compile, and then to try to get it to work, in three separate stages. The correct way is to write your code in one-method increments, testing as you go.

Good Luck!

Last modified 08:04:04 CST 01 November 2000 by Ron K. Cytron