Sunday, February 19, 2012

Comparable and Generics

The Comparable interface is defined this way:
public interface Comparable<T> {
    public int compareTo(T o);
}

The interface is a little non-intuitive because the method compareTo does not take a Comparable as a parameter, but instead takes the type itself as a parameter.


Consider a algorithm to find the max item, with input being a list of items, each implementing Comparable :

public static<T> Comparable<T>  max(Collection<Comparable<T>> coll){
  Iterator<Comparable<T>> iterator = coll.iterator();
  Comparable<T> maxElement = iterator.next();
  
  while(iterator.hasNext()){
   Comparable<T> nextElem = iterator.next();
   if (nextElem.compareTo((T)maxElement) > 0 ){
    maxElement = nextElem;
   }
  }
  return maxElement;
 }

Since the input is a Comparable type, the only way to invoke a compareTo method inside this algorithm is to cast from Comparable<T> to the java type, which defeats the use of generics, a better way to get it to work is to declare the type this way - <T extends Comparable<T>> , or even better this way: <T extends Comparable<? super T>>

public static<T extends Comparable<T>> T  max(Collection<? extends T> coll){
  Iterator<? extends T> iterator = coll.iterator();
  T maxElement = iterator.next();
  
  while(iterator.hasNext()){
   T nextElem = iterator.next();
   if (nextElem.compareTo(maxElement) > 0 ){
    maxElement = nextElem;
   }
  }
  return maxElement;
 }
  
 
 @Test
 public void testMaxForASmallListOfIntegers(){
  List<Integer> arr =Arrays.asList(5,3,10,2000,15,9,2,1);
  assertThat(max(arr), is(2000));
 }

This time around the generic type declaration is <T extends Comparable<T>>, which says that T implements Comparable, and the API from a client perspective is also clean as demonstrated in the accompanying test.

No comments:

Post a Comment