Arrays

“Arrays?” you ask yourself. I know what you’re thinking. You wonder why an article on a powerful object-oriented programming language in the year 2000 is focusing on arrays. Well, that’s a good question, with a good answer: arrays in Java are very different than arrays in C. In fact, they’re much safer and easier to use than C-arrays, although, as usual, you pay the price of increased overhead. In this article I discuss how arrays work in Java and also look at the array algorithms introduced to Java 2.

Like C, Only Different

Well, how different can they be? Like arrays in C, Java arrays are fixed-length, indexed sequences of objects of the same type. Furthermore, you use square brackets for indexing and indexes begin at zero. But that’s where the similarity between the two languages ends. The most important thing to remember about arrays in Java is:

Java arrays are runtime objects.

Arrays are created at runtime. Therefore, they always reside on the heap. Since arrays are objects they can store their length and check indexing operations for out-of-bounds errors – and so they do. Array elements are also automatically zero/null-initialized when they are created. The following program excerpt creates an array of ints.

int[] a; // line 1

a = new int[3]; // line 2

a[0] = 1;

a[1] = 2;

a[2] = 3;

for (int i = 0; i < a.length; ++i)

System.out.println(a[i]);

/* Output:

You can see from the first line above that you place the brackets with the type, not the array name, which makes sense, because a is an array of int, precisely what the expression “int[] “ suggests. Java will allow you to use a C-style declarator (int a[]), but that’s just to ease the transition from C to Java. “Real” Java programmers say “int[]”.

The second thing to learn from line 1 above is that you never specify an array’s dimension when you declare it – that comes later when you create it with the new operator. After line 1 executes, the variable a holds a null. After line 2, a points to heap space large enough to hold three contiguous ints, which are initialized immediately to zero. (Feel free to insert a print loop to verify the zero-initialization). The number of elements in an array is available in its read-only length member[1]. If you try to index outside of the range [0, length-1] you will get an IndexOutOfBoundsException.

Java allows C-style array-initializers for typists who prefer to minimize keystrokes. A single line, for example, could replace the first five lines of the excerpt above:

int[] a = {1,2,3,};

Note that Java allows a benign, trailing comma, probably for those of us who occasionally change our intializers but forget to delete that last comma.

There is yet another initializer mechanism which is particularly handy for those instances where an array doesn’t need a name. If you wanted to pass the array {1, 2, 3} as an argument to a function, for example, you could create the array on-the-fly as follows:

f(new int[]{1, 2, 3});[2]

Since arrays are runtime objects (somewhat similar to using calloc in C, in fact), you can reassign an array variable to another array, as in

// assume a is initialized, from above

a = new int[]{10, 20, 30, 40}; // now a.length == 4

The old array will be cleaned up when the garbage collector runs.

You can hold arrays of any type, of course, not just primitives. To create an array of Integers, you can do something like the following:

Integer[] a;

a = new Integer[3];

a[0] = new Integer(1);

a[1] = new Integer(2);

a[2] = new Integer(3);

or if you prefer

Integer[] a = {new Integer(1), new Integer(2), new Integer(3)};

Since arrays of objects only hold object references, you can always store objects in an array of the supertype, such as

Object[] a = {new Integer(1), new Integer(2), new Integer(3)};

If you try to store an object that is not compatible with an array’s element type you will get an ArrayStoreException.

Arrays as Objects

Each array type is a class that implicitly extends Object, as if declared as follows.

class <ArrayType> implements Cloneable

{

public final int length = <system provided value>;

public Object clone()

{

try

{

return super.clone();

}

catch (CloneNotSupportedException x)

{

throw new InternalError(e.getMessage());

}

Since the overridden clone method doesn’t throw an exception, you don’t have to worry about catching or declaring it in your code. Unfortunately, Object.equals() isn’t overridden, so you can’t use it to compare two arrays for equality (because it behaves the same as the == operator; in other words, it’s useless). There is an array algorithm discussed below that will do the job, however. The program in Figure 1 illustrates all of the above. Note the actual class name for an array of int. The length of an array is not part of its type name (it’s a field, remember), so all arrays of that hold the same type of element are instances of the same class. The class name of an array is not a valid Java token (because it contains a brace) and it reveals the array’s dimension (the number of braces).

The System class has a handy algorithm for copying a subsequence of one array to another. The following program copies the array a into the middle of array b.

class ArrayCopy

{

public static void main(String[] args)

{

int[] a = {1,2,3};

int[] b = new int[5];

System.arraycopy(a, 0, b, 1, a.length);

for (int i = 0; i < b.length; ++i)

System.out.print(b[i] + " ");

}

/* Output:

0 1 2 3 0

Of course all the indices need to be within range and the types of the two arrays must be compatible.

Multi-dimensional Arrays

Like C, Java interprets an array with multiple dimensions as an array of arrays. For example, the expression

int[][] a;

declares a to be an array where each element itself is an array of int. Unlike C, you can’t specify the size of each element array – that has to wait until runtime. If you want a to be a 3x4 array of ints, you again have three choices. You can allocate the space all at once, as in

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

and then initialize each element individually (i.e., a[0][0] = 0, a[0][1] = 1, etc.). Or, you can use a shorthand C-style initializer, such as

int a[][] = {{0,1,2,3},{4,5,6,7},{8,9,0,1}};

Finally, you can allocate each row individually, like this:

// 1^st dimension required in the next statement

int a[][] = new int[3][];

a[0] = new int[]{0,1,2,3};

a[1] = new int[]{4,5,6,7};

a[2] = new int[]{8,9,0,1};

Whenever you create an array with the new operator without an initializer, you must always provide at least the first dimension specifier, so the compiler knows how many elements the array will hold. The latter two techniques emphasize the fact that each element of a is itself an array. If you wanted to, you could define a as a ragged array by giving each element a different length:

a[0] = new int[]{0,1,2,3,4};

a[1] = new int[]{5,6,7};

a[2] = new int[]{8,9,0,1};

To print a row-wise requires using the length field for each element, as you can see in Figure 2. You can also define ragged arrays with a single initializer list, as the program in Figure 3 illustrates.

Since you can place the braces in an array declaration either with the type or with the variable (C-style), declarations can sometimes be hard to decipher. For example, the following statement declares a as a T[] and b as a T[][].

T[] a, b[]; // b is T[][]

I think it’s best not to mix the two declaration styles.

Array Algorithms

The class java.util.Arrays has some useful algorithms for processing arrays, namely

· binarySearch

· equals

· fill

· sort

These algorithms come in the form of overloaded methods that take arrays of Object and also of every primitive data type. The program in Figure 4 uses all four algorithms on arrays of int. The binarySearch algorithm requires an ordered array, of course, so the first thing I do is call the sort algorithm with the statement

Arrays.sort(array);

binarySearch returns the 0-based index the element you’re after occupies in the array, if it’s there, otherwise it returns

-pos - 1

where pos is the index of the position it should occupy. This way you can use the expression

-(pos + 1)

as either the element before which the search entry can be inserted, or you compare it to the length of the array to see if the search key should be appended to the array instead. Be aware the if there are multiple entries of a search object in an array, there is no guarantee as to which one the sort algorithm will find.

Unfortunately, Arrays.sort only put things in ascending order when used with arrays of primitives. If you want some other ordering scheme, you have to use arrays of objects and pass sort an extra comparator argument. A comparator is an object that implements the following interface:

public interface Comparator

{

int compare(Object o1, Object o2);

}

The compare method needs to behave like C’s strcmp function by returning a negative number if o1 precedes o2 in your ordering, zero if they are equal, or a positive number otherwise. The program in Figure 5 sorts an array of Integers in descending order by using the following comparator:

class Descending implements Comparator

{

public int compare(Object o1, Object o2)

{

Comparable c1 = (Comparable) o1;

Comparable c2 = (Comparable) o2;

return -c1.compareTo(c2);

}

A Comparable object implements the method int compareTo(Object o), which also behaves like strcmp. String, Date, and all the primitive wrapper classes implement Comparable, as do the new Java 2 collections (to be described in a future article). Arrays.sort uses Descending.compare to compare Integers in Figure 5.

Note that the definition of Descending above is totally generic – you can use it to reverse-sort any collection of objects derived from Comparable. Since this is something you’ll want to do quite often, the Java 2 library provides this comparator as the return value of Collections.reverseOrder, so you can replace the definition of desc in Figure 5 with the following one:

static Comparator desc = Collections.reverseOrder();

Since all Java 2 algorithms process instances of Object, it is easy to handle objects of any class. Figure 6 defines a Person class. Note that it implements Comparable, in case I want to sort an array of Persons. The fact that Person also implements Cloneable is a coincidence of my test program. I tried to implement hashCode and compareTo to insure that different Person objects will yield distinct results. The program in Figure 7 searches an array of Persons.

It’s possible to order and search an array by a subset of the objects’ fields by defining a suitable comparator. In Figure 8, I use a comparator that only looks at a Person's name. Unfortunately I have to use a complete Person object as the search key, even though the last 3 fields are ignored. As far as I can tell, there is no way to define a comparator to use a Person as one argument and a string as the other, as you can with function objects in the standard C++ library.

Conclusion

Because arrays are bona fide objects in Java you have ample runtime support for handling them safely. The length field constitutes a runtime query for the number of elements in an array, so you don’t have to pass it as a parameter as you do in C. If you accidentally use a bad index, the system will tell you instead of letting you march higgledy-piggledy through memory on your merry way to an access violation. The java.util.Arrays class provides commonly-needed algorithms for processing arrays of any type. Naturally there is some overhead for all this safety and convenience, but unless you’re building a performance-critical embedded system, the safety and ease of use is likely to be a winning proposition.

Like C, Only Different

Arrays as Objects

Array Algorithms

Conclusion

Figure 1 - Clones an Array

Figure 2 - Illustrates a Ragged Array

Figure 3 - Constructs Fibonacci Sequences with a single Initializer List

Figure 4 - Illustrates the Algorithms in java.util.Arrays

Figure 5 - Sorts/searches Integers in Descending Order

Figure 6 - A Person Class

Figure 7 - Sorts/Searches an Array of Person Objects

Figure 8 - Sorts/Searches by a Person's Name