Section 3.2. Maximum of a Collection

3.2. Maximum of a Collection

In this section, we show how to use the Comparable<T> interface to find the maximum element in a collection. We begin with a simplified version. The actual version found in the Collections Framework has a type signature that is a bit more complicated, and later we will see why.

Here is code to find the maximum element in a nonempty collection, from the class Collections:

 public static <T extends Comparable<T>> T max(Collection<T> coll) {     T candidate = coll.iterator().next();     for (T elt : coll) {         if (candidate.compareTo(elt) < 0) candidate = elt;     }     return candidate; } 

We first saw generic methods that declare new type variables in the signature in Section 1.4. For instance, the method asList takes an array of type E[] and returns a result of type List<E>, and does so for any type E. Here we have a generic method that declares a bound on the type variable. The method max takes a collection of type Collection<T> and returns a T, and it does this for any type T such that T is a subtype of Comparable<T>.

The highlighted phrase in angle brackets at the beginning of the type signature declares the type variable T, and we say that T is bounded by Comparable<T>. As with wildcards, bounds for type variables are always indicated by the keyword extends, even when the bound is an interface rather than a class, as is the case here. Unlike wildcards, type variables must always be bounded using extends, never super.

In this case, the bound is recursive, in that the bound on T itself depends upon T. It is even possible to have mutually recursive bounds, such as:

 <T extends C<T,U>, U extends D<T,U>> 

An example of mutually recursive bounds appears in Section 9.5.

The method body chooses the first element in the collection as a candidate for the maximum, and then compares the candidate with each element in the collection, setting the candidate to the element when the element is larger. We use iterator().next() rather than get(0) to get the first element, because get is not defined on collections other than lists. The method raises a NoSuchElement exception when the collection is empty.

When calling the method, T may be chosen to be Integer (since Integer implements Comparable<Integer>) or String (since String implements Comparable<String>):

 List<Integer> ints = Arrays.asList(0,1,2); assert Collections.max(ints) == 2; List<String> strs = Arrays.asList("zero","one","two"); assert Collections.max(strs).equals("zero"); 

But we may not choose T to be Number (since Number does not implement Comparable):

 List<Number> nums = Arrays.asList(0,1,2,3.14); assert Collections.max(nums) == 3,14;  // compile-time error 

As expected, here the call to max is illegal.

Here's an efficiency tip. The preceding implementation used a foreach loop to increase brevity and clarity. If efficiency is a pressing concern, you might want to rewrite the method to use an explicit iterator, as follows:

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

This allocates an iterator once instead of twice and performs one less comparison.

Signatures for methods should be as general as possible to maximize utility. If you can replace a type parameter with a wildcard then you should do so. We can improve the signature of max by replacing:

 <T extends Comparable<T>> T max(Collection<T> coll) 

with:

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

Following the Get and Put Principle, we use extends with Collection because we get values of type T from the collection, and we use super with Comparable because we put value of type T into the compareTo method. In the next section, we'll see an example that would not type-check if the super clause above was omitted.

If you look at the signature of this method in the Java library, you will see something that looks even worse than the preceding code:

 <T extends Object & Comparable<? super T>>   T max(Collection<? extends T> coll) 

This is there for backward compatibility, as we will explain at the end of Section 3.6.