The Way of the Java/Objects of Arrays
Objects of Arrays
[edit | edit source]deck
deck array!of Cards
In the previous chapter, we worked with an array of objects, but I also mentioned that it is possible to have an object that contains an array as an instance variable. In this chapter I am going to create a new object, called a Deck, that contains an array of Cards as an instance variable.
instance variable variable!instance
The class definition looks like this
verbatim class Deck
Card[] cards;
public Deck (int n) cards = new Card[n];
verbatim
The name of the instance variable is cards to help distinguish the Deck object from the array of Cards that it contains. Here is a state diagram showing what a Deck object looks like with no cards allocated:
state diagram constructor
figure=figs/deckobject.eps
As usual, the constructor initializes the instance variable, but in
this case it uses the new command to create the array of cards.
It doesn't create any cards to go in it, though. For that we could
write another constructor that creates a standard 52-card deck and
populates it with Card objects:
verbatim
public Deck ()
cards = new Card[52];
int index = 0;
for (int suit = 0; suit <= 3; suit++)
for (int rank = 1; rank <= 13; rank++)
cards[index] = new Card (suit, rank);
index++;
verbatim
Notice how similar this method is to buildDeck, except that we had to change the syntax to make it a constructor. To invoke it, we use the new command:
new statement!new
verbatim
Deck deck = new Deck ();
verbatim
Now that we have a Deck class, it makes sense to put all the methods that pertain to Decks in the Deck class definition. Looking at the methods we have written so far, one obvious candidate is printDeck (Section printdeck). Here's how it looks, rewritten to work with a Deck object:
printDeck
verbatim
public static void printDeck (Deck deck)
for (int i=0; i<deck.cards.length; i++)
Card.printCard (deck.cards[i]);
verbatim
The most obvious thing we have to change is the type of the parameter, from Card[] to Deck. The second change is that we can no longer use deck.length to get the length of the array, because deck is a Deck object now, not an array. It contains an array, but it is not, itself, an array. Therefore, we have to write deck.cards.length to extract the array from the Deck object and get the length of the array.
For the same reason, we have to use deck.cards[i] to access an element of the array, rather than just deck[i]. The last change is that the invocation of printCard has to say explicitly that printCard is defined in the Card class.
For some of the other methods, it is not obvious whether they should be included in the Card class or the Deck class. For example, findCard takes a Card and a Deck as arguments; you could reasonably put it in either class. As an exercise, move findCard into the Deck class and rewrite it so that the first parameter is a Deck object rather than an array of Cards.
Shuffling
[edit | edit source]shuffle
shuffling
For most card games you need to be able to shuffle the deck; that is, put the cards in a random order. In Section random we saw how to generate random numbers, but it is not obvious how to use them to shuffle a deck.
One possibility is to model the way humans shuffle, which is usually by dividing the deck in two and then reassembling the deck by choosing alternately from each deck. Since humans usually don't shuffle perfectly, after about 7 iterations the order of the deck is pretty well randomized. But a computer program would have the annoying property of doing a perfect shuffle every time, which is not really very random. In fact, after 8 perfect shuffles, you would find the deck back in the same order you started in. For a discussion of that claim, see http://www.wiskit.com/marilyn/craig.html or do a web search with the keywords ``perfect shuffle.
A better shuffling algorithm is to traverse the deck one card at a time, and at each iteration choose two cards and swap them.
pseudocode
Here is an outline of how this algorithm works. To sketch the program, I am using a combination of Java statements and English words that is sometimes called pseudocode:
verbatim
for (int i=0; i<deck.cards.length; i++)
// choose a random number between i and deck.cards.length
// swap the ith card and the randomly-chosen card
verbatim
The nice thing about using pseudocode is that it often makes it clear what methods you are going to need. In this case, we need something like randomInt, which chooses a random integer between the parameters low and high, and swapCards which takes two indices and switches the cards at the indicated positions.
random number
You can probably figure out how to write randomInt by looking at Section random, although you will have to be careful about possibly generating indices that are out of range.
swapCards reference
You can also figure out swapCards yourself. The only tricky thing is to decide whether to swap just the references to the cards or the contents of the cards. Does it matter which one you choose? Which is faster?
I will leave the remaining implementation of these methods as an exercise to the reader.
Sorting
[edit | edit source]sorting
sorting
Now that we have messed up the deck, we need a way to put it back in order. Ironically, there is an algorithm for sorting that is very similar to the algorithm for shuffling. This algorithm is sometimes called selection sort because it works by traversing the array repeatedly and selecting the lowest remaining card each time.
selection sort
During the first iteration we find the lowest card and swap it with the card in the 0th position. During the ith, we find the lowest card to the right of i and swap it with the ith card.
Here is pseudocode for selection sort:
verbatim
for (int i=0; i<deck.cards.length; i++)
// find the lowest card at or to the right of i
// swap the ith card and the lowest card
verbatim
Again, the pseudocode helps with the design of the helper methods. In this case we can use swapCards again, so we only need one new one, called findLowestCard, that takes an array of cards and an index where it should start looking.
helper method method!helper
Once again, I am going to leave the implementation up to the reader.
Subdecks
[edit | edit source]subdeck
How should we represent a hand or some other subset of a full deck? One good choice is to make a Deck object that has fewer than 52 cards.
We might want a method, subdeck, that takes an array of cards and a range of indices, and that returns a new array of cards that contains the specified subset of the deck:
verbatim
public static Deck subdeck (Deck deck, int low, int high) Deck sub = new Deck (high-low+1);
for (int i = 0; i<sub.cards.length; i++)
sub.cards[i] = deck.cards[low+i];
return sub;
verbatim
The length of the subdeck is high-low+1 because both the low card and high card are included. This sort of computation can be confusing, and lead to ``off-by-one errors. Drawing a picture is usually the best way to avoid them.
constructor overloading
Because we provide an argument with the new command, the constructor that gets invoked will be the first one, which only allocates the array and doesn't allocate any cards. Inside the for loop, the subdeck gets populated with copies of the references from the deck.
The following is a state diagram of a subdeck being created with the parameters low=3 and high=7. The result is a hand with 5 cards that are shared with the original deck; i.e. they are aliased.
figure=figs/subdeck.eps
aliasing reference
I have suggested that aliasing is not generally a good idea, since changes in one subdeck will be reflected in others, which is not the behavior you would expect from real cards and decks. But if the objects in question are immutable, then aliasing can be a reasonable choice. In this case, there is probably no reason ever to change the rank or suit of a card. Instead we will create each card once and then treat it as an immutable object. So for Cards aliasing is a reasonable choice.
As an exercise, write a version of findBisect that takes a subdeck as an argument, rather than a deck and an index range. Which version is more error-prone? Which version do you think is more efficient?
Shuffling and dealing
[edit | edit source]shuffling dealing
In Section shuffle I wrote pseudocode for a shuffling algorithm. Assuming that we have a method called shuffleDeck that takes a deck as an argument and shuffles it, we can create and shuffle a deck:
verbatim
Deck deck = new Deck (); shuffleDeck (deck);
verbatim
Then, to deal out several hands, we can use subdeck:
verbatim
Deck hand1 = subdeck (deck, 0, 4); Deck hand2 = subdeck (deck, 5, 9); Deck pack = subdeck (deck, 10, 51);
verbatim
This code puts the first 5 cards in one hand, the next 5 cards in the other, and the rest into the pack.
When you thought about dealing, did you think we should give out one card at a time to each player in the round-robin style that is common in real card games? I thought about it, but then realized that it is unnecessary for a computer program. The round-robin convention is intended to mitigate imperfect shuffling and make it more difficult for the dealer to cheat. Neither of these is an issue for a computer.
This example is a useful reminder of one of the dangers of engineering metaphors: sometimes we impose restrictions on computers that are unnecessary, or expect capabilities that are lacking, because we unthinkingly extend a metaphor past its breaking point. Beware of misleading analogies.
Mergesort
[edit | edit source]mergesort
efficiency sorting mergesort
In Section sorting, we saw a simple sorting algorithm that turns out not to be very efficient. In order to sort items, it has to traverse the array times, and each traversal takes an amount of time that is proportional to . The total time, therefore, is proportional to .
In this section I will sketch a more efficient algorithm called mergesort. To sort items, mergesort takes time proportional to . That may not seem impressive, but as gets big, the difference between and can be enormous. Try out a few values of and see.
The basic idea behind mergesort is this: if you have two subdecks, each of which has been sorted, it is easy (and fast) to merge them into a single, sorted deck. Try this out with a deck of cards:
enumerate
Form two subdecks with about 10 cards each and sort them so that when they are face up the lowest cards are on top. Place both decks face up in front of you.
Compare the top card from each deck and choose the lower one. Flip it over and add it to the merged deck.
Repeat step two until one of the decks is empty. Then take the remaining cards and add them to the merged deck.
enumerate
The result should be a single sorted deck. Here's what this looks like in pseudocode:
verbatim
public static Deck merge (Deck d1, Deck d2) // create a new deck big enough for all the cards Deck result = new Deck (d1.cards.length + d2.cards.length);
// use the index i to keep track of where we are in // the first deck, and the index j for the second deck int i = 0; int j = 0;
// the index k traverses the result deck for (int k = 0; k<result.cards.length; k++)
// if d1 is empty, d2 wins; if d2 is empty, d1 wins;
// otherwise, compare the two cards
// add the winner to the new deck return result;
verbatim
The best way to test merge is to build and shuffle a deck, use subdeck to form two (small) hands, and then use the sort routine from the previous chapter to sort the two halves. Then you can pass the two halves to merge to see if it works.
testing
If you can get that working, try a simple implementation of mergeSort:
verbatim
public static Deck mergeSort (Deck deck) // find the midpoint of the deck // divide the deck into two subdecks // sort the subdecks using sortDeck // merge the two halves and return the result
verbatim
Then, if you get that working, the real fun begins! The magical thing about mergesort is that it is recursive. At the point where you sort the subdecks, why should you invoke the old, slow version of sort? Why not invoke the spiffy new mergeSort you are in the process of writing?
recursion
Not only is that a good idea, it is necessary in order to achieve the performance advantage I promised. In order to make it work, though, you have to add a base case so that it doesn't recurse forever. A simple base case is a subdeck with 0 or 1 cards. If mergesort receives such a small subdeck, it can return it unmodified, since it is already sorted.
The recursive version of mergesort should look something like this:
verbatim
public static Deck mergeSort (Deck deck) // if the deck is 0 or 1 cards, return it
// find the midpoint of the deck // divide the deck into two subdecks // sort the subdecks using mergesort // merge the two halves and return the result
verbatim
As usual, there are two ways to think about recursive programs: you can think through the entire flow of execution, or you can make the ``leap of faith. I have deliberately constructed this example to encourage you to make the leap of faith.
leap of faith
When you were using sortDeck to sort the subdecks, you didn't feel compelled to follow the flow of execution, right? You just assumed that the sortDeck method would work because you already debugged it. Well, all you did to make mergeSort recursive was replace one sort algorithm with another. There is no reason to read the program differently.
Well, actually you have to give some thought to getting the base case right and making sure that you reach it eventually, but other than that, writing the recursive version should be no problem. Good luck!
Glossary
[edit | edit source]description
[pseudocode:] A way of designing programs by writing rough drafts in a combination of English and Java.
[helper method:] Often a small method that does not do anything enormously useful by itself, but which helps another, more useful, method.
pseudocode helper method method!helper
description