Java Generics and Collections

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Generics and collections work well with a number of other new features introduced in the latest versions of Java, including boxing and unboxing, a new form of loop, and functions that accept a variable number of arguments. We begin with an example that illustrates all of these. As we shall see, combining them is synergistic: the whole is greater than the sum of its parts.

Taking that as our motto, let's do something simple with sums: put three numbers into a list and add them together. Here is how to do it in Java with generics:

List<Integer> ints = Arrays.asList(1,2,3);
int s = 0;
for (int n : ints) { s += n; }
assert s == 6;

You can probably read this code without much explanation, but let's touch on the key features. The interface List and the class Arrays are part of the Collections Framework (both are found in the package java.util). The type List is now generic; you write List<E> to indicate a list with elements of type E. Here we write List<Integer> to indicate that the elements of the list belong to the class Integer, the wrapper class that corresponds to the primitive type int. Boxing and unboxing operations, used to convert from the primitive type to the wrapper class, are automatically inserted. The static method asList takes any number of arguments, places them into an array, and returns a new list backed by the array. The new loop form, foreach, is used to bind a variable successively to each element of the list, and the loop body adds these into the sum. The assertion statement (introduced in Java 1.4), is used to check that the sum is correct; when assertions are enabled, it throws an error if the condition does not evaluate to true.

Here is how the same code looks in Java before generics:

List ints = Arrays.asList( new Integer[] {
  new Integer(1), new Integer(2), new Integer(3)
} );
int s = 0;
for (Iterator it = ints.iterator(); it.hasNext(); ) {
  int n = ((Integer)it.next()).intValue();
  s += n;
}
assert s == 6;

Reading this code is not quite so easy. Without generics, there is no way to indicate in the type declaration what kind of elements you intend to store in the list, so instead of writing

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

An interface or class may be declared to take one or more type parameters, which are written in angle brackets and should be supplied when you declare a variable belonging to the interface or class or when you create a new instance of a class.

We saw one example in the previous section. Here is another:

List<String> words = new ArrayList<String>();
words.add("Hello ");
words.add("world!");
String s = words.get(0)+words.get(1);
assert s.equals("Hello world!");

In the Collections Framework, class ArrayList<E> implements interface List<E>. This trivial code fragment declares the variable words to contain a list of strings, creates an instance of an ArrayList, adds two strings to the list, and gets them out again.

In Java before generics, the same code would be written as follows:

List words = new ArrayList();
words.add("Hello ");
words.add("world!");
String s = ((String)words.get(0))+((String)words.get(1))
assert s.equals("Hello world!");

Without generics, the type parameters are omitted, but you must explicitly cast whenever an element is extracted from the list.

In fact, the bytecode compiled from the two sources above will be identical. We say that generics are implemented by erasure because the types List<Integer>, List<String>, and List<List<String>> are all represented at run-time by the same type, List. We also use erasure to describe the process that converts the first program to the second. The term erasure is a slight misnomer, since the process erases type parameters but adds casts.

Generics implicitly perform the same cast that is explicitly performed without generics. If such casts could fail, it might be hard to debug code written with generics. This is why it is reassuring that generics come with the following guarantee:

Cast-iron guarantee: the implicit casts added by the compilation of generics never fail.

There is also some fine print on this guaranteee: it applies only when no unchecked warnings have been issued by the compiler. Later, we will discuss at some length what causes unchecked warnings to be issued and how to minimize their effect.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Recall that every type in Java is either a reference type or a primitive type. A reference type is any class, instance, or array type. All reference types are subtypes of class Object, and any variable of reference type may be set to the value null. As shown in the following table, there are eight primitive types, and each of these has a corresponding library class of reference type. The library classes are located in the package java.lang.

Primitive	Reference
`byte`	`Byte`
`short`	`Short`
`int`	`Integer`
`long`	`Long`
`float`	`Float`
`double`	`Double`
`bool`	`Boolean`
`char`	`Character`

Conversion of a primitive type to the corresponding reference type is called boxing and conversion of the reference type to the corresponding primitive type is called

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Here, again, is our code that computes the sum of a list of integers.

List<Integer> ints = Arrays.asList(1,2,3);
int s = 0;
for (int n : ints) { s += n; }
assert s == 6;

The loop in the third line is called a foreach loop even though it is written with the keyword for. It is equivalent to the following:

for (Iterator<Integer> it = ints.iterator(); it.hasNext(); ) {
  int n = it.next();
  s += n;
}

The emphasized code corresponds to what was written by the user, and the unemphasized code is added in a systematic way by the compiler. It introduces the variable it of type Iterator<Integer> to iterate over the list ints of type List<Integer>. In general, the compiler invents a new name that is guaranteed not to clash with any name already in the code. Note that unboxing occurs when the expression it.next() of type Integer is assigned to the variable n of type int.

The foreach loop can be applied to any object that implements the interface Iterable<E> (in package java.lang), which in turn refers to the interface Iterator<E> (in package java.util). These define the methods iterator, hasNext, and next, which are used by the translation of the foreach loop (iterators also have a method remove, which is not used by the translation):

interface Iterable<E> {
  public Iterator<E> iterator();
}
interface Iterator<E> {
  public boolean hasNext();
  public E next();
  public void remove();
}

All collections, sets, and lists in the Collections Framework implement the Iterable<E> interface; and classes defined by other vendors or users may implement it as well.

The foreach loop may also be applied to an array:

public static int sumArray(int[] a) {
  int s = 0;
  for (int n : a) { s += n; }
  return s;
}

The foreach loop was deliberately kept simple and catches only the most common case. You need to explicitly introduce an iterator if you wish to use the remove method or to iterate over more than one list in parallel. Here is a method that removes negative elements from a list of doubles:

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Here is a method that accepts an array of any type and converts it to a list:

class Lists {
  public static <T> List<T> toList(T[] arr) {
    List<T> list = new ArrayList<T>();
    for (T elt : arr) list.add(elt);
    return list;
  }
}

The static method toList accepts an array of type T[] and returns a list of type List<T>, and does so for any type T. This is indicated by writing <T> at the beginning of the method signature, which declares T as a new type variable. A method which declares a type variable in this way is called a generic method. The scope of the type variable T is local to the method itself; it may appear in the method signature and the method body, but not outside the method.

The method may be invoked as follows:

List<Integer> ints = Lists.toList(new Integer[] { 1, 2, 3 });
List<String> words = Lists.toList(new String[] { "hello", "world" });

In the first line, boxing converts 1, 2, 3 from int to Integer.

Packing the arguments into an array is cumbersome. The vararg feature permits a special, more convenient syntax for the case in which the last argument of a method is an array. To use this feature, we replace T[] with T... in the method declaration:

class Lists {
  public static <T> List<T> toList(T... arr) {
    List<T> list = new ArrayList<T>();
    for (T elt : arr) list.add(elt);
    return list;
  }
}

Now the method may be invoked as follows:

List<Integer> ints = Lists.toList(1, 2, 3);
List<String> words = Lists.toList("hello", "world");

This is just shorthand for what we wrote above. At run time, the arguments are packed into an array which is passed to the method, just as previously.

Any number of arguments may precede a last vararg argument. Here is a method that accepts a list and adds all the additional arguments to the end of the list:

public static <T> void addAll(List<T> list, T... arr) {
  for (T elt : arr) list.add(elt);
}

Whenever a vararg is declared, one may either pass a list of arguments to be implicitly packed into an array, or explicitly pass the array directly. Thus, the preceding method may be invoked as follows:

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

We clarify our code by liberal use of the assert statement. Each occurrence of assert is followed by a boolean expression that is expected to evaluate to true. If assertions are enabled and the expression evaluates to false, an AssertionError is thrown, including an indication of where the error occurred. Assertions are enabled by invoking the JVM with the -ea or -enableassertions flag.

We only write assertions that we expect to evaluate to true. Since assertions may not be enabled, an assertion should never have side effects upon which any nonassertion code depends. When checking for a condition that might not hold (such as confirming that the arguments to a method call are valid), we use a conditional and throw an exception explicitly.

To sum up, we have seen how generics, boxing and unboxing, foreach loops, and varargs work together to make Java code easier to write, having illustrated this through the use of the Collections Framework.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Now that we've covered the basics, we can start to cover more-advanced features of generics, such as subtyping and wildcards. In this section, we'll review how subtyping works and we'll see how wildcards let you use subtyping in connection with generics. We'll illustrate our points with examples from the Collections Framework.

Subtyping is a key feature of object-oriented languages such as Java. In Java, one type is a subtype of another if they are related by an extends or implements clause. Here are some examples:

`Integer`	is a subtype of	`Number`
`Double`	is a subtype of	`Number`
`ArrayList<E>`	is a subtype of	`List<E>`
`List<E>`	is a subtype of	`Collection<E>`
`Collection<E>`	is a subtype of	`Iterable<E>`

Subtyping is transitive, meaning that if one type is a subtype of a second, and the second is a subtype of a third, then the first is a subtype of the third. So, from the last two lines in the preceding list, it follows that List<E> is a subtype of Iterable<E>. If one type is a subtype of another, we also say that the second is a

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Subtyping is a key feature of object-oriented languages such as Java. In Java, one type is a subtype of another if they are related by an extends or implements clause. Here are some examples:

`Integer`	is a subtype of	`Number`
`Double`	is a subtype of	`Number`
`ArrayList<E>`	is a subtype of	`List<E>`
`List<E>`	is a subtype of	`Collection<E>`
`Collection<E>`	is a subtype of	`Iterable<E>`

Subtyping is transitive, meaning that if one type is a subtype of a second, and the second is a subtype of a third, then the first is a subtype of the third. So, from the last two lines in the preceding list, it follows that List<E> is a subtype of Iterable<E>. If one type is a subtype of another, we also say that the second is a supertype of the first. Every reference type is a subtype of Object, and Object is a supertype of every reference type. We also say, trivially, that every type is a subtype of itself.

The Substitution Principle tells us that wherever a value of one type is expected, one may provide a value of any subtype of that type:

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Another method in the Collection interface is addAll, which adds all of the members of one collection to another collection:

interface Collection<E> {
  ...
  public boolean addAll(Collection<? extends E> c);
  ...
}

Clearly, given a collection of elements of type E, it is OK to add all members of another collection with elements of type E. The quizzical phrase "? extends E" means that it is also OK to add all members of a collection with elements of any type that is a subtype of E. The question mark is called a wildcard, since it stands for some type that is a subtype of E.

Here is an example. We create an empty list of numbers, and add to it first a list of integers and then a list of doubles:

List<Number> nums = new ArrayList<Number>();
List<Integer> ints = Arrays.asList(1, 2);
List<Double> dbls = Arrays.asList(2.78, 3.14);
nums.addAll(ints);
nums.addAll(dbls);
assert nums.toString().equals("[1, 2, 2.78, 3.14]");

The first call is permitted because nums has type List<Number>, which is a subtype of Collection<Number>, and ints has type List<Integer>, which is a subtype of Collection<? extends Number>. The second call is similarly permitted. In both calls, E is taken to be Number. If the method signature for addAll had been written without the wildcard, then the calls to add lists of integers and doubles to a list of numbers would not have been permitted; you would only have been able to add a list that was explicitly declared to be a list of numbers.

We can also use wildcards when declaring variables. Here is a variant of the example at the end of the preceding section, changed by adding a wildcard to the second line:

List<Integer> ints = Arrays.asList(1,2);
List<? extends Number> nums = ints;
nums.add(3.14);  // compile-time error
assert ints.toString().equals("[1, 2, 3.14]");  // uh oh!

Before, the second line caused a compile-time error (because List<Integer> is not a subtype of List<Number>), but the third line was fine (because a double is a number, so you can add a double to a

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Here is a method that copies into a destination list all of the elements from a source list, from the convenience class Collections:

public static <T> void copy(List<? super T> dst, List<? extends T> src) {
  for (int i = 0; i < src.size(); i++) {
    dst.set(i, src.get(i));
  }
}

The quizzical phrase ? super T means that the destination list may have elements of any type that is a supertype of T, just as the source list may have elements of any type that is a subtype of T.

Here is a sample call.

List<Object> objs = Arrays.<Object>asList(2, 3.14, "four");
List<Integer> ints = Arrays.asList(5, 6);
Collections.copy(objs, ints);
assert objs.toString().equals("[5, 6, four]");

As with any generic method, the type parameter may be inferred or may be given explicitly. In this case, there are four possible choices, all of which type-check and all of which have the same effect:

Collections.copy(objs, ints);
Collections.<Object>copy(objs, ints);
Collections.<Number>copy(objs, ints);
Collections.<Integer>copy(objs, ints);

The first call leaves the type parameter implicit; it is taken to be Integer, since that is the most specific choice that works. In the third line, the type parameter T is taken to be Number. The call is permitted because objs has type List<Object>, which is a subtype of List<? super Number> (since Object is a supertype of Number, as required by the super) and ints has type List<Integer>, which is a subtype of List<? extends Number> (since Integer is a subtype of Number, as required by the extends wildcard).

We could also declare the method with several possible signatures.

public static <T> void copy(List<T> dst, List<T> src)
public static <T> void copy(List<T> dst, List<? extends T> src)
public static <T> void copy(List<? super T> dst, List<T> src)
public static <T> void copy(List<? super T> dst, List<? extends T> src)

The first of these is too restrictive, as it only permits calls when the destination and source have exactly the same type. The remaining three are equivalent for calls that use implicit type parameters, but differ for explicit type parameters. For the example calls above, the second signature works only when the type parameter is

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

It may be good practice to insert wildcards whenever possible, but how do you decide which wildcard to use? Where should you use extends, where should you use super, and where is it inappropriate to use a wildcard at all?

Fortunately, a simple principle determines which is appropriate.

The Get and Put Principle: use an extends wildcard when you only get values out of a structure, use a super wildcard when you only put values into a structure, and don't use a wildcard when you both get and put.

We already saw this principle at work in the signature of the copy method:

public static <T> void copy(List<? super T> dest, List<? extends T> src)

The method gets values out of the source src, so it is declared with an extends wildcard, and it puts values into the destination dst, so it is declared with a super wildcard.

Whenever you use an iterator, you get values out of a structure, so use an extends wildcard. Here is a method that takes a collection of numbers, converts each to a double, and sums them up:

public static double sum(Collection<? extends Number> nums) {
  double s = 0.0;
  for (Number num : nums) s += num.doubleValue();
  return s;
}

Since this uses extends, all of the following calls are legal:

List<Integer> ints = Arrays.asList(1,2,3);
assert sum(ints) == 6.0;

List<Double> doubles = Arrays.asList(2.78,3.14);
assert sum(doubles) == 5.92;

List<Number> nums = Arrays.<Number>asList(1,2,2.78,3.14);
assert sum(nums) == 8.92;

The first two calls would not be legal if extends was not used.

Whenever you use the add method, you put values into a structure, so use a super wildcard. Here is a method that takes a collection of numbers and an integer n, and puts the first n integers, starting from zero, into the collection:

public static void count(Collection<? super Integer> ints, int n) {
  for (int i = 0; i < n; i++) ints.add(i);
}

Since this uses super, all of the following calls are legal:

List<Integer>

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

It is instructive to compare the treatment of lists and arrays in Java, keeping in mind the Substitution Principle and the Get and Put Principle.

In Java, array subtyping is covariant, meaning that type S[] is considered to be a subtype of T[] whenever S is a subtype of T. Consider the following code fragment, which allocates an array of integers, assigns it to an array of numbers, and then attempts to assign a double into the array:

Integer[] ints = new Integer[] {1,2,3};
Number[] nums = ints;
nums[2] = 3.14;  // array store 
 
 exception
 
 

assert Arrays.toString(ints).equals("[1, 2, 3.14]");  // uh oh!

Something is wrong with this program, since it puts a double into an array of integers! Where is the problem? Since Integer[] is considered a subtype of Number[], according to the Substitution Principle the assignment on the second line must be legal. Instead, the problem is caught on the third line, and it is caught at run time. When an array is allocated (as on the first line), it is tagged with its reified type (a run-time representation of its component type, in this case, Integer), and every time an array is assigned into (as on the third line), an array store exception is raised if the reified type is not compatible with the assigned value (in this case, a double cannot be stored into an array of Integer).

In contrast, the subtyping relation for generics is invariant, meaning that type List<S> is not considered to be a subtype of List<T>, except in the trivial case where S and T are identical. Here is a code fragment analogous to the preceding one, with lists replacing arrays:

List<Integer> ints = Arrays.asList(1,2,3);
List<Number> nums = ints; // compile-time error
nums.put(2, 3.14);
assert ints.toString().equals("[1, 2, 3.14]");  // uh oh!

Since List<Integer> is not considered to be a subtype of List<Number>, the problem is detected on the second line, not the third, and it is detected at compile time, not run time.

Wildcards reintroduce covariant subtyping for generics, in that type

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

The contains method checks whether a collection contains a given object, and its generalization, containsAll, checks whether a collection contains every element of another collection. This section presents two alternate approaches to giving generic signatures for these methods. The first approach uses wildcards and is the one used in the Java Collections Framework. The second approach uses type parameters and is often a more appropriate alternative.

Wildcards Here are the types that the methods have in Java with generics:

interface Collection<E> {
  ...
  public boolean contains(Object o);
  public boolean containsAll(Collection<?> c);
  ...
}

The first method does not use generics at all! The second method is our first sight of an important abbreviation. The type Collection<?> stands for:

Collection<? extends Object>

Extending Object is one of the most common uses of wildcards, so it makes sense to provide a short form for writing it.

These methods let us test for membership and containment:

Object obj = "one";
List<Object> objs = Arrays.<Object>asList("one", 2, 3.14, 4);
List<Integer> ints = Arrays.asList(2, 4);
assert objs.contains(obj);
assert objs.containsAll(ints);
assert !ints.contains(obj);
assert !ints.containsAll(objs);

The given list of objects contains both the string "one" and the given list of integers, but the given list of integers does not contain the string "one", nor does it contain the given list of objects.

The tests ints.contains(obj) and ints.containsAll(objs) might seem silly. Of course, a list of integers won't contain an arbitrary object, such as the string "one". But it is permitted because sometimes such tests might succeed:

Object obj = 1;
List<Object> objs = Arrays.<Object>asList(1, 3);
List<Integer> ints = Arrays.asList(1, 2, 3, 4);
assert ints.contains(obj);
assert ints.containsAll(objs);

In this case, the object may be contained in the list of integers because it happens to be an integer, and the list of objects may be contained within the list of integers because every object in the list happens to be an integer.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

When a generic method is invoked, the type parameter may be chosen to match the unknown type represented by a wildcard. This is called wildcard capture.

Consider the method reverse in the convenience class java.util.Collections, which accepts a list of any type and reverses it. It can be given either of the following two signatures, which are equivalent:

public static void reverse(List<?> list);
public static void <T> reverse(List<T> list);

The wildcard signature is slightly shorter and clearer, and is the one used in the library.

If you use the second signature, it is easy to implement the method:

public static void <T> reverse(List<T> list) {
  List<T> tmp = new ArrayList<T>(list);
  for (int i = 0; i < list.size(); i++) {
    list.set(i, tmp.get(list.size()-i-1));
  }
}

This copies the argument into a temporary list, and then writes from the copy back into the original in reverse order.

If you try to use the first signature with a similar method body, it won't work:

public static void reverse(List<?> list) {
  List<Object> tmp = new ArrayList<Object>(list);
  for (int i = 0; i < list.size(); i++) {
    list.set(i, tmp.get(list.size()-i-1));  // compile-time error
  }
}

Now it is not legal to write from the copy back into the original, because we are trying to write from a list of objects into a list of unknown type. Replacing List<Object> with List<?> won't fix the problem, because now we have two lists with (possibly different) unknown element types.

Instead, you can implement the method with the first signature by implementing a private method with the second signature, and calling the second from the first:

public static void reverse(List<?> list) { rev(list); }
private static <T> void rev(List<T> list) {
  List<T> tmp = new ArrayList<T>(list);
  for (int i = 0; i < list.size(); i++) {
    list.set(i, tmp.get(list.size()-i-1));
  }
}

Here we say that the type variable T has captured the wildcard. This is a generally useful technique when dealing with wildcards, and it is worth knowing.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Wildcards may not appear at the top level in class instance creation expressions (new), in explicit type parameters in generic method calls, or in supertypes (extends and implements).

Instance Creation In a class instance creation expression, if the type is a parameterized type, then none of the type parameters may be wildcards. For example, the following are illegal:

List<?> list = new ArrayList<?>();  // compile-time error
Map<String, ? extends Number> map
  = new HashMap<String, ? extends Number>();  // compile-time error

This is usually not a hardship. The Get and Put Principle tells us that if a structure contains a wildcard, we should only get values out of it (if it is an extends wildcard) or only put values into it (if it is a super wildcard). For a structure to be useful, we must do both. Therefore, we usually create a structure at a precise type, even if we use wildcard types to put values into or get values from the structure, as in the following example:

List<Number> nums = new ArrayList<Number>();
List<? super Number> sink = nums;
List<? extends Number> source = nums;
for (int i=0; i<10; i++) sink.add(i);
double sum=0; for (Number num : source) sum+=num.doubleValue();

Here wildcards appear in the second and third lines, but not in the first line that creates the list.

Only top-level parameters in instance creation are prohibited from containing wildcards. Nested wildcards are permitted. Hence, the following is legal:

List<List<?>> lists = new ArrayList<List<?>>();
lists.add(Arrays.asList(1,2,3));
lists.add(Arrays.asList("four","five"));
assert lists.toString().equals("[[1, 2, 3], [four, five]]");

Even though the list of lists is created at a wildcard type, each individual list within it has a specific type: the first is a list of integers and the second is a list of strings. The wildcard type prohibits us from extracting elements from the inner lists at any type other than Object, but since that is the type used by toString, this code is well typed.

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Now that we have the basics, let's look at some more-advanced uses of generics. This chapter describes the interfaces Comparable<T> and Comparator<T>, which are used to support comparison on elements. These interfaces are useful, for instance, if you want to find the maximum element of a collection or sort a list. Along the way, we will introduce bounds on type variables, an important feature of generics that is particularly useful in combination with the Comparable<T> interface.

The interface Comparable<T> contains a single method that can be used to compare one object to another:

interface Comparable<T> {
  public int compareTo(T o);
}

The compareTo method returns a value that is negative, zero, or positive depending upon whether the argument is less than, equal to, or greater than the given object. When a class implements Comparable, the ordering specified by this interface is called the natural ordering for that class.

Typically, an object belonging to a class can only be compared with an object belonging to the same class. For instance, Integer implements Comparable<Integer>:

Integer int0 = 0;
Integer int1 = 1;
assert int0.compareTo(int1) < 0;

The comparison returns a negative number, since 0 precedes 1 under numerical ordering. Similarly, String implements Comparable<String>:

  String str0 = "zero";
  String str1 = "one";
  assert str0.compareTo(str1) > 0;

This comparison returns a positive number, since "zero" follows "one" under alphabetic ordering.

The type parameter to the interface allows nonsensical comparisons to be caught at compile time:

Integer i = 0;
String s = "one";
assert i.compareTo(s) < 0;  // compile-time error

You can compare an integer with an integer or a string with a string, but attempting to compare an integer with a string signals a compile-time error.

Comparison is not supported between arbitrary numerical types:

Number m = new Integer(2);
Number n = new Double(3.14);
assert m.compareTo(n) < 0;

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

The interface Comparable<T> contains a single method that can be used to compare one object to another:

interface Comparable<T> {
  public int compareTo(T o);
}

The compareTo method returns a value that is negative, zero, or positive depending upon whether the argument is less than, equal to, or greater than the given object. When a class implements Comparable, the ordering specified by this interface is called the natural ordering for that class.

Typically, an object belonging to a class can only be compared with an object belonging to the same class. For instance, Integer implements Comparable<Integer>:

Integer int0 = 0;
Integer int1 = 1;
assert int0.compareTo(int1) < 0;

The comparison returns a negative number, since 0 precedes 1 under numerical ordering. Similarly, String implements Comparable<String>:

  String str0 = "zero";
  String str1 = "one";
  assert str0.compareTo(str1) > 0;

This comparison returns a positive number, since "zero" follows "one" under alphabetic ordering.

The type parameter to the interface allows nonsensical comparisons to be caught at compile time:

Integer i = 0;
String s = "one";
assert i.compareTo(s) < 0;  // compile-time error

You can compare an integer with an integer or a string with a string, but attempting to compare an integer with a string signals a compile-time error.

Comparison is not supported between arbitrary numerical types:

Number m = new Integer(2);
Number n = new Double(3.14);
assert m.compareTo(n) < 0;  // compile-time error

Here the comparison is illegal, because the Number class does not implement the Compar-able interface.

Consistent with Equals Usually, we require that two objects are equal if and only if they compare as the same:

x.equals(y)  if and only if  x.compareTo(y) == 0

In this case, we say that the natural ordering is consistent with equals.

It is recommended that when designing a class you choose a natural ordering that is consistent with equals. This is particularly important if you use the interfaces

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

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

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

The Comparable<T> interface gives fine control over what can and cannot be compared. Say that we have a Fruit class with subclasses Apple and Orange. Depending on how we set things up, we may prohibit comparison of apples with oranges or we may permit such comparison.

Example 3.2 prohibits comparison of apples with oranges. Here are the three classes it declares:

class Fruit {...}
class Apple extends Fruit implements Comparable<Apple> {...}
class Orange extends Fruit implements Comparable<Orange> {...}

Each fruit has a name and a size, and two fruits are equal if they have the same name and the same size. Following good practice, we have also defined a hash method, to ensure that equal objects have the same hash code. Apples are compared by comparing their sizes, and so are oranges. Since Apple implements Comparable<Apple>, it is clear that you can compare apples with apples, but not with oranges. The test code builds three lists, one of apples, one of oranges, and one containing mixed fruits. We may find the maximum of the first two lists, but attempting to find the maximum of the mixed list signals an error at compile time.

Example 3.1 permits comparison of apples with oranges. Compare these three class declarations with those given previously (all differences between Examples 3.2 and 3.1 are highlighted):

Example 3-1. Permitting comparison of apples with oranges

abstract class Fruit implements Comparable<Fruit> {
  protected String name;
  protected int size;
  protected Fruit(String name, int size) {
    this.name = name; this.size = size;
  }
  public boolean equals(Object o) {
    if (o instanceof Fruit) {
      Fruit that = (Fruit)o;
      return this.name.equals(that.name) && this.size == that.size;
    } else return false;
  }
  public int hash() {
    return name.hash()*29 + size;
  }
  public int compareTo(Fruit that) {
    return this.size < that.size ? - 1 :
           this.size == that.size ? 0 : 1 ;
  }
}
class Apple extends Fruit {
  public Apple(int size) { super("Apple", size); }
}
class Orange extends Fruit {
  public Orange(int size) { super("Orange", size); }
}
class Test {
  public static void main(String[] args) {

    Apple a1 = new Apple(1);  Apple a2 = new Apple(2);
    Orange o3 = new Orange(3);  Orange o4 = new Orange(4);

    List<Apple> apples = Arrays.asList(a1,a2);
    assert Collections.max(apples).equals(a2);

    List<Orange> oranges = Arrays.asList(o3,o4);
    assert Collections.max(oranges).equals(o4);

    List<Fruit> mixed = Arrays.<Fruit>asList(a1,o3);
    assert Collections.max(mixed).equals(o3);

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

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 object—just 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:

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|Buy reprint rights for this chapter

Java 5 includes support for enumerated types. Here is a simple example:

enum Season { WINTER, SPRING, SUMMER, FALL }

Each enumerated type declaration can be expanded into a corresponding class in a stylized way. The corresponding class is designed so that it has exactly one instance for each of the enumerated constants, bound to a suitable static final variable. For example, the enum declaration above expands into a class called Season. Exactly four instances of this class exist, bound to four static final variables with the names WINTER, SPRING, SUMMER, and FALL.

Each class that corresponds to an enumerated type is a subclass of java.lang.Enum. Its definition in the Java documentation begins like this:

class Enum<E extends Enum<E>>

You may find this frightening at first sight—both of us certainly did! But don't panic. Actually, we've already seen something similar. The worrying phrase E extends Enum<E> is a lot like the phrase T extends Comparable<T> that we encountered in the definition of max (see Section 3.2), and we'll see that they appear for related reasons.

To understand what's going on, we need to take a look at the code. Example 3.4 shows the base class Enum and Example 3.5 shows the class Season that corresponds to the enumerated type declaration above. (The code for Enum follows the source in the Java library, but we have simplified a few points.)

Example 3-4. Base class for enumerated types

public abstract class Enum<E extends Enum<E>> implements Comparable<E> {
  private final String name;
  private final int ordinal;
  protected Enum(String name, int ordinal) {
    this.name = name; this.ordinal = ordinal;
  }
  public final String name() { return name; }
  public final int ordinal() { return ordinal; }
  public String toString() { return name; }
  public final int compareTo(E o) {
    return ordinal - o.ordinal;
  }
}

Example 3-5. Class corresponding to an enumerated type

// corresponds to
// enum Season { WINTER, SPRING, SUMMER, FALL }
final class Season extends Enum<Season> {
  private Season(String name, int ordinal) { super(name,ordinal); }
  public static final Season WINTER = new Season("WINTER",0);
  public static final Season SPRING = new Season("SPRING",1);
  public static final Season SUMMER = new Season("SUMMER",2);
  public static final Season FALL   = new Season("FALL",3);
  private static final Season[] VALUES = { WINTER, SPRING, SUMMER, FALL };
  public static Season[] values() { return VALUES.clone(); }
  public static Season valueOf(String name) {
    for (Season e : VALUES) if (e.name().equals(name)) return e;
    throw new IllegalArgumentException();
  }
}

Additional content appearing in this section has been removed.
Purchase this book now or read it online at Safari to get the whole thing!

Content preview·Buy PDF of this chapter|

Table of Contents