Methods that alter/construct arrays

Copying arrays

Remember that in Java, array assignment leads to aliasing. So if we declare
int[] a,b;
and later, after having set variable a to refer to some array object, we execute the assignment
b = a;
then b and a will refer to the same array, not two separate copies. If we were, for example, to execute
a[3]=100;
next, then b[3] will also be 100, because a[3] and b[3] are the same variable, not just two variables holding the same value. If the array is of length 10 and the values in the array are all 0, then the situation can be represented diagrammatically as:

Note that Java (unlike the language C, for example) has no concept of pointers referring to a particular part of an array, so the exact position of the arrow heads here has no meaning, they could be anywhere on the outside of the box representing the whole array, as variables can only be set to refer to the whole array. The situation after executing a[3]=100 is represented by:

If we actually want to copy the array referred to by a so that b refers to the copy, we must execute some code to do it. A simple code fragment that does it consists of two parts. First we set b to refer to a new array of the same size as the array referred to be a:

b = new int[a.length];
Then we copy each item individually from its location in a to the equivalent location in array b:
for(int i=0; i<a.length; i++)
   b[i]=a[i];
You can see this code works for arrays of any length, since it always uses a.length which means "whatever length a is" rather than a specific integer value. The situation after executing this could be represented diagrammatically (again assuming a refers to an array of length 10 all of whose components have the value 0 as:

and then the situation after executing a[3]=100 is:

We could put the code for copying an array into a method:

public static int[] copy(int[] a)
{
 int[] b = new int[a.length];
 for(int i=0; i<a.length; i++)
    b[i]=a[i];
 return b;
}
then whenever we have an array of integers referenced by any variable v and we want a copy to be referred to by variable u, we can execute u=copy(v). This is useful if we want to perform some operation which changes an array, but we want to keep a copy of how it was before it was changed.

The return type of this method is int[] because it is returning a reference to an array of integers. As we saw when we looked at scope of objects, although the array is created within the method and initially referred to by variable b which has scope only within the method, when the method is finished it remains in existence referred to by the variable that was set to refer to the result of the method call. Again we have the issue that as this method only deals with arrays of integers it looks like if we were dealing with arrays of a number of different base types we would have to write a similar copy method for every different base type.

Changing arrays

Now let's consider an operation which changes the content of an array. A typical example might be "given an array of integers and two integers m and n, change all occurrences of m to n in the array". So, for example, if the array were:

and the m was 6 and n was 7, the result would be:

Note that changing all occurrences of 6 to 7 does not imply that existing occurrences of 7 should be changed.

Here is some code that will make the change as asked for:

for(int i=0; i<a.length; i++)
   if(a[i]==m)
      a[i]=n;
This code relies on the array being referred to by a variable called a and the two integer values being stored in variables actually called m and n. Putting this code into a static method and making these variables its parameters:
public static void change(int[] a,int m,int n)
{
 for(int i=0; i<a.length; i++)
   if(a[i]==m)
      a[i]=n;
}
generalises this code. Now, for any reference to an array of integers a and integer values m and n, a call change(a,m,n) will change the contents of a so that all occurrences of m are replaced by n. So the call change(b,p,q) will change all occurrences of what is in variable p to what is in variable q in the array referred to by variable b, so long as b is of type int[] and p and q are of type int. The arguments to the method need not be variables, the second or third for example could be an integer constant or or an arithmetic expression which evaluates to an integer or a call to a method which returns an integer.

This is an example of a method which has its effect by changing the internal state of an object which is passed to it as an argument. Its return type is void meaning that it returns no value, and unlike a method which does return a value it does not need to have any return statement in it. A call to the method will always take the form of a statement on its own.

Now suppose we have variables b and c of type int[]. Suppose c=b had been executed, and since then no b=..., where ... could be anything, has been executed. This means that b and c are two aliases to the same array object. When the call change(b,p,q) is executed, it will cause the array referred to by c to be changed because it is the same array as that referred to by b. Within the method execution, the same array is referred to by a, so this is what it looks like in terms of environments, assuming the variables have been set to the values given as an illustration previously:

It can be seen that changing the array referred to as a in the method will change the array referred to as b and c in the environment outside the method. Note that integer values are actually stored inside variable, and are copied into the corresponding variables in the new environment, so m and n hold 6 and 7 copied from p and q.

If we did not want the array referred to through c to be changed, then we could have replaced the statement c=b by c=copy(b) using the method copy as given above. This would result in the situation at the start of the method call being as shown by the diagram:

However, suppose we could not be sure whether b was aliased by another variable. We could make our method change so that instead of actually changing the array passed to it as an argument, it constructs a new array which reflects the required changes. This would make the code for change:

public static int[] change(int[] a,int m,int n)
{
 int[] a1 = new int[a.length];
 for(int i=0; i<a.length; i++)
   if(a[i]==m)
      a1[i]=n;
   else
      a1[i]=a[i];
 return a1;
}
This creates an entirely new array, referred to internally to the method through the variable a1 of the same length as the array referred to by the parameter a. The array a1 is then filled in, for each indexed component with a copy of the component with the same index from a unless that component is the integer value to be changed in which case it is filled in with the integer value it is to be changed to.

If b and c start off as aliases, and we execute the call

b=change(b,p,q);
where change is defined as just above, the situation when the method has reached its end is:

Then the execution of the return statement causes b to stop referring to what it did refer to and start referring to what a1 refers to inside the method call, so:

The call b=change(b,p,q) doesn't change any object, rather it creates a new object and causes b to refer to that object, so it has the effect of changing b without changing anything which was aliased to b.

There is, however, no requirement that we assign the result of calling change(b,p,q) to b. If we made the call

d=change(b,p,q);
where d is another variable of type int[], then b would continue to refer to what it referred to before the call, and c would continue to refer to it as well, and d would refer to the new array which represents changing all occurrences of the value in p to the value in q in the array referred to by b. This would make the situation at the end of the method call:

The two alternative forms of the method change are termed destructive and constructive. A destructive method is one that is meant to change an object and does so by changing the actual object, so it destroys the original form of the object. A constructive method is one that is meant to represent changing an object but it actually produces a new object representing the change. Destructive methods work by changing an object passed as an argument, constructive methods work by returning a reference to a new object.

You need to be aware of these two approaches, and be clear when you are writing code or specifying code for someone else to write whether you want constructive or destructive methods. Constructive methods are neater because you know when you call them you will never have any unexpected side-effects due to aliasing you hadn't taken into account. Destructive methods, however, are more efficient as they don't involve the extra work in creating a new object and filling in the unchanged data. You should make sure that if you are writing a method that is intended to be constructive that it does not have any destructive effects so that nowhere in its code do you make any changes to any object through a variable which is one of the method's parameters. If a method which is intended to return a result also changes an object passed to it as an argument without that change being acknowledged as a required effect of the method call, that could cause serious errors in a program as object get unexpectedly changed due to being used as arguments to the method.

To demonstrate use of the methods discussed here, you can look at the two files UseArrays6.java and UseArrays7.java in the directory ~mmh/DCS128/code/arrays. The first of these shows use of a destructive change method along with a copy method, the second shows use of a constructive change method. Once again, the main method in these files is given just so you can run the methods we are discussing on simple examples and display the result, you do not have to worry about everything that is in it.


Matthew Huntbach

Last modified: 17 June 2005