Array element comparisons
One of the missing features in the Java 1.0 and 1.1 libraries was algorithmic operations—even simple sorting. This was a rather confusing situation to someone expecting an adequate standard library. Fortunately, Java 2 remedied the situation, at least for the sorting problem.
A problem with writing generic sorting code is that sorting must perform comparisons based on the actual type of the object. Of course, one approach is to write a different sorting method for every different type, but you should be able to recognize that this does not produce code that is easily reused for new types.
A primary goal of programming design is to “separate things that change from things that stay the same,” and here, the code that stays the same is the general sort algorithm, but the thing that changes from one use to the next is the way objects are compared. So instead of placing the comparison code into many different sort routines, the technique of the callback is used. With a callback, the part of the code that varies from case to case is separated, and the part of the code that’s always the same will call back to the code that changes.
Java has two ways to provide comparison functionality. The first is with the “natural” comparison method that is imparted to a class by implementing the java.lang.Comparable interface. This is a very simple interface with a single method, compareTo( ). This method takes another Object as an argument and produces a negative value if the current object is less than the argument, zero if the argument is equal, and a positive value if the current object is greater than the argument .
Here’s a class that implements Comparable and demonstrates the comparability by using the Java standard library method Arrays.sort( ):
//: c11:CompType.java
// Implementing Comparable in a class.
import com.bruceeckel.util.*;
import java.util.*;
public class CompType implements Comparable {
int i;
int j;
public CompType(int n1, int n2) {
i = n1;
j = n2;
}
public String toString() {
return "[i = " + i + ", j = " + j + "]";
}
public int compareTo(Object rv) {
int rvi = ((CompType)rv).i;
return (i < rvi ? -1 : (i == rvi ? 0 : 1));
}
private static Random r = new Random();
public static Generator generator() {
return new Generator() {
public Object next() {
return new CompType(r.nextInt(100),r.nextInt(100));
}
};
}
public static void main(String[] args) {
CompType[] a = new CompType[10];
Arrays2.fill(a, generator());
System.out.println(
"before sorting, a = " + Arrays.asList(a));
Arrays.sort(a);
System.out.println(
"after sorting, a = " + Arrays.asList(a));
}
} ///:~
When you define the comparison method, you are responsible for deciding what it means to compare one of your objects to another. Here, only the i values are used in the comparison, and the j values are ignored.
The static randInt( ) method produces positive values between zero and 100, and the generator( ) method produces an object that implements the Generator interface by creating an anonymous inner class (see Chapter 8). This builds CompType objects by initializing them with random values. In main( ), the generator is used to fill an array of CompType, which is then sorted. If Comparable hadn’t been implemented, then you’d get a ClassCastException at run time when you tried to call sort( ). This is because sort( ) casts its argument to Comparable.
Now suppose someone hands you a class that doesn’t implement Comparable, or hands you this class that does implement Comparable, but you decide you don’t like the way it works and would rather have a different comparison method for the type. The solution is in contrast to hard-wiring the comparison code into each different object. Instead, the strategy design pattern[54] is used. With a strategy, the part of the code that varies is encapsulated inside its own class (the strategy object). You hand a strategy object to the code that’s always the same, which uses the strategy to fulfill its algorithm. That way, you can make different objects to express different ways of comparison and feed them to the same sorting code. Here, you create a strategy by defining a separate class that implements an interface called Comparator. This has two methods, compare( ) and equals( ). However, you don’t have to implement equals( ) except for special performance needs, because anytime you create a class, it is implicitly inherited from Object, which has an equals( ). So you can just use the default Object equals( ) and satisfy the contract imposed by the interface.
The Collections class (which we’ll look at more later) contains a single Comparator that reverses the natural sorting order. This can be applied easily to the CompType:
//: c11:Reverse.java
// The Collecions.reverseOrder() Comparator
import com.bruceeckel.util.*;
import java.util.*;
public class Reverse {
public static void main(String[] args) {
CompType[] a = new CompType[10];
Arrays2.fill(a, CompType.generator());
System.out.println(
"before sorting, a = " + Arrays.asList(a));
Arrays.sort(a, Collections.reverseOrder());
System.out.println(
"after sorting, a = " + Arrays.asList(a));
}
} ///:~
The call to Collections.reverseOrder( ) produces the reference to the Comparator.
As a second example, the following Comparator compares CompType objects based on their j values rather than their i values:
//: c11:ComparatorTest.java
// Implementing a Comparator for a class.
import com.bruceeckel.util.*;
import java.util.*;
class CompTypeComparator implements Comparator {
public int compare(Object o1, Object o2) {
int j1 = ((CompType)o1).j;
int j2 = ((CompType)o2).j;
return (j1 < j2 ? -1 : (j1 == j2 ? 0 : 1));
}
}
public class ComparatorTest {
public static void main(String[] args) {
CompType[] a = new CompType[10];
Arrays2.fill(a, CompType.generator());
System.out.println(
"before sorting, a = " + Arrays.asList(a));
Arrays.sort(a, new CompTypeComparator());
System.out.println(
"after sorting, a = " + Arrays.asList(a));
}
} ///:~
The compare( ) method must return a negative integer, zero, or positive integer if the first argument is less than, equal to, or greater than the second, respectively.
