Section 3.4. Comparator


3.4. Comparator

Sometimes we want to compare objects that do not implement the Comparable interface, or to compare objects using a different ordering from the one specified by that interface. The ordering provided by the Comparable interface is called the natural ordering, so the Comparator interface provides, so to speak, an unnatural ordering.

We specify additional orderings using the Comparator interface, which contains a single method:

 interface Comparator<T> {   public int compare(T o1, T o2); } 

The compare method returns a value that is negative, zero, or positive depending upon whether the first object is less than, equal to, or greater than the second objectjust as with compareTo.

Here is a comparator that considers the shorter of two strings to be smaller. Only if two strings have the same length are they compared using the natural (alphabetic) ordering.

 Comparator<String> sizeOrder =   new Comparator<String>() {     public int compare(String s1, String s2) {       return         s1.length() < s2.length() ? -1 :         s1.length() > s2.length() ? 1 :         s1.compareTo(s2) ;       }   }; 

Here is an example:

 assert "two".compareTo("three") > 0; assert sizeOrder.compare("two","three") < 0; 

In the natural alphabetic ordering, "two" is greater than "three", whereas in the size ordering it is smaller.

The Java libraries always provide a choice between Comparable and Comparator. For every generic method with a type variable bounded by Comparable, there is another generic method with an additional argument of type Comparator. For instance, corresponding to:

 public static <T extends Comparable<? super T>>   T max(Collection<? extends T> coll) 

we also have:

 public static <T>   T max(Collection<? extends T> coll, Comparator<? super T> cmp) 

There are similar methods to find the minimum. For example, here is how to find the maximum and minimum of a list using the natural ordering and using the size ordering:

 Collection<String> strings = Arrays.asList("from","aaa","to","zzz"); assert max(strings).equals("zzz"); assert min(strings).equals("aaa"); assert max(strings,sizeOrder).equals("from"); assert min(strings,sizeOrder).equals("to"); 

The string "from" is the maximum using the size ordering because it is longest, and "to" is minimum because it is shortest.

Here is the code for a version of max using comparators:

 public static <T>   T max(Collection<? extends T> coll, Comparator<? super T> cmp) {   T candidate = coll.iterator().next();   for (T elt : coll) {     if (cmp.compare(candidate, elt) < 0) { candidate = elt; }   }   return candidate; } 

Compared to the previous version, the only change is that where before we wrote candidate.compareTo(elt), now we write cmp.compare(candidate,elt).

It is easy to define a comparator that provides the natural ordering:

 public static <T extends Comparable<? super T>>   Comparator<T> naturalOrder() {   return new Comparator<T> {     public int compare(T o1, T o2) { return o1.compareTo(o2); }   } } 

Using this, it is easy to define the version of max that uses the natural ordering in terms of the version that uses a given comparator:

 public static <T extends Comparable<? super T>>   T max(Collection<? extends T> coll) {   return max(coll, Comparators.<T>naturalOrder()); } 

A type parameter must be explicitly supplied for the invocation of the generic method naturalOrder, since the algorithm that infers types would fail to work out the correct type otherwise.

It is also easy to define a method that takes a comparator and returns a new comparator with the reverse of the given ordering:

 public static <T> Comparator<T>   reverseOrder(final Comparator<T> cmp) {   return new Comparator<T>() {     public int compare(T o1, T o2) { return cmp.compare(o2,o1); }   }; } 

This simply reverses the order of arguments to the comparator. (By the contract for comparators, it would be equivalent to leave the arguments in the original order but negate the result.) And here is a method that returns the reverse of the natural ordering:

 public static <T extends Comparable<? super T>>   Comparator<T> reverseOrder() {   return new Comparator<T>() {     public int compare(T o1, T o2) { return o2.compareTo(o1); }   }; } 

Similar methods are provided in java.util.Collections, see Section 17.4.

Finally, we can define the two versions of min in terms of the two versions of max by using the two versions of reverseOrder:

 public static <T>   T min(Collection<? extends T> coll, Comparator<? super T> cmp) {   return max(coll, reverseOrder(cmp)); } public static <T extends Comparable<? super T>>   T min(Collection<? extends T> coll) {   return max(coll, Comparators.<T>reverseOrder()); } 

For easy reference, the code we have presented here is summarized in Example 3.3.

Example 3-3. Comparators

 class Comparators {   public static <T>     T max(Collection<? extends T> coll, Comparator<? super T> cmp)   {     T candidate = coll.iterator().next();     for (T elt : coll) {       if (cmp.compare(candidate, elt) < 0) { candidate = elt; }     }     return candidate;   }   public static <T extends Comparable<? super T>>     T max(Collection<? extends T> coll)   {     return max(coll, Comparators.<T>naturalOrder());   }   public static <T>     T min(Collection<? extends T> coll, Comparator<? super T> cmp)   {     return max(coll, reverseOrder(cmp));   }   public static <T extends Comparable<? super T>>     T min(Collection<? extends T> coll)   {     return max(coll, Comparators.<T>reverseOrder());   }   public static <T extends Comparable<? super T>>     Comparator<T> naturalOrder()   {     return new Comparator<T>() {       public int compare(T o1, T o2) { return o1.compareTo(o2); }     };   }   public static <T> Comparator<T>     reverseOrder(final Comparator<T> cmp)   {     return new Comparator<T>() {       public int compare(T o1, T o2) { return cmp.compare(o2,o1); }     };   }   public static <T extends Comparable<? super T>>     Comparator<T> reverseOrder()   {     return new Comparator<T>() {       public int compare(T o1, T o2) { return o2.compareTo(o1); }     };   } } 

The Collections Framework does provide two versions each of min and max with the signatures given here, see Section 17.1. However, if you examine the source code of the library, you will see that none of the four is defined in terms of any of the others; instead, each is defined directly. The more direct version is longer and harder to maintain, but faster. With Sun's current JVM, measurements show a speedup of around 30 percent. Whether such a speedup is worth the code duplication depends on the situation in which the code is used. Since the Java utilities might well be used in a critical inner loop, the designers of the library were right to prefer speed of execution over economy of expression. But this is not always the case. An improvement of 30 percent may sound impressive, but it's insignificant unless the total time of the program is large and the routine appears in a heavily-used inner loop. Don't make your own code needlessly prolix just to eke out a small improvement.

As a final example of comparators, here is a method that takes a comparator on elements and returns a comparator on lists of elements:

 public static <E>   Comparator<List<E>> listComparator(final Comparator<E> comp) {   return new Comparator<List<E>>() {     public int compare(List<E> list1, List<E> list2) {       int n1 = list1.size();       int n2 = list2.size();       for (int i = 0; i < Math.min(n1,n2); i++) {         int k = comp.compare(list1.get(i), list2.get(i));         if (k != 0) return k;       }       return (n1 < n2) ? -1 : (n1 == n2) ? 0 : 1;     }   }; } 

The loop compares corresponding elements of the two lists, and terminates when corresponding elements are found that are not equal (in which case, the list with the smaller element is considered smaller) or when the end of either list is reached (in which case, the shorter list is considered smaller). This is the usual ordering for lists; if we convert a string to a list of characters, it gives the usual ordering on strings.




Java Generics and Collections
Java Generics and Collections
ISBN: 0596527756
EAN: 2147483647
Year: 2006
Pages: 136

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net