9.1: Section 1-

Arrays and Array Processing

After studying this chapter, you will

Know how to use array data structures.

Be able to solve problems that require collections of data.

Know how to sort an array of data.

Be familiar with sequential and binary search algorithms.

Gain a better understanding of inheritance and polymorphism.

Introduction

One-Dimensional Arrays

Simple Array Examples

Example: Counting Frequencies of Letters

Array Algorithms: Sorting

Array Algorithms: Searching

Two-Dimensional Arrays

Multidimensional Arrays (Optional)

Object-Oriented Design: Polymorphic Sorting (Optional)

From the Java Library: java.util.Vector

Case Study: An N-Player Computer Game

A GUI-Based Game (Optional Graphics)

Chapter Summary

Solutions to Self-Study Exercises

Exercises

Introduction

In this chapter we will learn about arrays. An array is a named collection of contiguous storage locations—storage locations that are next to each other—that contain data items of the same type.

Arrays offer a more streamlined way to store data than using individual data items for each variable. Arrays also allow you to work with their data more efficiently than with data stored in individual variables.

Let’s see why. Suppose you want to create a GUI that has 26 buttons on it, one for each letter of the alphabet. Given our present knowledge of Java, our only alternative would be to declare a separate JButton variable for each letter of the alphabet:

 JButton button1;
 JButton button2;
 ...
 JButton button26;

Obviously, requiring 26 separate variables for this problem is tedious and inconvenient. Similarly, to instantiate and assign a label to each button would require 26 statements:

 button1 = new JButton("A");
 button2 = new JButton("B");
 ...
 button26 = new JButton("Z");

This approach is also tedious. What we need is some way to use a loop to process each button, using a loop counter, k, to refer to the kth button on each iteration of the loop. An array lets us do that. For example, the following code will declare an array for storing 26 JButtons and then instantiate and label each button:

 JButton letter[]  = new JButton[26];
 for (int k = 0; k < 26; k++)
     letter[k] = new JButton("A" + k);

You don’t yet understand the code in this segment, but you can see how economical it is. It uses just three lines of code to do what would have required 50 or 60 lines of code without arrays.

Our discussion of arrays will show how to store and retrieve data from one-, two-, and three-dimensional arrays. We also study sorting and searching algorithms to process arrays. Finally, we illustrate how arrays can be used in a variety of applications, including an animation problem, a sorting class, and a card-playing

One-Dimensional Arrays

An array is considered a data structure. A data structure is an organized collection of data. In an array, data are arranged in a linear or sequential structure, with one element following another. When referencing elements in an array, we refer to the position of the particular element within the array. For example, if the array is named arr, then the elements are named arr[0], arr[1], arr[2], ... arr[n-1], where n gives the number of elements in the array. This naming also reflects the fact that the array’s data are contained in storage locations that are next to each other. In Java, as in C, C++, and some other programming languages, the first element of an array has index 0. (This is the same convention we used for Strings.)

Figure [fig-intarray] shows an array named arr that contains 15 int elements. The syntax for referring to elements of an array is

where arrayname is the name of the array—any valid identifier will do—and subscript is the position of the element within the array. As Figure [fig-intarray] shows, the first element in the array has subscript 0, the second has subscript 1, and so on.

A subscript is an integer quantity contained in square brackets that is used to identify an array element. An subscript must be either an integer value or an integer expression. Using Figure [fig-intarray] to illustrate an example, suppose that j and k are integer variables equaling 5 and 7, respectively. Each of the following then would be valid references to elements of the array arr:

arr[4]     //Refers to 16
arr[j]     //Is arr[5] which refers to 20
arr[j + k] //Is arr[5+7] which is arr[12] which refers to 45
arr[k % j] //Is arr[7%5] which is arr[2] which refers to -1

These examples show that when an expression, such as j + k, is used as a subscript, it is evaluated (to 12 in this case) before the reference is made.

It is a syntax error to use a noninteger type as an array subscript. Each of the following expressions would be invalid:

arr[5.0]  // 5.0 is a float and can't be an array subscript
arr["5"]  // "5" is a string not an integer

For a given array, a valid array subscript must be in the range 0 ... N-1, where N is the number of elements in the array or it is considered out-of-bounds. An out-of-bounds subscript creates a run-time error—that is, an error that occurs when the program is running—rather than a syntax error, which can be detected when the program is compiled. For the array arr, each of the following expressions contain out-of-bounds subscripts:

arr[-1]  // Arrays cannot have negative subscripts
arr['5'] // Char '5' promoted to its Unicode value, 53
arr[15]  // The last element of arr has subscript 14
arr[j*k] // Since j*k equals 35

Each of these references would lead to an IndexOutOfBoundsException. (Exceptions are covered in detail in Chapter 10.)

Declaring and Creating Arrays

For the most part, arrays in Java are treated as objects. Like objects, they are instantiated with the new operator and they have instance variables (for example, length). Like variables for objects, array variables are considered reference variables. When arrays are used as parameters, a reference to the array is passed rather than a copy of the entire array. The primary difference between arrays and full-fledged objects is that arrays aren’t defined in terms of an Array class. Thus, arrays don’t fit into Java’s Object hierarchy. They don’t inherit any properties from Object and they cannot be subclassed.

You can think of an array as a container that contains a number of variables. As we’ve seen, the variables contained in an array object are not referenced by name but by their relative position in the array. The variables are called components. If an array object has N components, then we say that the array length is N. Each of the components of the array has the same type, which is called the array’s component type. An empty array is one that contains zero variables.

A one-dimensional array has components that are called the array’s elements. Their type is the array’s element type. An array’s elements may be of any type, including primitive and reference types. This means you can have arrays of int, char, boolean, String, Object, Image, TextField, TwoPlayerGame, and so on.

When declaring a one-dimensional array, you have to indicate both the array’s element type and its length. Just as in declaring and creating other kinds of objects, creating an array object requires that we create both a name for the array and then the array itself. The following statements create the array shown in Figure [fig-intarray]:

int arr[];          // Declare a name for the array
arr = new int[15];  // Create the array itself

These two steps can be combined into a single statement as follows:

int arr[] = new int[15];

In this example, the array’s element type is int and its length is 15, which is fixed and cannot be changed. This means that the array contains 15 variables of type int, which will be referred to as arr[0], arr[1], …arr[14].

Array Allocation

Creating the array in Figure [fig-intarray] means allocating 15 storage locations that can store integers. Note that one difference between declaring an array and declaring some other kind of object is that square brackets () are used to declare an array type. The brackets can be attached either to the array’s name or to its type, as in the following examples:

int arr[];     // The brackets may follow the array's name
int[] arr;     // The brackets may follow the array's type

The following example creates an array of five Strings and then uses a for loop to assign the strings "hello1", "hello2", "hello3", "hello4", and "hello5" to the five array locations:

String strarr[];                // Declare a name for the array
strarr = new String[5];              // Create the array itself
                                 // Assign strings to the array
for (int k = 0; k < strarr.length; k++)     // For each element
  strarr[k] = new String("hello" + (k + 1)); // Assign a string

Note that the expression k < strarr.length specifies the loop bound. Every array has a length instance variable, which refers to the number of elements contained in the array. As we mentioned, arrays, like Strings, are zero indexed, so the last element of the array is always given by its length-1. However, length is an instance variable for arrays, whereas length() is an instance method for Strings. Therefore, it would be a syntax error in this example to refer to strarr.length().

In the example, we first use the new operator to create strarr, an array of type String of length five. We then use a String constructor to create the five Strings that are stored in the array. It is important to realize that creating an array to store five Objects (as opposed to five primitive data elements) does not also create the Objects themselves that will be stored in the array.

When an array of objects is created, the array’s elements are references to those objects (Fig. [fig-arrayobjs]). Their initial values, like all reference variables, are null. So to create and initialize the array strarr, we need to create six objects—the array itself, which will contain five Strings, and then the five Strings that are stored in strarr.

One more example will help underscore this point. The following statements create four new Objects, an array to store three Students plus the three Students themselves:

Student school[] = new Student[3];   // A 3 Student array
school[0] = new Student("Socrates"); // The first Student
school[1] = new Student("Plato");    // The second Student
school[2] = new Student("Aristotle");// The third Student

The first statement creates an array named school to store three s, and the next three statements create the individual Students and assign them to the array (Fig. 9.3). Thus, creating the array and initializing its elements require four new statements.

The following sequence of statements would lead to a null pointer exception because the array’s elements have not been instantiated:

Student students[] = new Student[3]; // A 3 Student array
System.out.println(students[0].getName());

In this case, students[0] is a null reference, thus causing the exception.

Now that we’ve assigned the three Students to the array, we can refer to them by means of subscripted references. A reference to the named “Socrates” is now school[0], and a reference to the named “Plato” is school[1]. In other words, to refer to the three individual students we must refer to their locations within school. Of course, we can also use variables, such as loop counters, to refer to a Student’s location within school. The following for loop invokes each Student’s getState() method to print out its current state:

for (int k = 0; k < school.length; k++)
    System.out.println(school[k].getState());

What if the three Students already existed before the array was created? In that case, we could just assign their references to the array elements, as in the following example:

Student student1 = new Student("Socrates"); 
Student student2 = new Student("Plato");
Student student3 = new Student("Aristotle");
Student school = new Student[3]; // A 3 Student array
school[0] = student1;
school[1] = student2;
school[2] = student3;

In this case, each of the three Student objects can be referenced by two different references—its variable identifier (such as student1) and its array location (such as school[0]). For arrays of objects, Java stores just the reference to the object in the array itself, rather than the entire object. This conserves memory, since references require only 4 bytes each whereas each object may require hundreds of bytes (Fig. 9.4).

When an array of N elements is created, the compiler allocates storage for N variables of the element’s type. In the case of arr that we discussed earlier, the compiler would allocate storage for 15 ints—60 contiguous bytes of storage, because each int requires 4 bytes (32 bits) of storage. If we declare an array of 20 doubles,

double arr[] = new double[20];

the compiler will allocate 160 bytes of storage—20 variables of 8 bytes (64 bits) each. In the case of the examples and String examples, because these are objects (not primitive types), the compiler will allocate space for N addresses, where N is the length of the array and where each address requires 4 bytes.

How much space (in bytes) would be allocated for each of the following?

int a[] = new int[5];

double b[] = new double[10];

char c[] = new char[30];

String s[] = new String[10];

Student p[] = new Student[5];

Initializing Arrays

Array elements are automatically initialized to default values that depend on the element type: Boolean elements are initialized to false, and integer and real types are initialized to 0. Reference types—that is, arrays of objects—are initialized to null.

Arrays can also be assigned initial values when they are created, although this is feasible only for relatively small arrays. An array initializer is written as a list of expressions separated by commas and enclosed by braces. For example, we can declare and initialize the array shown in Figure [fig-intarray] with the following statement:

int arr[] = {-2,8,-1,-3,16,20,25,16,16,8,18,19,45,21,-2};

Similarly, to create and initialize an array of Strings, we can use the following statement:

String strings[] = {"hello", "world", "goodbye", "love"};

This example creates and stores four Strings in the array. Subsequently, to refer to “hello”, we would use the reference strings[0], and to refer to “love”, we would use the reference strings[3]. Note in these examples that when an array declaration contains an initializer, it is not necessary to use new and it is not necessary to specify the number of elements in the array. The number of elements is determined from the number of values in the initializer list.

Assigning and Using Array Values

Array elements can be used in the same way as other variables. The only difference, of course, is that references to the elements are subscripted. For example, the following assignment statements assign values to the elements of two arrays, named arr and strings:

arr[0] = 5;
arr[5] = 10;
arr[2] = 3;
strings[0] = "who";
strings[1] = "what";
strings[2] = strings[3] = "where";

The following loop assigns the first 15 squares—1, 4, 9 …—to the array arr:

for (int k = 0; k < arr.length; k++)
    arr[k] = (k+1) * (k+1);

The following loop prints the values of the array arr:

for (int k = 0; k < arr.length; k++)
    System.out.println(arr[k]);

Declare an array named farr that contains ten floats initialized to the values 1.0, 2.0, …, 10.0.

Write an expression that prints the first element of farr.

Write an assignment statement that assigns 100.0 to the last element in farr.

Write a loop to print all of the elements of farr.

Simple Array Examples

The program in Figure [fig-initarrays] creates two arrays of ten elements each and displays their values on the Java console. In this

public class PrintArrays { 
  static final int ARRSIZE = 10;         // The array's size
  static int intArr[] = new int[ARRSIZE];// Create int array
  static double realArr[] = { 1.1, 2.2, 3.3, 4.4,
     5.5, 6.6, 7.7, 8.8, 9.9, 10.10 }; // And a double array

  public static void main(String args[]) {
    System.out.println("Ints \t Reals");  // Print a heading
                          // For each int and double element
    for (int k = 0; k < intArr.length; k++) 
       System.out.println( intArr[k] + " \t " + 
                                 realArr[k]);  // Print them
    } // main()
} // PrintArrays

example, the elements of have not been given initial values whereas the elements of have been initialized. Note the use of the integer constant to store the arrays’ size. By using the constant in this way, we do not have to use the literal value 10 anywhere in the program, thereby making it easier to read and to modify the program. If we want to change the size of the array that the program handles, we can just change the value of ARRSIZE. This is an example of the maintainability principle.

Note the use of the static qualifier throughout the PrintArrays class. This enables us to refer to the array and the other variables from within the main() method. [fig:printarraysout] If intArr were not declared static, we would get the compiler error attempt to make static use of a non-static variable. This use of static is justified mainly as a coding convenience rather than a principle of object-oriented design. The only examples we’ve seen so far in which static elements were a necessary design element were the use of static elements in the Math class—Math.PI and Math.sqrt()—and the use of static final variables in TwoPlayerGame—TwoPlayerGame.PLAYER_ONE.

For large arrays, it is not always feasible to initialize them in an initializer statement. Consider the problem of initializing an array with the squares of the first 100 integers. Not only would it be tedious to set these values in an initializer statement, it would also be error prone, since it is relatively easy to type in the wrong value for one or more of the squares.

The example in Figure [fig-squares100] creates an array of 50 integers and then fills the elements with the values 1, 4, 9, 16, and so on. It then prints the entire array.

public class Squares {
  static final int ARRSIZE = 50;     // The array's size
  static int intArr[] = new int[ARRSIZE]; // Instantiate
  public static void main(String args[]) {
    for (int k = 0; k < intArr.length; k++)// Initialize
      intArr[k] = (k+1) * (k+1);
    System.out.print("The first 50 squares are"); 
    for (int k = 0; k < intArr.length; k++) { // Print
      if (k % 5 == 0)             // For each 5th square
        System.out.println(" ");//   print a new line
      System.out.print( intArr[k] + " ");
    } // for
  } // main()
} // Squares

This example illustrates some important points about the use of array variables. The array’s elements are individual storage locations. In this example, intArr has 50 storage locations. Storing a value in one of these variables is done by an assignment statement:

intArr[k] = (k+1) * (k+1);

[fig-squaresout] The use of the variable k in this assignment statement allows us to vary the location that is assigned on each iteration of the for loop. Note that in this example, k occurs as the array index on the left-hand side of this expression, while k+1 occurs on the right-hand side as the value to be squared. The reason for this is that arrays are indexed starting at 0 but we want our table of squares to begin with the square of 1. So the square of some number n+1 will always be stored in the array whose index is one less than the number itself—that is, n.

An array’s length variable can always be used as a loop bound when iterating through all elements of the array:

for (int k = 0; k < intArr.length; k++)
    intArr[k] = (k+1) * (k+1);

However, it is important to note that the last element in the array is always at location length-1. Attempting to refer to intArr[length] would cause an IndexOutOfBoundsException because no such element exists.

Declare an array of 100 doubles and write a loop to assign the first 100 square roots to its elements. [Use Math.sqrt(double).]

Example: Counting Frequencies of Letters

Suppose you wish to write a program to help break a text message that has been encrypted with one of the historical ciphers that we have discussed in the two previous chapters. It is well known that historical ciphers often can be broken, that is, the plaintext can be found from the ciphertext, by examining the frequencies of letters and comparing them to the average frequencies of typical samples of plaintext. For example, E and T are the two most frequently used letters in the English language. So, in a ciphertext encrypted with a Caesar cipher, E and T are good guesses as the plaintext letter corresponding to the most frequent letter in a ciphertext message.

Let’s write a program that will count how many times each of the 26 letters of the English language appears in a given string. There are a number of ways to design such a program depending on how flexible you wish the program to be. Let us keep this example simple by assuming that we will only be interested in counting occurrences of the letters A through Z and not of occurrences of spaces or punctuation marks. Assume further that we will change lowercase letters in our string sample to uppercase before counting letters and that we will want to print out the frequencies of letters to the console window. Finally, assume that, later in the chapter after we discuss sorting arrays, we will want to enhance our program so that it can print out the letter frequencies in order of increasing frequency.

A Class to Store the Frequency of One Letter

It is clear that an array should be used for storing the frequencies, but a decision must also be made as to what to store as the array elements. If we store letter frequencies as int values, with the frequency of A stored at index 0, and the frequency of B at index 1, and so forth, we will not be able to rearrange the frequencies into increasing order without losing track of which letter corresponds to which frequency. One way of solving this problem is to create an array of objects, where each object stores both a letter and its frequency.

So let us design a LetterFreq class that stores a letter in an instance variable of type char and its frequency in an instance variable of type int. These instance variables can be declared as:

 private char letter;    //A character being counted
 private int freq;       //The frequency of letter

We will want a constructor that can initialize these two values and two accessor methods to return these values. We are familiar enough with these kinds of methods that it will not be necessary to discuss them any further. We need one additional method to increment freq whenever we encounter the letter while processing the string:

 public void incrFreq() {
     freq++;
 } //setFreq()

A UML diagram for the LetterFreq class is given in Figure 9.9 and the class definition is given

public class LetterFreq {
    private char letter;    //A character being counted
    private int freq;       //The frequency of letter

    public LetterFreq(char ch, int fre) {
        letter = ch;
        freq = fre;
    }
    public char getLetter() {
        return  letter;
    }
    public int getFreq() {
        return  freq;
    }
    public void incrFreq() {
        freq++;
    }
} //LetterFreq

in Figure [fig-letfreq]. Note that we will have to make a minor modification to this class later in this chapter to enable us to sort an array of objects from this class.

A Class to Count Letter Frequencies

Now let us turn to designing a class named AnalyzeFreq that will use an array of objects of type LetterFreq to count the frequencies of the letters A through Z in a given string. The array, let’s call it freqArr, will be the only instance variable of the class. The class needs a constructor to instantiate the array and to create the 26 array elements, each with a different letter and an initial frequency of 0. This class should also have two methods: a method to count the frequencies of the 26 letters in a given string and a method that prints out the frequency of each letter to the console window. The UML diagram for the class is given in Figure 9.11.

The array instance variable can be declared by:

 private LetterFreq[] freqArr; //An array of frequencies

The constructor creates an array of 26 elements to store references to LetterFreq objects with the statement

 freqArr = new LetterFreq[26];

The indices of the array range from 0 to 25 and the elements at these locations should store the letters A to Z. Recall that in Java, char data are a form of int data and can be used in arithmetic. If we let k be an integer that ranges between 0 and 25, then the expression (char)(’A’ + k) will correspond to the letters A to Z. . Thus, the following loop will initialize the array correctly.

for (int k = 0; k < 26; k++) {
    freqArr[k] = new LetterFreq((char)('A' + k), 0);
} //for

The countLetters() method must identify the array index for LetterFreq object that stores a letter between A and Z. If let is a char variable that stores such a letter, then the expression (let - ’A’) will give the index of the array element corresponding to let. Thus the following code will calculate the frequencies the letters in the string parameter, str:

 public void countLetters(String str) {
     char let;     //For use in the loop.
     str = str.toUpperCase();
     for (int k = 0; k < str.length(); k++) {
         let = str.charAt(k);
         if ((let >= 'A') && (let <= 'Z')) {
             freqArr[let - 'A'].incrFreq();
         } //if
     } //for
 } //countLetters()

The definition of the printArray() method is completely straight forward:

public void printArray() {
  for (int k = 0; k < 26; k++) {
    System.out.print("letter: " + freqArr[k].getLetter());
    System.out.println("   freq: " + freqArr[k].getFreq());
  } //for
} //printArray()

The entire definition of AnalyzeFreq is

public class AnalyzeFreq {
  private LetterFreq[] freqArr; //An array of frequencies

  public AnalyzeFreq() {
    freqArr = new LetterFreq[26];
    for (int k = 0; k < 26; k++) {
      freqArr[k] = new LetterFreq((char)('A' + k), 0);
    } //for
  }
  public void countLetters(String str) {
    char let; //For use in the loop.
    str = str.toUpperCase();
    for (int k = 0; k < str.length(); k++) {
      let = str.charAt(k);
      if ((let >= 'A') && (let <= 'Z')) {
        freqArr[let - 'A'].incrFreq();
      } //if
    } //for
  }
  public void printArray() {
    for (int k = 0; k < 26; k++) {
      System.out.print("letter: " + freqArr[k].getLetter());
      System.out.println(" freq: " + freqArr[k].getFreq());
    } //for
  } 
} //AnalyzeFreq

given in Figure [fig-anafreq]. We will modify this class later in the chapter to be able to sort the array after counting. The following main() method, either in this class or in its own class will demonstrate how the class methods are used.

public static void main(String[] argv) {
  AnalyzeFreq af = new AnalyzeFreq();
  af.countLetters("Now is the time for all good students" +
     " to study computer related topics.");
  af.printArray();
} //main()

Rewrite the main() of the AnalyzeFreq class so that it opens a file named freqtest.txt and counts the frequencies of the letters of the text stored in the file. You will need to use the Scanner class to read from the file as was done in Chapter 4. Create a file named freqtest.txt that contains several hundred characters of typical English text to test the new main() method

Array Algorithms: Sorting

an array is the process of arranging its elements in ascending or descending order. Sorting algorithms are among the most widely used algorithms. Any time large amounts of data are maintained, there is some need to arrange them in a particular order. For example, the telephone company needs to arrange its accounts by the last name of the account holder as well as by phone number.

Insertion Sort

The first sorting algorithm we’ll look at is known as insertion sort, so named because as it traverses through the array from the first to the last element, it inserts each element into its correct position in the partially sorted array.

For an array of N elements, let’s think of the array as divided into two parts. The sorted part will be the left hand side of the array. And the unsorted part will be the right hand side of the array. Initially, the sorted part consists of the first element in the array—the element at index 0.

Insertion sort moves through the unsorted portion of the array—that is its loop variable, k, ranges from 1 through N-1. On each iteration it inserts the kth element into its correct position in the sorted part of the array. To insert an element into the sorted part of the array, it may be necessary to move elements greater than the one being inserted out of the way.

In pseudocode, insertion sort can be represented as follows:

-6.5pc

Insertion Sort of an array, arr, of N elements into ascending order
1. For k assigned 1 through N-1
2.   Remove the element arr[k] and store it in x.
3.   For i starting at k-1 and for all preceding elements greater than x
4.     Move arr[i] one position to the right in the array.
5.   Insert x at its correct location.

As is apparent from the pseudocode, we have a nested for loops. The outer (k) loop, iterates through the array from 1 to N-1. The inner loop iterates as many times as necessary, starting with the element just to the left of the kth element in order to insert the kth element into its correct position in the sorted portion. Note that the kth element is always removed from the array (and stored in the variable x), to make room for elements that have to be moved to the right.

To see how this works, consider an integer array containing the ages of five friends:

21 |  20  27  24  19      x = 20
      k 

For this five-element array, insertion sort initially will assume that the element at index 0 is in the correct position. The vertical line marks the boundary between the sorted and unsorted portions of the array. The outer loop will look at each of the remaining elements, one at a time, inserting it into its proper position in the sorted portion of the array. To insert 20, the number at index 1, the inner loop will move 21 to the right by one position. To do this, the algorithm will remove 20 from its location and store it in x. It will then move 21 one space to the right. Finally, it will insert 20, which is stored in x, at index 0, where it belongs relative to the other elements in the sorted part of the array. At this point, the sorted portion of the array consists of the first two elements, which are in the correct order, relative to each other.

20  21 |  27  24  19     x = 27
          k  

For the next element, 27, none of elements in the sorted portion need to be moved, so the inner for loop will iterate zero times. This gives us:

20  21  27 |  24  19    x = 24
              k 

For the fourth element, 24, only the previous element, 27, needs to be moved to the right, giving:

20  21  24  27 | 19    x = 19
                 k 

At this point, the sorted part of the array consists of the first four elements, which are in the correct order relative to each other. Finally, for the last element, 19, all of the elements in the sorted part of the array need to be moved one space to the right. This will require four iterations of the inner loop. We show the state of the array after each iteration of the inner for loop:

              k
20 21 24 27 | 19   Remove 19 and store it x = 19  
20 21 24 27 | 27   Move 27 to the right
20 21 24 24 | 27   Move 24 to the right
20 21 21 24 | 27   Move 21 to the right
20 20 21 24 | 27   Move 20 to the right
19 20 21 24 27 |   Insert x=19 at index 0

Clearly, the fact that so many elements may have to moved on each iteration of the outer loop shows that insertion sort is not a very efficient algorithm.

The Sort class (Fig [fig-bubblemeth]) provides an implementation of the insertionSort() method. There are several points worth noting about this code. First, because it takes an int array as a parameter, the insertionSort() method will sort any array of integers, regardless of the array’s length.

public class Sort {
  public void insertionSort(int arr[]) {
    int temp;  // Temporary variable for insertion
    for (int k = 1; k < arr.length; k++)  { 
      temp = arr[k]; // Remove element from array
      int i;         // For larger preceding elements
      for (i = k-1; i >= 0 && arr[i] > temp; i--) 
        arr[i+1] = arr[i]; // Move it right by one
      arr[i+1] = temp;       // Insert the element
    }
  } // insertionSort()
  public void print(int arr[]) {
    for (int k = 0; k < arr.length; k++)// For each integer
      System.out.print( arr[k] + " \t "); //  Print it
    System.out.println();
  } // print()
  public static void main(String args[]) {
    int intArr[] = { 21, 20, 27, 24, 19 };
    Sort sorter = new Sort();
    sorter.print(intArr);
    sorter.insertionSort(intArr); // Passing an array
    sorter.print(intArr);
  } // main()
} //Sort

Second, note how empty brackets () are used to declare an array parameter. If the brackets were omitted, then arr would be indistinguishable from an ordinary int parameter. Using the brackets indicates that this method takes an array of integers as its parameter.

Third, note how an array of integers is passed to the insertionSort() method in the main() method:

 sorter.insertionSort(intArr); // Pass intArr to the method

That is, when passing an array to a method, you use just the name of the array, without brackets. Both of the following statements would cause syntax errors:

sorter.insertionSort(intArr[]); // Err: Can't have brackets
sorter.insertionSort(intArr[5]);// Err: passing an integer

In the first case, empty brackets are only used when you declare an array variable, not when you are passing the array to a method. In the second case, intArr[5] is an int, not an array, and cannot legally be passed to insertionSort().

Finally, within the insertionSort() method itself, note that we declare the index for the inner for loop outside of the for statement. This is so it can be used outside the scope of the for loop to insert temp at location arr[i+1], its correct location. Note also that the index of its correct location is i+1, rather than just i. This is because the inner loop might iterate past location 0, which would give i a value of -1 at that point.

Selection Sort

There are a large variety of array sorting algorithms. Selection sort is different from, but comparable to, insertion sort in its overall performance. To illustrate the selection sort algorithm, suppose you want to sort a deck of 25 index cards, numbered from 1 to 25. Lay the 25 cards out on a table, one card next to the other. Starting with the first card, look through the deck and find the smallest card, the number 1 card, and exchange it with the card in the first location. Then, go through the deck again starting at the second card, find the next smallest card, the number 2 card, and exchange it with the card in the second location. Repeat this process 24 times.

Translating this strategy into pseudocode gives the following

Selection sort of a 25-card deck from small to large
1. For count assigned 1 to 24  // Outer loop
2.   smallestCard = count
3.   For currentCard assigned count+1 to 25 // Inner loop
4.     If deck[currentCard] < deck[smallestCard]
5.        smallestCard = currentCard
6.   If smallestCard != count // You need to swap
7       Swap deck[count] and deck[smallestCard]

For a deck of 25 cards, you need to repeat the outer loop 24 times. In other words, you must select the smallest card and insert it in its proper location 24 times. The inner loop takes care of finding the smallest remaining card.

On each iteration of this outer loop, the algorithm assumes that the card specified by the outer loop variable, count, is the smallest card (line 2). It usually won’t be, of course, but we have to start somewhere.

The inner loop then iterates through the remaining cards (from count+1 to 25) and compares each one with the card that is currently the smallest (lines 4 and 5). Whenever it finds a card that is smaller than the smallest card, it designates it as the smallest card (line 5). At the end of the loop, the smallestCard variable will remember where the smallest card is in the deck.

Finally, when the inner loop is finished, the algorithm swaps the smallest card with the card in the location designated by count.

Algorithm: Swapping Memory Elements

An important feature of the selection sort algorithm is its need to swap two array elements, or cards, to continue our example. Swapping two memory elements, whether they are array elements or not, requires the use of a temporary variable. For example, to swap the jth and kth elements in an int array named arr, you would use the following algorithm:

int temp = arr[j]; // Store the jth element in temp
arr[j] = arr[k];   // Move the kth element into j
arr[k] = temp;     // Move the jth element into k

The temp variable temporarily stores the jth element so its value is not lost when its location is overwritten by the kth element. The need for this variable is a subtlety that beginning programmers frequently overlook. But consider what would happen if we used the following erroneous algorithm:

arr[j] = arr[k]; // Erroneous swap code
arr[k] = arr[j];

If arr[j] refers to 4 and arr[k] refers to 2 in the array , then the erroneous algorithm would produce , the wrong result.

The following method implements the swap algorithm for two elements, el1 and el2 of an int array:

void swap(int arr[], int el1, int el2) {
    int temp = arr[el1]; // Assign first element to temp
    arr[el1] = arr[el2]; // Overwrite first with second
    arr[el2] = temp;     // Overwrite second with first
} // swap()

Sort the array, 24 18 90 1 0 85 34 18, using the insertion sort algorithm. Show the order of the elements after each iteration of the outer loop.

Sort the array, 24 18 90 1 0 85 34 18, using the selection sort algorithm. Show the order of the elements after each iteration of the outer loop.

Write a Java code segment to swap two Student objects, student1 and student2.

Write a Java implementation of the selectionSort() method to sort an array of int.

Passing a Value and Passing a Reference

Recall from Chapter 3 that when an Object is passed to a method, a copy of the reference to the Object is passed. Because an array is an object, a reference to the array is passed to insertionSort(), rather than the whole array itself. This is in contrast to how a value of a primitive type is passed. In that case, a copy of the actual value is passed.

One implication of this distinction is that for arguments of primitive type, the original argument cannot be changed from within the method because the method has only a copy of its value. For example, the following method takes an int parameter n, which is incremented within the method:

public void add1(int n) {
  System.out.print("n = " + n);
  n = n + 1;
  System.out.println(",  n = " + n);
}

But because n is a parameter of primitive type, incrementing it within the method has no effect on its associated argument. Thus, in the following segment, the value of Num—n’s associated argument—will not be affected by what goes on inside the add() method. The output produced by the code segment is shown in the comments:

int Num = 5;
System.out.println("Num = " + Num); // Prints Num = 5
add1(Num);                    // Prints n = 5,  n = 6            
System.out.println("Num = " + Num); // Prints Num = 5

Note that while n’s value has changed inside the method, Num’s value remains unaffected.

The case is much different when we pass a reference to an object. In that case, the object itself can be manipulated from within the method. The insertionSort() method is a good illustration. In the following code segment, the array anArr is printed, then sorted, and then printed again:

 Sort sorter = new Sorter();
 int anArr[] = { 5, 10, 16, -2, 4, 6, 1 }; 
 sorter.print(anArr);           // Prints 5 10 16 -2 4 6 1
 sorter.insertionSort(anArr);   // Sorts anArr
 sorter.print(anArr);           // Prints -2 1 4 5 6 10 16

As you can see, the object itself (the array) has been changed from within the method. This shows that changes within insertionSort to the array referenced by arr are actually being made to anArr itself. If fact, because insertionSort() is passed a copy of the reference variable anArr, both arr and anArr are references to the very same object—that is, to the same array (Fig. [fig-arrayparam]).

The justification for passing a reference to an object rather than the entire object itself is a matter of efficiency. A reference uses just 4 bytes of data, whereas an object may use thousands of bytes. It would just be too inefficient to copy hundreds of bytes each time an object is passed to a method. Instead, the method is passed a reference to the object, thereby giving it access to the object without incurring the expense of copying large amounts of data. Indeed, Java provides no way to pass a copy of an object to a method.

Give the values that will be stored in myArr and k after you invoke mystery(myArr, k), where myArr, k and mystery() are declared as follows:

int myArr[] = {1,2,3,4,5};    int k = 3;
void mystery(int a[], int m) {
    ++a[m];
    --m;
}

Array Algorithms: Searching

Suppose we have a large array and we need to find one of its elements. We need an algorithm to search the array for a particular value, usually called the key. If the elements of the array are not arranged in any particular order, the only way we can be sure to find the key, assuming it is in the array, is to search every element, beginning at the first element, until we find it.

Sequential Search

This approach is known as a sequential search, because each element of the array will be examined in sequence until the key is found (or the end of the array is reached). A pseudocode description of this algorithm is as follows:

1. For each element of the array
2.    If the element equals the key
3.       Return its index
4. If the key is not found in the array
5.    Return -1 (to indicate failure)

This algorithm can easily be implemented in a method that searches an integer array, which is passed as the method’s parameter. If the key is found in the array, its location is returned. If it is not found, then \(-1\) is returned to indicate failure.

The Search class (Figs. 9.15 and [fig-search]) provides the Java implementation of the sequentialSearch() method. The method takes two parameters: the array to be searched and the key to be searched for. It uses a for statement to examine each element of the array, checking whether it equals the key or not. If an element that equals the key is found, the method immediately returns that element’s index. Note that the last statement in the method will only be reached if no element matching the key is found.

public class Search {

  public int sequentialSearch(int arr[], int key) {
    for (int k = 0; k < arr.length; k++)
      if (arr[k] == key)
        return k;
    return -1;           // Failure if this is reached
  } // sequentialSearch()

  public int binarySearch(int arr[], int key) {
    int low = 0;                // Initialize bounds
    int high = arr.length - 1;
    while (low <= high) {   // While not done
      int mid = (low + high) / 2;
      if (arr[mid] == key)
        return mid;            // Success
      else if (arr[mid] < key)
        low = mid + 1;        // Search top half
      else
        high = mid - 1;       // Search bottom half
    }  // while
    return -1;     // Post: if low > high search failed
  } // binarySearch()
}//Search

Binary Search

If the elements of an array have been sorted into ascending or descending order, it is not necessary to search sequentially through each element of the array in order to find the key. Instead, the search algorithm can make use of the knowledge that the array is ordered and perform what’s known as a binary search, which is a divide-and-conquer algorithm that divides the array in half on each iteration and limits its search to just that half that could contain the key.

To illustrate the binary search, recall the familiar guessing game in which you try to guess a secret number between 1 and 100, being told “too high” or “too low” or “just right” on each guess. A good first guess should be 50. If this is too high, the next guess should be 25, because if 50 is too high the number must be between 1 and 49. If 50 was too low, the next guess should be 75, and so on. After each wrong guess, a good guesser should pick the midpoint of the sublist that would contain the secret number.

Proceeding in this way, the correct number can be guessed in at most \(log_2 N\) guesses, because the base-2 logarithm of N is the number of times you can divide N in half. For a list of 100 items, the search should take no more than seven guesses (\(2^7 = 128 > 100\)). For a list of \(1,000\) items, a binary search would take at most ten guesses (2\(^{10}=1,024>1,000\)).

So a binary search is a much more efficient way to search, provided the array’s elements are in order. Note that “order” here needn’t be numeric order. We could use binary search to look up a word in a dictionary or a name in a phone book.

A pseudocode representation of the binary search is given as follows:

TO SEARCH AN ARRAY OF N ELEMENTS IN ASCENDING ORDER

1. Assign 0 low and assign N-1 to high initially
2. As long as low is not greater than high
3.    Assign (low + high) / 2 to mid
4.    If the element at mid equals the key
5.        then return its index
6.    Else if the element at mid is less than the key
7.        then assign mid + 1 to low
8.    Else assign mid - 1 to high
9. If this is reached return -1 to indicate failure

Just as with the sequential search algorithm, this algorithm can easily be implemented in a method that searches an integer array that is passed as the method’s parameter (Fig. [fig-search]). If the key is found in the array, its location is returned. If it is not found, then \(-1\) is returned to indicate failure. The binarySearch() method takes the same type of parameters as sequentialSearch(). Its local variables, low and high, are used as pointers, or references, to the current low and high ends of the array, respectively. Note the loop-entry condition: low <= high. If low ever becomes greater than high, this indicates that key is not contained in the array. In that case, the algorithm returns \(-1\).

As a binary search progresses, the array is repeatedly cut in half and low and high will be used to point to the low and high index values in that portion of the array that is still being searched. The local variable mid is used to point to the approximate midpoint of the unsearched portion of the array. If the key is determined to be past the midpoint, then low is adjusted to mid+1; if the key occurs before the midpoint, then high is set to mid-1. The updated values of low and high limit the search to the unsearched portion of the original array.

Unlike sequential search, binary search does not have to examine every location in the array to determine that the key is not in the array. It searches only that part of the array that could contain the key. For example, suppose we are searching for \(-5\) in the following array:

int sortArr[] = 
   { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};

The \(-5\) is smaller than the smallest array element. Therefore, the algorithm will repeatedly divide the low end of the array in half until the condition low > high becomes true. We can see this by tracing the values that low, mid, and high will take during the search:

 Key  Iteration  Low   High    Mid
----------------------------------
 -5   0          0     19      9
 -5   1          0     8       4
 -5   2          0     3       1
 -5   3          0     0       0
 -5   4          0     -1      Failure

As this trace shows, the algorithm examines only four locations to determine that \(-5\) is not in the array. After checking location 0, the new value for high will become \(-1\), which makes the condition low <= high false. So the search will terminate.

The TestSearch class (Figs. 9.17 and [fig-testsearch]) provides a program that can be used to test two search methods. It creates an integer array, whose values are in ascending order. It then uses the getInput() method to input an integer from the keyboard and then performs both a sequentialSearch() and a binarySearch() for the number.

For the array containing the elements 2, 4, 6, and so on up to 28 in that order, draw a trace showing which elements are examined if you search for 21 using a binary search.

-2pc

import java.io.*;
public class TestSearch {
  public static int getInput() {
    KeyboardReader kb = new KeyboardReader();
    kb.prompt("This program searches for values in an array.");
    kb.prompt(
    "Input any positive integer (or any negative to quit) : ");
    return kb.getKeyboardInteger();
  } // getInput()

  public static void main(String args[]) throws IOException {
    int intArr[] = { 2,4,6,8,10,12,14,16,18,20,22,24,26,28};
    Search searcher = new Search();
    int key = 0, keyAt = 0;
    key = getInput();
    while (key >= 0) {
      keyAt = searcher.sequentialSearch( intArr, key );
      if (keyAt != -1)
        System.out.println("  Sequential: " + key + 
                              " is at intArr[" + keyAt + "]");
      else
        System.out.println("  Sequential: " + key 
                           + " is not contained in intArr[]");
      keyAt = searcher.binarySearch(intArr, key);
      if (keyAt != -1)
        System.out.println("  Binary: " + key + 
                              " is at intArr[" + keyAt + "]");
      else
        System.out.println("  Binary: " + key + 
                             " is not contained in intArr[]");
      key = getInput();
    } // while
  } // main()
} // TestSearch

Two-Dimensional Arrays

A two-dimensional array, an array whose components are themselves arrays, is necessary or useful for certain kinds of problems. For example, you would use this type of array if you are doing a scientific study in which you have to track the amount of precipitation for every day of the year.

One way to organize these data would be to create a one-dimensional array, consisting of 365 elements:

double rainfall[] = new double[365];

However, with this representation, it would make it very difficult to calculate the average rainfall within a given month, which might be an important part of your study.

A better representation for this problem would be to use a two-dimensional array, one dimension for the months and one for the days. The following statement declares the array variable rainfall and creates a 12 by 31 array object as its reference:

double rainfall[][] = new double[12][31];

Thus, rainfall is an array of arrays. You can think of the first array as the 12 months required for the problem. And you can think of each month as an array of 31 days. The months will be indexed from 0 to 11, and the days will be indexed from 0 to 30.

The problem with this representation is that when we want to refer to the rainfall for January 5, we would have to use rainfall[0][4]. This is awkward and misleading. The problem is that dates—1/5/1999—are unit indexed, while arrays are zero indexed. Because it will be difficult to remember this fact, our representation of the rainfall data may cause us to make errors when we start writing our algorithms.

We can easily remedy this problem by just defining our array to have an extra month and an extra day each month:

double rainfall[][] = new double[13][32];

This representation creates an array with 13 months, indexed from 0 to 12, with 32 days per month, indexed from 0 to 31. However, we can simply ignore the 0 month and 0 day by using unit indexing in all of the algorithms that process the array. In other words, if we view this array as a two-dimensional table, consisting of 13 rows and 32 columns, we can leave row 0 and column 0 unused (Fig. [fig-rainfall]).

As Figure [fig-rainfall] shows, the very first element of this 416-element array has subscripts (0,0) while the last location has subscripts (12,31). The main advantages of this representation is that the program as a whole will be much easier to read and understand and much less prone to error.

In order to refer to an element in a two-dimensional array, you need to use two subscripts. For the rainfall array, the first subscript will specify the month and the second will specify the day within the month. Thus, the following statements assign 1.15 to the rainfall element representing January 5, and then print its value:

rainfall[1][5] = 1.15;   // Rainfall for January 5
System.out.println( rainfall[1][5] );

Just as in the case of one-dimensional arrays, it is an error to attempt to reference an element that is not in the array. Each of the following examples would cause Java to raise an IndexOutOfBoundsException:

rainfall[13][32] = 0.15 ;  // No such element
rainfall[11][33] = 1.3;    // No such column
rainfall[14][30] = 0.74;   // No such row

If the initial values of an array’s elements are supposed to be zero, there is no need to initialize the elements. Java will do it automatically when you create the array with new. However, for many array problems it is necessary to initialize the array elements to some other value. For a two-dimensional array, this would require a nested loop. To illustrate this algorithm, let’s use a nested for loop to initialize each element of the rainfall array to 0:

// Note that both loops are unit indexed.
for (int month = 1; month < rainfall.length; month++)
  for (int day = 1; day < rainfall[month].length; day++)
     rainfall[month][day] = 0.0;

Note that both for loops use unit indexing. This is in keeping with our decision to leave month 0 and day 0 unused.

Remember that when you have a nested for loop, the inner loop iterates faster than the outer loop. Thus, for each month, the inner loop will iterate over 31 days. This is equivalent to processing the array as if you were going across each row and then down to the next row in the representation shown in Figure [fig-rainfall].

Note that for a two-dimensional array, both dimensions have an associated length variable, which is used in this example to specify the upper bound of each for loop. For the rainfall array, the first dimension (months) has a length of 13 and the second dimension (days) has a length of 32.

Another way to view the rainfall array is to remember that it is an array of arrays. The length of the first array, which corresponds to the number (13) of months, is given by rainfall.length. The length of each month’s array, which corresponds to the number of days (32) in a month, is given by rainfall[month].length.

The outer loop of the nested for loop iterates through months 1 through 12, and the inner for loop iterates through days 1 through 31. In this way, \(372\; =\; 12\;\times\; 31\) elements of the array are set to 0.0. In Table 9.1, the boldface numbers along the top represent the day subscripts, while the boldface numbers along the left represent the month subscripts.

[2pt]	0	1	2	3	\(\cdots\)	30	31
[-4pt]
[2pt] 0	–	–	–	–	\(\cdots\)	–	–
[2pt] 1	–	0.0	0.0	0.0	\(\cdots\)	0.0	0.0
[2pt] 2	–	0.0	0.0	0.0	\(\cdots\)	0.0	0.0
[0pt] \(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)	\(\vdots\)
[4pt] 10	–	0.0	0.0	0.0	\(\cdots\)	0.0	0.0
[2pt] 11	–	0.0	0.0	0.0	\(\cdots\)	0.0	0.0
[2pt] 12	–	0.0	0.0	0.0	\(\cdots\)	0.0	0.0
[-4pt]

Declare a two-dimensional array of int, named int2d, that contains five rows, each of which contains ten integers.

Write a statement that prints the last integer in the third row of the array that you created in the previous exercise. Then write an assignment statement that assigns 100 to the last element in the int2d array.

Write a loop to print all of the elements of int2d, which you declared in the previous exercise. Print one row per line with a space between each element on a line.

Two-Dimensional Array Methods

Now that we have figured out how to represent the data for our scientific experiment, let’s develop methods to calculate some results. First, we want a method to initialize the array. This method will simply incorporate the nested loop algorithm we developed previously:

public void initRain(double rain[][]) {
    for (int month = 1; month < rain.length; month++)
        for (int day = 1; day < rain[month].length; day++)
            rain[month][day] = 0.0;
} // initRain()

Note how we declare the parameter for a multidimensional array. In addition to the element type (double), and the name of the parameter (rain), we must also include a set of brackets for each dimension of the array.

Note also that we use the parameter name within the method to refer to the array. As with one-dimensional arrays, the parameter is a reference to the array, which means that any changes made to the array within the method will persist when the method is exited.

The avgDailyRain() Method

One result that we need from our experiment is the average daily rainfall. To calculate this result, we would add up all of the rainfalls stored in the \(12 \;\times\; 31\) array and divide by 365. Of course, the array itself contains more than 365 elements. It contains 416 elements, but we’re not using the first month of the array, and within some months—those with fewer than 31 days—we’re not using some of the day elements. For example, there’s no such day as rainfall[2][30], which would represent February 30. However, because we initialized all of the array’s elements to 0, the rainfall recorded for the non-days will be 0, which won’t affect our overall average.

The method for calculating average daily rainfall should take our two-dimensional array of as a parameter, and it should return a . Its algorithm will use a nested for loop to iterate through the elements of the array, adding each element to a running total. When the loops exits, the total will be divided by 365 and returned:

public double avgDailyRain(double rain[][]) {
    double total = 0;
    for (int month = 1; month < rain.length; month++)
        for (int day = 1; day < rain[month].length; day++)
            total += rain[month][day];
    return total/365;
} // avgDailyRain()

The avgRainForMonth() Method

One reason we used a two-dimensional array for this problem is so we could calculate the average daily rainfall for a given month. Let’s write a method to solve this problem. The algorithm for this method will not require a nested for loop. We will just iterate through the 31 elements of a given month, so the month subscript will not vary. For example, suppose we are calculating the average for January, which is represented in our array as month 1:

double total = 0;
for (int day = 1; day < rainfall[1].length; day++)
    total = total + rainfall[1][day];

Thus, the month subscript is held constant (at 1) while the day subscript iterates from 1 to 31. Of course, in our method we would use a parameter to represent the month, thereby allowing us to calculate the average daily rainfall for any given month.

Another problem that our method has to deal with is that months don’t all have 31 days, so we can’t always divide by 31 to compute the monthly average. There are various ways to solve this problem, but perhaps the easiest is to let the number of days for that month be specified as a third parameter. That way, the month itself and the number of days for the month are supplied by the user of the method:

public double avgRainForMonth(double rain[][], 
                           int month, int nDays) {
    double total = 0;
    for (int day = 1; day < rain[month].length; day++)
        total = total + rain[month][day];
    return total/nDays;
} // avgRainForMonth()

Given this definition, we can call this method to calculate and print the average daily rainfall for March as in the following statement:

System.out.println("March: " + 
                         avgRainForMonth(rainfall,3,31));

Note that when passing the entire two-dimensional array to the method, we just use the name of the array. We do not have to follow the name with

Passing Part of an Array to a Method

Instead of passing the entire rainfall array to the avgRainForMonth() method, we could redesign this method so that it is only passed the particular month that’s being averaged. Remember that a two-dimensional array is an array of arrays, so if we pass the month of January, we are passing an array of 32 days. If we use this approach, we need only two parameters: the month, which is array of days, and the number of days in that month:

public double avgRainForMonth(double monthRain[], 
                                          int nDays) {
    double total = 0;
    for (int day = 1; day < monthRain.length; day++)
        total = total + monthRain[day];
    return total/nDays;
} // avgRainForMonth()

Given this definition, we can call it to calculate and print the average daily rainfall for March as in the following statement:

System.out.println("March: " + 
                      avgRainForMonth(rainfall[3],31));

In this case, we’re passing an array of double to the method, but in order to reference it, we have to pull it out of the two-dimensional array by giving its row subscript as well. Thus, rainfall[3] refers to one month of data in the two-dimensional array, the month of March. But rainfall[3] is itself a one-dimensional array. Figure [fig-twodrow] helps to clarify this point.

It’s important to note that deciding whether to use brackets when passing data to a method is not just a matter of whether you are passing an array. It is a matter of what type of data the method parameter specifies. So, whenever you call a method that involves a parameter, you have to look at the method definition to see what kind of data that parameter specifies. Then you must supply an argument that refers to that type of data.

For our two-dimensional rainfall array, we can refer to the entire array as rainfall. We can refer to one of its months as rainfall[j], where j is any integer between 1 and 12. And we can refer to any of its elements as rainfall[j][k], where j is any integer between 1 and 12, and k is any integer between 1 and 31.

The Rainfall class (Figs. 9.21 and [fig-rainfallclass])

public class Rainfall {
  /**
   * Initializes the rainfall array
   * @param rain is a 2D-array of rainfalls
   * Pre:  rain is non null
   * Post: rain[x][y] == 0 for all x,y in the array
   * Note that the loops use unit indexing.
   */
  public void initRain(double rain[][]) {
    for (int month = 1; month < rain.length; month++)
      for (int day = 1; day < rain[month].length; day++)
        rain[month][day] = Math.random() * 2.0;    // Random rainfall
  } // initRain()
  /**
   * Computes average daily rainfall for a year of rainfall data
   * @param rain is a 2D-array of rainfalls
   * @return The sum of rain[x][y] / 356
   * Pre:  rain is non null
   * Post: The sum of rain / 365 is calculated
   * Note that the loops are unit indexed
   */
  public double avgDailyRain(double rain[][]) {
    double total = 0;
    for (int month = 1; month < rain.length; month++)
      for (int day = 1; day < rain[month].length; day++)
        total += rain[month][day];
    return total/365;
  } // avgDailyRain()
  /**
   * Computes average daily rainfall for a given month containing nDays
   * @param monthRain is a 1D-array of rainfalls
   * @param nDays is the number of days in monthRain
   * @return The sum of monthRain / nDays
   * Pre:  1 <= nDays <= 31
   * Post: The sum of monthRain / nDays is calculated
   */
  public double avgRainForMonth(double monthRain[], int nDays) {
    double total = 0;
    for (int day = 1; day < monthRain.length; day++)
      total = total + monthRain[day];
    return total/nDays;
  } // avgRainForMonth()
  public static void main(String args[]) {
    double rainfall[][] = new double[13][32];
    Rainfall data = new Rainfall();
    data.initRain(rainfall);
    System.out.println("The average daily rainfall = " 
                      +  data.avgDailyRain(rainfall));
    System.out.println("The average daily rainfall for March = " 
                      +  data.avgRainForMonth(rainfall[3],31));
  } // main()
}//Rainfall

shows how we can test our array algorithms. It creates the rainfall array in the main() method. It then initializes the array and prints out average daily rainfall and average daily rainfall for the month of March. However, note that we have made a slight modification to the initRain() method. Instead of just assigning 0 to each element, we assign a random value between 0 and 2.0:

rain[month][day] = Math.random() * 2.0;

Using the Math.random() method in this way enables us to generate some realistic test data. In this case, we have scaled the data so that the daily rainfall is between 0 and 2 inches. (Rainfall like this would probably be appropriate for an Amazonian rain forest!) Testing our algorithms with these data provides some indication that our methods are in fact working properly.

Suppose you’re going to keep track of the daily newspaper sales at the local kiosk. Declare a \(52\;\times\;7\) two-dimensional array of int and initialize each of its elements to 0.

Write a method to calculate the average number of newspapers sold per week, using the array you declared in the previous

Write a method to calculate the average number of newspapers sold on Sundays, using the array you declared in the previous exercise. Assume that Sunday is the last day of the week.

Multidimensional Arrays (Optional)

Java doesn’t limit arrays to just two dimensions. For example, suppose we decide to extend our rainfall survey to cover a ten-year period. For each year we now need a two-dimensional array. This results in a three-dimensional array consisting of an array of years, each of which contains an array of months, each of which contains an array of days:

final int NYEARS = 10;
final int NMONTHS = 13;
final int NDAYS = 32;
double rainfall[][] = new double[NYEARS][NMONTHS][NDAYS];

Following the design convention of not using the 0 month and 0 days, we end up with a \(10 \;\times\; 13 \;\times\; 32\) array. Note the use of final variables to represent the size of each dimension of the array. This helps to make the program more readable.

In Figure [fig-threedarray], each year of the rainfall data is represented as a separate page. On each page, there is a two-dimensional table that consists of 12 rows (1 per month) and 31 columns (1 per day).

You might imagine that our study could be extended to cover rainfall data from a number of different cities. That would result in a four-dimensional array, with the first dimension now being the city. Of course, for this to work, cities would have to be represented by integers, because array subscripts must be integers.

As you might expect, algorithms for processing each element in a three-dimensional table would require a three-level nested loop. For example, the following algorithm would be used to initialize all elements of our three-dimensional rainfall array:

-2pc

for (int year = 0; year < rainfall.length; year++)
 for (int month = 0; month < rainfall[year].length; month++)
  for (int day = 0; day < rainfall[year][month].length; day++)
   rainfall[year][month][day] = 0.0;

Note again the proper use of the length attribute for each of the three dimensions of the array. In the outer loop, rainfall.length, we’re referring to the number of years. In the middle loop, rainfall[year].length, we’re referring to number of months within a given year. In the inner loop, rainfall[year][month].length, we’re referring to the number of days within a month.

If we added a fourth dimension to our array and wanted to extend this algorithm to initialize it, we would simply embed the three-level loop within another for loop that would iterate over each city.

Array Initializers

It is possible to use an initializer with a multidimensional array. For instance, the following examples create several small arrays and initialize their elements:

int a[][] = {{1,2,3}, {4,5,6}};
char c[][] = {{'a','b'}, {'c','d'}};
double d[][][] = 
    {{1.0,2.0,3.0}, {4.0,5.0}, {6.0,7.0,8.0,9.0}};

The first of these declarations creates a \(2\; \times \;3\) array of integers. The second example creates a \(2\; \times\; 2\) array of characters, and the third example creates an array of double consisting of three rows, each of which has a different number of elements. The first row contains three elements, the second contains two elements, and the last row contains four elements. As this last example shows, the rows in a multidimensional array don’t all have to have the same length.

Using initializers, as in these examples, is feasible only for relatively small arrays. To see why, just imagine what the initializer expression would be for our three-dimensional rainfall array. It would require \(4,160 \;=\; 10 \; \times \; 13 \; \times \; 32\) zeroes, separated by commas!

OBJECT-ORIENTED DESIGN:
Polymorphic Sorting (Optional)

One limitation of the sort routines developed so far is that they only work on one particular type of data. If you’ve written an insertion sort to sort ints, you can’t use it to sort doubles. What would be far more desirable is a polymorphic sort method—that is, one method that could sort any kind of data. This is easily done by making use of Java wrapper classes, such as Integer and Double, together with the java.lang.Comparable interface, which is specially designed for this purpose.

The java.lang.Comparable interface consists of the method:

public abstract interface Comparable {
  public int compareTo(Object o);// Abstract method
}

By implementing compareTo(), a class can impose an order on its objects. The Comparable interface is implemented by all of Java’s wrapper classes—that is, by Integer, Double, Float, Long, and so on (Fig. 9.24).

As we saw in Chapter 8, Java interfaces allow us to create a form of multiple inheritance. For example, as Figure 9.24 shows, an Integer is both an and a Comparable. One implication of this is that an Integer can be used in any method that takes either an Object parameter or a Comparable parameter.

The compareTo() method takes an Object parameter and returns an int. It is meant to be invoked as o1.compareTo(o2), where o1 and o2 are objects of the same type. Classes that implement compareTo() must abide by the following rules for its return value:

if (o1 < o2)       then o1.compareTo(o2) < 0
if (o1.equals(o2)) then o1.compareTo(o2) == 0
if (o1 > o2)       then o1.compareTo(o2) > 0

In other words, if o1 < o2, then o1.compareTo(o2) will return a negative integer. If o1 > o2, then o1.compareTo(o2) will return a positive integer. And if o1 and o2 are equal, then o1.compareTo(o2) will return 0.

For a class that implements Comparable, we can use the method to help sort its elements. For example, the following revised version of insertionSort() method can be used to sort any array of Comparable objects—that is, any array of objects whose class implements Comparable:

-1pc

public void sort(Comparable[] arr) {
  Comparable temp;   // Temporary variable for insertion
  for (int k = 1; k < arr.length; k++)  {
    temp = arr[k];    // Remove it from array
    int i;
    for (i = k-1; i >= 0 && arr[i].compareTo(temp) > 0; i--) 
      arr[i+1] = arr[i];   // Move it right by one
    arr[i+1] = temp;        // Insert the element
  }
} // sort()

In this version, the parameter is an array of Comparable. Thus, we can pass it any array whose elements implement Comparable, including an array of Integer or Float, and so on. Then, to compare elements of a Comparable array, we use the compareTo() method:

for (i = k-1; i >= 0 && arr[i].compareTo(temp) > 0; i--) 

Note that our algorithm no longer refers to ints, as in the original insertion sort. Indeed, it doesn’t mention the specific type—Integer, Float, or whatever—of the objects that it is sorting. It refers only to Comparables. Therefore, we can use this method to sort any type of object, as long as the object’s class implements the Comparable interface. Thus, by using Comparable, we have a more general insertionSort() method, one that can sort any one-dimensional array of Comparables.

The TestSort class (Figs. 9.25 and [fig-testsort]) provides an example of how to use the polymorphic sort() method.

It contains three methods: The sort() method that we just described; a polymorphic print() method, which can be used to print the values of any array of Comparable; and a main() method. The main() method creates arrays of Integer and Float and then uses the polymorphic sort() method to sort them. Note how the print() method uses the polymorphic toString() method to print the elements of a Comparable array.

-2pc

public class TestSort {
  public static int MAXSIZE = 25;

  public void sort(Comparable[] arr) {
    Comparable temp;      // Temporary variable for insertion
    for (int k = 1; k < arr.length; k++) { // For each element
      temp = arr[k];                     // Remove it 
      int i;
      for (i = k-1; i >= 0 && arr[i].compareTo(temp) > 0; i--) 
        arr[i+1] = arr[i]; // Move larger to the right
      arr[i+1] = temp;       // Insert the element
    }
  } // sort()
  public void print(Comparable arr[]) {
    for (int k = 0; k < arr.length; k++) {
      if (k % 5 == 0)  System.out.println();  // New row  
        System.out.print(arr[k].toString() + "\t"); 
    }
    System.out.println();
  }
  // Sorts two different types of array with the same method.
  public static void main(String args[]) {
    Integer iArr[] = new Integer[TestSort.MAXSIZE]; 
    Float fArr[] = new Float[TestSort.MAXSIZE];   
    for (int k = 0; k < TestSort.MAXSIZE; k++) { // Create data
      iArr[k] = new Integer((int) (Math.random() * 10000));
      fArr[k] = new Float(Math.random() * 10000);
    }
    TestSort test = new TestSort();
    test.sort(iArr);     // Sort and print Integers
    test.print(iArr);
    test.sort(fArr);     // Sort and print Floats
    test.print(fArr);                      
  } // main()
}

This example of polymorphic sorting illustrates once again the great power of inheritance and polymorphism in object-oriented programming. The Integer and Float classes use class inheritance to inherit features from the Object class, and they use interface implementation to inherit the compareTo() method from the Comparable class. By implementing versions of the toString() and compareTo() methods that are appropriate for these wrapper classes, Java makes it easier to use Integer and Float objects in a variety of contexts. Taken together, inheritance and polymorphism enable us to design very general and extensible algorithms. In this example, we defined a sort() method that can sort an array containing any kind of object as long as the object implements the Comparable interface.

The java.util.Arrays.sort() Method

While sorting algorithms provide a good way to introduce the concepts of array processing, real-world programmers never write their own sort algorithms. Instead they use library methods, which have been written and optimized by programming experts. Moreover, library sort routines use sort algorithms that are much more efficient than the ones we’ve discussed.

The java.util.Arrays class contains a polymorphic sort method that is very simple to use. For example, here’s how we would use it to sort the two arrays declared in the TestSort program:

java.util.Arrays.sort(iArr);
java.util.Arrays.sort(fArr);

That’s all there is to it! Obviously, learning how to use Java’s class and method library, saves real-word programmers lots of effort.

Add a definition of a compareTo() method to the LetterFreq class so that it implements the Comparable interface. The method should define one object to be less than another object if its freq instance variable is less.

Add a definition of a sort() method that can be added to the definition of the AnalyzeFreq class. Make it so the array in the class can be sorted into ascending order using the ordering of LetterFreq defined in the previous exercise. Use the java.util.Arrays.sort() method.

Rewrite the main() of the AnalyzeFreq class to make use of the sort() method of the previous exercise.

From the Java Library: java.util.Vector

The java.util.Vector class implements an array of objects that can grow in size as needed. One limitation of regular arrays is that their lengths remain fixed. Once the array is full—once every element is used—you can’t allocate additional elements.

The Vector class contains methods for storing and retrieving objects, and for accessing objects by their index position within the Vector (Fig. 9.27).

One use for a Vector would be when a program needs to store input from the user or a file without knowing in advance how many items there are. Using a Vector is less efficient than an array in terms of processing speed, but it gives you the flexibility of growing the data structure to meet the storage requirements.

As an illustration of this idea, the program in Figure [fig-vectordemo] creates a random number of integers and then stores them in a Vector. The Vector, which is declared and instantiated in main(), is initially empty. Integers from 0 to the random bound are then inserted into the Vector. In this case, insertions are done with the addElement() method, which causes the Vector object to insert the element at the next available location, increasing its size, if necessary.

import java.util.Vector;

public class VectorDemo {

  public static void printVector(Vector v) {
    for (int k=0; k < v.size(); k++)
      System.out.println(v.elementAt(k).toString());
  } // printVector()

  public static void main(String args[]) {
    Vector vector = new Vector();  // An empty vector

    int bound = (int)(Math.random() * 20);
    for (int k = 0; k < bound; k++ )   // Insert a random
      vector.addElement(new Integer(k));// number of Integers
    printVector(vector);            // Print the elements
  } // main()
}// VectorDemo

Once all the integers have been inserted, the printVector() method is called. Note that it uses the size() method to determine how many elements the Vector contains. This is similar to using the length() method to determine the number of characters in a String.

Finally, note that a Vector stores objects. It cannot be used to store primitive data values. You cannot store an int in a Vector. Therefore, we need to use the Integer wrapper class to convert ints into Integers before they can be inserted into the Vector. Because you can’t just print an Integer, or any other Object, the toString() method is used to print the string representation of the object.

By defining Vector to store Objects, Java’s designers have made it as general as possible and, therefore, as widely useful as possible.

Case Study: An N-Player Computer Game

In this section we will make use of arrays to extend our game-playing library by developing a design that can support games that involve more than two players. We will use an array to store a variable number of players. Following the object-oriented design principles described in Chapter 8, we will make use of inheritance and polymorphism to develop a design that is flexible and extensible, one that can be used to implement a wide variety of computer games. As in our TwoPlayer game example from Chapter 8, our design will allow both humans and computers to play the games. To help simplify the example, we will modify the WordGuess game that we developed in the Chapter 8. As you will see, it requires relatively few modifications to convert it from a subclass of TwoPlayerGame to a subclass of ComputerGame, the superclass for our N-Player game hierarchy.

The ComputerGame Hierarchy

Figure [fig-game] provides a summary overview of the ComputerGame hierarchy. This figure shows the relationships among the many classes and interfaces involved. The two classes whose symbols are bold, WordGuess and WordGuesser, are the classes that define the specific game we will be playing. The rest of the classes and interfaces are designed to be used with any N-player game.

At the root of this hierarchy is the abstract ComputerGame class. Note that it uses from 1 to N Players. These objects will be stored in a one-dimensional array in ComputerGame. Recall from Chapter 8 that an IPlayer was any class that implements the makeAMove() method. In this design, we have put the abstract makeAMove() method into the Player class, a class that defines a generic player of computer games. For the WordGuess game, the WordGuesser class extends Player. In order to play Word Guess, we will create a WordGuess instance, plus one or more instances of WordGuessers. This is similar to the OneRowNim example from the previous chapter,

Note where the TwoPlayerGame and OneRowNim classes occur in the hierarchy. TwoPlayerGame will now be an extension of ComputerGame. This is in keeping with the fact that a two-player game is a special kind of N-player computer game. As we will see when we look at the details of these classes, TwoPlayerGame will override some of the methods inherited from ComputerGame.

Because it contains the abstract makeAMove() method, the Player class is an abstract class. Its purpose is to define and store certain data and methods that can be used by any computer games. For example, one important piece of information defined in Player is whether the player is a computer or a person. Player’s data and methods will be inherited by WordGuesser and by other classes that extend Player. Given its position in the hierarchy, we will be able to define polymorphic methods for WordGuessers that treat them as Players. As we will see, this will give our design great flexibility and extensibility.

The ComputerGame Class

Figure 9.30 shows the design details of the ComputerGame class. One of the key tasks of the ComputerGame class is to manage the one or more computer game players. Because this is a task that is common to all computer games, it makes sense to manage it here in the superclass. Toward this end, ComputerGame declares four instance variables and several methods. Three int variables define the total number of players (nPlayers), the number of players that have been added to the game (addedPlayers), and the player whose turn it is (whoseTurn). An array named player stores the Players. In keeping with the zero indexing convention of arrays, we number the players from 0 to nPlayers-1. These variables are all declared protected, so that they can be referenced directly by ComputerGame subclasses, but as protected variables, they remain hidden from all other classes.

The ComputerGame(int) constructor allows the number of players to be set when the game is constructed. The default constructor sets the number of players to one. The constructors create an array of length nPlayers:

public ComputerGame(int n) {
  nPlayers = n;
  player = new Player[n]; // Create the array
}

The setPlayer() and getPlayer() methods are the mutator and accessor methods for the whoseTurn variable. This variable allows a user to determine and set whose turn it is, a useful feature for initializing a game. The changePlayer() method uses the default expression,

 whoseTurn = (whoseTurn + 1) % nPlayers 

for changing whose turn it is. Assuming that players are numbered from 0 to nPlayers-1, this code gives the turn to the next player, wrapping around to player 0, if necessary. Of course, a subclass of ComputerGame can override this method if the game requires some other order of play.

The addPlayer(Player) method is used to add a new Player to the game, including any subclass of Player. The method assumes that addedPlayers is initialized to 0. It increments this variable by 1 each time a new player is added to the array. For the game WordGuess, we would be adding Players of type WordGuesser to the game.

The complete source code for ComputerGame is shown in Figure [fig-gamesource].

public abstract class ComputerGame {   
  protected int nPlayers;
  protected int addedPlayers = 0;
  protected int whoseTurn;
  protected Player player[];  // An array of players

  public ComputerGame() {
    nPlayers = 1;       // Default: 1 player game
    player = new Player[1];
  }
  public ComputerGame(int n) {
    nPlayers = n;
    player = new Player[n]; // N-Player game
  }
  public void setPlayer(int starter) { 
    whoseTurn = starter; 
  }
  public int getPlayer() { 
    return whoseTurn;  
  }
  public void addPlayer(Player p) {
    player[addedPlayers] = p;
    ++addedPlayers;
  }
  public void changePlayer() { 
    whoseTurn = (whoseTurn + 1) % nPlayers;
  }
  public String getRules() {
    return "The rules of this game are: ";
  }
  public String listPlayers() {
    StringBuffer result = 
          new StringBuffer("\nThe players are:\n");
    for (int k = 0; k < nPlayers; k++)
      result.append("Player" + k + " " + 
                      player[k].toString() + "\n");
      result.append("\n");
      return result.toString();
  }
  public abstract boolean gameOver(); // Abstract
  public abstract String getWinner(); //  methods
} //ComputerGame

There are several points worth noting about this implementation. First, note that just as in the case of the abstract TwoPlayerGame class from Chapter 8, the methods gameOver() and getWinner() are defined as abstract and the getRules() method is given a generic implementation. The intent here is that the subclass will override getRules() and will provide game-specific implementations for the abstract methods.

Second, note how the addPlayer() method is coded. It uses the addedPlayers variable as the index into the player array, which always has length nPlayers. An attempt to call this method when the array is already full will lead to the following exception being thrown by Java:

Exception in thread ``main'' 
    java.lang.ArrayIndexOutOfBoundsException: 2
    at ComputerGame.addPlayer(ComputerGame.java:22)
    at TwentyOne.main(TwentyOne.java:121)

In other words, it is an error to try to add more players than will fit in the player array. In Chapter 11, we will learn how to design our code to guard against such problems.

Finally, note the implementation of the listPlayers() method (Fig. [fig-gamesource]). Here is a good example of polymorphism at work. The elements of the player array have a declared type of Player. Their dynamic type is WordGuesser. So when the expression player[k].toString() is invoked, dynamic binding is used to bind this method call to the implementation of toString() defined in the WordGuesser class. Thus, by allowing toString() to be bound at run time, we are able to define a method here that doesn’t know the exact types of the objects it will be listing.

The power of polymorphism is the flexibility and extensibility it lends to our class hierarchy. Without this feature, we would not be able to define listPlayers() here in the superclass, and would instead have to define it in each subclass.

The WordGuess and WordGuesser Classes

We will assume here that you are familiar with the WordGuess example from Chapter 8. If not, you will need to review that section before proceeding. Word Guess is a game in which players take turns trying to guess a secret word by guessing its letters. Players keep guessing as long as they correctly guess a letter in the word. If they guess wrong, it becomes the next player’s turn. The winner of the game is the person who guesses the last letter secret letter, thereby completely identifying the word.

Figure 9.32 provides an overview of the WordGuess class. If you compare it with the design we used in Chapter 8, the only change in the instance methods and instance variables is the addition of a new constructor, WordGuess(int), and an init() method. This constructor takes an integer parameter representing the number of players. The default constructor assumes that there is one player. Of course, this version of WordGuess extends the ComputerGame class, rather than the TwoPlayerGame class. Both constructors call the init() method to initialize the game:

 public WordGuess() { super(1); init(); }
 public WordGuess(int m) { super(m); init(); } 
 public void init() {
     secretWord = getSecretWord();
     currentWord = new StringBuffer(secretWord);
     previousGuesses = new StringBuffer();
     for (int k = 0; k < secretWord.length(); k++)
        currentWord.setCharAt(k,'?');
     unguessedLetters = secretWord.length();
 }

The only other change required to convert WordGuess to an N-player game, is to rewrite its play() method. Because the new play() method makes use of functionality inherited from the ComputerGame() class, it is actually much simpler than the play() method in the Chapter 8 version:

public void play(UserInterface ui) {
  ui.report(getRules());
  ui.report(listPlayers());
  ui.report(reportGameState());

  while(!gameOver()) {  
    WordGuesser p = (WordGuesser)player[whoseTurn];
    if (p.isComputer())
      ui.report(submitUserMove(p.makeAMove(getGamePrompt())));
    else {
      ui.prompt(getGamePrompt());
      ui.report(submitUserMove(ui.getUserInput()));
    }
    ui.report(reportGameState());
  } // while
}

The method begins by displaying the game’s rules and listing its players. The listPlayers() method is inherited from the ComputerGame class. After displaying the game’s current state, the method enters the play loop. On each iteration of the loop, a player is selected from the array:

 WordGuesser p = (WordGuesser)player[whoseTurn];

The use of the WordGuesser variable, p, just makes the code somewhat more readable. Note that we have to use a cast operator, (WordGuesser), to convert the array element, a Player, into a WordGuesser. Because p is a WordGuesser, we can refer directly to its isComputer() method.

If the player is a computer, we prompt it to make a move, submit the move to the submitUserMove() method, and then report the result. This is all done in a single statement:

 ui.report(submitUserMove(p.makeAMove(getGamePrompt())));

If the player is a human, we prompt the player and use the KeyboardReader’s getUserInput() method to read the user’s move. We then submit the move to the submitUserMove() method and report the result. At the end of the loop, we report the game’s updated state. The following code segment illustrates a small portion of the interaction generated by this play() method:

 Current word ???????? Previous guesses GLE
 Player 0 guesses next.Sorry, Y is NOT a new letter 
                       in the secret word
 Current word ???????? Previous guesses GLEY
 Player 1 guesses next.Sorry, H is NOT a new letter 
                       in the secret word
 Current word ???????? Previous guesses GLEYH
 Player 2 guesses next.
 Guess a letter that you think is in the secret word: a
 Yes, the letter A is in the secret word

In this example, players 0 and 1 are computers and player 2 is a human.

In our new design, the WordGuesser class is a subclass of Player (Figure 9.33). The WordGuesser class itself requires no changes other than its declaration:

 public class WordGuesser extends Player

As we saw when we were discussing the WordGuess class, the play() method invokes WordGuesser’s isComputer() method. But this method is inherited from the Player class. The only other method used by play() is the makeAMove() method. This method is coded exactly the same as it was in the previous version of WordGuesser.

Figure [fig-player] shows the implementation of the Player class. Most of its code is very simple. Note that the default value for the kind variable is HUMAN and the default id is -1, indicating the lack of an assigned identification.

public abstract class Player  {   
  public static final int COMPUTER=0;
  public static final int HUMAN=1;
  protected int id = -1;  // Id between 0 and nPlayers-1
  protected int kind = HUMAN; // Default is HUMAN

  public Player() { }
  public Player(int id, int kind) {
    this.id = id;
    this.kind = kind;
  }
  public void setID(int k) { id = k; }
  public int getID() { return id; }
  public void setKind(int k) { kind = k; }
  public int getKind() { return kind; }
  public boolean isComputer() { return kind == COMPUTER; }
  public abstract String makeAMove(String prompt); 
} // Player

What gives Player its utility is the fact that it encapsulates those attributes and actions that are common to all computer game players. Defining these elements, in the superclass, allows them to be used throughout the Player hierarchy. It also makes it possible to establish an association between a Player and a ComputerGame.

Given the ComputerGame and Player hierarchies and the many interfaces they contain, the task of designing and implementing a new N-player game is made much simpler. This too is due to the power of object-oriented programming. By learning to use a library of classes, such as these, even inexperienced programmers can create relatively sophisticated and complex computer games.

Finally, the following main() method instantiates and runs an instance of the WordGuess game in a command-line user interface (CLUI):

public static void main(String args[]) 
{ KeyboardReader kb = new KeyboardReader();
  ComputerGame game = new WordGuess(3);
  game.addPlayer(new WordGuesser((WordGuess)game, 0, 
                                           Player.HUMAN));
  game.addPlayer(new WordGuesser((WordGuess)game, 1, 
                                         Player.COMPUTER);
  game.addPlayer(new WordGuesser((WordGuess)game, 2, 
                                         Player.COMPUTER);
  ((CLUIPlayableGame)game).play(kb);
} //main()

In this example, we create a three player game in which two of the players are computers. Note how we create a new WordGuesser, passing it a reference to the game itself, as well as its individual identification number, and its type (HUMAN or COMPUTER). To run the game, we simply invoke its play() method. You know enough now about object-oriented design principles to recognize that the use of play() in this context is an example of polymorphism.

A GUI-Based Game (Optional Graphics)

Most modern computer games do not use a command-line interface. This section addresses this shortcoming by expanding our ComputerGame hierarchy so that it works with Graphical User Interfaces (GUIs) as well as Command-Line User Interfaces (CLUIs).

The Sliding Tile Puzzle is a puzzle game. It is played by one player, a human. The puzzle consists of six tiles arranged on a board containing seven spaces. Three of the tiles are labeled L and three are labeled R. Initially the tiles are arranged as RRR_LLL. In other words, the R tiles are arranged to the left of the L tiles, with the blank space in the middle. The object of the puzzle is to rearrange the tiles into LLL_RRR. The rules are that tiles labeled R can only move right. Tiles labeled L can only move left. Tiles may move directly into the blank space or they can jump over one tile into the blank space.

Our purpose in this section is to develop a GUI that plays this game. An appropriate GUI is shown Figure [fig-capture]. Here the tiles and the blank space are represented by an array of buttons. To make a move the user clicks on the ’tile’ he or she wishes to move. The GUI will assume that the user wants to move that tile into the blank space. If the proposed move is legal, the GUI will carry out the move. Otherwise, it will just ignore it. For example, if the user were to click on the third R button from the left, a legal move, the GUI would rearrange the labels on the buttons so that their new configuration would be RR_RLLL. On the other hand, if the user were to click on the rightmost L button, the GUI would ignore that move, because it is illegal.

The GUIPlayableGame Interface

How should we extend our game-playing hierarchy to accommodate GUI-based games? As we learned in Chapter 4, one difference between GUI-based applications and CLUI-based applications, is the locus of control. In a CLUI-based application, control resides in the computational object which, for games, is the game object. That’s why the play() method in our CLUI-based games contains the game’s control loop. By contrast, control resides in the GUI’s event loop in GUI-based applications. That’s why, we learned how to manage Java’s event hierarchy in Chapter 4. Thus, in the GUI shown in Figure [fig-capture], the GUI will listen and take action when the user clicks one of its buttons.

However, given that control will reside in the GUI, there is still a need for communication between the GUI and the game object. In the CLUI-based games, we have used the CLUIPlayableGame interface to manage the communication between the game and the user interface. We will follow the same design strategy in this case. Thus, we will design a GUIPlayableGame interface that can be implemented by any game that wishes to use a GUI (Fig. 9.36).

What method(s) should this interface contain? One way to answer this question is to think about the type of interaction that must take place when the user clicks one of the tiles. If the user clicks the third R button, the GUI should pass this information to the game. The game should then decide whether or not that is a legal move and communicate this back to the GUI. Assuming it is a legal move, the game should also update its representation of the game’s state to reflect that the tile array has changed. And it should somehow make communicate the game’s state to the GUI.

Because it is impossible to know in advance just what form of data a game’s moves might take, we will use Java Strings to communicate between the user interface and the game object. Thus, a method with the following signature will enable us to submit a String representing the user’s move to the game and receive in return a String representing the game object’s response to the move:

 submitUserMove(String move): String;

In addition to this method, a GUI interface could use the reportGameState() and getGamePrompt() methods that are part of the IGame interface. Th design shown in Figure 9.36 leads to the following definition for the GUIPlayableGame interface:

public interface GUIPlayableGame extends IGame {
    public String submitUserMove(String theMove);
}

Because it extends IGame, this interface inherits the getGamePrompt() and reportGameState() from the IGame interface. The GUI should be able to communicate with any game that implements this interface.

The SlidingTilePuzzle

Let’s now discuss the design and details of the SlidingTilePuzzle itself. Its design is summarized in Figure 9.37. Most of the methods should be familiar to you, because the design closely follows the design we employed in the WordGuess example. It has implementations of inherited methods from the ComputerGame class and the GUIPlayableGame interface.

We will represent the sliding tile puzzle in a one-dimensional array of char. We will store the puzzle’s solution in a Java String and we will use an int variable to keep track of where the blank space is in the array. This leads to the following class-level declarations:

 private char puzzle[] = {'R','R','R',' ','L','L','L'};
 private String solution = "LLL RRR";
 private int blankAt = 3;

Note how we initialize the puzzle array with the initial configuration of seven characters. Taken together, these statements initialize the puzzle’s state.

Because a puzzle is a one-person game and our sliding tile puzzle will be played by a human, this leads to a very simple constructor definition:

 public SlidingTilePuzzle() {
     super(1);
 }

We call the super() constructor (ComputerGame()) to create a one-person game.

The puzzle’s state needs to be communicated to the GUI as a String. This is the purpose of the reportGameState() method:

 public String reportGameState() {   
     StringBuffer sb = new StringBuffer();
     sb.append(puzzle);
     return sb.toString();
 }

We use a StringBuffer() to convert the puzzle, a char array, into a String.

The most important method for communicating with the GUI is the submitUserMove() method:

public String submitUserMove(String usermove) {   
  int tile = Integer.parseInt(usermove);
  char ch = puzzle[tile];
  if (ch == 'L' && 
               (blankAt == tile-1 || blankAt == tile-2))
    swapTiles(tile,blankAt);
  else if (ch == 'R' && 
               (blankAt == tile+1 || blankAt == tile+2))
    swapTiles(tile,blankAt);
  else 
    return "That's an illegal move.\n";
  return "That move is legal.\n";
}

This is the method that processes the user’s move, which is communicated through the GUI. As we saw, the puzzle’s ’tiles’ are represented by an array of buttons in the GUI. The buttons are indexed 0 through 6 in the array. When the user clicks a button, the GUI should pass its index, represented as a String to the submitUserMove() method. Given the index number of the tile that was selected by the user, this method determines if the move is legal.

The Integer.parseInt() method is used to extract the tile’s index from the method’s parameter. This index is used to get a ’tile’ from the puzzle array. The logic in this method reflects the rules of the game. If the tile is an L, then it can only move into a blank space that is either 1 or 2 spaces to its left. Similarly, an R tile can only move into a blank space that is 1 or 2 spaces to its right. All other moves are illegal. For legal moves, we simply swap the tile and the blank space in the array, a task handled by the swap() method. In either case, the method returns a string reporting whether the move was legal or illegal.

Figure [fig-puzzlecode] shows the full implementation for the SlidingTilePuzzle, the remaining details of which are straight forward.

public class SlidingTilePuzzle extends ComputerGame 
                            implements GUIPlayableGame {
  private char puzzle[] = {'R','R','R',' ','L','L','L'};
  private String solution = "LLL RRR";
  private int blankAt = 3;
  public SlidingTilePuzzle() { super(1); }

  public boolean gameOver() { // True if puzzle solved
    StringBuffer sb = new StringBuffer();
    sb.append(puzzle);
    return sb.toString().equals(solution);    
  } 
  public String getWinner() {   
    if (gameOver())
      return "\nYou did it! Very Nice!\n";
    else return "\nGood try. Try again!\n";
  }
  public String reportGameState() {   
    StringBuffer sb = new StringBuffer();
    sb.append(puzzle);
    return sb.toString();
  } 
  public String getGamePrompt() {    
    return "To move a tile, click on it.";
  } //prompt()

  public String submitUserMove(String usermove) {   
    int tile = Integer.parseInt(usermove);
    char ch = puzzle[tile];
    if (ch=='L' && (blankAt==tile-1 || blankAt==tile-2))
      swapTiles(tile,blankAt);
    else if (ch=='R' && 
                   (blankAt==tile+1 || blankAt==tile+2))
      swapTiles(tile,blankAt);
    else 
      return "That's an illegal move.\n";
    return "That move is legal.\n";
  }
  private void swapTiles(int ti, int bl) {
    char ch = puzzle[ti];
    puzzle[ti] = puzzle[bl];
    puzzle[bl] = ch;
    blankAt = ti;   // Reset the blank
  }
} //SlidingTilePuzzle

The SlidingGUI Class

Let’s now implement a GUI that can be used to play the sliding tile puzzle. We will model the GUI itself after those we designed in Chapter 4.

Figure 9.39 provides a summary of the design. As an implementor of the interface, SlidingGUI implements the actionPerformed() method, which is where the code that controls the puzzle is located. The main data structure is an array of seven JButtons, representing the seven tiles in the puzzles. The buttons’ labels will reflect the state of the puzzle. They will be rearranged after every legal move by the user. The reset button is used to reinitialize the game. This allows users to play again or to start over if they get stuck.

The puzzleState is a String variable that stores the puzzle’s current state, which is updated repeatedly from the SlidingTilePuzzle by calling its reportGameState() method. The private labelButtons() method will read the puzzleState and use its letters to set the labels of the GUI’s buttons.

The implementation of SlidingGUI is shown in Figure [fig-GUIsource]. Its constructor and buildGUI() methods are responsible for setting up the GUI. We use of a for loop in buildGUI() to create the JButtons, associate an ActionListener with them, and add them to the GUI. Except for the fact that we have an array of buttons, this is very similar to the GUI created in Chapter 4. Recall that associating an ActionListener with the buttons allows the program to respond to button clicks in its actionPerformed() method.

Note how an instance of the SlidingTilePuzzle is created in the constructor, and how its state is retrieved and stored in the puzzleState variable:

 puzzleState = sliding.reportGameState();

The labelButtons() method transfers the letters in puzzleState onto the buttons.

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
public class SlidingGUI extends JFrame implements ActionListener {
  private JButton tile[] = new JButton[7];
  private JButton reset = new JButton("Reset");
  private SlidingTilePuzzle sliding;
  private String puzzleState;
  private Label label;
  private String prompt = "Goal: [LLL RRR]. " +
    " Click on the tile you want to move." +
    " Illegal moves are ignored.";
  public SlidingGUI(String title) {
    sliding = new SlidingTilePuzzle();
    buildGUI();
    setTitle(title);
    pack();
    setVisible(true);
  } // SlidingGUI()
  private void buildGUI() {
    Container contentPane = getContentPane();
    contentPane.setLayout(new BorderLayout());
    JPanel buttons = new JPanel();
    puzzleState = sliding.reportGameState();
    for (int k = 0; k < tile.length; k++) {
      tile[k] = new JButton(""+puzzleState.charAt(k));
      tile[k].addActionListener(this);
      buttons.add(tile[k]);
    }
    reset.addActionListener(this);
    label = new Label(prompt);
    buttons.add(reset);
    contentPane.add("Center", buttons);
    contentPane.add("South", label);
  } // buildGUI()
  private void labelButtons(String s) {
    for (int k = 0; k < tile.length; k++)
      tile[k].setText(""+ s.charAt(k));
  } // labelButtons()
  public void actionPerformed(ActionEvent e) {
    String result = "";
    if (e.getSource() == reset) { // Reset clicked?
      sliding = new SlidingTilePuzzle();
      label.setText(prompt);
    }
    for (int k = 0; k < tile.length; k++) // Tile clicked?
      if (e.getSource() == tile[k])
        result = ((GUIPlayableGame)sliding).submitUserMove(""+ k);
    if (result.indexOf("illegal") != -1)
      java.awt.Toolkit.getDefaultToolkit().beep();
    puzzleState = sliding.reportGameState();
    labelButtons(puzzleState);
    if (sliding.gameOver()) 
      label.setText("You did it! Very nice!");
  } // actionPerformed()
  public static void main(String args[]) {
    new SlidingGUI("Sliding Tile Puzzle");
  } // main()
} // SlidingGUI

The most important method in the GUI is the actionPerformed() method. This method controls the GUI’s actions and is called automatically whenever one of the GUI’s buttons is clicked. First, we check whether the reset button has been clicked. If so, we reset the puzzle by creating a new instance of SlidingTilePuzzle and re-initializing the prompt label.

Next we use a for loop to check whether one of the tile buttons has been clicked. If so, we use the loop index, k, as the tile’s identification and submit this to the puzzle as the user’s move:

if (e.getSource() == tile[k])
  result = ((GUIPlayableGame)sliding).submitUserMove(""+ k);

The cast operation is necessary here because we declared sliding as a SlidingTilePuzzle rather than as a GUIPlayableGame. Note also that we have to convert k to a String when passing it to submitUserMove().

As a result of this method call, the puzzle returns a result, which is checked to see if the user’s move was illegal. If result contains the word “illegal”, the computer beeps to signal an error:

 if (result.indexOf("illegal") != -1)
    java.awt.Toolkit.getDefaultToolkit().beep();

The java.awt.Toolkit is a class that contains lots of useful methods, including the beep() method. Note that no matter what action is performed, a reset or a tile click, we update puzzleState by calling reportGameState() and use it to relabel the tile buttons. The last task in the actionPerformed() method is to invoke the puzzle’s gameOver() method to check if the user has successfully completed the puzzle. If so, we display a congratulatory message in the GUI’s window.

Finally, the main() for a GUI is very simple, consisting of a single line of code:

   new SlidingGUI("Sliding Tile Puzzle");

Once a SlidingGUI is created, with the title of “Sliding Tile Puzzle,” it will open a window and manage the control of the puzzle.

array

array initializer

array length

binary search

data structure

element

element type

insertion sort

multidimensional array

one-dimensional array

polymorphic sort method

selection sort

sequential search

sorting

subscript

two-dimensional array

An array is a named collection of contiguous storage locations, each of which stores a data item of the same data type. Each element of an array is referred to by a subscript—that is, by its position in the array. If the array contains N elements, then its length is N and its indexes are 0, 1, …N-1.

Array elements are referred to using the following subscript notation arrayname[subscript], where arrayname is any valid identifier, and subscript is an integer value in the range 0 to arrayname.length - 1. The array’s length instance variable can be used as a bound for loops that process the array.

An array declaration provides the name and type of the array. An array instantiation uses the keyword new and causes the compiler to allocate memory for the array’s elements:

int arr[]; // Declare a one-dimensional array variable
arr = new int[15];// Allocate 15 int locations for it

Multidimensional arrays have arrays as their components:

int twoDarr[][]; // Declare a two-dimensional array variable
twoDarr = new int[10][15]; // Allocate 150 int locations

An array’s values must be initialized by assigning values to each array location. An initializer expression may be included as part of the array declaration.

Insertion sort and selection sort are examples of array sorting algorithms. Both algorithms require several passes over the array.

When an array is passed as a argument to a method, a reference to the array is passed rather than the entire array itself.

Swapping two elements of an array, or any two locations in memory, requires the use of a temporary variable.

Sequential search and binary search are examples of array searching algorithms. Binary search requires that the array be sorted.

For multidimensional arrays, each dimension of the array has its own length variable.

Inheritance and polymorphism are useful design features for developing a hierarchy of computer games.

Space (in bytes) allocated for each of the following?

1. int a[] = new int[5]; // 5 * 4 = 20 bytes
2. double b[] = new double[10]; // 10 * 8 = 80 bytes
3. char c[] = new char[30]; // 30 * 2 = 60 bytes
4. String s[] = new String[10]; // 10 * 4 (reference) = 40 bytes
5. Student s[] = new Student[5]; // 5 * 4 (reference) = 20 bytes

An array containing 10 floats, 1.0 to 10.0.

float farr[] = {1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0,10.0};

Prints the first element of farr.

System.out.println(farr[0]);

Assigns 100.0 to the last element in farr.

farr[farr.length-1] = 100.0;

A loop to print all of the elements of farr.

for (int j = 0; j < farr.length; j++)
    System.out.println(farr[j]);

An array containing the first 100 square roots.

double doubarr[] = new double[100];
for (int k = 0; k < doubarr.length; k++)
    doubarr[k] = Math.sqrt(k+1);

Analyzing the letter frequencies in a file.

import java.io.*;
import java.util.Scanner;
public static void main(String[] argv) {
  Scanner fileScan;  // To read lines of text from the file
  String str;        // To store the line of text
  AnalyzeFreq af = new AnalyzeFreq();
  try {         // Create a Scanner
    File theFile = new File("freqtest.txt");
    fileScan = Scanner.create(theFile);
    fileScan = fileScan.useDelimiter("\r\n"); //For Windows
    while (fileScan.hasNext()) { // Read and count
      str = fileScan.next();
      af.countLetters(str);
    } //while
    af.printArray(); // Print frequencies
  } catch (Exception e) {
     e.printStackTrace();
  } //catch()
} //main()

Sort 24 18 90 1 0 85 34 18 with insertion sort.

  24 18 90 1  0  85 34 18 // Initial
  18 24 90 1  0  85 34 18 // Pass 1
  18 24 90 1  0  85 34 18 // Pass 2
  1  18 24 90 0  85 34 18 // Pass 3
  0  1  18 24 90 85 34 18 // Pass 4
  0  1  18 24 85 90 34 18 // Pass 5
  0  1  18 24 34 85 90 18 // Pass 6
  0  1  18 18 24 34 85 90 // Pass 7

Sort 24 18 90 1 0 85 34 18 with selection sort.

24 18 90 1   0   85 34 18 // Initial
0  18 90 1   24  85 34 18 // Pass 1
0  1  90 18  24  85 34 18 // Pass 2
0  1  18 90  24  85 34 18 // Pass 3
0  1  18 18  24  85 34 90 // Pass 4
0  1  18 18  24  85 34 90 // Pass 5
0  1  18 18  24  34 85 90 // Pass 6
0  1  18 18  24  34 85 90 // Pass 7

Code to swap two Students.

Student tempStud = student1;
student1 = student2;
student2 = tempStud;

Implementation of the selectionSort().

 public void selectionSort(int arr[]) {
    int smallest;      // Location of smallest element
    for (int k = 0; k < arr.length-1; k++) {  
        smallest = k;
        for (int j = k+1; j < arr.length; j++) 
            if (arr[j] < arr[smallest]) 
                smallest = j;
        if (smallest != k) {   // Swap smallest and kth
            int temp = arr[smallest];      
            arr[smallest] = arr[k]; 
            arr[k] = temp;
        } // if
    } // outer for
 } // selectionSort()

After mystery(myArr,k), myArr will store 1,2,3,5,5 and k will store 3.

Binary search trace for 21 in 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28:

key  iteration  low   high    mid
--------------------------------------
21   0          0     13      6
21   1          7     13      10
21   2          7     9       8
21   3          9     9       9
21   4          10    9       failure

A two-dimensional array with 5 rows of 10 integers.

int int2d[][] = new int[5][10];

Prints the last integer in the third row int2d and assigns 100 to its last element.

System.out.println(int2d[2][9]);
int2d[4][9] = 100;

Prints all of the elements of int2d.

for (int k = 0; k < int2d.length; k++) {
     for (int j = 0; j < int2d[k].length; j++)
         System.out.print( int2d[k][j] + " ");
     System.out.println();    // new line
}

A \(52\; \times \;7\) two-dimensional array of int.

int sales[][] = new int[52][7];
for (int k = 0; k < sales.length; k++)
    for (int j= 0; j < sales[k].length; j++)
        sales[k][j] = 0;

A method to calculate average number of newspapers per week.

double avgWeeklySales(int arr[][]) {
    double total = 0;
    for (int k = 0; k < arr.length; k++)
        for (int j= 0; j < arr[k].length; j++)
            total += arr[k][j];
    return total/52;
}

A method to calculate average Sunday newspapers.

double avgSundaySales(int arr[][]) {
    double total = 0;
    for (int k = 0; k < arr.length; k++)
        total += arr[k][6];
    return total/52;
}

A compareTo() for LetterFreq.

public int compareTo(Object lf) {
     LetterFreq  letFreq = (LetterFreq)lf;
     if (freq < letFreq.getFreq())
         return -1;
     else if (freq > letFreq.getFreq())
         return +1;
     else return 0; //The frequencies must be equal.
} //compareTo()

A sort() for AnalyzeFreq.

public void sort() {
     java.util.Arrays.sort(freqArr);
} //sort()

A new AnalyzeFreq.main() that uses sort().

public static void main(String[] argv) {
  AnalyzeFreq af = new AnalyzeFreq();
  af.countLetters("Now is the time for all good students" +
     " to study computer-related topics.");
  af.sort();
  af.printArray();
} //main()

Explain the difference between the following pairs of terms:

An element and an element type.

A subscript and an array element.

A one-dimensional array and two-dimensional array.

An array and a vector.

A insertion sort and a selection sort.

A binary search and a sequential search.

Fill in the blanks.

=14pt

The process of arranging an array’s elements into a particular order is known as

---

 .

One of the preconditions of the binary search method is that the array has to be

---

 .

An

---

is an object that can store a collection of elements of the same type.

An

---

is like an array except that it can grow.

For an array, its

---

is represented by an instance variable.

An expression that can be used during array instantiation to assign values to the array is known as an

---

 .

A

---

is an array of arrays.

A sort method that can be used to sort different types of data is known as a

---

method.

To instantiate an array you have to use the

---

operator.

An array of objects stores

---

to the objects.

=11pt

Make each of the following array declarations:

A \(4 \times 4\) array of doubles.

A \(20 \times 5\) array of Strings.

A \(3 \times 4\) array of char initialized to ‘*’;

A \(2 \times 3 \times 2\) array of boolean initialized to true.

A \(3 \times 3\) array of Students.

A \(2 \times 3\) array of Strings initialized to “one,” “two,” and so on.

Identify and correct the syntax error in each of the following expressions:

int arr = new int[15];

int arr[] = new int(15);

float arr[] = new [3];

float arr[] = new float {1.0,2.0,3.0};

int arr[] = {1.1,2.2,3.3};

int arr[][] = new double[5][4];

int arr[][] = { {1.1,2.2}, {3.3, 1} };

Evaluate each of the following expressions, some of which may be erroneous:

int arr[] = { 2,4,6,8,10 };

2

arr[4]

arr[ arr.length ]

arr[ arr[0] ]

arr[ arr.length / 2 ]

arr[ arr[1] ]

arr[ 5 % 2 ]

arr[ arr[ arr[0] ] ]

arr[ 5 / 2.0 ]

arr[ 1 + (int) Math.random() ]

arr[ arr[3] / 2 ]

What would be printed by the following code segment?

int arr[] = { 24, 0, 19, 21, 6, -5, 10, 16};
for (int k = 0; k < arr.length; k += 2)
  System.out.println( arr[k] );

What would be printed by the following code segment?

int arr[][] = { {24, 0, 19}, {21, 6, -5}, {10, 16, 3}, 
                                           {1, -1, 0} };
for (int j = 0; j < arr.length; j++)
  for (int k = 0; k < arr[j].length; k++)
    System.out.println( arr[j][k] );

What would be printed by the following code segment?

int arr[][] = { {24, 0, 19}, {21, 6, -5}, {10, 16, 3}, 
                                           {1, -1, 0} };
for (int j = 0; j < arr[0].length; j++)
    for (int k = 0; k < arr.length; k++)
        System.out.println(arr[k][j]);

What’s wrong with the following code segment, which is supposed to swap the values of the int variables, n1 and n2?

int temp = n1;
n2 = n1;
n1 = temp;

Explain why the following method does not successfully swap the values of its two parameters? Hint: Think about the difference between value and reference parameters.

public void swapEm(int n1, int n2) {
    int temp = n1;
    n1 = n2;
    n2 = temp;
}

Declare and initialize an array to store the following two-dimensional table of values:

1   2   3   4
5   6   7   8
9  10  11  12

For the two-dimensional array you created in the previous exercise, write a nested for loop to print the values in the following order: 1 5 9 2 6 10 3 7 11 4 8 12. That is, print the values going down the columns instead of going across the rows.

Define an array that would be suitable for storing the following values:

The GPAs of 2,000 students.

The lengths and widths of 100 rectangles.

A week’s worth of hourly temperature measurements, stored so that it is easy to calculate the average daily temperature.

A board for a tic-tac-toe game.

The names and capitals of the 50 states.

Write a code segment that will compute the sum of all the elements of an array of int.

Write a code segment that will compute the sum of the elements in a two-dimensional array of int.

Write a method that will compute the average of all the elements of a two-dimensional array of float.

Write a method that takes two parameters, an int array and an integer, and returns the location of the last element of the array that is greater than or equal to the second parameter.

Write a program that tests whether a \(3\; \times \;3\) array, input by the user, is a magic square. A magic square is an \(N\; \times\; N\) matrix of numbers in which every number from 1 to \(N^2\) must appear just once, and every row, column, and diagonal must add up to the same total—for example,

6 7 2
1 5 9
8 3 4

Revise the program in the previous exercise so that it allows the user to input the dimensions of the array, up to \(4\; \times\; 4\).

Modify the AnalyzeFreq program so that it can display the relative frequencies of the 10 most frequent and 10 least frequent letters.

The merge sort algorithm takes two collections of data that have been sorted and merges them together. Write a program that takes two 25-element int arrays, sorts them, and then merges them, in order, into one 50-element array.

Challenge: Design and implement a BigInteger class that can add and subtract integers with up to 25 digits. Your class should also include methods for input and output of the numbers. If you’re really ambitious, include methods for multiplication and division.

Challenge: Design a data structure for this problem: As manager of Computer Warehouse, you want to track the dollar amount of purchases made by those clients that have regular accounts. The accounts are numbered from 0, 1, …, N. The problem is that you don’t know in advance how many purchases each account will have. Some may have one or two purchases. Others may have 50 purchases.

An anagram is a word made by rearranging the letters of another word. For example, act is an anagram of cat, and aegllry is an anagram of allergy. Write a Java program that accepts two words as input and determines if they are anagrams.

Challenge: An anagram dictionary is a dictionary that organizes words together with their anagrams. Write a program that lets the user enter up to 100 words (in a TextField, say). After each word is entered, the program should display (in a TextArea perhaps) the complete anagram dictionary for the words entered. Use the following sample format for the dictionary. Here the words entered by the user were: felt, left, cat, act, opt, pot, top.

act:  act cat
eflt:  felt left
opt:   opt pot top

Acme Trucking Company has hired you to write software to help dispatch its trucks. One important element of this software is knowing the distance between any two cities that it services. Design and implement a Distance class that stores the distances between cities in a two-dimensional array. This class will need some way to map a city name, Boise, into an integer that can be used as an array subscript. The class should also contain methods that would make it useful for looking up the distance between two cities. Another useful method would tell the user the closest city to a given city.

Rewrite the main() method for the WordGuess example so that it allows the user to input the number of players and whether each players is a computer or a human. Use a KeyboardReader.

Write a smarter version of the WordGuesser class that “knows” which letters of the English language are most frequent. HINT: Rather than using random guesses, store the player’s guesses in a string in order of decreasing frequency: "ETAONRISHLGCMFBDGPUKJVWQXYZ".

Write a CLUI version of the SlidingTilePuzzle. You will need to make modifications to the SlidingTilePuzzle class.