Chapter 12  Arrays of objects

In the remaining chapters, we will develop programs that work with playing cards and decks of cards. Here is an outline of the road ahead:

• In this chapter, we define a Card class and write methods that work with cards and arrays of cards.
• In Chapter 13.1, we create a Deck class that encapsulates an array of cards, and we write methods that operate on decks.
• In Chapter 14, we introduce inheritance as a way to create new classes that extend existing classes. We then use all these classes to implement the card game Crazy Eights.

The code for this chapter is in Card.java, which is in the directory ch12 in the repository for this book. Instructions for downloading this code are on page ??.

12.1  Card objects

If you are unfamiliar with traditional playing cards, now would be a good time to get a deck or read through https://en.wikipedia.org/wiki/Standard_52-card_deck.

There are 52 cards in a standard deck. Each card belongs to one of four suits and one of 13 ranks. The suits are Spades, Hearts, Diamonds, and Clubs. The ranks are Ace, 2, 3, 4, 5, 6, 7, 8, 9, 10, Jack, Queen, and King.

If we want to define a class to represent a playing card, it is pretty obvious what the instance variables should be: rank and suit. It is not as obvious what types they should be. One possibility is a String containing things like "Spade" for suits and "Queen" for ranks. A problem with this design is that it would not be easy to compare cards to see which had a higher rank or suit.

An alternative is to use integers to encode the ranks and suits. By “encode” we don’t mean to encrypt or translate into a secret code. We mean “define a mapping between a sequence of numbers and the things we want to represent.”

Here is a mapping for suits:

We use the mathematical symbol ↦ to make it clear that these mappings are not part of the program. They are part of the program design, but they never appear explicitly in the code.

Each of the numerical ranks (2 through 10) maps to the corresponding integer, and for face cards:

So far, the class definition for the Card type looks like this:

The instance variables are private: we can access them from inside this class, but not from other classes.

The constructor takes a parameter for each instance variable. To create a Card object, we use the new operator:

The result is a reference to a Card that represents the 3 of Clubs.

12.2  Card toString

When you create a new class, the first step is to declare the instance variables and write constructors. A good next step is to write toString, which is useful for debugging and incremental development.

To display Card objects in a way that humans can read easily, we need to map the integer codes onto words. A natural way to do that is with an array of Strings. We can create the array like this:

And then assign values to the elements:

Or we can create the array and initialize the elements at the same time, as we saw in Section 8.3:

The state diagram in Figure 12.1 shows the result. Each element of the array is a reference to a String.

---

Figure 12.1: State diagram of an array of strings.

---

Now we need an array to decode the ranks:

The zeroth element should never be used, because the only valid ranks are 1–13. We set it to null to indicate an unused element.

Using these arrays, we can create a meaningful String using suit and rank as indexes.

The expression suits[card.suit] means “use the instance variable suit from the object card as an index into the array suits.”

Now we can wrap all that in a toString method.

When we display a card, println automatically calls toString:

The output is Jack of Diamonds.

12.3  Class variables

So far we have seen local variables, which are declared inside a method, and instance variables, which are declared in a class definition, usually before the method definitions.

Local variables are created when a method is invoked, and their space is reclaimed when the method ends. Instance variables are created when you construct an object and reclaimed when the object is garbage-collected.

Now it’s time to learn about class variables. Like instance variables, class variables are defined in a class definition, before the method definitions. But they are identified by the keyword static. They are created when the program begins (or when the class is used for the first time) and survive until the program ends. Class variables are shared across all instances of the class.

Class variables are often used to store constant values that are needed in several places. In that case, they should also be defined as final. Note that whether a variable is static or final involves two separate considerations: static means the variable is shared, and final means the variable is constant.

Naming static final variables with capital letters is a common convention that makes it easier to recognize their role in the class. Inside toString we can refer to SUITS and RANKS as if they were local variables, but we can tell that they are class variables.

One advantage of defining SUITS and RANKS as class variables is that they don’t need to be created (and garbage-collected) every time toString is called. They may also be needed in other methods and classes, so it’s helpful to make them available everywhere. Since the array variables are final, and the strings they reference are immutable, there is no danger in making them public.

12.4  The compareTo method

As we saw in Section 11.7, it’s helpful to create an equals method to test whether two objects are equivalent.

It would also be nice to have a method for comparing cards, so we can tell if one is higher or lower than another. For primitive types, we can use the comparison operators – <, >, etc. – to compare values. But these operators don’t work for object types.

For Strings, Java provides a compareTo method, as we saw in Section 9.6. Like the equals method, we can write our own version of compareTo for the classes that we define.

Some types are “totally ordered”, which means that you can compare any two values and tell which is bigger. Integers and strings are totally ordered.

Other types are “unordered”, which means that there is no meaningful way to say that one element is bigger than another. In Java, the boolean type is unordered; if you try to compare true < false, you get a compiler error.

The set of playing cards is “partially ordered”, which means that sometimes we can compare cards and sometimes not. For example, we know that the 3 of Clubs is higher than the 2 of Clubs, and the 3 of Diamonds is higher than the 3 of Clubs. But which is better, the 3 of Clubs or the 2 of Diamonds? One has a higher rank, but the other has a higher suit.

To make cards comparable, we have to decide which is more important: rank or suit. The choice is arbitrary, and it might be different for different games. But when you buy a new deck of cards, it comes sorted with all the Clubs together, followed by all the Diamonds, and so on. So for now, let’s say that suit is more important.

With that decided, we can write compareTo as follows:

compareTo returns 1 if this wins, -1 if that wins, and 0 if they are equivalent. It compares suits first. If the suits are the same, it compares ranks. If the ranks are also the same, it returns 0.

12.5  Cards are immutable

The instance variables of Card are private, so they can’t be accessed from other classes. We can provide getters to allow other classes to read the rank and suit values:

Whether or not to provide setters is a design decision. If we did, cards would be mutable, so you could transform one card into another. That is probably not a feature we need, and in general mutable objects are more error-prone. So it might be better to make cards immutable. To do that, all we have to do is not provide any modifier methods (including setters).

That’s easy enough, but it is not foolproof, because some fool might come along later and add a modifier. We can prevent that possibility by declaring the instance variables final:

You can still assign values to these variables inside a constructor. But if someone writes a method that tries to modify these variables, they’ll get a compiler error.

12.6  Arrays of cards

Just as you can create an array of String objects, you can create an array of Card objects. The following statement creates an array of 52 cards:

Figure 12.2 shows the state diagram for this array.

---

Figure 12.2: State diagram of an unpopulated Card array.

---

Although we call it an “array of cards”, the array contains references to objects; it does not contain the Card objects themselves. The elements are initialized to null. You can access the elements of the array in the usual way:

But if you try to access the instance variables of the non-existent Cards, you will get a NullPointerException.

That code won’t work until we put cards in the array. One way to populate the array is to write nested for loops:

The outer loop iterates suits from 0 to 3. For each suit, the inner loop iterates ranks from 1 to 13. Since the outer loop runs 4 times, and the inner loop runs 13 times for each suit, the body is executed 52 times.

We use a separate variable index to keep track of where in the array the next card should go. Figure 12.3 shows what the array looks like after the first two cards have been created.

---

Figure 12.3: State diagram of a Card array with two cards.

---

When you work with arrays, it is convenient to have a method that displays the contents. We have seen the pattern for traversing an array several times, so the following method should be familiar:

Since cards has type Card[], an element of cards has type Card. So println invokes the toString method in the Card class. This method is similar to invoking System.out.println(Arrays.toString(cards)).

12.7  Sequential search

The next method we’ll write is search, which takes an array of cards and a Card object as parameters. It returns the index where the Card appears in the array, or -1 if it doesn’t. This version of search uses the algorithm we saw in Section 8.6, which is called sequential search:

The method returns as soon as it discovers the card, which means we don’t have to traverse the entire array if we find the target. If we get to the end of the loop, we know the card is not in the array. Notice that this algorithm depends on the equals method.

If the cards in the array are not in order, there is no way to search faster than sequential search. We have to look at every card, because otherwise we can’t be certain the card we want is not there. But if the cards are in order, we can use better algorithms.

We will learn in the next chapter how to sort arrays. If you pay the price to keep them sorted, finding elements becomes much easier. Especially for large arrays, sequential search is rather inefficient.

12.8  Binary search

When you look for a word in a dictionary, you don’t just search page by page from front to back. Since the words are in alphabetical order, you probably use a binary search algorithm:

1. Start on a page near the middle of the dictionary.
2. Compare a word on the page to the word you are looking for. If you find it, stop.
3. If the word on the page comes before the word you are looking for, flip to somewhere later in the dictionary and go to step 2.
4. If the word on the page comes after the word you are looking for, flip to somewhere earlier in the dictionary and go to step 2.

If you find two adjacent words on the page and your word comes between them, you can conclude that your word is not in the dictionary.

Getting back to the array of cards, we can write a faster version of search if we know the cards are in order:

First, we declare low and high variables to represent the range we are searching. Initially we search the entire array, from 0 to length - 1.

Inside the while loop, we repeat the four steps of binary search:

1. Choose an index between low and high – call it mid – and compare the card at mid to the target.
2. If you found the target, return the index.
3. If the card at mid is lower than the target, search the range from mid + 1 to high.
4. If the card at mid is higher than the target, search the range from low to mid - 1.

If low exceeds high, there are no cards in the range, so we break out of the loop and return -1. Notice that this algorithm depends on the compareTo method of the object.

12.9  Tracing the code

To see how binary search works, it’s helpful to add the following print statement at the beginning of the loop:

If we invoke binarySearch like this:

We expect to find this card at position 10. Here is the result:

If we search for a card that’s not in the array, like new Card(15, 1), which is the “15 of Diamonds”, we get the following:

Each time through the loop, we cut the distance between low and high in half. After k iterations, the number of remaining cards is 52 / 2^k. To find the number of iterations it takes to complete, we set 52 / 2^k = 1 and solve for k. The result is log₂ 52, which is about 5.7. So we might have to look at 5 or 6 cards, as opposed to all 52 if we did a sequential search.

More generally, if the array contains n elements, binary search requires log₂ n comparisons, and sequential search requires n. For large values of n, binary search can be much faster.

12.10  Recursive version

Another way to write a binary search is with a recursive method. The trick is to write a method that takes low and high as parameters, and turn steps 3 and 4 into recursive invocations. Here’s what the code looks like:

Instead of a while loop, we have an if statement to terminate the recursion. If high is less than low, there are no cards between them, and we conclude that the card is not in the array.

Two common errors in recursive programs are (1) forgetting to include a base case, and (2) writing the recursive call so that the base case is never reached. Either error causes infinite recursion and a StackOverflowException.

12.11  Vocabulary

encode:

To represent one set of values using another set of values, by constructing a mapping between them.

class variable:

A variable declared within a class as static. There is only one copy of a class variable, no matter how many objects there are.

sequential search:

An algorithm that searches array elements, one by one, until a target value is found.

binary search:

An algorithm that searches a sorted array by starting in the middle, comparing and element to the target, and eliminating half of the remaining elements.

12.12  Exercises

The code for this chapter is in the ch12 directory of ThinkJavaCode. See page ?? for instructions on how to download the repository. Before you start the exercises, we recommend that you compile and run the examples.