Friday, February 22, 2013

Mystery of Collections.max() Declaration

Introduction

I'm sure that every software developer who used Java for a while knows about Collections utility class. It contains a lot of useful methods which facilitate collection sorting, finding maximum and minimum of a collection, making synchronized or unmodifiable collection, etc. When I first looked at the source code of Collections class I was puzzled by the declaration of max() method:
public static <T extends Object & Comparable<? super T>> T max(
        Collection<? extends T> coll) {
    // …
}
In this post I’m going to explain why the aforementioned method declaration is written exactly that way.

Mystery Uncovered

The first attempt to define this method might look like this:
public static <T extends Comparable<T>> T max(Collection<T> coll) {
    // …
}
This declaration is too restrictive. Assume you have two classes: the first one (Foo) defines natural ordering (i.e. implements Comparable interface) and the second one (Bar) is a subclass of the first one:
class Foo implements Comparable<Foo> {

    // ...

    @Override
    public int compareTo(Foo o) {
        // ...
    }
}

class Bar extends Foo {
    // ...
}
It is safe to build a collection of Bar instances and pass it to max() method (which should base its search on the natural order defined by the Foo class). However the above declaration disallows this:
public class MaxDeclaration {
    public static void main(String[] args) {
        List<Bar> list = new ArrayList<Bar>();
        max(list); // compile-time error
    }

    public static <T extends Comparable<T>> T max(Collection<T> coll) {
        // …
    }
}
To make the above code compile without an error constraints on type parameter T must be loosen a bit. Application of “Get and Put Principle” leads us to the following declaration of max() method:
public static <T extends Comparable<? super T>> T max(
        Collection<? extends T> coll) {
    // …
}
This declaration looks almost like the one in Collections class. The last thing to figure out is the reason for presence of phrase “Object &” in T bound declaration. Short answer – it’s there for backward compatibility. Longer answer follows.

If you look at the documentation of Collections class for Java 1.4 or earlier you notice that max() method is declared to return Object. According to JLS, the erasure of a type variable is the erasure of its leftmost bound. Hence if phrase “Object &” would be omitted for Java 5 or later version of Collections class then the erasure of type variable T would be Comparable, not Object, which would break backward compatibility with Java 1.4 and earlier. This reasoning leads us to the original max() method declaration given in the beginning of the post.

Thanks for reading,
See you soon!

No comments:

Post a Comment