java

Website Notes: Ch.5 - Arrays in Java.

Introduction

With the basic built-in Java data types we have seen in the previous

chapters, each identifier corresponds to a single variable. But when you

want to handle sets of values of the same type – the first 1000 primes

for example – you really don't want to have to name them individually.

What you need is an array.

1. An array is a named set of variables of the same type. Each variable in

the array is called an array element. To reference a particular element in

an array you use the array name combined with an integer value of type int,

called an index. The first element has an index of zero.

2. You are not obliged to create the array itself when you declare the array

variable. The array variable is distinct from the array itself. You could

declare the integer array variable primes with the statement:

int[] primes;              // Declare an integer array variable

3. The variable primes is now a place holder for an integer array that you

have yet to define. No memory is allocated to hold the array itself at this

point. We will see in a moment that to create the array itself we must

specify its type and how many elements it is to contain.

4. The square brackets following the type in the previous statement indicates

that the variable is for referencing an array of int values, and not for storing a

single value of type int.

5. Once you have declared an array variable, you can define an array that it

will reference:

primes = new int[10];   // Define an array of 10 integers

This statement creates an array that will store 10 values of type int, and

records a reference to the array in the variable primes.

6. The reference is simply where the array is in memory. You could also

declare the array variable and define the array of type int to hold 10 prime

numbers with a single statement.

int []primes = new int[10]; // An array of 10 integers

7. The first part of the definition specifies the type of the array. The type

name, int in this case, is followed by an empty pair of square brackets to

indicate you are declaring an array rather than a single variable of type int.

The part following the equal sign defines the array. The keyword new

indicates that you are allocating new memory for the array, and int[10]

specifies you want capacity for 10 variables of type int in the array.

8. When an array is created like this, all the array elements are initialized

to a default value automatically. The initial value is zero in the case of an

array of numerical values, false for boolean arrays, '\u0000' for arrays

storing type char, and null for an array of a class type.

9. Before we go any further, let's clarify a bit of terminology we have been

using in this discussion. A declaration for an array just defines the

variable name. So the statement:

double[] myArray;

is a declaration for the array name, myArray. No memory has been allocated

to store the array itself and the number of elements has not been defined.

10. The statement:

double[] myArray = new double[100];

is a declaration of the array variable myArray and a definition of the array,

since the array size is specified. The variable myArray will refer to an array

of 100 values of type double and each element will have the value 0.0

assigned by default.

11. You refer to an element of an array by using the array name followed by

the element's index value enclosed between square brackets. You can

specify an index value by any expression that produces zero or a positive

result of type int.

12. The first element of the primes array that we declared previously is

referred to as primes[0], and you reference the fifth element in the array as

primes[4]. The maximum index value for an array is one less than the

number of elements in the array.

13. Java checks that the index values you use are valid. If you use an index

value that is less than 0, or greater than the index value for the last

element in the array, an exception will be thrown – throwing an exception is

just the way errors at execution time are signaled and there are different

types of exceptions for signaling various kinds of errors.

14. The exception in this case is called an IndexOutOfBoundsException.

When such an exception is thrown, your program will normally be terminated.

15. The array variable is separate from the array itself. Rather like the way

an ordinary variable can refer to different values at different times, you can

use an array variable to reference different arrays at different points in your

program.

16. Suppose you have declared and defined the variable primes as before:

int[] primes = new int[10];   // Allocate an array of 10 integer elements

This produces an array of 10 elements of type int. Perhaps a bit later in your

program you want the array variable primes to refer to a larger array, with

50 elements say. You would simply write:

primes = new int[50];         // Allocate an array of 50 integer elements

17. Now the variable primes refers to a new array of values of type int that

is entirely separate from the original. When this statement is executed, the

previous array of 10 elements is discarded, along with all the data values

you may have stored in it. The variable primes can now only be used to

reference elements of the new array.

18. The array variable primes now points to a new integer array of 50

elements, with index values running from 0 to 49. Although you can change

the array that an array variable references, you can't alter the type of value

that an element stores.

19. All the arrays referenced by a given variable must correspond to the

original type specified when the array variable was declared. The variable

primes, for example, can only reference arrays of type int.

20. We have used an int array in the above examples, but everything

applies equally well to long or double or to any of the basic types.

Check-out this index finder:

public class IndexFinder {

public static void main(String[] args) {
int index = -100;
int a[] = {1, 3, 5, 7, 4, 5, 6, 9, 2, 0};

System.out.println(" Element Index");

for (int k=0; k < a.length; k++)
{ for (int j=0; j < a.length; j++)
{
if (a[j] == k) index = j;
}

System.out.println("\t"+ k +"\t\t"+ index);
} } }

Initializing Arrays

1. You can initialize an array with your own values when you declare it,

and at the same time determine how many elements it will have.

2. Following the declaration of the array variable, simply add an equal sign

followed by the list of element values enclosed between braces.

For example, if you write:

int[] primes = {2, 3, 5, 7, 11, 13, 17};    // An array of 7 elements

the array is created with sufficient elements to store all of the initializing

values that appear between the braces, seven in this case.

3. The array size is determined by the number of initial values so no other

information is necessary to define the array. If you specify initializing

values for an array, you must include values for all the elements.

4. If you only want to set some of the array elements to values explicitly,

you should use an assignment statement for each element. For example:

int[] primes = new int[100]; 
primes[0] = 2;
primes[1] = 3;

5. The first statement declares and defines an integer array of 100

elements, all of which will be initialized to zero. The two assignment

statements then set values for the first two array elements.

6. You can also initialize an array with an existing array. For example, you

could declare the following array variables:

long[] even = {2L, 4L, 6L, 8L, 10L};
long[] value = even;

where the array even is used to initialize the array value in its declaration.

This has the effect shown below.

7. You have created two array variables, but you only have one array. Both

arrays refer to the same set of elements and you can access the elements

of the array through either variable name – for example, even[2] refers to

the same variable as value[2].

8. One use for this is when you want to switch the arrays referenced by two

variables. If you were sorting an array by repeatedly transferring elements

from one array to another, by flipping the array you were copying from with

the array you were copying to, you could use the same code.

9. For example, if we declared array variables as:

double[] inputArray = new double[100];        // Array to be sorted
double[] outputArray = new double[100];       // Reordered array
double[] temp;                                // Temporary array reference

when we want to switch the array referenced by outputArray to be the new

input array, we could write:

temp = inputArray;         // Save reference to inputArray in temp
inputArray = outputArray;  // Set inputArray to refer to outputArray
outputArray = temp;        // Set outputArray to refer to what was inputArray

None of the array elements are moved here. Just the addresses of where

the arrays are located in memory are swapped, so this is a very fast process.

10. Of course, if you want to replicate an array, you have to define a new

array of the same size and type, and then copy each element of the array

individually to your new array.

Using Arrays

1. You can use array elements in expressions in exactly the same way as

you might use a single variable of the same data type. For example, if you

declare an array samples, you can fill it with random values between 0.0

and 100.0 with the following code:

double[] samples = new double[50];    // An array of 50 double values
for(int i = 0; i < 50; i++)
samples[i] = 100.0*Math.random();     // Generate random values

2. To show that array elements can be used in exactly the same way as

ordinary variables, you could write:

double result = (samples[10]*samples[0] – 
                                      Math.sqrt(samples[49]))/samples[29];

This is a totally arbitrary calculation of course.

3. More sensibly, to compute the average of the values stored in the

samples array, you could write:

double average = 0.0;          // Variable to hold the average

for(int i = 0; i < 50; i++)
  average += samples[i];       // Sum all the elements

average /= 50;                 // Divide by the total number of elements

4. Within the loop we accumulate the sum of all the elements of the array

samples in the variable average. We then divide this sum by the number

of elements.

5. Notice how we use the length of the array, 50, all over the place. It

appears in the for loop, and in floating point form as a divisor to calculate

the average. When you use arrays you will often find that references to

the length of the array are strewn all through your code.

6. If you later want to change the program, to handle 100 elements for

instance, you need to be able to decide whether any particular value of

50 in the code is actually the number of elements, and therefore should

be changed to 100, or if it is a value that just happens to be the same

and should be left alone.

Array Length

1. You can refer to the length of the array using length, a data member

of the array object. For our array samples, we can refer to its length as

samples.length. We could use this to write the calculation of the

average as:

double average = 0.0;          // Variable to hold the average
for(int i = 0; i < samples.length; i++)
average += samples[i];            // Sum all the elements
average /= samples.length;     // Divide by the total number of elements

2. Now the code is independent of the number of array elements. If you

change the number of elements in the array, the code will automatically

deal with that.

3. Let's try out an array in an improved program to calculate prime

numbers from the code we used during the first nine weeks. This program

computes as many prime numbers as the capacity of the array allows.

public class MorePrimes {
  public static void main(String[] args) {
    long[] primes = new long[20];    // Array to store primes
    primes[0] = 2;                   // Seed the first prime
    primes[1] = 3;                   // and the second
    int count = 2;                   // Count of primes found – up to now,
                                     // which is also the array index
    long number = 5;                 // Next integer to be tested

    outer:
    for( ; count < primes.length; number += 2) {
      // The maximum divisor we need to try is square root of number
      long limit = (long)Math.ceil(Math.sqrt((double)number));

      // Divide by all the primes we have up to limit
      for(int i = 1; i < count && primes[i] <= limit; i++) {
        if(number%primes[i] == 0) {            // Is it an exact divisor?
          continue outer;                       // Yes, try the next number
        }
      }
      primes[count++] = number;               // We got one!
    }

    for(int i=0; i < primes.length; i++)
      System.out.println(primes[i]);          // Output all the primes
  }
}

Arrays of Arrays (Two Dimensional Arrays).

1. We have only worked with one-dimensional arrays up to now, that is,

arrays that use a single index. Why would you ever need the complications

of using more indexes to access the elements of an array?

2. Suppose that you have a project to do involving the weather, and you

are intent on recording the temperature each day at 10 separate locations

throughout the year 2007.

3. Once you have sorted out the logistics of actually collecting this

information, you can use an array of 10 elements corresponding to the

number of locations, where each of these elements is an array of 365

elements to store the temperature values. You would declare this array

with the statement:

float[][] temperature = new float[10][365];

4. This is called a two-dimensional array, since it has two dimensions –

one with index values running from 0 to 9, and the other with index

values from 0 to 364. The first index will relate to a geographical location,

and the second index corresponds to the day of the year.

5. That's much handier than a one-dimensional array with 3650 elements.

There are 10 arrays, each having 365 elements. In referring to an element,

the first square brackets enclose the index for a particular array, and the

second pair of square brackets enclose the index value for an element

within that array.

6. So to refer to the temperature for day 100 for the sixth location, you

would use temperature[5][99]. Since each float variable occupies 4 bytes,

the total space required to store the elements in this two-dimensional

array is 10x365x4 bytes, which is a total of 14,600 bytes.

7. For a fixed second index value in a two-dimensional array, varying the

first index direction is often referred to as accessing a column of the

array. Similarly, fixing the first index value and varying the second, you

access a row of the array.

8. You could just as well have used two statements to create the last

array, one to declare the array variable, and the other to define the

array:

float [][] temperature;              // Declare the array variable
temperature = new float[10][365];    // Create the array

9. The first statement declares the array variable temperature for

two-dimensional arrays of type float. The second statement creates the

array with ten elements, each of which is an array of 365 elements.

10. Let's exercise this two-dimensional array in a program to calculate

the average annual temperature for each location.

11. In the absence of real samples, we will generate the temperatures

as random values between -10^o and 35^o. This assumes we are recording

temperatures in degrees Celsius.

12. If you prefer Fahrenheit you could use 14^o to 95^o to cover the same

range.

public class WeatherFan {
   public static void main(String[] args) {
      float[][] temperature = new float[10][365]; // Temperature array

      // Generate random temperatures
      for(int i = 0; i < temperature.length; i++) {
         for(int j = 0; j < temperature[i].length; j++)
            temperature[i][j] = (float)(45.0*Math.random() – 10.0);
        }
      }

      // Calculate the average per location
      for(int i = 0; i < temperature.length; i++) {
         float average = 0.0f;     // Place to store the average

         for(int j = 0; j < temperature[0].length; j++)
            average += temperature[i][j];

         // Output the average temperature for the current location
         System.out.println("Average temperature at location "
                + (i+1) + " = " + average/(float)temperature[i].length);
      }
   }
}

Additional Notes on Two-Dimensional Arrays.

1. Any data-type can be used a base for an array. You can have an array of

ints, an array of Strings, an array of Objects, and so on. In particular, since an

array type is a first-class Java type, you can have an array of arrays.

2. For example, an array of ints has type int[]. This means that there is

automatically another type, int[][], which represents an "array of arrays of ints".

3. Such an array is said to be a two-dimensional array. Of course once you

have the type int[][], and also the type int[][][], which, of course, represents a

three-dimensional array -- and so on.

4. There is no limit on the number of dimensions that an array type can have.

However, arrays of dimension three or higher are fairly uncommon, so we

concentrate here mainly on two-dimensional arrays.

5. The type BaseType[][] is usually read "two-dimensional array of BaseType"

or "BaseType array array".

6. The declaration statement "int[][] A;" declares a variable named A of type

int[][]. This variable can hold a reference to an object of type int[][].

7. The assignment statement "A = new int[3][4];" creates a new two-dimensional

array object and sets A to point to the newly created object.

8. As usual, the declaration and assignment could be combined in a single

declaration statement "int[][] A = new int[3][4];". The newly created object is an

array of arrays-of-ints.

9. The notation int[3][4] indicates that there are 3 arrays-of-ints in the array A,

and that there are 4 ints in each array-of-ints. However, trying to think in such

terms can get a bit confusing -- as you might have already noticed.

10. So it is customary to think of a two-dimensional array of items as a

rectangular grid or matrix of items. The notation "new int[3][4]" can then be

taken to describe a grid of ints with 3 rows and 4 columns.

11. For example, A[1][3] refers to item number 3 in row number 1. Keep in

mind, of course, that both rows and columns are numbered starting from

zero. So, in the above example, A[1][3] is 5.

12. More generally, A[i][j] refers to the grid position in row number i and

column number j. The 12 items in A are named as follows:

      A[0][0]    A[0][1]     A[0][2]     A[0][3]
      A[1][0]    A[1][1]     A[1][2]     A[1][3]
      A[2][0]    A[2][1]     A[2][2]     A[2][3]

13. A[i][j] is actually a variable of type int. You can assign integer values to

it or use it in any other context where an integer variable is allowed.

14. It might be worth noting that A.length gives the number of rows of A. To

get the number of columns in A, you have to ask how many ints there are in

a row; this number would be given by A[0].length, or equivalently by A[1].length

or A[2].length.

15. There is actually no rule that says that all the rows of an array must have

the same length, and some advanced applications of arrays use varying-sized

rows. But if you use the new operator to create an array in the manner described

above, you'll always get an array with equal-sized rows.)

16. It's possible to fill a multi-dimensional array with specified items at the

time it is declared. Recall that when an ordinary one-dimensional array variable

is declared, it can be assigned an "array initializer," which is just a list of values

enclosed between braces, { and }.

17. Array initializers can also be used when a multi-dimensional array is declared.

An initializer for a two-dimensional array consists of a list of one-dimensional

array initializers, one for each row in the two-dimensional array.

18. For example, the array A shown in the picture above could be created with:

        int[][]  A  =  {  {  1,  0, 12, -1 },
                          {  7, -3,  2,  5 },
                          { -5, -2,  2,  9 }
                       };

19. If no initializer is provided for an array, then when the array is created it is

automatically filled with the appropriate value: zero for numbers, false for

boolean, and null for objects.

20. Just as in the case of one-dimensional arrays, two-dimensional arrays are

often processed using for statements. To process all the items in a two-

dimensional array, you have to use one for statement nested inside another.

21. If the array A is declared as

          int[][]  A  =  new int[3][4];

then you could store a zero into each location in A with:

          for (int row = 0;  row < 3;  row++) {
             for (int column = 0;  column < 4;  column++) {
                A[row][column] = 0;
             }
          }

22. The first time the outer for loop executes (with row = 0), the inner for loop

fills in the four values in the first row of A, namely A[0][0] = 0, A[0][1] = 0,

A[0][2] = 0, and A[0][3] = 0. The next execution of the outer for loop fills in the

second row of A. And the third and final execution of the outer loop fills in the

final row of A.

23. Similarly, you could add up all the items in A with:

          int sum = 0;
          for (int i = 0; i < 3; i++)
             for (int j = 0; j < 4; i++)
                sum = sum + A[i][j];

24. If we encounter a three-dimensional array, we would, of course, use triply-

nested for loops.

The Back Burner	Back-Burner Assignments (Click on the back burner of the stove for descriptions.)
	1. Computerized Player Evaluation - due Nov. 16.
	2. The Rhine Test - due Nov. 18.
	3. The 23 Matches - due Nov. 22.
	4. Your Own Game - due Nov. 30.
	5. Your Revised AI Program - due Dec. 9.