Arrays

Declaration, Allocation, and Initialization

Before it can be used, a variable must be both declared (to specify its type) and initialized (to give it an initial value). For a variable of an array type, there are three steps we must perform: declaration, allocation, and initialization. First, we must declare the variable. For example:

int[] nums;

The second step is to allocate space for the array. We have to tell Java how many elements the array will have so that it can set aside the appropriate amount of memory. The syntax for allocation uses the keyword new:

nums = new int[4];

The array now exists, but the elements themselves have not yet been initialized. They have default valuesin this case, they are all 0. We often use a for loop to initialize the elements:

for (int i = 0; i < nums.length; i++) { nums[i] = i * 2; }

The effects of these steps are summarized in Figure 2-6.

We can perform all three of these steps in a single statement by explicitly supplying the values of the array elements. This is reasonable only for relatively short arrays:

int[] nums = new int[] {0, 2, 4, 6};

The ability of a variable of an array type to hold an array of any size is another example of polymorphism.

Multidimensional Arrays

We can declare an array of anything. An array of Die objects would be declared like this:

Die[] dice;

An array of ints would be declared like this:

int[] nums;

We can even declare an array of arrays of ints, like this:

int[][] rows;

An array of arrays is called a multidimensional array. Specifically, rows is a two-dimensional array, analogous to a Chess board. If we allocate rows with the statement

rows = new int[3][4];

then we get the data structure shown in Figure 2-7.

Figure 2-7. Instance diagram showing a two-dimensional array. The shaded element is rows[2][3].

The array rows is said to have dimensionality 2, because we have to specify two indices to get at a particular element. The dimensions of the array are 3 (the number of rows) and 4 (the number of columns).

While it would be difficult to draw, we could declare and allocate an array of dimensionality 4:

int[][][][] tesseract = new int[2][5][4][3];

This array has dimensions 2, 5, 4, and 3. It is rare to see dimensionalities greater than 3, because such arrays quickly become impractically large. Even tesseract has 120 elements!

This array-of-arrays representation allows for several interesting tricks. If we supply only one index for rows, we get a reference to a single row of the array. For example, if we say

int[] middleRow = rows[1];

we get the situation in Figure 2-8.

Figure 2-8. A reference to a single row of a two-dimensional array.

We can also allocate an array one part at a time. For example,

int[][] rows = new int[3][];

allocates the spine of the array, but not any of the rows. Since the elements of this array are references, they get the default value null. This is shown in Figure 2-9.

Figure 2-9. A two-dimensional array with only the spine allocated.

Now we can allocate the first row with

rows[0] = new int[4];

giving the situation shown in Figure 2-10.

Figure 2-10. A two-dimensional array with the first row allocated.

There is no reason the other rows have to have the same length. If we now allocate

rows[1] = new int[2]; rows[2] = new int[3];

we get a ragged array, as shown in Figure 2-11.

Figure 2-11. In a ragged array, different rows have different lengths.

Example: Domineering

To illustrate the use of arrays, we now write a program to let two people play the game of Domineering (Figure 2-12).

What classes will we need? An initial sketch (Figure 2-13) suggests that we'll need a Domineering object, one Board object, and a number of Domino objects.

Figure 2-13. This UML class diagram says that a Domineering object is associated with one Board object and 0 to many Domino objects. The asterisk denotes "many." Our actual program will not have this structure.

(This item is displayed on page 48 in the print version)

Further thought reveals that this is overkill. While Domineering involves dominoes, they don't have any interesting state. We don't even care what numbers are on them. All they do is take up space on the board. As long as we keep track of which board squares are occupied, we don't really need a Domino class for this game.

In fact, the board is such a simple thing that we can represent it with a two-dimensional array of booleans. An individual element is true if that square is occupied. We can implement Domineering with a single class (Figure 2-14).

Figure 2-14. The Domineering game can be implemented with a single class. As always, static fields and methods are underlined. It is not yet obvious what all of the fields and methods are for, but we show them here for completeness.

The field squares, the constructor, and the main() method are shown in Figure 2-15.

After allocating squares, we could have initialized the elements with the code

for (int row = 0; row < 8; row++) { for (int column = 0; column < 8; column++) { squares[row][column] = false; } }

but, since false is the default value for booleans, we don't have to do this.

Figure 2-15. A field, constructor, and main() method for Domineering.

The toString() method (Figure 2-16) uses nested for loops.

Figure 2-16. The toString() method uses nested for loops.

Figure 2-17 shows a String the method might return for a board where one horizontal and one vertical domino have been placed.

As in BeetleGame, the play() method contains a loop which repeats until the game is over. This method must keep track of who the current player is. Rather than numbering the players and trying to remember which one plays horizontally and which one vertically, we define two

Figure 2-17. Typical output of the toString() method.

constants HORIZONTAL and VERTICAL. This makes the code easier to read. Since there are only two choices, we can use the boolean values false and true for these constants.

An added advantage of this representation is that we can switch players with the simple statement:

player = !player;

The play() method and these constants are shown in Figure 2-18.

Figure 2-18. The play() method and associated constants. On line 15, we want to print a blank line above the diagram of the board. We do this by adding the newline String " " to this (which is implicitly this.toString()) and passing the result to System.out.println().

The play() method invokes two other methods, hasLegalMoveFor() and playAt(). The first determines if there is any legal move left for the current playerif not, the game is over. The second actually updates the array squares.

We present playAt() first, as it is simpler. This method (Figure 2-19) sets two elements of squares to true.

Figure 2-19. The playAt() method actually modifies the elements of squares. Two elements are modified: one in line 5 and one in either line 7 or line 9.

The hasLegalMoveFor() method is more complicated, because it has to act slightly differently depending on the current player. If it is looking for horizontal moves, it has to check rows 0 through 7 and columns 0 through 6, making sure that both

squares[row][column]

and

squares[row][column + 1]

are unoccupied. On the other hand, when looking for vertical moves, it has to check rows 0 through 6 and columns 0 through 7, making sure that both

squares[row][column]

and

squares[row + 1][column]

are unoccupied. Rather than write loops for each of these very similar cases, we write the loops once, using variables rowOffset and columnOffset to control which version we use. Thus, the second square we check is:

squares[row + rowOffset][column + columnOffset]

If player is HORIZONTAL, rowOffset is 0 and columnOffset is 1. If player is VERTICAL, rowOffset is 1 and columnOffset is 0.

These variables are also used in the termination tests in the for loops. The hasLegalMoveFor() method is shown in Figure 2-20.

Figure 2-20. The exact behavior of the nested for loop in lines 1219 of hasLegalMoveFor() is controlled by the variables rowOffset and columnOffset.

We conclude the example with testing. The first few turns of a game of Domineering are shown in Figure 2-21.

Figure 2-21. Beginning a game of Domineering. Text typed by the user is in grey.

Exercises