23 Javanotes 9.0, Section 7.2 — Array Processing
Section 7.2
Array Processing
Most examples of array processing that we
have looked at have actually been fairly straightforward: processing
the elements of the array in order from beginning to end, or random
access to an arbitrary element of the array. In this section
and later in the chapter, you’ll see some of the more interesting
things that you can do with arrays.
7.2.1 Some Processing Examples
To begin, here’s an example to remind you to be careful about
avoiding array indices outside the legal range. Suppose that
lines is an array of type String[],
and we want to know whether lines contains any
duplicate elements in consecutive locations. That is, we
want to know whether lines[i].equals(lines[i+1])
for any index i. Here is a failed attempt
to check that condition:
boolean dupp = false; // Assume there are no duplicates
for ( int i = 0; i < list.length; i++ ) {
if ( lines[i].equals(lines[i+1]) ) { // THERE IS AN ERROR HERE!
dupp = true; // we have found a duplicate!
break;
}
}
This for loop looks like many others that we have written,
so what’s the problem? The error occurs when i takes on
its final value in the loop, when i is equal to lines.length-1.
In that case, i+1 is equal to lines.length. But
the last element in the array has index lines.length-1,
so lines.length is not a legal index. This means that the
reference to lines[i+1] causes an ArrayIndexOutOfBoundsException.
This is easy to fix; we just need to stop the loop before i+1
goes out of range:
boolean dupp = false; // Assume there are no duplicates
for ( int i = 0; i < list.length - 1 ; i++ ) {
if ( lines[i].equals(lines[i+1]) ) {
dupp = true; // we have found a duplicate!
break;
}
}
This type of error can be even more insidious when working with partially full
arrays (see Subsection 3.8.4), where usually only part of the array is in
use, and a counter is used to keep track of how many spaces in the array are used.
With a partially full array, the problem
is not looking beyond the end of the array, but looking beyond the part of the array
that is in use. When your program tries to look beyond the end of an array, at
least the program will crash to let you know that there is a problem. With a
partially full array, the problem can go undetected.
For the next example, let’s continue with partially full arrays. We have seen how to add
an item to a partially full array, but suppose that we also want to be able to
remove items? Suppose that you write a game
program, and that players can join the game and leave the game as it
progresses. As a good object-oriented programmer, you probably have a class
named Player to represent the individual players in the game. A list
of all players who are currently in the game could be stored in an array,
playerList, of type Player[]. Since the number of players can
change, you will follow the partially full array pattern, and
you will need a variable, playerCt, to record the number
of players currently in the game. Assuming that there will never be more than
10 players in the game, you could declare the variables as:
Player[] playerList = new Player[10]; // Up to 10 players. int playerCt = 0; // At the start, there are no players.
After some players have joined the game, playerCt will be greater
than 0, and the player objects representing the players will be stored in the
array elements playerList[0], playerList[1], …,
playerList[playerCt-1]. Note that the array element
playerList[playerCt] is not in use: Besides being the
number of items in the array, playerCt is also the index
of the next open spot in the array. The procedure for
adding a new player, newPlayer, to the game is simple:
playerList[playerCt] = newPlayer; // Put new player in next
// available spot.
playerCt++; // And increment playerCt to count the new player.
But deleting a player from the game is a little harder, since you don’t want to
leave a “hole” in the array where the deleted player used to be.
Suppose you want to delete the player at index
k in playerList. The number of players goes down
by one, so one fewer space is used in the array.
If you are not worried about keeping the
players in any particular order, then one way to delete player number k is to move the player
from the last occupied position in the array
into position k and then
to decrement the value of playerCt:
playerList[k] = playerList[playerCt - 1]; playerCt--;
The player previously in position k has been replaced and
is no longer in the array, so we have deleted that player from the list. The
player previously in position playerCt – 1 is now in the array twice.
But it’s only in the occupied or valid part of the array once, since
playerCt has decreased by one. Remember that every element of the
array has to hold some value, but only the values in positions 0 through
playerCt – 1 will be looked at or processed in any way.
You can set playerList[playerCt] = null, which could
free up the deleted Player object for
garbage collection, but that is not necessary
to correctly delete the player from the list of (active) players.
(By the way, you should think about what happens if the player that is being deleted
is in the last position in the list. The code does still work in this case. What
exactly happens?)
Suppose that when deleting the player in position k, you’d like to
keep the remaining players in the same order. (Maybe because they take turns in
the order in which they are stored in the array.) To do this, all the players
in positions k+1 and following must move up one position in the array.
Player k+1 replaces player k, who is out of the game. Player
k+2 fills the spot left open when player k+1 is moved. And so
on. The code for this is
for (int i = k+1; i < playerCt; i++) {
playerList[i-1] = playerList[i];
}
playerCt--;
Here is an illustration of the two ways of deleting an item from a partially full
array. Here, player “C” is being deleted:
This leaves open the question of what happens when a partially full array
becomes full, but you still want to add more items to it? We can’t change
the size of the array—but we can make a new, bigger array and copy the data
from the old array into the new array. But what does it mean to copy an
array in the first place?
Suppose that A and B are array variables, with the same base type,
and that A already refers to an array. Suppose that we want B to
refer to a copy of A. The first thing to note is that
the assignment statement
B = A;
does not make a copy of A. Arrays are objects, and an array variable can only
hold a pointer to an array. The assignment statement copies the pointer from A
into B, and the result is that A and B now point
to the same array. For example, A[0] and B[0] are just
different names for exactly the same array element. To make B refer to
a copy of A, we need to make an entirely new array and copy all the items from
A into B. Let’s say that A and B
are of type double[]. Then to make a copy of A, we can say
double[] B;
B = new double[A.length]; // Make a new array with the same length as A.
for ( int i = 0; i < A.length; i++ ) {
B[i] = A[i];
}
To solve the problem of adding to a partially full array that has become full,
we just need to make a new array that is bigger than the existing array. The usual
choice is to make a new array twice as big as the old. We need to meet one
more requirement: At the end, the variable that referred to the old array
must now point to the new array. That variable is what gives us access to the
data, and in the end, the data is in the new array. Fortunately, a simple
assignment statement will make the variable point to the correct array.
Let’s suppose that we are using playerList and playerCt
to store the players in a game, as in the example above, and we want to add
newPlayer to the game. Here is how we can do that even if the
playerList array is full:
if ( playerCt == playerList.length ) {
// The number of players is already equal to the size of the array.
// The array is full. Make a new array that has more space.
Player[] temp; // A variable to point to the new array.
temp = new Player[ 2*playerList.length ]; // Twice as big as the old array.
for ( int i = 0; i < playerList.length; i++ ) {
temp[i] = playerList[i]; // Copy item from old array into new array.
}
playerList = temp; // playerList now points to the new, bigger array.
}
// At this point, we know that there is room in the array for newPlayer.
playerList[playerCt] = newPlayer;
playerCt++;
After the new array has been created, there is no longer any variable that
points to the old array, so it will be garbage collected.
7.2.2 Some Standard Array Methods
Copying an array seems like such a common method that you might expect
Java to have a built-in method already defined to do it. In fact,
Java comes with several standard array-processing methods. The
methods are defined as static methods in a class
named Arrays, which is in the package java.util.
For example, for any array, list,
Arrays.copyOf( list, lengthOfCopy )
is a function that returns a new array whose length is given by lengthOfCopy,
containing items copied from list. If lengthOfCopy is greater
than list.length, then extra spaces in the new array will have their default
value (zero for numeric arrays, null for object arrays, and so on).
If lengthOfCopy is less than or equal to list.length, then
only as many items are copied from list as will fit in the new array.
So if A is any array, then
B = Arrays.copyOf( A, A.length );
sets B to refer to an exact copy of A, and
playerList = Arrays.copyOf( playerList, 2*playerList.length );
could be used to double the amount of space available in a partially full array with
just one line of code.
We can also use Arrays.copyOf to decrease the size of a partially full array.
We might want to do that to avoid having a lot of excess, unused spaces. To implement
this idea, the code for deleting player number k from the list of players
might become
playerList[k] = playerList[playerCt-1];
playerCt--;
if ( playerCt < playerList.length/4 ) {
// More than 3/4 of the spaces are empty. Cut the array size in half.
playerList = Arrays.copyOf( playerList, playerList.length/2 );
}
I should mention that class Arrays actually contains a bunch
of copyOf methods, one for each of the primitive types and one for
objects. I should also note that when an array of objects is copied, it is only
pointers to objects that are copied into the new array. The contents of the
objects are not copied. This is the usual rule for assignment of pointers.
If what you want is a simple copy of an array, with the same
size as the original, there is an even easier way to do it. Every array has
an instance method named clone() that makes a copy of the array.
To get a copy of an int array, A, for example,
you can simply say
int[] B = A.clone();
The Arrays class contains other useful methods. I’ll mention
a few of them. As with Arrays.copyOf, there are actually multiple versions
of all of these methods, for different array types.
-
Arrays.fill( array, value ) — Fill an entire array with
a specified value. The type of value must be compatible with the base type of
the array. For example, assuming that numlist is an array
of type double[], then Arrays.fill(numlist,17) will set
every element of numlist to have the value 17. -
Arrays.fill( array, fromIndex, toIndex, value ) — Fills part
of the array with value, starting at index number fromIndex
and ending with index number toIndex-1. Note that toIndex itself
is not included. -
Arrays.toString( array ) — A function that returns a String
containing all the values from array, separated by commas and enclosed between
square brackets. The values in the array are converted into strings in the same way
they would be if they were printed out. -
Arrays.sort( array ) — Sorts the entire array. To sort an
array means to rearrange the values in the array so that they are in increasing order.
This method works for arrays of String and arrays of primitive type values
(except for boolean, which would be kind of silly). But it does not work
for all arrays, since it must be meaningful to compare any two values in the array, to
see which is “smaller.” We will discuss array-sorting algorithms in Section 7.5. -
Arrays.sort( array, fromIndex, toIndex ) — Sorts just
the elements from array[fromIndex] up to array[toIndex-1] -
Arrays.binarySearch( array, value ) — Searches for value
in the array. The array must already be sorted into increasing order.
This is a function that returns an int. If the value is found in the array,
the return value is the index of an element that contains that value. If the value does not
occur in the array, the return value is -1. We will discuss the binary search algorithm
in Section 7.5.
7.2.3 RandomStrings Revisited
One of the examples in Subsection 6.2.4 was a GUI program,
RandomStrings.java,
that shows multiple copies of a message in random positions, colors, and fonts.
When the user clicks a button, the positions, colors, and fonts are
changed to new random values. But suppose that we want the message strings
to move. That is, we want to run an animation where the strings drift
around in the window. In that case, we need to store the properties of
each string, since they will be needed to redraw the strings in each frame
of the animation. A new version of the program that does that is RandomStringsWithArray.java.
There are 25 strings. We need to store the (x,y) coordinates where each string is drawn,
the color of each string, and the font that is used for each string. To make the
strings move, I also store a velocity for each string, represented as two numbers
dx and dy. In each frame, the dx for each string,
multiplied by the elapsed time since the previous frame,
is added to the x coordinate of the string, similarly
for dy. Now, the data for the string could be
stored in six arrays
double[] x = new double[25]; double[] y = new double[25]; double[] dx = new double[25]; double[] dy = new double[25]; Color[] color = new Color[25]; Font[] font = new Font[25];
These arrays would be filled with random values. In the
method that draws the strings, the i-th string would be
drawn at the point (x[i],y[i]). Its color would be given by
color[i]. And it would be drawn in the font font[i].
(The dx and dy would not be used for the drawing;
they are used when updating the data for the next frame.) This
would be accomplished by code such as:
g.setFill(Color.WHITE); // (Fill with white background.)
g.fillRect(0,0,canvas.getWidth(),canvas.getHeight());
for (int i = 0; i < 25; i++) {
g.setFill( color[i] );
g.setFont( font[i] );
g.fillText( MESSAGE, x[i], y[i] );
g.setStroke(Color.BLACK);
g.strokeText( MESSAGE, x[i], y[i] );
}
This approach is said to use parallel arrays.
The data for a given copy of the message is spread out across several arrays.
If you think of the arrays as laid out in parallel columns—array x
in the first column, array y in the second, array color in
the third, and array font in the fourth—then the data for the
i-th string can be found along the i-th row. There is
nothing wrong with using parallel arrays in this simple example, but it does go
against the object-oriented philosophy of keeping related data in one object.
If we follow this rule, then we don’t have to imagine the relationship
among the data, because all the data for one copy of the message is physically
in one place. So, when I wrote the program, I made a simple class to represent
all the data that is needed for one copy of the message:
private static class StringData { // Info needed to draw one string.
double x,y; // location of the string;
double dx,dy; // velocity of the string;
Color color; // color of the string;
Font font; // the font that is used to draw the string
}
To store the data for multiple copies of the message, I use an array of
type StringData[]. The array is declared as an instance variable, with
the name stringData:
StringData[] stringData;
Of course, the value of stringData is null until an actual array
is created and assigned to it. The array has to be created and filled with data.
Furthermore, each element of the array is an object of type StringData
which has to be created before it can be used. The following subroutine
creates the array and fills it with random data:
private void createStringData() {
stringData = new StringData[25];
for (int i = 0; i < 25; i++) {
stringData[i] = new StringData();
stringData[i].x = canvas.getWidth() * Math.random();
stringData[i].y = canvas.getHeight() * Math.random();
stringData[i].dx = 1 + 3*Math.random();
if (Math.random() < 0.5) // 50% chance that dx is negative
stringData[i].dx = -stringData[i].dx;
stringData[i].dy = 1 + 3*Math.random();
if (Math.random() < 0.5) // 50% chance that dy is negative
stringData[i].dy = -stringData[i].dy;
stringData[i].color = Color.hsb( 360*Math.random(), 1.0, 1.0 );
stringData[i].font = fonts[ (int)(5*Math.random()) ];
}
}
This method is called in the start() method. It is also called to
make new random data when the user clicks a button. The strings can
now be drawn using a for loop such as:
for (int i = 0; i < 25; i++) {
g.setFill( stringData[i].color );
g.setFont( stringData[i].font );
g.fillText( MESSAGE, stringData[i].x, stringData[i].y );
g.setStroke(Color.BLACK);
g.strokeText( MESSAGE, stringData[i].x, stringData[i].y );
}
But in fact, in my program, I used an equivalent for-each loop, which might be easier
to understand:
for ( StringData data : stringData ) {
g.setFill( data.color );
g.setFont( data.font);
g.fillText( MESSAGE, data.x, data.y );
g.setStroke( Color.BLACK );
g.strokeText( MESSAGE, data.x, data.y );
}
In this loop, the loop control variable, data, holds a copy of one
of the values from the array. That value is a reference to an object of type
StringData, which has instance variables named
color, font, x, and y.
Once again, the use of a for-each loop has eliminated the need to work with
array indices.
As for how the animation is done, you can check out the full
source code. Animation was
discussed in Subsection 6.3.5.
RandomStringsWithArray uses one other array of objects. The font for a given copy of the
message is chosen at random from a set of five possible fonts. In the original
version, there were five variables of type Font to
represent the fonts. The variables were named font1, font2,
font3, font4, and font5. To select one of these
fonts at random, a switch statement could be used:
Font randomFont; // One of the 5 fonts, chosen at random.
int rand; // A random integer in the range 0 to 4.
fontNum = (int)(Math.random() * 5);
switch (fontNum) {
case 0 -> randomFont = font1;
case 1 -> randomFont = font2;
case 2 -> randomFont = font3;
case 3 -> randomFont = font4;
case 4 -> randomFont = font5;
}
In the new version of the program, the five fonts are stored in an array,
which is named fonts. This array is declared as a static final member
variable of type Font[]:
private static final fonts= new Font[] {
Font.font("Times New Roman", FontWeight.BOLD, 20),
Font.font("Arial", FontWeight.BOLD, FontPosture .ITALIC, 28),
Font.font("Verdana", 32),
Font.font(40),
Font.font("Times New Roman", FontWeight.BOLD, FontPosture .ITALIC, 60)
};
This makes it much easier to select one of the fonts at random. It can be
done with the statements
Font randomFont; // One of the 5 fonts, chosen at random. int fontIndex; // A random number in the range 0 to 4. fontIndex = (int)(Math.random() * 5); randomFont = fonts[ fontIndex ];
In fact, the preceding four lines can be replaced by the single line
Font randomFont = fonts[ (int)(Math.random() * 5) ];
The switch statement has been replaced by a single line of code.
This is a very typical application of arrays. Note that this example uses
the random access property: We can pick an array index at random
and go directly to the array element at that index.
Here is another example of the
same sort of thing. Months are often stored as numbers 1, 2, 3, …, 12.
Sometimes, however, these numbers have to be translated into the names January,
February, …, December. The translation can be done very easily with an array. The array
can be declared and initialized as
static String[] monthName = { "January", "February", "March",
"April", "May", "June",
"July", "August", "September",
"October", "November", "December" };
If mnth is a variable that holds one of the integers 1 through 12,
then monthName[mnth-1] is the name of the corresponding month. We need
the “-1” because months are numbered starting from 1, while array
elements are numbered starting from 0. Simple array indexing does the
translation for us!
7.2.4 Dynamic Arrays
Earlier, we discussed how a partially full array can be used to store a list of
players in a game, allowing the list to grow and shrink over the course of the game.
The list is “dynamic” in the sense that its size changes while the program is running.
Dynamic lists are very common, and we might think about trying to write a class to
represent the concept. By writing a class, we can avoid having to repeat the same
code every time we want to use a similar data structure.
We want something that is like an array, except that its
size can change. Think about operations that we might want to perform
on a dynamic array. Some essential and useful operations would include
- add an item to the end of the array
- remove the item at a specified position in the array
- get the value of one of the elements in the array
- set the value of one of the elements in the array
- get the number of items currently in the array
When we design our class, these operations will become instance methods in that
class. The items in the dynamic array will actually be stored in a normal array,
using the partially full array pattern. Using what we know, the class is not
difficult to write. We do have to decide what to do when an attempt is made to access an
array element that doesn’t exist. It seems natural to throw an
index-out-of-bounds exception in that case.
Let’s suppose that the items in the array will be of type
int.
import java.util.Arrays;
/**
* Represents a list of int values that can grow and shrink.
*/
public class DynamicArrayOfInt {
private int[] items = new int[8]; // partially full array holding the ints
private int itemCt;
/**
* Return the item at a given index in the array.
* Throws ArrayIndexOutOfBoundsException if the index is not valid.
*/
public int get( int index ) {
if ( index < 0 || index >= itemCt )
throw new ArrayIndexOutOfBoundsException("Illegal index, " + index);
return items[index];
}
/**
* Set the value of the array element at a given index.
* Throws ArrayIndexOutOfBoundsException if the index is not valid.
*/
public void set( int index, int item ) {
if ( index < 0 || index >= itemCt )
throw new ArrayIndexOutOfBoundsException("Illegal index, " + index);
items[index] = item;
}
/**
* Returns the number of items currently in the array.
*/
public int size() {
return itemCt;
}
/**
* Adds a new item to the end of the array. The size increases by one.
*/
public void add(int item) {
if (itemCt == items.length)
items = Arrays.copyOf( items, 2*items.length );
items[itemCt] = item;
itemCt++;
}
/**
* Removes the item at a given index in the array. The size of the array
* decreases by one. Items following the removed item are moved up one
* space in the array.
* Throws ArrayIndexOutOfBoundsException if the index is not valid.
*/
public void remove(int index) {
if ( index < 0 || index >= itemCt )
throw new ArrayIndexOutOfBoundsException("Illegal index, " + index);
for (int j = index+1; j < itemCt; j++)
items[j-1] = items[j];
itemCt--;
}
} // end class DynamicArrayOfInt
Everything here should be clear, except possibly why the original size of the
items array is 8. In fact, the number 8 is arbitrary and has no
effect on the functionality of the class. Any positive integer would work, but it
doesn’t make sense for the array to start off very big. The array will grow
as needed if the number of items turns out to be large.
The example ReverseInputNumbers.java used a partially full array
of int to print a list of input numbers in the reverse of the order in
which they are input. In that program, an ordinary array of length 100 was used to
hold the numbers. In any given run of the program, the size of the array could
be much too large, or it could be too small, resulting in an exception. The program
can now be written using a DynamicArrayOfInt, which will adapt itself to any reasonable number
of inputs. For the program, see ReverseWithDynamicArray.java.
It’s a silly program, but the principle holds in any application where the amount of
data cannot be predicted in advance: The size of a dynamic data structure can
adapt itself to any amount of data, limited only by the amount of memory available
to the program.
This is a nice example, but there is a real problem with it. Suppose that
we want to have a dynamic array of String. We can’t use
a DynamicArrayOfInt object to hold strings, so it looks
like we need to write a whole new class, DynamicArrayOfString.
If we want a dynamic array to store players in a game, we would need a class
DynamicArrayOfPlayer. And so on. It looks like we have
to write a dynamic array class for every possible type of data! That can’t be
right! In fact, Java has a solution to this problem, a standard class that
implements dynamic arrays and can work with any type of data. The class
is called ArrayList, and we’ll see how it works
in the next section.