Team LiB
Previous Section Next Section

4.1. Generic Types

Generic types and methods are the defining new feature of Java 5.0. A generic type is defined using one or more type variables and has one or more methods that use a type variable as a placeholder for an argument or return type. For example, the type java.util.List<E> is a generic type: a list that holds elements of some type represented by the placeholder E. This type has a method named add(), declared to take an argument of type E, and a method named get(), declared to return a value of type E.

In order to use a generic type like this, you specify actual types for the type variable (or variables), producing a parameterized type such as List<String>.[1] The reason to specify this extra type information is that the compiler can provide much stronger compile-time type checking for you, increasing the type safety of your programs. This type checking prevents you from adding a String[], for example, to a List that is intended to hold only String objects. Also, the additional type information enables the compiler to do some casting for you. The compiler knows that the get( ) method of a List<String> (for example) returns a String object: you are no longer required to cast a return value of type Object to a String.

[1] Throughout this chapter, I've tried to consistently use the term " generic type" to mean a type that declares one or more type variables and the term "parameterized type" to mean a generic type that has had actual type arguments substituted for its type varaiables. In common usage, however, the distinction is not a sharp one and the terms are sometimes used interchangeably.

The collections classes of the java.util package have been made generic in Java 5.0, and you will probably use them frequently in your programs. Typesafe collections are the canonical use case for generic types. Even if you never define generic types of your own and never use generic types other than the collections classes in java.util, the benefits of typesafe collections are so significant that they justify the complexity of this major new language feature.

We begin by exploring the basic use of generics in typesafe collections, then delve into more complex details about the use of generic types. Next we cover type parameter wildcards and bounded wildcards. After describing how to use generic types, we explain how to write your own generic types and generic methods. Our coverage of generics concludes with a tour of important generic types in the core Java API. It explores these types and their use in depth in order to provide a deeper understanding of how generics work.

4.1.1. Typesafe Collections

The java.util package includes the Java Collections Framework for working with sets and lists of objects and mappings from key objects to value objects. Collections are covered in Chapter 5. Here, we discuss the fact that in Java 5.0 the collections classes use type parameters to identify the type of the objects in the collection. This is not the case in Java 1.4 and earlier. Without generics, the use of collections requires the programmer to remember the proper element type for each collection. When you create a collection in Java 1.4, you know what type of objects you intend to store in that collection, but the compiler cannot know this. You must be careful to add elements of the appropriate type. And when querying elements from a collection, you must write explicit casts to convert them from Object to their actual type. Consider the following Java 1.4 code:

public static void main(String[] args) {
    // This list is intended to hold only strings.
    // The compiler doesn't know that so we have to remember ourselves.
    List wordlist = new ArrayList();  

    // Oops! We added a String[] instead of a String.
    // The compiler doesn't know that this is an error.
    wordlist.add(args);

    // Since List can hold arbitrary objects, the get() method returns
    // Object.  Since the list is intended to hold strings, we cast the
    // return value to String but get a ClassCastException because of
    // the error above.
    String word = (String)wordlist.get(0);
}

Generic types solve the type safety problem illustrated by this code. List and the other collection classes in java.util have been rewritten to be generic. As mentioned above, List has been redefined in terms of a type variable named E that represents the type of the elements of the list. The add( ) method is redefined to expect an argument of type E instead of Object and get( ) has been redefined to return E instead of Object.

In Java 5.0, when we declare a List variable or create an instance of an ArrayList, we specify the actual type we want E to represent by placing the actual type in angle brackets following the name of the generic type. A List that holds strings is a List<String>, for example. Note that this is much like passing an argument to a method, except that we use types rather than values and angle brackets instead of parentheses.

The elements of the java.util collection classes must be objects; they cannot be used with primitive values. The introduction of generics does not change this. Generics do not work with primitives: we can't declare a Set<char>, or a List<int> for example. Note, however, that the autoboxing and autounboxing features of Java 5.0 make working with a Set<Character> or a List<Integer> just as easy as working directly with char and int values. (See Chapter 2 for details on autoboxing and autounboxing).

In Java 5.0, the example above would be rewritten as follows:

public static void main(String[] args) {
    // This list can only hold String objects
    List<String> wordlist = new ArrayList<String>();

    // args is a String[], not String, so the compiler won't let us do this
    wordlist.add(args);  // Compilation error!

    // We can do this, though.  
    // Notice the use of the new for/in looping statement
    for(String arg : args) wordlist.add(arg);

    // No cast is required.  List<String>.get() returns a String.
    String word = wordlist.get(0);
}

Note that this code isn't much shorter than the nongeneric example it replaces. The cast, which uses the word String in parentheses, is replaced with the type parameter, which places the word String in angle brackets. The difference is that the type parameter has to be declared only once, but the list can be used any number of times without a cast. This would be more apparent in a longer example. But even in cases where the generic syntax is more verbose than the nongeneric syntax, it is still very much worth using generics because the extra type information allows the compiler to perform much stronger error checking on your code. Errors that would only be apparent at runtime can now be detected at compile time. Furthermore, the compilation error appears at the exact line where the type safety violation occurs. Without generics, a ClassCastException can be thrown far from the actual source of the error.

Just as methods can have any number of arguments, classes can have more than one type variable. The java.util.Map interface is an example. A Map is a mapping from key objects to value objects. The Map interface declares one type variable to represent the type of the keys and one variable to represent the type of the values. As an example, suppose you want to map from String objects to Integer objects:

public static void main(String[] args) {
    // A map from strings to their position in the args[] array
    Map<String,Integer> map = new HashMap<String,Integer>();

    // Note that we use autoboxing to wrap i in an Integer object.
    for(int i=0; i < args.length; i++) map.put(args[i], i);  

    // Find the array index of a word.  Note no cast is required!
    Integer position = map.get("hello");

    // We can also rely on autounboxing to convert directly to an int,
    // but this throws a NullPointerException if the key does not exist 
    // in the map
    int pos = map.get("world");
}

A parameterized type like List<String> is itself a type and can be used as the value of a type parameter for some other type. You might see code like this:

// Look at all those nested angle brackets!
Map<String, List<List<int[]>>> map = getWeirdMap();

// The compiler knows all the types and we can write expressions
// like this without casting.  We might still get NullPointerException
// or ArrayIndexOutOfBounds at runtime, of course.
int value = map.get(key).get(0).get(0)[0];

// Here's how we break that expression down step by step.
List<List<int[]>> listOfLists = map.get(key);
List<int[]> listOfIntArrays = listOfLists.get(0);
int[] array = listOfIntArrays.get(0);
int element = array[0];

In the code above, the get( ) methods of java.util.List<E> and java.util.Map<K,V> return a list or map element of type E and V respectively. Note, however, that generic types can use their variables in more sophisticated ways. Look up List<E> in the reference section of this book, and you'll find that its iterator( ) method is declared to return an Iterator<E>. That is, the method returns an instance of a parameterized type whose actual type parameter is the same as the actual type parameter of the list. To illustrate this concretely, here is a way to obtain the first element of a List<String> without calling get(0).

List<String> words = // ...initialized elsewhere...
Iterator<String> iterator = words.iterator();
String firstword = iterator.next();

4.1.2. Understanding Generic Types

This section delves deeper into the details of generic type usage, explaining the following topics:

  • The consequences of using generic types without type parameters

  • The parameterized type hierarchy

  • A hole in the compile-time type safety of generic types and a patch to ensure runtime type safety

  • Why arrays of parameterized types are not typesafe

4.1.2.1 Raw types and unchecked warnings

Even though the Java collection classes have been modified to take advantage of generics, you are not required to specify type parameters to use them. A generic type used without type parameters is known as a raw type. Existing pre-5.0 code continues to work: you simply write all the casts that you're already used to writing, and you put up with some pestering from the compiler. Consider the following code that stores objects of mixed types into a raw List:

List l = new ArrayList();
l.add("hello");  
l.add(new Integer(123));
Object o = l.get(0);

This code works fine in Java 1.4. If we compile it using Java 5.0, however, javac compiles the code but prints this complaint:

Note: Test.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

When we recompile with the -Xlint option as suggested, we see these warnings:

Test.java:6: warning: [unchecked]
    unchecked call to add(E) as a member of the raw type java.util.List
        l.add("hello");  
         ^
Test.java:7: warning: [unchecked]
    unchecked call to add(E) as a member of the raw type java.util.List
        l.add(new Integer(123));
         ^

The compiler warns us about the add( ) calls because it cannot ensure that the values being added to the list have the correct types. It is letting us know that because we've used a raw type, it cannot verify that our code is typesafe. Note that the call to get( ) is okay because it is extracting an element that is already safely in the list.

If you get unchecked warnings on files that do not use any of the new Java 5.0 features, you can simply compile them with the -source 1.4 flag, and the compiler won't complain. If you can't do that, you can ignore the warnings, suppress them with an @SuppressWarnings("unchecked") annotation (see Section 4.3 later in this chapter) or upgrade your code to specify a type parameter.[2] The following code, for example, compiles with no warnings and still allows you to add objects of mixed types to the list:

[2] At the time of this writing, javac does not yet honor the @SuppressWarnings annotation. It is expected to do so in Java 5.1.

List<Object> l = new ArrayList<Object>();
l.add("hello");  
l.add(123);              // autoboxing
Object o = l.get(0);

4.1.2.2 The parameterized type hierarchy

Parameterized types form a type hierarchy, just as normal types do. The hierarchy is based on the base type, however, and not on the type of the parameters. Here are some experiments you can try:

ArrayList<Integer> l = new ArrayList<Integer>();
List<Integer> m = l;                            // okay
Collection<Integer> n = l;                      // okay
ArrayList<Number> o = l;                        // error
Collection<Object> p = (Collection<Object>)l;   // error, even with cast

A List<Integer> is a Collection<Integer>, but it is not a List<Object>. This is nonintuitive, and it is important to understand why generics work this way. Consider this code:

List<Integer> li = new ArrayList<Integer>();
li.add(123);

// The line below will not compile.  But for the purposes of this
// thought-experiment, assume that it does compile and see how much
// trouble we get ourselves into.
List<Object> lo = li;  

// Now we can retrieve elements of the list as Object instead of Integer
Object number = lo.get(0);

// But what about this?
lo.add("hello world");

// If the line above is allowed then the line below throws ClassCastException
Integer i = li.get(1);  // Can't cast a String to Integer!

This then is the reason that a List<Integer> is not a List<Object>, even though all elements of a List<Integer> are in fact instances of Object. If the conversion to List<Object> were allowed, non-Integer objects could be added to the list.

4.1.2.3 Runtime type safety

As we've seen, a List<X> cannot be converted to a List<Y>, even when X can be converted to Y. A List<X> can be converted to a List, however, so that you can pass it to a legacy method that expects an argument of that type and has not been updated for generics.

This ability to convert parameterized types to nonparameterized types is essential for backward compatibility, but it does open up a hole in the type safety system that generics offer:

// Here's a basic parameterized list.
List<Integer> li = new ArrayList<Integer>();

// It is legal to assign a parameterized type to a nonparameterized variable
List l = li;   

// This line is a bug, but it compiles and runs.
// The Java 5.0 compiler will issue an unchecked warning about it.
// If it appeared as part of a legacy class compiled with Java 1.4, however,
// then we'd never even get the warning.  
l.add("hello");

// This line compiles without warning but throws ClassCastException at runtime.
// Note that the failure can occur far away from the actual bug.
Integer i = li.get(0);

Generics provide compile-time type safety only. If you compile all your code with the Java 5.0 compiler and do not get any unchecked warnings, these compile-time checks are enough to ensure that your code is also typesafe at runtime. But if you have unchecked warnings or are working with legacy code that manipulates your collections as raw types, you may want to take additional steps to ensure type safety at runtime. You can do this with methods like checkedList() and checkedMap( ) of java.util.Collections. These methods enclose your collection in a wrapper collection that performs runtime type checks to ensure that only values of the correct type are added to the collection. For example, we could prevent the type safety hole shown above like this:

// Here's a basic parameterized list.
List<Integer> li = new ArrayList<Integer>();

// Wrap it for runtime type safety
List<Integer> cli = Collections.checkedList(li, Integer.class);

// Now widen the checked list to the raw type
List l = cli;   

// This line compiles but fails at runtime with a ClassCastException.
// The exception occurs exactly where the bug is, rather than far away
l.add("hello");

4.1.2.4 Arrays of parameterized type

Arrays require special consideration when working with generic types. Recall that an array of type S[ ] is also of type T[], if T is a superclass (or interface) of S. Because of this, the Java interpreter must perform a runtime check every time you store an object in an array to ensure that the runtime type of the object and of the array are compatible. For example, the following code fails this runtime check and throws an ArrayStoreException:

String[] words = new String[10];
Object[] objs = words;
objs[0] = 1;  // 1 autoboxed to an Integer, throws ArrayStoreException

Although the compile-time type of objs is Object[], its runtime type is String[ ], and it is not legal to store an Integer in it.

When we work with generic types, the runtime check for array store exceptions is no longer sufficient because a check performed at runtime does not have access to the compile-time type parameter information. Consider this (hypothetical) code:

List<String>[] wordlists = new ArrayList<String>[10];
ArrayList<Integer> ali = new ArrayList<Integer>();
ali.add(123);
Object[] objs = wordlists;
objs[0] = ali;                       // No ArrayStoreException
String s = wordlists[0].get(0);      // ClassCastException!

If the code above were allowed, the runtime array store check would succeed: without compile-time type parameters, the code simply stores an ArrayList into an ArrayList[] array, which is perfectly legal. Since the compiler can't prevent you from defeating type safety in this way, it instead prevents you from creating any array of parameterized type. The scenario above can never occur because the compiler will refuse to compile the first line.

Note that this is not a blanket restriction on using arrays with generics; it is just a restriction on creating arrays of parameterized type. We'll return to this issue when we look at how to write generic methods.

4.1.3. Type Parameter Wildcards

Suppose we want to write a method to display the elements of a List.[3] Before List was a generic type, we'd just write code like this:

[3] The three printList() methods shown in this section ignore the fact that the List implementations classes in java.util all provide working toString() methods. Notice also that the methods assume that the List implements RandomAccess and provides very poor performance on LinkedList instances.

public static void printList(PrintWriter out, List list) {
    for(int i=0, n=list.size(); i < n; i++) {
        if (i > 0) out.print(", ");
        out.print(list.get(i).toString());
    }
}

In Java 5.0, List is a generic type, and, if we try to compile this method, we'll get unchecked warnings. In order to get rid of those warnings, you might be tempted to modify the method as follows:

public static void printList(PrintWriter out, List<Object> list) {
    for(int i=0, n=list.size(); i < n; i++) {
        if (i > 0) out.print(", ");
        out.print(list.get(i).toString());
    }
}

This code compiles without warnings but isn't very useful because the only lists that can be passed to it are lists explicitly declared of type List<Object>. Remember that List<String> and List<Integer> (for example) cannot be widened or cast to List<Object>. What we really want is a typesafe printList() method to which we can pass any List, regardless of how it has been parameterized. The solution is to use a wildcard as the type parameter. The method would then be written like this:

public static void printList(PrintWriter out, List<?> list) {
    for(int i=0, n=list.size(); i < n; i++) {
        if (i > 0) out.print(", ");
        Object o = list.get(i);
        out.print(o.toString());
    }
}

This version of the method compiles without warnings and can be used the way we want it to be used. The ? wildcard represents an unknown type, and the type List<?> is read as "List of unknown."

As a general rule, if a type is generic and you don't know or don't care about the value of the type variable, you should always use a ? wildcard instead of using a raw type. Raw types are allowed only for backward compatibility and should be used only in legacy code. Note, however, that you cannot use a wildcard when invoking a constructor. The following code is not legal:

List<?> l = new ArrayList<?>();

There is no sense in creating a List of unknown type. If you are creating it, you should know what kind of elements it will hold. You may later want to pass such a list to a method that does not care about its element type, but you need to specify an element type when you create it. If what you really want is a List that can hold any type of object, do this:

List<Object> l = new ArrayList<Object>();

It should be clear from the printList( ) variants above that a List<?> is not the same thing as a List<Object> and that neither is the same thing as a raw List. A List<?> has two important properties that result from the use of a wildcard. First, consider methods like get() that are declared to return a value of the same type as the type parameter. In this case, that type is unknown, so these methods return an Object. Since all we need to do with the object is invoke its toString() method, this is fine for our needs.

Second, consider List methods such as add() that are declared to accept an argument whose type is specified by the type parameter. This is the more surprising case: when the type parameter is unknown, the compiler does not let you invoke any methods that have a parameter of the unknown type because it cannot check that you are passing an appropriate value. A List<?> is effectively read-only since the compiler does not allow us to invoke methods like add( ), set(), and addAll( ).

4.1.3.1 Bounded wildcards

Let's continue now with a slightly more complex variant of our original example. Suppose that we want to write a sumList() method to compute the sum of a list of Number objects. As before, we could use a raw List, but we would give up type safety and have to deal with unchecked warnings from the compiler. Or we could use a List<Number>, but then we wouldn't be able to call the method for a List<Integer> or List<Double>, types we are more likely to use in practice. But if we use a wildcard, we don't actually get the type safety that we want because we have to trust that our method will be called with a List whose type parameter is actually Number or a subclass and not, say, a String. Here's what such a method might look like:

public static double sumList(List<?> list) {
    double total = 0.0;
    for(Object o : list) {
        Number n = (Number) o;  // A cast is required and may fail
        total += n.doubleValue();
    }
    return total;
}

To fix this method and make it truly typesafe, we need to use a bounded wildcard that states that the type parameter of the List is an unknown type that is either Number or a subclass of Number. The following code does just what we want:

public static double sumList(List<? extends Number> list) {
    double total = 0.0;
    for(Number n : list) total += n.doubleValue();
    return total;
}

The type List<? extends Number> could be read as "List of unknown descendant of Number." It is important to understand that, in this context, Number is considered a descendant of itself.

Note that the cast is no longer required. We don't know the type of the elements of the list, but we know that they have an "upper bound" of Number so we can extract them from the list as Number objects. The use of a for/in loop obscures the process of extracting elements from a list somewhat. The general rule is that when you use a bounded wildcard with an upper bound, methods (like the get() method of List) that return a value of the type parameter use the upper bound. So if we called list.get( ) instead of using a for/in loop, we'd also get a Number. The prohibition on calling methods like list.add( ) that have arguments of the type parameter type still stands: if the compiler allowed us to call those methods we could add an Integer to a list that was declared to hold only Short values, for example.

It is also possible to specify a lower-bounded wildcard using the keyword super instead of extends. This technique has a different impact on what methods can be called. Lower-bounded wildcards are much less commonly used than upper-bounded wildcards, and we discuss them later in the chapter.

4.1.4. Writing Generic Types and Methods

Creating a simple generic type is straightforward. First, declare your type variables by enclosing a comma-separated list of their names within angle brackets after the name of the class or interface. You can use those type variables anywhere a type is required in any instance fields or methods of the class. Remember, though, that type variables exist only at compile time, so you can't use a type variable with the runtime operators instanceof and new.

We begin this section with a simple generic type, which we will subsequently refine. This code defines a tree data structure that uses the type variable V to represent the type of the value held in each node of the tree:

import java.util.*;

/**
 * A tree is a data structure that holds values of type V.
 * Each tree has a single value of type V and can have any number of
 * branches, each of which is itself a Tree.
 */
public class Tree<V> {
    // The value of the tree is of type V.
    V value;

    // A Tree<V> can have branches, each of which is also a Tree<V>
    List<Tree<V>> branches = new ArrayList<Tree<V>>();

    // Here's the constructor.  Note the use of the type variable V.
    public Tree(V value) { this.value = value; }

    // These are instance methods for manipulating the node value and branches.
    // Note the use of the type variable V in the arguments or return types.
    V getValue() { return value; }
    void setValue(V value) { this.value = value; }
    int getNumBranches() { return branches.size(); }
    Tree<V> getBranch(int n) { return branches.get(n); }
    void addBranch(Tree<V> branch) { branches.add(branch); }
}

As you've probably noticed, the naming convention for type variables is to use a single capital letter. The use of a single letter distinguishes these variables from the names of actual types since real-world types always have longer, more descriptive names. The use of a capital letter is consistent with type naming conventions and distinguishes type variables from local variables, method parameters, and fields, which are sometimes written with a single lowercase letter. Collection classes like those in java.util often use the type variable E for "Element type." When a type variable can represent absolutely anything, T (for Type) and S are used as the most generic type variable names possible (like using i and j as loop variables).

Notice that the type variables declared by a generic type can be used only by the instance fields and methods (and nested types) of the type and not by static fields and methods. The reason, of course, is that it is instances of generic types that are parameterized. Static members are shared by all instances and parameterizations of the class, so static members do not have type parameters associated with them. Methods, including static methods, can declare and use their own type parameters, however, and each invocation of such a method can be parameterized differently. We'll cover this later in the chapter.

4.1.4.1 Type variable bounds

The type variable V in the declaration above of the TRee<V> class is unconstrained: TRee can be parameterized with absolutely any type. Often we want to place some constraints on the type that can be used: we might want to enforce that a type parameter implements one or more interfaces, or that it is a subclass of a specified class. This can be done by specifying a bound for the type variable. We've already seen upper bounds for wildcards, and upper bounds can also be specified for type variables using a similar syntax. The following code is the tree example rewritten to make tree objects Serializable and Comparable. In order to do this, the example uses a type variable bound to ensure that its value type is also Serializable and Comparable. Note how the addition of the Comparable bound on V enables us to write the compareTo() method tree by guaranteeing the existence of a compareTo() method on V.[4]

[4] The bound shown here requires that the value type V is comparable to itself, in other words, that it implements the Comparable interface directly. This rules out the use of types that inherit the Comparable interface from a superclass. We'll consider the Comparable interface in much more detail at the end of this section and present an alternative there.

import java.io.Serializable;
import java.util.*;

public class Tree<V extends Serializable & Comparable<V>>
    implements Serializable, Comparable<Tree<V>>
{
    V value;
    List<Tree<V>> branches = new ArrayList<Tree<V>>();

    public Tree(V value) { this.value = value; }

    // Instance methods
    V getValue() { return value; }
    void setValue(V value) { this.value = value; }
    int getNumBranches() { return branches.size(); }
    Tree<V> getBranch(int n) { return branches.get(n); }
    void addBranch(Tree<V> branch) { branches.add(branch); }

    // This method is a nonrecursive implementation of Comparable<Tree<V>>
    // It only compares the value of this node and ignores branches.
    public int compareTo(Tree<V> that) {
        if (this.value == null && that.value == null) return 0;
        if (this.value == null) return -1;
        if (that.value == null) return 1;
        return this.value.compareTo(that.value);
    }

    // javac -Xlint warns us if we omit this field in a Serializable class
    private static final long serialVersionUID = 833546143621133467L;
}

The bounds of a type variable are expressed by following the name of the variable with the word extends and a list of types (which may themselves be parameterized, as Comparable is). Note that with more than one bound, as in this case, the bound types are separated with an ampersand rather than a comma. Commas are used to separate type variables and would be ambiguous if used to separate type variable bounds as well. A type variable can have any number of bounds, including any number of interfaces and at most one class.

4.1.4.2 Wildcards in generic types

Earlier in the chapter we saw examples using wildcards and bounded wildcards in methods that manipulated parameterized types. They are also useful in generic types. Our current design of the tree class requires the value object of every node to have exactly the same type, V. Perhaps this is too strict, and we should allow branches of a tree to have values that are a subtype of V instead of requiring V itself. This version of the tree class (minus the Comparable and Serializable implementation) is more flexible:

public class Tree<V> {
    // These fields hold the value and the branches
    V value;
    List<Tree<? extends V>> branches = new ArrayList<Tree<? extends V>>();

    // Here's a constructor
    public Tree(V value) { this.value = value; }

    // These are instance methods for manipulating value and branches
    V getValue() { return value; }
    void setValue(V value) { this.value = value; }
    int getNumBranches() { return branches.size(); }
    Tree<? extends V> getBranch(int n) { return branches.get(n); }
    void addBranch(Tree<? extends V> branch) { branches.add(branch); }
}

The use of bounded wildcards for the branch type allow us to add a tree<Integer>, for example, as a branch of a tree<Number>:

Tree<Number> t = new Tree<Number>(0);  // Note autoboxing
t.addBranch(new Tree<Integer>(1));     // int 1 autoboxed to Integer

If we query the branch with the getBranch( ) method, the value type of the returned branch is unknown, and we must use a wildcard to express this. The next two lines are legal, but the third is not:

Tree<? extends Number> b = t.getBranch(0);
Tree<?> b2 = t.getBranch(0);
Tree<Number> b3 = t.getBranch(0);  // compilation error

When we query a branch like this, we don't know the precise type of the value, but we do still have an upper bound on the value type, so we can do this:

Tree<? extends Number> b = t.getBranch(0);
Number value = b.getValue();

What we cannot do, however, is set the value of the branch, or add a new branch to that branch. As explained earlier in the chapter, the existence of the upper bound does not change the fact that the value type is unknown. The compiler does not have enough information to allow us to safely pass a value to setValue() or a new branch (which includes a value type) to addBranch(). Both of these lines of code are illegal:

b.setValue(3.0); // Illegal, value type is unknown
b.addBranch(new Tree<Double>(Math.PI));

This example has illustrated a typical trade-off in the design of a generic type: using a bounded wildcard made the data structure more flexible but reduced our ability to safely use some of its methods. Whether or not this was a good design is probably a matter of context. In general, generic types are more difficult to design well. Fortunately, most of us will use the preexisting generic types in the java.util package much more frequently than we will have to create our own.

4.1.4.3 Generic methods

As noted earlier, the type variables of a generic type can be used only in the instance members of the type, not in the static members. Like instance methods, however, static methods can use wildcards. And although static methods cannot use the type variables of their containing class, they can declare their own type variables. When a method declares its own type variable, it is called a generic method.

Here is a static method that could be added to the TRee class. It is not a generic method but uses a bounded wildcard much like the sumList() method we saw earlier in the chapter:

/** Recursively compute the sum of the values of all nodes on the tree */
public static double sum(Tree<? extends Number> t) {
    double total = t.value.doubleValue();
    for(Tree<? extends Number> b : t.branches) total += sum(b);
    return total;
}

This method could also be rewritten as a generic method by declaring a type variable to express the upper bound imposed by the wildcard:

public static <N extends Number> double sum(Tree<N> t) {
    N value = t.value;
    double total = value.doubleValue();
    for(Tree<? extends N> b : t.branches) total += sum(b);
    return total;
}

The generic version of sum() is no simpler than the wildcard version and the declaration of the type variable does not gain us anything. In a case like this, the wildcard solution is typically preferred over the generic solution. Generic methods are required where a single type variable is used to express a relationship between two parameters or between a parameter and a return value. The following method is an example:

// This method returns the largest of two trees, where tree size
// is computed by the sum() method.  The type variable ensures that 
// both trees have the same value type and that both can be passed to sum().
public static <N extends Number> Tree<N> max(Tree<N> t, Tree<N> u) {
    double ts = sum(t);
    double us = sum(u);
    if (ts > us) return t;
    else return u;
}

This method uses the type variable N to express the constraint that both arguments and the return value have the same type parameter and that that type parameter is Number or a subclass.

It could be argued that constraining both arguments to have the same value type is too restrictive and that we should be allowed to call the max( ) method on a tree<Integer> and a tree<Double>. One way to express this is to use two unrelated type variables to represent the two unrelated value types. Note, however, that we cannot use either variable in the return type of the method and must use a wildcard there:

public static <N extends Number, M extends Number>
    Tree<? extends Number> max(Tree<N> t, Tree<M> u) {...}

Since the two type variables N and M have no relation to each other, and since each is used in only a single place in the signature, they offer no advantage over bounded wildcards. The method is better written this way:

public static Tree<? extends Number> max(Tree<? extends Number> t,
                                         Tree<? extends Number> u) {...}

All the examples of generic methods shown here have been static methods. This is not a requirement: instance methods can declare their own type variables as well.

4.1.4.4 Invoking generic methods

When you use a generic type, you must specify the actual type parameters to be substituted for its type variables. The same is not generally true for generic methods: the compiler can almost always figure out the correct parameterization of a generic method based on the arguments you pass to the method. Consider the max() method defined above, for instance:

public static <N extends Number> Tree<N> max(Tree<N> t, Tree<N> u) {...}

You need not specify N when you invoke this method because N is implicitly specified in the values of the method arguments t and u. In the following code, for example, the compiler determines that N is Integer:

Tree<Integer> x = new Tree<Integer>(1);
Tree<Integer> y = new Tree<Integer>(2);
Tree<Integer> z = Tree.max(x, y);

The process the compiler uses to determine the type parameters for a generic method is called type inference. Type inference is relatively intuitive to understand, but the actual algorithm the compiler must use is surprisingly complex and is well beyond the scope of this book. Complete details are in Chapter 15 of The Java Language Specification, Third Edition.

Let's look at a slightly more complex version of type inference. Consider this method:

public class Util {
    /** Set all elements of a to the value v; return a. */
    public static <T> T[] fill(T[] a, T v) {
        for(int i = 0; i < a.length; i++) a[i] = v;
        return a;
    }
}

Here are two invocations of the method:

Boolean[] booleans = Util.fill(new Boolean[100], Boolean.TRUE);
Object o = Util.fill(new Number[5], new Integer(42));

In the first invocation, the compiler can easily determine that T is Boolean. In the second invocation, the compiler determines that T is Number.

In very rare circumstances you may need to explicitly specify the type parameters for a generic method. This is sometimes necessary, for example, when a generic method expects no arguments. Consider the java.util.Collections.emptySet( ) method: it returns a set with no elements, but unlike the Collections.singleton( ) method (you can look these up in the reference section), it takes no arguments that would specify the type parameter for the returned set. You can specify the type parameter explicitly by placing it in angle brackets before the method name:

Set<String> empty = Collections.<String>emptySet();

Type parameters cannot be used with an unqualified method name: they must follow a dot or come after the keyword new or before the keyword this or super used in a constructor.

It turns out that if you assign the return value of Collections.emptySet() to a variable, as we did above the type inference mechanism is able to infer the type parameter based on the variable type. Although the explicit type parameter specification in the code above can be a helpful clarification, it is not necessary and the line could be rewritten as:

Set<String> empty = Collections.emptySet();

An explicit type parameter is necessary when you use the return value of the emptySet( ) method within a method invocation expression. For example, suppose you want to call a method named printWords( ) that expects a single argument of type Set<String>. If you want to pass an empty set to this method, you could use this code:

printWords(Collections.<String>emptySet());

In this case, the explicit specification of the type parameter String is required.

4.1.4.5 Generic methods and arrays

Earlier in the chapter we saw that the compiler does not allow you to create an array whose type is parameterized. This is not, however, a restriction on all uses of arrays with generics. Consider the Util.fill() method defined above, for example. Its first argument and its return value are both of type T[]. The body of the method does not have to create an array whose element type is T, so the method is perfectly legal.

If you write a method that uses varargs (see Section 2.6.4 in Chapter 2) and a type variable, remember that invoking a varargs method performs an implicit array creation. Consider this method:

/** Return the largest of the specified values or null if there are none */
public static <T extends Comparable<T>> T max(T... values) { ...  }

You can invoke this method with parameters of type Integer because the compiler can insert the necessary array creation code for you when you call it. But you cannot call the method if you've cast the same arguments to be type Comparable<Integer> because it is not legal to create an array of type Comparable<Integer>[ ].

4.1.4.6 Parameterized exceptions

Exceptions are thrown and caught at runtime, and there is no way for the compiler to perform type checking to ensure that an exception of unknown origin matches type parameters specified in a catch clause. For this reason, catch clauses may not include type variables or wildcards. Since it is not possible to catch an exception at runtime with compile-time type parameters intact, you are not allowed to make any subclass of THRowable generic. Parameterized exceptions are simply not allowed.

You can, however, use a type variable in the throws clause of a method signature. Consider this code, for example:

public interface Command<X extends Exception> {
    public void doit(String arg) throws X;
}

This interface represents a "command": a block of code with a single string argument and no return value. The code may throw an exception represented by the type parameter X. Here is an example that uses a parameterization of this interface:

Command<IOException> save = new Command<IOException>() {
    public void doit(String filename) throws IOException {
        PrintWriter out = new PrintWriter(new FileWriter(filename));
        out.println("hello world");
        out.close();
    }
};

try { save.doit("/tmp/foo");  }
catch(IOException e) { System.out.println(e); }

4.1.5. Generics Case Study: Comparable and Enum

The new generics features in Java 5.0 are used in the Java 5.0 APIs, most notably in java.util but also in java.lang, java.lang.reflect, and java.util.concurrent. These APIs were carefully created or reviewed by the inventors of generic types, and we can learn a lot about the good design of generic types and methods through the study of these APIs.

The generic types of java.util are relatively easy: for the most part they are collections classes, and type variables are used to represent the element type of the collection. Several important generic types in java.lang are more difficult. They are not collections, and it is not immediately apparent why they have been made generic. Studying these difficult generic types gives us a deeper understanding of how generics work and introduces some concepts that we have not yet covered in this chapter. Specifically, we'll examine the Comparable interface and the Enum class (the supertype of enumerated types, described later in this chapter) and will learn about an important but infrequently used feature of generics known as lower-bounded wildcards.

In Java 5.0, the Comparable interface has been made generic, with a type variable that specifies what a class is comparable to. Most classes that implement Comparable implement it on themselves. Consider Integer:

public final class Integer extends Number implements Comparable<Integer>

The raw Comparable interface is problematic from a type-safety standpoint. It is possible to have two Comparable objects that cannot be meaningfully compared to each other. Prior to Java 5.0, the nongeneric Comparable interface was useful but not fully satisfactory. The generic version of this interface, however, captures exactly the information we want: it tells us that a type is comparable and tells us what we can compare it to.

Now consider subclasses of comparable classes. Integer is final and cannot be subclassed, so let's look at java.math.BigInteger instead:

public class BigInteger extends Number implements Comparable<BigInteger>

If we implement a BiggerInteger subclass of BigInteger, it inherits the Comparable interface from its superclass. But note that it inherits Comparable<BigInteger> and not Comparable<BiggerInteger>. This means that BigInteger and BiggerInteger objects are mutually comparable, which is usually a good thing. BiggerInteger can override the compareTo( ) method of its superclass, but it is not allowed to implement a different parameterization of Comparable. That is, BiggerInteger cannot both extend BigInteger and implement Comparable<BiggerInteger>. (In general, a class is not allowed to implement two different parameterizations of the same interface: we cannot define a type that implements both Comparable<Integer> and Comparable<String>, for example.)

When you're working with comparable objects (as you do when writing sorting algorithms, for example), remember two things. First, it is not sufficient to use Comparable as a raw type: for type safety, you must also specify what it is comparable to. Second, types are not always comparable to themselves: sometimes they're comparable to one of their ancestors. To make this concrete, consider the java.util.Collections.max() method:

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

This is a long, complex generic method signature. Let's walk through it:

  • The method has a type variable T with complicated bounds that we'll return to later.

  • The method returns a value of type T.

  • The name of the method is max( ).

  • The method's argument is a Collection. The element type of the collection is specified with a bounded wildcard. We don't know the exact type of the collection's elements, but we know that they have an upper bound of T. That is, we know that the elements of the collection are type T or a subclass of T. Any element of the collection could therefore be used as the return value of the method.

That much is relatively straightforward. We've seen upper-bounded wildcards elsewhere in this section. Now let's look again at the type variable declaration used by the max( ) method:

<T extends Comparable<? super T>>

This says first that the type T must implement Comparable. (Generics syntax uses the keyword extends for all type variable bounds, whether classes or interfaces.) This is expected since the purpose of the method is to find the "maximum" object in a collection. But look at the parameterization of the Comparable interface. This is a wildcard, but it is bounded with the keyword super instead of the keyword extends. This is a lower-bounded wildcard. ? extends T is the familiar upper bound: it means T or a subclass. ? super T is less commonly used: it means T or a superclass.

To summarize, then, the type variable declaration states "T is a type that is comparable to itself or to some superclass of itself." The Collections.min() and Collections.binarySearch( ) methods have similar signatures.

For other examples of lower-bounded wildcards (that have nothing to do with Comparable), consider the addAll(), copy( ), and fill() methods of Collections. Here is the signature for addAll():

public static <T> boolean addAll(Collection<? super T> c, T... a)

This is a varargs method that accepts any number of arguments of type T and passes them as a T[ ] named a. It adds all the elements of a to the collection c. The element type of the collection is unknown but has a lower bound: the elements are all of type T or a superclass of T. Whatever the type is, we are assured that the elements of the array are instances of that type, and so it is always legal to add those array elements to the collection.

Recall from our earlier discussion of upper-bounded wildcards that if you have a collection whose element type is an upper-bounded wildcard, it is effectively read-only. Consider List<? extends Serializable>. We know that all elements are Serializable, so methods like get() return a value of type Serializable. The compiler won't let us call methods like add() because the actual element type of the list is unknown. You can't add arbitrary serializable objects to the list because their implementing class may not be of the correct type.

Since upper-bounded wildcards result in read-only collections, you might expect lower-bounded wildcards to result in write-only collections. This isn't actually the case, however. Suppose we have a List<? super Integer>. The actual element type is unknown, but the only possibilities are Integer or its ancestors Number and Object. Whatever the actual type is, it is safe to add Integer objects (but not Number or Object objects) to the list. And, whatever the actual element type is, all elements of the list are instances of Object, so List methods like get( ) return Object in this case.

Finally, let's turn our attention to the java.lang.Enum class. Enum serves as the supertype of all enumerated types (described later). It implements the Comparable interface but has a confusing generic signature:

public class Enum<E extends Enum<E>> implements Comparable<E>, Serializable

At first glance, the declaration of the type variable E appears circular. Take a closer look though: what this signature really says is that Enum must be parameterized by a type that is itself an Enum. The reason for this seemingly circular type variable declaration becomes apparent if we look at the implements clause of the signature. As we've seen, Comparable classes are usually defined to be comparable to themselves. And subclasses of those classes are comparable to their superclass instead. Enum, on the other hand, implements the Comparable interface not for itself but for a subclass E of itself!

    Team LiB
    Previous Section Next Section