Array Comparison – Collections: Part II

Array Comparison

The compare() method of the Comparable<E> interface allows two objects to be compared. The comparison relationship is generalized by the Arrays.compare() static method to lexicographically compare arrays.

Click here to view code image

int compare(
type
[] a,
type
[] b)
<T extends Comparable<? super T>> int compare(T[] a, T[] b)

The permitted type for elements includes all primitive types (boolean, byte, char, double, float, int, long, short).

These methods return the value 0 if the first and second arrays are equal; a value less than 0 if the first array is lexicographically less than the second array; and a value greater than 0 if the first array is lexicographically greater than the second array.

The second method only permits arrays whose objects implement the compare-To() method of the Comparable<E> interface.

Two null array references are considered equal, and a null array reference is considered lexicographically less than a non-null array reference.

Consider the case where the two arrays diceA and diceD that represent the result of rolling a dice a fixed number of times. The arrays have a prefix ([5, 2]) which is common to both arrays. At index 2, diceA[2] (value 6) is greater than diceD[2] (value 3). In this case, the compare() method returns a positive value to indicate that array diceA is lexicographically greater than array diceD. Note that the index 2 is equal to the length of the prefix [5, 2] and it is a valid index in both arrays. The prefix [5, 2] is called the common prefix of diceA and diceD.

Index      0  1  2  3
diceA ==> [5, 2, 6, 3]
diceD ==> [5, 2, 3]
Common prefix: [5,2]
Compare value: 1

In the example below, the compare() method returns a negative value to indicate that diceA is lexicographically less than diceE because diceA[1] (value 2) is less than diceE[1] (value 6), where the common prefix [5] has length 1.

Index      0  1  2  3
diceA ==> [5, 2, 6, 3]
diceE ==> [5, 6]
Common prefix: [5]
Compare value: -1

If the arrays share a common prefix, as in the examples above, the lexicographical comparison is determined by the corresponding pair of values at the index given by the length of the common prefix. The length of a common prefix is always greater than or equal to 0 and less than the minimum length of the two arrays. By this definition, the length of a common prefix can never be equal to the length of the two arrays. A common prefix of length 0 means that the elements at index 0 from each array determine the comparison result.

Where the prefix is equal to one of the arrays, we need to consider the lengths of the arrays:

• If the lengths are equal, as shown in the example below, the arrays must be lexicographically equal and the compare() method returns the value 0.

Index      0  1  2  3
diceA ==> [5, 2, 6, 3]
diceB ==> [5, 2, 6, 3]
Prefix: [5, 2, 6, 3]
Compare value: 0

• If the lengths are not equal, as shown in the example below, lexicographical comparison is based on the lengths of the arrays. The longer array (diceC, length 4) is lexicographically greater than the shorter array (diceD, length 3). The compare() method returns a positive value. Note that the length of the prefix, 3 in this example, is a valid index in the longer array, diceC, but not in the shorter array, diceD.

Index      0  1  2  3
diceC ==> [5, 2, 3, 6]

diceD ==> [5, 2, 3]
Proper prefix: [5, 2, 3]
Compare value: 1

In the example above, the shorter array diceD is a prefix for the longer array diceC. Such a prefix is called a proper prefix—that is, it is equal to one of the arrays, where the lengths of the arrays are different.

The following code can be used to demonstrate lexicographic comparison of arrays, where System.out is statically imported:

Click here to view code image

int[] diceA = { 5, 2, 6, 3 };
int[] diceB = { 5, 2, 6, 3 };
int[] diceC = { 5, 2, 3, 6 };
int[] diceD = { 5, 2, 3 };
int[] diceE = { 5, 6 };
…
out.println(“Compare value: ” + Arrays.compare(diceA, diceD)); // 1
out.println(“Compare value: ” + Arrays.compare(diceA, diceE)); // -1
out.println(“Compare value: ” + Arrays.compare(diceA, diceB)); // 0
out.println(“Compare value: ” + Arrays.compare(diceC, diceD)); // 1