Generics allow reference types (classes, interfaces, and array types) and methods to be parameterized with type information. An abstract data type (ADT) defines both the types of objects and the operations that can be performed on these objects. Generics allow us to specify the types used by the ADT, so that the same definition of an ADT can be used on different types of objects.
Generics in Java are a way of providing type information in ADTs, so that the compiler can guarantee type-safety of operations at runtime. Generics are implemented as compile-time transformations, with negligible impact on the JVM. The generic type declaration is compiled once into a single Java class file, and the use of the generic type is checked against this file. Also, no extraneous Java class files are generated for each use of the generic type.
The primary benefits of generics are increased language expressiveness with improved type safety, resulting in improved robustness and reliability of code. Generics avoid verbosity of using casts in many contexts, thus improving code clarity. Since the compiler guarantees type-safety, this eliminates the necessity of explicit type checking and casting at runtime.
One major goal when introducing generics in Java has been backward compatibility with legacy code (i.e., non-generic code). Interoperability with legacy code and the lack of generic type information at runtime largely determine how generics work in Java. Many of the restrictions on generics in Java can be attributed to these two factors.
Generics are used extensively in implementing the Java Collections Framework. An overview of Chapter 15 on collections and maps is therefore recommended as many of the examples in this chapter make use of generic types from this framework.
Before the introduction of generics in Java, a general implementation of a collection maintained its objects in references of the type Object. The bookkeeping of the actual type of the objects fell on the client code. Example 14.1 illustrates this approach. It implements a self-referential data structure called a node. Each node holds a data value and a reference to another node. Such data structures form the basis for building linked data structures.
Example 14.1 A Legacy Class
class LegacyNode {
private Object data; // The value in the node
private LegacyNode next; // The reference to the
next node.
LegacyNode(Object data, LegacyNode next) {
this.data = data;
this.next = next;
}
public void setData(Object obj) { this.data = obj; }
public Object getData() { return this.data; }
public void setNext(LegacyNode next) { this.next = next; }
public LegacyNode getNext() { return this.next; }
public String toString() {
return this.data + (this.next == null? "" : ", " +
this.next);
}
}
The class LegacyNode can be used to create a linked list with arbitrary objects:
LegacyNode node1 = new LegacyNode(4, null); // (Integer, null)
LegacyNode node2 = new LegacyNode("July", node1); // (String, Integer, null)
Primitive values are encapsulated in corresponding wrapper objects. If we want to retrieve the data from a node, this object is returned via an Object reference:
Object obj = node2.getData();
In order to access type-specific properties or behavior of the fetched object, the reference value in the Object reference must be converted to the right type. To avoid a ClassCastException at runtime when applying the cast, we must make sure that the object referred to by the Object reference is of the right type:
if (obj instanceof String) { // Is the
object of the right type?
String str = (String) obj; // Type conversion
to the subclass String.
System.out.println(str.toUpperCase()); // Specific method in the String class.
}
The approach outlined above places certain demands on how to use the class LegacyNode to create and maintain linked structures. For example, it is the responsibility of the client code to ensure that the objects being put in nodes are of the same type. Implementing classes for specific types of objects is not a good solution. First, it can result in code duplication, and second, it is not always known in advance what types of objects will be put in the nodes. Generic types offer a better solution, where one generic class is defined and specific reference types are supplied each time we want to instantiate the class.
We first introduce the basic terminology and concepts relating to generics in Java.
A generic type is a reference type that defines a list of formal type parameters or type variables (T1, T2, ..., Tn) that must be provided before it can be used as a type. Example 14.2 declares a generic type which, in this case, is a generic class called Node<E>, that allows nodes of specific types to be maintained. It has only one formal type parameter, E, that represents the type of the data in a node.
The formal type parameter E does not explicitly specify a type, but serves as a placeholder for a type to be defined in an invocation of the generic type. The formal type parameters of a generic type are specified within angular brackets,
<>, immediately after the class name. A type parameter is an unqualified identifier. If a generic class has several formal type parameters, these are specified as a commaseparated list, <T1, T2, ..., Tn>. It is quite common to use one-letter names for formal type parameters; a convention that we will follow in this book. For example, E is used for the type of elements in a collection, K and V are used for the type of the keys and the type of the values in a map, and T is used to represent an arbitrary type.
As a starting point for declaring a generic class, we can begin with a class where the Object type is utilized to generalize the use of the class. In the declaration of the generic class Node<E> we have used E in all the places where the type Object was used in the declaration of the class LegacyNode in Example 14.1. From the declaration of the class Node<E> we can see that the formal type E is used like a reference type in the class body: as a field type (1), as a return type (5), and as a parameter type in the methods (4). Use of the class name in the generic class declaration is parameterized by the type parameter ((2), (6), (7)), with one notable exception: the formal type parameter is not specified after the class name in the constructor declaration at (3). Which actual reference type the formal type parameter E represents is not known in the generic class Node<E>. Therefore, we can only call methods that are inherited from the Object class on the field data, as these methods are inherited by all objects, regardless of their object type. One such example is the call to the toString() method in the method declaration at (8).
The scope of the type parameter E of the generic type includes any non-static inner classes, but excludes any static inner classes—the parameter E cannot be accessed in static context. It also excludes any nested generic declarations where the same name is redeclared as a formal type parameter. However, shadowing of type parameter names should be avoided.
Example 14.2 A Generic Class for Nodes
class Node<E> {
private E data; // Data (1)
private Node<E> next; // Reference to next node (2)
Node(E data, Node<E> next) { // (3)
this.data = data;
this.next = next;
}
public void setData(E data) { this.data = data; } // (4)
public E getData() { return this.data; } // (5)
public void setNext(Node<E> next) { this.next = next; } // (6)
public Node<E> getNext() { return this.next; } // (7)
public String toString() { // (8)
return this.data.toString() +
(this.next == null ? "" : ", " + this.next.
toString());
}
}
A constructor declaration in a generic class cannot specify the formal type parameters of the generic class in its constructor header after the class name:
class Node<E> {
...
Node<E>() { ... } // Compile-time error!
...
}
A formal type parameter cannot be used to create a new instance, as it is not known which concrete type it represents. The following code in the declaration of the Node<E> class would be illegal:
E ref = new E(); // Compile-time error!
A formal type parameter is a non-static type. It cannot be used in a static context, for much the same reason as an instance variable cannot be used in a static context: it is associated with objects. The compiler will report errors at (1), (2), and (3) in the code below:
class Node<E> {
public static E e1; // (1) Compile-time error!
public static E oneStaticMethod(E e2) { // (2) Compile-time error!
E e3; // (3) Compile-time error!
System.out.println(e3);
}
// ...
}
A parameterized type (also called type instance) is an invocation or instantiation of a generic type, that is a specific usage of the generic type where the formal type parameters are replaced by actual type parameters. Analogy with method declarations and method invocations can be helpful in understanding the relationship between generic types and parameterized types. We pass actual parameters in a method invocation to execute a method. In the case of a generic type invocation, we pass actual type parameters in order to instantiate a generic type.
We can declare references and create objects of parameterized types, and call methods on these objects, in much the same way as we use non-generic classes.
Node<Integer> intNode = new Node<Integer>(2008, null);
The actual type parameter Integer, explicitly specified in the declaration statement above, binds to the formal type parameter E in Example 14.2. The compiler treats the parameterized type Node<Integer> as a new type. The parameterized type Node<Integer> constrains the generic type Node<E> to Integer objects, thus implementing homogenous nodes with Integers. The reference intNode can only refer to a Node of Integer.
In the object creation expression of the new operator, the actual type parameter is mandatory after the class name, and the node created can only be used to store an object of this concrete type. Methods can be called on objects of parameterized types:
Integer iRef = intNode.getData(); // 2008
In the method call above, the actual type parameter is determined from the type of the reference used to make the call. The type of the intNode reference is Node<Integer>, therefore, the actual type parameter is Integer. The method header is Integer getData(), meaning that the method will return a value of type Integer. The compiler checks that the return value can be assigned. As the compiler guarantees that the return value will be an Integer and can be assigned, no explicit cast or runtime check is necessary. Here are some more examples of calling methods of parameterized types:
intNode.setData(2010); // Ok.
intNode.setData("TwentyTen"); // (1) Compile-time error!
intNode.setNext(new Node<Integer>(2009, null)); // (2010, (2009, null))
intNode.setNext(new Node<String>("Hi", null)); // (2) Compile-time error!
In the method calls shown above, the compiler determines that the actual type parameter is Integer. The method signatures are setData(Integer) and setNext(Node<Integer>). As expected, we get a compile-time error when we try to pass an argument that is not compatible with the parameter types in the method signatures, e.g., at (1) and (2). The parameterized types Node<Integer> and Node<String> are two unrelated types. The compiler reports any inconsistent use of a parameterized type, so that errors can be caught earlier at compile-time and use of explicit casts in the source code is minimized, as evident from (3) and (4), respectively.
Node<String> strNode = new Node<String>("hi", null);
intNode = strNode; // (3) Compile-time error!
String str = strNode.getData(); // (4) No explicit cast necessary.
Generic types also include generic interfaces, which are declared analogous to generic classes. The specification of formal type parameters in a generic interface is the same as in a generic class. Example 14.3 declares a generic interface for objects that store a data value of type E and return a reference value of type IMonoLink<E>.
Example 14.3 A Generic Interface and its Implementation
interface IMonoLink<E> {
void setData(E data);
E getData();
void setNext(IMonoLink<E> next);
IMonoLink<E> getNext();
}
class MonoNode<E> implements IMonoLink<E> {
private E data; // Data
private IMonoLink<E> next; // Reference
to next node // (1)
MonoNode(E data, IMonoLink<E> next) { // (2)
this.data = data;
this.next = next;
}
public void setData(E data) { this.data = data; }
public E getData() { return this.data; }
public void setNext(IMonoLink<E> next) { this.next = next; } // (2)
public IMonoLink<E> getNext() { return this.next; } // (3)
public String toString() {
return this.data.toString() +
(this.next == null? "" : ", " + this.next.toString());
}
}
A generic interface can be implemented by a generic (or a non-generic) class:
class MonoNode<E> implements IMonoLink<E> {
// ...
}
Note that the construct <E> is used in two different ways in the class header. The first occurrence of <E> declares E to be a type parameter, and the second occurrence of <E> parameterizes the generic interface with this type parameter. The declare-before-use rule also applies to type parameters. The version of the MonoNode class in Example 14.3 differs from the Node class in Example 14.2 at (1), (2), (3), and (4). These changes were necessary to make the MonoNode<E> class compliant with the IMonoLink<E> interface.
A generic interface can be parameterized in the same way as a generic class. In the code below, the reference strNode has the parameterized type IMonoLink<String>. It is assigned the reference value of a node of type MonoNode<String>. The assignment is legal, since the parameterized type MonoNode<String> is a subtype of the parameterized type IMonoLink<String>:
IMonoLink<String> strNode2 = new MonoNode<String>("Bye", null);
System.out.println(strNode2.getData()); // Prints: Bye
As with non-generic interfaces, generic interfaces cannot be instantiated either:
IMonoLink<String> strNode3 = new IMonoLink<String>("Bye", null); // Error!
Below is an example of a non-generic class implementing a generic interface:
class LymphNode implements IMonoLink<Lymph> {
private Lymph body;
private IMonoLink<Lymph> location;
public void setData(Lymph obj) { body = obj; }
public Lymph getData() { return body; }
public void setNext(IMonoLink<Lymph> loc) { this.location = loc; }
public IMonoLink<Lymph> getNext() { return this.location; }
}
class Lymph { /*... */ }
The generic interface IMonoLink<E> is parameterized by a concrete type, namely, Lymph. The type LymphNode is a subtype of the parameterized type IMonoLink<Lymph>, as it implements the methods of the generic interface IMonoLink<E> in accordance with the type parameter Lymph.
The Java standard library contains many examples of generic interfaces. Two of these interfaces are discussed in detail in the subsections The Comparable<E> Interface, p. 765, and The Comparator<E> Interface, p. 771.
A non-final generic type can be extended. Example 14.4 shows that the generic interface IBiLink<E> extends the generic interface IMonoLink<E>, and that the generic class BiNode<E> extends the generic class MonoNode<E> and implements the generic interface IBiLink<E> (see Figure 14.1).
interface IBiLink<E> extends IMonoLink<E> {
// ...
}
class BiNode<E> extends MonoNode<E> implements IBiLink<E> {
// ...
}
The compiler checks that the formal type parameters of the superclass in the extends clause can be resolved. In the case above, the formal type parameter E, that is specified for the subclass, is also used as the type parameter for the superclass and also to constrain the interface to the same type parameter. This dependency ensures that an invocation of the subclass will result in the same actual parameter being used by the superclass and for the interface.
BiNode<Integer> intBiNode = new BiNode<Integer>(2020, null, null);
MonoNode<Integer> intMonoNode = intBiNode; // (1)
Integer iRef = intMonoNode.getData(); // 2020
MonoNode<Number> numMonoNode = intBiNode; // (2) Compile-time error.
The assignment at (1) is type-safe, as the parameterized class BiNode<Integer> is a subtype of the parameterized class MonoNode<Integer>. It is important to note that the superclass and the subclass are parameterized with the same type parameter, otherwise the subtype relationship between the superclass and the subclass does not hold. We get a compile-time error at (2) because the parameterized class BiNode<Integer> is not a subtype of the parameterized class MonoNode<Number>. Section 14.4 provides more details on subtype relationships for generic types.
Example 14.4 Extending Generic Types
interface IBiLink<T> extends IMonoLink<T> {
void setPrevious(IBiLink<T> previous);
IBiLink<T> getPrevious();
}
class BiNode<E> extends MonoNode<E> implements IBiLink<E> {
private IBiLink<E> previous; // Reference
to previous node
BiNode(E data, IBiLink<E> next, IBiLink<E> previous) {
super(data, next);
this.previous = previous;
}
public void setPrevious(IBiLink<E> previous) { this.previous = previous; }
public IBiLink<E> getPrevious() { return this.previous; }
public String toString() {
return (this.previous == null? "" : this.previous
+ ", ") +
this.getData() +
(this.getNext() == null? "" : ", " + this.getNext());
}
}
Example 14.4 showed examples of generic types being extended to new generic subtypes. We can extend a non-generic type to a generic subtype as well:
class AbstractNode { /* ... */ } // A
non-generic supertype
class SimpleNode<E> extends AbstractNode { /* ... */ }// A
generic subtype
We can also extend concrete parameterized types to specialized non-generic subtypes:
class IntegerBiNode extends BiNode<Integer> { // A
non-generic subtype
IntegerBiNode(Integer data, IntegerBiNode next, IntegerBiNode previous) {
super(data, next, previous);
}
//...
}
Note that a subtype can inherit only one parameterization of the same generic interface supertype. Implementing or extending a parameterized type fixes the parameterization for the base type and any subtypes. In the declaration below, the subtype WeirdNode<E> tries to implement the interface IMonoLink<Integer>, but at the same time, it is a subtype of the interface IMonoLink<E> which the superclass MonoNode<E> implements:
class WeirdNode<E> extends MonoNode<E> implements IMonoLink<
Integer> { // Error!
//...
}
There is great flexibility in extending reference types, but care must be exercised to achieve the desired result.
A generic type without its formal type parameters is called a raw type. The raw type is the supertype of all parameterized types of the generic class. For example, the raw type Node is the supertype of the parameterized types Node<String>, Node<Integer>, and Node<Node<String>>. The last parameterized type is an example of a nested parameterization. It means that a node of this type has a node of type Node<String> as data.
A parameterized type (e.g., Node<String>) is not a class. Parameterized types are used by the compiler to check that objects created are used correctly in the program. The parameterized types Node<String>, Node<Integer>, Node<Node<String>> are all represented at runtime by their raw type Node. In other words, the compiler does not create a new class for each parameterized type. Only one class (Node) exists that has the name of the generic class (Node<E>), and the compiler generates only one class file (Node.class) with the Java byte code for the generic class.
Only reference types (excluding array creation and enumerations) can be used in invocations of generic types. A primitive type is not permitted as an actual type parameter, the reason being that values of primitive types have different sizes. This would require different code being generated for each primitive type used as an actual type parameter, but there is only one implementation of a generic class in Java.
Generics are implemented in the compiler only. The JVM is oblivious about the use of generic types. It does not differentiate between Node<String> and Node<Integer>, and just knows about the class Node. The compiler translates the generic class by a process known as type erasure; meaning that information about type parameters is erased and casts are inserted to make the program type-safe at runtime. The compiler guarantees that casts added at compile time never fail at runtime, when the program compiles without any unchecked warnings.
It is possible to use a generic class by its raw type only, like a non-generic class, without specifying actual type parameters for its usage. Example 14.5 illustrates mixing generic and non-generic code. The compiler will issue an unchecked warning if such a use can be a potential problem at runtime. Such usage is permitted for backward compatibility with legacy code, but is strongly advised against when writing new code. The assignment at (5) below shows that it is always possible to assign the reference value of a parameterized type to a reference of the raw type, as the latter is the supertype of the former. However, the raw type reference can be used to violate the type safety of the node at runtime, as shown at (6). Calling a method on a node using the raw type reference results in an unchecked call warning. In this particular case, a String is set as the data of an Integer node.
Node rawNode = intNode; // (5)
Assigning to raw type always possible.
rawNode.setData("BOOM"); // (6) Unchecked call warning!
Node<Integer> intNode = rawNode; // (7)
Unchecked conversion warning!
iRef = intNode.getData(); // (8) ClassCastException!
Assigning the reference value of a raw type to a reference of the parameterized type results in an unchecked conversion warning, shown at (7). If the node referenced by the raw type reference is not of the Integer type, using it as a node of Integer could lead to problems at runtime. Note that the assignment at (8) is type compatible, but its type safety is compromised by the corruption of the Integer node at runtime, resulting in a ClassCastException.
The class Preliminaries in Example 14.5 is shown compiled with the non-standard option -Xlint:unchecked. The compiler recommends using this option when nongeneric and generic code are mixed this way. The program compiles in spite of the unchecked warnings, and can be executed. But all guarantees of type-safety are off in the face of unchecked warnings.
Example 14.5 Unchecked Warnings
//A client for the generic class Node<T>.
public class Preliminaries {
public static void main(String[] args) {
Node<Integer> intNode = new Node<Integer>(2008, null);
Integer iRef = intNode.getData(); // 2008
intNode.setData(2010); // Ok.
// intNode.setData("TwentyTen"); // (1) Compile-time error!
intNode.setNext(new Node<Integer>(2009, null)); // (2010, (2009, null))
// intNode.setNext(new Node<String>("Hi", null)); // (2) Compile-time error!
Node<String> strNode = new Node<String>("hi", null);
// intNode = strNode; // (3) Compile-time error!
String str = strNode.getData(); // (4) No explicit cast necessary.
Node rawNode = intNode; // (5)
Assigning to raw type always possible.
rawNode.setData("BOOM"); // (6) Unchecked call warning!
intNode = rawNode; // (7)
Unchecked conversion warning!
iRef = intNode.getData(); // (8) ClassCastException!
}
}
Compiling the program:
>javac -Xlint:unchecked Preliminaries.java
Preliminaries.java:16: warning: [unchecked] unchecked call
to setData(E) as a
member of the raw type Node
rawNode.setData("BOOM"); // (6) Unchecked call warning!
^
Preliminaries.java:17: warning: [unchecked] unchecked
conversion
found : Node
required: Node<java.lang.Integer>
intNode = rawNode; // (7) Unchecked conversion
warning!
^
2 warnings
Running the program:
>java Preliminaries
Exception in thread "main" java.lang.
ClassCastException: java.lang.String cannot
be cast to java.lang.Integer
at Preliminaries.main(Preliminaries.java:18)
Before the introduction of generics in Java 1.5, a collection in the Java Collections Framework could hold references to objects of any type. For example, any object which is an instance of the java.lang.Object class or its subclasses could be maintained in an instance of the java.util.ArrayList class, which implements the java.util.List interface.
List wordList = new ArrayList(); // Using non-generic types.
wordList.add("two zero zero eight"); // Can add any object.
wordList.add(2004);
//...
Object element = wordList.get(0); // Always returns an Object.
//...
if (element instanceof String) { // Runtime check
to avoid ClassCastException
String strInt = (String) element; // Cast required.
//...
}
The client of a collection has to do most of the bookkeeping with regard to using the collection in a type-safe manner: which objects are put in the collection and how objects retrieved are used. Using the Object class as the element type allows the implementation of the collection class to be specific, but its use to be generic.
An ArrayList is a specific implementation of the List interface, but usage of the class ArrayList is generic with regard to any object.
Using a generic collection, the compiler provides the type-safety, and the resulting code is less verbose.
List<String> wordList = new ArrayList<String>(); // Using a specific type.
wordList.add("two zero zero eight"); // Can add strings only
wordList.add(2004); // Compile-time error!
//...
String element = wordList.get(0); // Always returns a String.
//...
Runtime checks or explicit casts are not necessary now. Generic types allow the implementation of the collection class to be generic, but its use to be specific. The generic type ArrayList<E> is a generic implementation of the List<E> interface, but now the usage of the parameterized type ArrayList<String> is specific, as it constrains the generic type ArrayList<E> to strings.
In this section, we discuss how using wildcards can increase the expressive power of generic types. But first we examine one major difference between array types and parmeterized types. The generic class Node<E> used in this subsection is defined in Example 14.2, p. 664.
The following three declarations create three nodes of Integer, Double, and Number type, respectively.
Node<Integer> intNode = new Node<Integer>(2010,null); // (1)
Node<Double> doubleNode = new Node<Double>(3.14,null); // (2)
Node<Number> numNode = new Node<Number>(2020, null); // (3)
In the declaration at (3), the formal type parameter E is bound to the actual type parameter Number, i.e., the signature of the constructor is Node(Number, Node<Number>). The signature of the constructor call is Node(Integer, null). Since the type Integer is a subtype of the type Number, and null can be assigned to any reference, the constructor call succeeds.
In the method calls at (4) and (5) below, the method signature in both cases is setData(Number). The method calls again succeed, since the actual parameters are of types Double and Integer, that are subtypes of Number:
numNode.setData(10.5); // (4)
numNode.setData(2009); // (5)
However, the following calls do not succeed:
numNode.setNext(intNode); // (6) Compile-time error!
numNode = new Node<Number>(2030, doubleNode); // (7) Compile-time error!
The actual type parameter is determined to be Number at (6). The compiler complains that the method setData(Node<Number>) is not applicable for the arguments (Node<Integer>), i.e., the method signature setData(Node<Number>) is not compatible with the method call signature setData(Node<Integer>). The compiler also complains at (7): the constructor signature Node(Number, Node<Number>) is not applicable for the arguments (Integer, Node<Double>). The problem is with the second argument at (7). We cannot pass an argument of type Node<Integer> or Node<Double> where a parameter of type Node<Number> is expected. The following assignments will also not compile:
numNode = intNode; // (8) Compile-time error!
numNode = doubleNode; // (9) Compile-time error!
The reason for the compile-time errors is that Node<Integer> and Node<Double> are not subtypes of Node<Number>, although Integer and Double are subtypes of Number. In the case of arrays, the array types Integer[] and Double[] are subtypes of the array type Number[]. The subtyping relationship between the individual types carries over to corresponding array types. This type relationship is called subtype covariance (see Figure 14.2). This relationship holds for arrays because the element type is available at runtime. If it were allowed for parameterized types at compile-time, it could lead to problems at runtime, since the element type would not be known, as it has been erased by the compiler.
numNode = intNode; // If this was allowed,
numNode.setData(25.5); // the data could be corrupted,
Integer iRef = intNode.getData(); // resulting in a ClassCastException!
Therefore, the subtype covariance relationship does not hold for parameterized types that are instantiations of the same generic type with different actual type parameters, regardless of any subtyping relationship between the actual type parameters. The actual type parameters are concrete types (e.g., Integer, Number), and, therefore, the parameterized types are called concrete parameterized types. Such parameterized types are totally unrelated. As an example from the Java Collections Framework, the parameterized type Map<String, Integer> is not a subtype of the parameterized type Map<String, Number>.
Wildcard types are type parameters defined using the wildcard symbol ?. The wildcard ? by itself represents all types. The parameterized type List<?> represents a list of all types, whereas the concrete parameterized type List<Integer> only represents a list of Integer. In other words, a wildcard type can represent many types. Therefore a parameterized type that has wildcard card types as actual type parameters can represent a family of types, in contrast to a concrete parameterized type that only represents itself. The wildcard types provided in Java represent different subtype relationships that are summarized in Table 14.1.
Wildcard types provide the solution for increased expressive power to overcome the limitations discussed earlier when using generics in Java, but introduce limitations of their own as to what operations can be carried out on an object using references of wildcard types. We will use the class Node<E> in Example 14.2 as a running example to discuss the use of wildcard types.
The wildcard type ? extends Type represents all subtypes of Type (including Type itself). The wildcard type ? extends Type is called an upper bounded wildcard with Type representing its upper bound.
The wildcard type ? extends Number denotes all subtypes of Number, and the parameterized type Node<? extends Number> denotes the family of invocations of Node<E> for types that are subtypes of Number. Figure 14.3 shows a partial type hierarchy for the parameterized type Node<? extends Number>. Note that the parameterized type Node<? extends Integer> is a subtype of the parameterized type Node<? extends Number>, since the wildcard type ? extends Integer represents all subtypes of Integer, and these are also subtypes of Number.
The wildcard type ? super Type represents all supertypes of Type (including Type itself). The wildcard type ? super Type is called a lower bounded wildcard with Type representing its lower bound.
The wildcard type ? super Integer denotes all supertypes of Integer, and the parameterized type Node<? super Integer> denotes a family of invocations of Node<E> for types that are supertypes of Integer. Figure 14.4 shows a partial type hierarchy for the parameterized type Node<? super Integer>. Note that the parameterized type Node<? super Number> is a subtype of the parameterized type Node<? super Integer>, since the wildcard type ? super Number represents all supertypes of Number, and these are also supertypes of Integer.
As mentioned earlier, the wildcard type ? represents all types. The wildcard type ? is called the unbounded wildcard, since it has no bounds as the other two wildcard types. By definition, it represents both the upper and the lower bounded wildcards for any bound.
The parameterized type Node<?> denotes the family of invocations of Node<E> for any type, i.e., denotes a Node of any kind, and is therefore the supertype of all invocations of Node<E> (see also Figure 14.5, p. 678).
When a concrete type Type is used as an actual type parameter in a parameterized type, it represents Type itself. Since Type can be any concrete type, it is called an unbounded type parameter. The concrete parameterized type Node<Integer> represents the invocation of Node<E> for the concrete actual type parameter Integer. As we have seen earlier, there is no subtype covariance relationship between concrete parameterized types, but there is such relationship between bounded parameterized types and concrete parameterized types (see also Figure 14.3 and Figure 14.4).
Let us recapitulate the basic terminology before proceeding further. A generic type can specify one or more formal type parameters. A parameterized type is an invocation of a generic type, supplying the required actual type parameters. An actual type parameter can be a wildcard type (possibly bounded) or a concrete type. A concrete type is either a non-generic type or a parameterized type that has concrete types as parameters.
Wildcards cannot be used in instance creation expressions:
Node<?> anyNode = new Node<?>(2006, null); // Compile-time error!
Node<? extends Integer> extIntNodeA
= new Node<? extends Integer>(0, null); // Compile-time error!
Node<? extends Integer> extIntNodeB = new Node<Integer>(0, null); // OK
The actual type parameter in the constructor call must be a concrete type. Creating instances of wildcard parameterized types is analogous to instantiating interface types; neither can be used in instance creation expressions.
Wildcards cannot be used in the header of reference type declarations. Supertypes in the extends and implements clauses cannot have wildcards.
class QuestionableNode<?> { /* ... */ } // Not OK.
class SubNode extends Node<?> { /* ... */ } // Not OK.
interface INode extends Comparable<? extends Node<?>> { /* ... */ } // Not OK.
However, nested wildcards are not a problem in a reference type declaration header or in an object creation expression:
class OddNode extends Node<Node<?>> implements Comparable<Node<?>> { /* ... */ }
...
Node<?> nodeOfAnyNode = new Node<Node<?>>(new Node<Integer>(2006, null), null);
A wildcard type can be used to declare parameterized references, i.e., references whose type is a wildcard parameterized type. In this section, we look at how such references are used in the following contexts: assignment between such references, and calling methods of generic types using such references. The generic class Node<E> used in this subsection is defined in Example 14.2, p. 664.
A reference of a supertype can refer to an object of a subtype, and this substitution principle applies to parameterized types as well. Assignment compatibility is according to the type hierarchy of the parameterized types. Figure 14.5 shows partial type hierarchy for selected parameterized types of the generic class Node<E>. It combines the type hierarchies from Figure 14.3 and Figure 14.4. As we would expect, widening reference conversions according to the type hierarchy are always type-safe. All but the last assignment statement in the code below are legal. The types Node<Number> and Node<Integer> are unrelated. (The notation B
<: A means B is a subtype of A.)
Node<Object> objNode;
Node<Number> numNode;
Node<Integer> intNode;
Node<? extends Number> extNumNode
= intNode; // Node<Integer> <:
Node<? extends Number>
Node<? super Integer> supIntNode
= numNode; // Node<Number>
<: Node<? super Integer>
supIntNode = objNode; // Node<Object>
<: Node<? super Integer>
numNode = intNode; // Compile-time error! Types unrelated.
In the following code, we get an error at (1) because the types Node<? extends Number> and Node<? super Number> are unrelated, but that is not the case for the types Node<? extends Object> and Node<? super Object> at (2). The family of types denoted by the type Node<? super Object> has the type Node<Object> only, which is also a subtype of the type Node<? extends Object>.
Node<? super Number> supNumNode;
Node<? extends Object> extObjNode;
Node<? super Object> supObjNode;
extNumNode = supNumNode; // (1) Compile-time error! Types unrelated.
extObjNode = supObjNode; // (2) Node<? super Object>
<: Node<? extends Object>
supObjNode = extObjNode; // (3) Compile-time error!
Narrowing reference conversion requires an explicit cast, except for the cases noted below (see also Figure 14.5). The raw type Node and the unbounded wildcard parameterized type Node<?> are essentially equivalent in this regard. Conversion between the two is type-safe:
Node rawNode;
Node<?> anyNode;
rawNode = anyNode; // Node <-- Node<?> is type-safe.
anyNode = rawNode; // Node<?>
<-- Node is type-safe.
The unbounded wildcard parameterized type Node<?> and the upper bounded wildcard parameterized type Node<? extends Object> are also essentially equivalent (see (4)), except when assigned a value of the raw type Node (see (5)).
Assigning a value of the raw type Node to a reference of the type Node<? extends Object> results in a unchecked conversion warning—which conforms to the general rule when mixing legacy and generic code: assigning the value of a raw type to a reference of a bounded wildcard parameterized type or a concrete parameterized type results in an unchecked conversion warning, as illustrated by the examples below.
extNumNode = rawNode; // Node<? extends Number>
<-- Node: Unchecked Conversion
intNode = rawNode; // Node<Integer> <-- Node:
Unchecked Conversion Warning
For a discussion of explicit casting of parameterized references, see the subsection Implications for Casting, p. 724.
Generic classes are suitable for implementing ADTs called collections (also called containers) where the element type is usually specified by a type parameter. The Java Collections Framework is a prime example of such collections. A collection usually provides two basic operations: a set operation (also called a write or put operation) to add an element to the collection, and a get operation (also called a read operation) to retrieve an element from the collection. The set operation takes a parameter of the type T, where T is a type parameter of the generic class. The get operation returns a value of the type parameter T. The class Node<E> provides these two basic operations to manipulate the data in a node:
class Node<E> {
private E data;
// ...
public void setData(E obj) { data = obj; } // (1)
public E getData() { return data; } // (2)
// ...
}
So far we have called these two methods using references of concrete parameterized types:
Node<Number> numNode = new Node<Number>(2008, null);
numNode.setData(2010); // (3) Can only set a Number.
Number data = numNode.getData(); // (4) Can only get a Number.
The actual type parameter in the above method calls is a concrete type, but what happens when we use a reference of a wildcard parameterized type that represents a family of types? For example, what if the type of the reference numNode is Node<? extends Number>. Is the method call in (3) type-safe? Is the assignment in (4) type-safe? Operations that can potentially break the type-safety are either flagged as compile-time errors or warnings. If there are warnings but no errors, the program still compiles. However, type-safety at runtime is not guaranteed.
The key to using generics in Java is understanding the implications of wildcard parameterized types in the language—and why the compiler will not permit certain operations involving wildcards, since these might break the type-safety of the program. To illustrate some of the subtleties, we compile the class in Example 14.6 successively with different headers for the method checkIt(). The parameter type is different in each method header, from (h1) to (h5). The method uses three local variables object, number and integer of type Object, Number, and Integer, respectively ((v1) to (v3)). There are three calls to the setData() method of the generic class Node<E> to set an Object, a Number, and an Integer as the data in the node referenced by the reference s0 ((s1) to (s3)). There are also three calls to the getData() method of the generic class Node<E>, assigning the return value to each of the local variables (s4) to (s6)). And finally, the last statement, (s7), tests whether the data retrieved can be put back in again.
Example 14.6 Illustrating Get and Set Operations Using Parameterized References
class WildcardAccessRestrictions {
//static void checkIt(Node s0) { // (h1)
//static void checkIt(Node<?> s0) { // (h2)
//static void checkIt(Node<? extends Number> s0) { // (h3)
//static void checkIt(Node<? super Number> s0) { // (h4)
static void checkIt(Node<Number> s0) { // (h5)
// Local variables
Object object = new Object(); // (v1)
Number number = 1.5; // (v2)
Integer integer = 10; // (v3)
// Method calls
s0.setData(object); // (s1)
s0.setData(number); // (s2)
s0.setData(integer); // (s3)
object = s0.getData(); // (s4)
number = s0.getData(); // (s5)
integer = s0.getData(); // (s6)
s0.setData(s0.getData()); // (s7)
}
}
Attempts to compile the method in Example 14.6 with different headers are shown in Table 14.2. The rows are statements from (s1) to (s7) from Example 14.6. The columns indicate the type of the parameter s0 in the method headers (h1) to (h5). The reference s0 is used to call the methods. The entry ok means the compiler did not report any errors or any unchecked warnings. The entry ! means the compiler did not report any errors but issued an unchecked call warning. The entry
× means the compiler reported an error. In other words, we cannot carry out the operations that are marked with the entry
×.
The type of the reference s0 is the raw type Node. This case illustrates the nongeneric paradigm of using a collection: we can put any object, but we can only get an Object. From Table 14.2, we see that we can put any object as data in a node of the raw type Node, but the compiler issues unchecked call warnings, as we are putting an object into a raw type node whose element type is not known. We can only get an Object, as we cannot be more specific about the data type.
The type of the reference s0 is Node<?>. The compiler determines that the actual type parameter for each method call is the wildcard ?, i.e., any type. Obviously, we cannot set any data in a node whose element type cannot be determined. It might not be type-safe. And we cannot guarantee the type of its data either, because the data type can be any type, but we can safely read it as an Object. Note that we can always write a null, as the null value can be assigned to any reference.
The type of the reference s0 is Node<? extends Number>, where Type is Number. This means that the reference s0 refers to a node containing an object whose type is either Number or a subtype of Number, but the specific (sub)type of the object cannot always be determined at compile time. Putting any object, except a null, into such a node might not be type-safe.
The code below shows what would happen if any object was allowed to be set as data in a Long node via its alias s0. If (1), (2), or (3) were allowed, we would get a ClassCastException at (4) because the data could not be assigned to a Long reference, as the type-safety of the node longNode will have been violated, either with a supertype object or an object of an unrelated type.
Long longInt = 20L;
Node<Long> longNode = new Node<Long>(longInt, null); // Node of Long, that is
Node<? extends Number> s0 = longNode;// referenced by a
Node<? extends Number> ref.
s0.setData(object); // If this was allowed, or (1)
s0.setData(number); // if this was allowed, or (2)
s0.setData(integer); // if this was allowed, (3)
longInt = longNode.getData(); // we would get an exception here. (4)
The following method call will also not compile, as the compiler cannot give any guarantees at compile time that the reference s0 will refer to a node of Long at runtime:
s0.setData(longInt); // Compile-time error!
The upper bound in the wildcard type ? extends Number is Number. Therefore, the data of the node with the wildcard type ? extends Number must be a Number (i.e., either an object of type Number or an object of a subtype of Number). Thus, we can only safely assign the reference value returned by the get operation to a reference of type Number or a supertype of Number.
Using a reference of type Node<? super Number>, where Type is Number, we can only put a Number or a subtype object of Number into the node, as such a number would also be a subtype object of any supertype of Number. Since we cannot guarantee which specific supertype of Number the node actually has, we cannot put any supertype object of Number in the node. The code below shows what would happen if an unrelated supertype object was put in as data in a Node<? super Number>. If (1) were allowed, we would get a ClassCastException at (2) because the data value (of a supertype) cannot be assigned to a Number reference (which is a subtype).
Node<Number> numNode = new Node<Number>(2008, null);
Node<? super Number> s0 = numNode;
s0.setData(object); // (1) If this was allowed,
number = numNode.getData(); // (2) we would get an exception here.
Since the type of the reference s0 is Node<? super Number>, the reference s0 can refer to a node containing an object whose type is either Number or some supertype of Number. When we get the data from such a node, we can only safely assume that it is an Object. Keeping in mind that a supertype of Number can refer to objects that are unrelated to Number (e.g., an Object reference that can refer to a String), if (3) were allowed in the code below, we would get a ClassCastException at (3):
Node<Object> objNode = new Node<Object>("Hi", null); // String as data.
Node<? super Number> s0 = objNode;
number = s0.getData(); // (3) If allowed, we would get an exception here.
object = s0.getData(); // This is always ok.
The type of the reference s0 is Node<Number>, where Type is Number. The actual type parameter for each method call is determined to be Number. Thus the type of the parameter in the setData() method and the return value of the getData() method is Number. Therefore we can pass the reference value of a Number or a subclass object of Number to the setData() method, and can assign the reference value returned by the getData() method to a reference of the type Number or a supertype of Number. In this case, we can put a Number, and get a Number.
Table 14.3 gives a summary of using parameterized references for set and get operations. If we only want to get an element of type T from a container, we can use the upper bounded wildcard ? extends T. If we only want to put an element of type T into a container, we can use the lower bounded wildcard ? super T. If we want to both get and set elements of type T in a container, we can use the unbounded type T.
In the declaration of the generic class Node<E>, the type parameter E is unbounded, i.e. it can be any reference type. However, sometimes it may necessary to restrict what type the type parameter E can represent. The canonical example is restricting that the type parameter E is Comparable<E>, so that objects can be compared.
Wildcard types cannot be used in the header of a generic class to restrict the type parameter:
class CmpNode<? extends Comparable> { ... }
// Compile-time error!
However, the type parameter can be bounded by a constraint as follows:
class CmpNode<E extends Comparable<E>> {
// E is bounded.
CmpNode(E data, CmpNode<E> next) {
super(data, next);
}
// ...
}
In the constraint <E extends Comparable<E>>, E is bounded and Comparable<E> is the upper bound. The declaration above states that the actual type parameter when we parameterize the generic class CmpNode must not only implement the Comparable interface, but the objects of the actual type parameter must be comparable to each other. This implies that the type, say A, that we can use to parameterize the generic class, must implement the parameterized interface Comparable<A>.
If we base the implementation of the CmpNode class on the generic class Node<E>, we can write the declaration as follows:
class CmpNode<E extends Comparable<E>> extends Node<E> {
// ...
}
The extends clause is used in two different ways: for the generic class CmpNode to extend the class Node<E>, and to constrain the type parameter E of the generic class CmpNode to the Comparable<E> interface. Although the type parameter E must implement the interface Comparable<E>, we do not use the keyword implements in a constraint. Neither can we use the super clause to constrain the type parameter of a generic class.
If we want CmpNodes to have a natural ordering based on the natural ordering of their data values, we can declare the generic class CmpNode as follows:
class CmpNode<E extends Comparable<E>> extends Node<E>
implements
Comparable<CmpNode<E>> {
CmpNode(E data, CmpNode<E> next) {
super(data, next);
}
public int compareTo(CmpNode<E> node2) {
return this.getData().compareTo(node2.getData());
}
}
Note how the Comparable interface is parameterized in the implements clause. The constraint <E extends Comparable<E>> specifies that the type parameter E is Comparable, and the clause implements Comparable<CmpNode<E>> specifies that the generic class CmpNode is Comparable.
Here are some examples of how the generic class CmpNode can be parameterized:
CmpNode<Integer> intCmpNode = new CmpNode<Integer>(2020, null); // (1)
CmpNode<Number> numCmpNode = new CmpNode<Number>(2020, null); // (2) Error!
CmpNode<Integer> intCmpNode2 = new CmpNode<Integer>(2010, null);
int result = intCmpNode.compareTo(intCmpNode2);
The actual type parameter Integer in (1) implements Comparable<Integer>, but the actual type parameter Number in (2) is not Comparable. In the invocation CmpNode<A>, the compiler ensures that A implements Comparable<A>.
A bounded type parameter can have multiple bounds, B1 & B2 & ... & Bn, which must be satisfied by the actual type parameter:
class CmpNode<T extends Number & Serializable> ...
An extra bound, the Serializable interface, has been added using the ampersand (&). The formal type parameter T is a subtype of both Number and Serializable, and represents both of these concrete types in the body of the generic class. The constraint above will only allow the generic type to be parameterized by an actual type parameter which is a subtype of both Number and Serializable.
We can add as many bounds as necessary. A type parameter E having multiple bounds is a subtype of all of the types denoted by the individual bounds. A bound can be a parameterized type, as in the following generic class header:
class CmpNode<E extends Comparable<E> & Serializable> ...
If the raw type of a bound is a (non-final) superclass of the bounded type parameter, it can only be specified as the first bound and there can only be one such bound (as a subclass can only extend one immediate superclass). The raw type of an individual bound cannot be used with different type arguments, since a type parameter cannot be the subtype of more than one bound having the same raw type. In the class header below, whatever E is, it cannot be a subtype of two parameterizations of the same interface type (i.e., Comparable) at the same time:
class CmpNode<E extends Comparable<E> & Serializable &
Comparable<String>> //Error
If the type parameter has a bound, methods of the bound can be invoked on instances of the type parameter in the generic class. Otherwise, only methods from the Object class can be invoked on instances of the type parameter. In the declaration of the generic class Node<E> in Example 14.2, we cannot call any methods on instances of the type parameter except for those in the Object class, because the type parameter is unbounded. Since the instances of the type parameter E are guaranteed to be Comparable<E> in the generic class CmpNode, we can call the method compareTo() of the Comparable interface on these instances.
Review Questions
14.1 What will be the result of attempting to compile and run the following code?
public class RQ100_50 {
public static void main(String[] args) {
List<Integer> lst = new ArrayList<Integer>(); // (1)
lst.add(2007);
lst.add(2008);
List<Number> numList = lst; // (2)
for(Number n : numList) // (3)
System.out.println(n + " ");
}
}
Select the one correct answer.
(a) The code will fail to compile because of an error in (1).
(b) The code will fail to compile because of an error in (2).
(c) The code will fail to compile because of an error in (3).
(d) The code will compile, but throw a ClassCastException at runtime in (2).
(e) The code will compile and will print "2007 2008", when run.
14.2 What will be the result of attempting to compile and run the following code?
class Fruit {}
class Apple extends Fruit {}
class Orange extends Fruit {}
public class RQ100_60 {
public static void main(String[] args) {
ArrayList<Apple> aList = new ArrayList<Apple>();
aList.add(new Apple());
ArrayList bList = aList; // (1)
ArrayList<Orange> oList = bList; // (2)
oList.add(new Orange());
System.out.println(aList);
}
}
Select the one correct answer.
(a) The code will fail to compile because of errors in (1) and (2).
(b) The code will fail to compile because of an error in (1).
(c) The code will fail to compile because of an error in (2).
(d) The code will compile with an unchecked warning in both (1) and (2).
(e) The code will compile with an unchecked warning in (1).
(f) The code will compile with an unchecked warning in (2).
(g) The code will compile without warnings, but throw a ClassCastException at runtime in (2).
(h) The code will compile without warnings and will print "[Apple@hhhhhh, Orange@HHHHHHH]", when run. (hhhhhh and HHHHHHH represent some hash code.)
14.3 What will be the result of attempting to compile and run the following code?
public class RQ100_40 {
public static void main(String[] args) {
List <? super Integer> sList = new ArrayList<Number>(); //(1)
int i = 2007;
sList.add(i);
sList.add(++i); //(2)
Number num = sList.get(0); //(3)
}
}
Select the one correct answer.
(a) The code will fail to compile because of an error in (1).
(b) The code will fail to compile because of an error in (2).
(c) The code will fail to compile because of an error in (3).
(d) The code will compile, but throw a ClassCastException at runtime at (3).
(e) The code will compile and execute normally.
14.4 What will be the result of attempting to compile the following code?
public class RQ100_70 {
public static void main(String[] args) {
List<Integer> glst1 = new ArrayList(); //(1)
List nglst1 = glst1; //(2)
List nglst2 = nglst1; //(3)
List<Integer> glst2 = glst1; //(4)
}
}
Select the one correct answer.
(a) The code will compile without any warnings.
(b) The code will compile with an unchecked warning in (1).
(c) The code will compile with an unchecked warning in (2).
(d) The code will compile with an unchecked warning in (3).
(e) The code will compile with an unchecked warning in (4).
14.5 Which occurrences of the type parameter T are illegal?
public class Box<T> {
private T item; // (1)
private static T[] storage = new T[100]; // (2)
public Box(T item) { this.item = item; } // (3)
public T getItem() { return item; } // (4)
public void setItem(T newItem) { item = newItem; } // (5)
public static void getAllItems(T newItem) { // (6)
T temp; // (7)
}
}
Select the three correct answers.
(a) Occurrence of the type parameter T in (1).
(b) Occurrences of the type parameter T in (2).
(c) Occurrence of the type parameter T in (3).
(d) Occurrence of the type parameter T in (4).
(e) Occurrence of the type parameter T in (5).
(f) Occurrence of the type parameter T in (6).
(g) Occurrence of the type parameter T in (7).
14.6 Which statements are true about the following code?
Select the one correct answer.
(a) The compiler will report errors in the code.
(b) The code will compile with an unchecked warning in (1).
(c) The code will compile with an unchecked warning in (2).
(d) The code will compile with an unchecked warning in (3).
(e) The code will compile without unchecked warnings.
14.7 Which declarations will compile without warnings?
Select the four correct answers.
(a) Map<Integer, Map<Integer, String>> map1
= new HashMap<Integer, HashMap<Integer, String>>();
(b) Map<Integer, HashMap<Integer, String>> map2
= new HashMap<Integer, HashMap<Integer, String>>();
(c) Map<Integer, Integer> map3 = new HashMap<Integer, Integer>();
(d) Map<? super Integer, ? super Integer> map4
= new HashMap<? super Integer, ? super Integer>();
(e) Map<? super Integer, ? super Integer> map5 = new HashMap<Number,
Number>();
(f) Map<? extends Number, ? extends Number> map6
= new HashMap<Number, Number>();
(g) Map <?,?> map7 = new HashMap<?,?>();
14.8 Which statement is true about the following code?
class Fruit {}
class Apple extends Fruit {}
public class RQ100_15 {
public static void main(String[] args) {
List<? extends Apple> lst1 = new ArrayList<Fruit>(); // (1)
List<? extends Fruit> lst2 = new ArrayList<Apple>(); // (2)
List<? super Apple> lst3 = new ArrayList<Fruit>(); // (3)
List<? super Fruit> lst4 = new ArrayList<Apple>(); // (4)
List<?> lst5 = lst1; // (5)
List<?> lst6 = lst3; // (6)
List lst7 = lst6; // (7)
List<?> lst8 = lst7; // (8)
}
}
Select the one correct answer.
(a) (1) will compile, but (2) will not.
(b) (3) will compile, but (4) will not.
(c) (5) will compile, but (6) will not.
(d) (7) will compile, but (8) will not.
(e) None of the above.
14.9 Which statements can be inserted at (1) without the compiler reporting any errors?
public class RQ100_12 {
public static void main(String[] args) {
List lst = new ArrayList<String>();
// (1) INSERT HERE
}
}
Select the four correct answers.
(a) lst.add(null);
(b) lst.add("OK");
(c) lst.add(2007);
(d) String v1 = lst.get(0);
(e) Object v2 = lst.get(0);
14.10 Which declaration can be inserted at (1) so that the program compiles without errors?
public class RQ100_84 {
// (1) INSERT DECLARATION HERE...
public long getNum(String name) {
Long number = accounts.get(name);
return number == null ? 0 : number;
}
public void setNum(String name, long number) {
accounts.put(name, number);
}
}
Select the one correct answer.
(a) private Map<String, long> accounts = new HashMap<String, long>();
(b) private Map<String, Long> accounts = new HashMap<String, Long>();
(c) private Map<String<Long>> accounts = new HashMap<String<Long>>();
(d) private Map<String, Long> accounts = new Map<String, Long>();
(e) private Map accounts = new HashMap();
14.11 What will be the result of attempting to compile and run the following code?
public class RQ100_11 {
public static void main(String[] args) {
Set set = new TreeSet<String>();
set.add("one");
set.add(2);
set.add("three");
System.out.println(set);
}
}
Select the one correct answer.
(a) The program does not compile.
(b) The program compiles with unchecked warnings and prints the elements in the set.
(c) The program compiles without unchecked warnings and prints the elements in the set.
(d) The program compiles with unchecked warnings and throws an exception at runtime.
(e) The program compiles without unchecked warnings and throws an exception at runtime.
14.12 What will be the result of attempting to compile the following code?
class Vehicle { }
class Car extends Vehicle { }
class Sedan extends Car { }
class Garage<V> {
private V v;
public V get() { return this.v; }
public void put(V v) { this.v = v; }
}
public class GarageAdmin {
private Object object = new Object();
private Vehicle vehicle = new Vehicle();
private Car car = new Car();
private Sedan sedan = new Sedan();
public void doA(Garage g) {
g.put(object); // (1)
g.put(vehicle); // (2)
g.put(car); // (3)
g.put(sedan); // (4)
object = g.get(); // (5)
vehicle = g.get(); // (6)
car = g.get(); // (7)
sedan = g.get(); // (8)
}
}
Select the two correct answers.
(a) The call to the put() method in statements (1) - (4) will compile.
(b) The assignment statement (5) will compile.
(c) The assignment statements (6), (7), and (8) will compile.
14.13 What will be the result of attempting to compile the following code?
class Vehicle { }
class Car extends Vehicle { }
class Sedan extends Car { }
class Garage<V> {
private V v;
public V get() { return this.v; }
public void put(V v) { this.v = v; }
}
public class GarageAdmin {
private Object object = new Object();
private Vehicle vehicle = new Vehicle();
private Car car = new Car();
private Sedan sedan = new Sedan();
public void doB(Garage<Car> g) {
g.put(object); // (1)
g.put(vehicle); // (2)
g.put(car); // (3)
g.put(sedan); // (4)
object = g.get(); // (5)
vehicle = g.get(); // (6)
car = g.get(); // (7)
sedan = g.get(); // (8)
}
}
Select the two correct answers.
(a) The call to the put() method in statements (1) - (2) will compile.
(b) The call to the put() method in statements (3) - (4) will compile.
(c) The assignment statements (5), (6) and (7) will compile.
(d) The assignment statement (8) will compile.
14.14 What will be the result of attempting to compile the following code?
class Vehicle { }
class Car extends Vehicle { }
class Sedan extends Car { }
class Garage<V> {
private V v;
public V get() { return this.v; }
public void put(V v) { this.v = v; }
}
public class GarageAdmin {
private Object object = new Object();
private Vehicle vehicle = new Vehicle();
private Car car = new Car();
private Sedan sedan = new Sedan();
public void doC(Garage<?> g) {
g.put(object); // (1)
g.put(vehicle); // (2)
g.put(car); // (3)
g.put(sedan); // (4)
object = g.get(); // (5)
vehicle = g.get(); // (6)
car = g.get(); // (7)
sedan = g.get(); // (8)
}
}
Select the one correct answer.
(a) The call to the put() method in statements (1) - (2) will compile.
(b) The call to the put() method in statements (3) - (4) will compile.
(c) The assignment statement (5) will compile.
(d) The assignment statements (6), (7), and (8) will compile.
14.15 What will be the result of attempting to compile the following code?
class Vehicle { }
class Car extends Vehicle { }
class Sedan extends Car { }
class Garage<V> {
private V v;
public V get() { return this.v; }
public void put(V v) { this.v = v; }
}
public class GarageAdmin {
private Object object = new Object();
private Vehicle vehicle = new Vehicle();
private Car car = new Car();
private Sedan sedan = new Sedan();
public void doD(Garage<? extends Car> g) {
g.put(object); // (1)
g.put(vehicle); // (2)
g.put(car); // (3)
g.put(sedan); // (4)
object = g.get(); // (5)
vehicle = g.get(); // (6)
car = g.get(); // (7)
sedan = g.get(); // (8)
}
}
Select the one correct answer.
(a) The call to the put() method in statements (1) - (2) will compile.
(b) The call to the put() method in statements (3) - (4) will compile.
(c) The assignment statements (5), (6), and (7) will compile.
(d) The assignment statement (8) will compile.
14.16 What will be the result of attempting to compile the following code?
class Vehicle { }
class Car extends Vehicle { }
class Sedan extends Car { }
class Garage<V> {
private V v;
public V get() { return this.v; }
public void put(V v) { this.v = v; }
}
public class GarageAdmin {
private Object object = new Object();
private Vehicle vehicle = new Vehicle();
private Car car = new Car();
private Sedan sedan = new Sedan();
public void doE(Garage<? super Car> g) {
g.put(object); // (1)
g.put(vehicle); // (2)
g.put(car); // (3)
g.put(sedan); // (4)
object = g.get(); // (5)
vehicle = g.get(); // (6)
car = g.get(); // (7)
sedan = g.get(); // (8)
}
}
Select the two correct answers.
(a) The call to the put() method in statements (1) - (2) will compile.
(b) The call to the put() method in statements (3) - (4) will compile.
(c) The assignment statement (5) will compile.
(d) The assignment statements (6), (7), and (8) will compile.
14.17 Given the following class declaration:
class ClassA<U> implements Comparable<U> {
public int compareTo(U a) { return 0; }
}
Which class declarations below will compile without errors?
Select the three correct answers.
(a) class ClassB<U,V> extends ClassA<R> {}
(b) class ClassC<U,V> extends ClassA<U>
{}
(c) class ClassD<U,V> extends ClassA<V, U> {}
(d) class ClassE<U> extends ClassA<Comparable<Number>> {}
(e) class ClassF<U extends Comparable<U> & Serializable> extends ClassA<Number> {}
(f) class ClassG<U implements Comparable<U>> extends ClassA<Number> {}
(g) class ClassH<U extends Comparable<U>> extends ClassA<? extends Number> {}
(h) class ClassI<U extends String & Comparable<U>> extends ClassA<U>
{}
(i) class ClassJ<U> extends ClassA<Integer> implements Comparable<Number>{}
The Node<E> class from Example 14.2, p. 664, can be used to implement linked data structures. Example 14.7 is an implementation of a simplified generic stack. The emphasis is not on how to develop a full-blown, industrial-strength implementation, but on how to present a simple example in the context of this book in order to become familiar with code that utilizes generics. For thread-safety issues concerning a stack, see the subsection Waiting and Notifying, p. 640, in Chapter 13, on threads.
The class MyStack<E> implements the interface IStack<E> shown in Example 14.7, and uses the class Node<E> from Example 14.2. The class NodeIterator<E> in Example 14.7 provides an iterator to traverse linked nodes. The class MyStack<E> is Iterable<E>, meaning we can use the for(:) loop to traverse a stack of this class (see (9) and (12)). It is instructive to study the code to see how type parameters are used in various contexts, how the iterator is implemented, and how we can use the for(:) loop to traverse a stack. For details on the Iterable<E> and Iterator<E> interfaces, see the subsection Iterators, p. 785, in Chapter 15.
Example 14.7 Implementing a Simplified Generic Stack
import java.util.Iterator;
/** Interface of a generic stack */
public interface IStack<E> extends Iterable<E> {
void push(E element); // Add the element to the top
of the stack
E pop(); // Remove the element at the
top of the stack.
E peek(); // Get the element at the
top of the stack.
int size(); // No. of elements on the stack.
boolean isEmpty(); // Determine if the stack is empty.
boolean isMember(E element); // Determine if the element is in the stack.
E[] toArray(E[] toArray); // Copy elements from stack to array
String toString(); // Return suitable string representation of
// elements on the stack:
(e1, e2, ..., en)
}
_____________________________________________________
import java.util.Iterator;
import java.util.NoSuchElementException;
/** Simplified implementation of a generic stack */
public class MyStack<E> implements IStack<E> { // (1)
// Top of stack.
private Node<E> tos; // (2)
// Size of stack
private int numOfElements; // (3)
public boolean isEmpty() { return tos == null; } // (4)
public int size() { return numOfElements; } // (5)
public void push(E element) { // (6)
tos = new Node<E>(element, tos);
++numOfElements;
}
public E pop() { // (7)
if (!isEmpty()) {
E data = tos.getData();
tos = tos.getNext();
--numOfElements;
return data;
}
throw new NoSuchElementException("No elements.");
}
public E peek() { // (8)
if (!isEmpty()) return tos.getData();
throw new NoSuchElementException("No elements.");
}
// Membership
public boolean isMember(E element) { // (9)
for (E data : this)
if (data.equals(element))
return true; // Found.
return false; // Not found.
}
// Get iterator.
public Iterator<E> iterator() { // (10)
return new NodeIterator<E>(this.tos);
}
// Copy to array as many elements as possible.
public E[] toArray(E[] toArray) { // (11)
Node<E> thisNode = tos;
for (int i = 0; thisNode != null && i < toArray.length; i++) {
toArray[i] = thisNode.getData();
thisNode = thisNode.getNext();
}
return toArray;
}
// String representation: (e1, e2, ..., en).
public String toString() { // (12)
StringBuilder rep = new StringBuilder("(");
for (E data : this)
rep.append(data + ", ");
if (!isEmpty()) {
int len = rep.length();
rep.delete(len - 2, len);
}
rep.append(")");
return rep.toString();
}
}
_____________________________________________________
import java.util.Iterator;
/** Iterator for nodes */
public class NodeIterator<E> implements Iterator<E> {
private Node<E> thisNode;
public NodeIterator(Node<E> first) { thisNode = first; }
public boolean hasNext() { return thisNode != null; }
public E next() {
E data = thisNode.getData();
thisNode = thisNode.getNext();
return data;
}
public void remove() { throw new UnsupportedOperationException(); }
}
We first look at how generic methods and constructors are declared, and then at how they can be called—both with and without explicit actual type parameters.
To facilitate experimenting, the code snippets used in this subsection have been collected in Example 14.8.
Example 14.8 Declaring and Calling Generic Methods
public class Utilities {
// The key and the array element type can be any type.
static boolean containsV1(Object key, Object[] array) { // (1) Non-generic
// version
for(Object element : array)
if(key.equals(element)) return true;
return false;
}
// The key and the array element type are the same.
static <E> boolean containsV2(E key, E[] array) { // (2) Generic version
for(E element : array)
if(key.equals(element)) return true;
return false;
}
// The type of the key is a subtype of the array element type.
static <E, K extends E> boolean containsV3(K key, E[] array) {
for(E element : array)
if(key.equals(element)) return true;
return false;
}
public static void main(String[] args) {
Integer[] intArray = {10, 20, 30};
// (1) E is Integer.
// Method signature: containsV2(Integer, Integer[])
// Method call signature: containsV2(Integer, Integer[])
assert Utilities.<Integer>containsV2(20, intArray) == true;
// (2) E is Number.
// Method signature: containsV2(Number, Number[])
// Method call signature: containsV2(Double, Integer[])
assert Utilities.<Number>containsV2(30.5, intArray) == false;
// (3) E is Comparable<Integer>.
// Method signature: containsV2(Comparable<Integer>,
// Comparable<Integer>[])
// Method call signature: containsV2(Integer, Integer[]).
assert Utilities.<Comparable<Integer>> containsV2(20, intArray) == true;
// (4) E is Integer.
// Method signature: containsV2(Integer, Integer[])
// Method call signature: containsV2(Double, Integer[])
// assert Utilities.<Integer>containsV2(30.5, intArray) == false; // Error!
// assert <Integer>containsV2(20, intArray) == true; // (5) Syntax error
// (6) E is inferred to be Integer.
// Method signature: containsV2(Integer, Integer[])
// Method call signature: containsV2(Integer, Integer[])
assert Utilities.containsV2(20, intArray) == true;
// (7) E is inferred to be ? extends Number.
// Method signature: containsV2(? extends Number, ? extends Number[])
// Method call signature: containsV2(Double, Integer[])
assert Utilities.containsV2(30.5, intArray) == false;
// (8) E is inferred to be ? extends Object.
// Method signature: containsV2(? extends Object, ? extends Object[])
// Method call signature: containsV2(String, Integer[])
assert Utilities.containsV2("Hi", intArray) == false;
// Method signature: containsV2(Integer, Integer[])
// Method call signature: containsV2(String, Integer[])
// assert Utilities.<Integer>containsV2("Hi", intArray) == false;// (9) Error!
// assert Utilities.containsV3("Hi", intArray) == false; // (10) Error!
// assert Utilities.containsV3(30.5, intArray) == false; // (11) Error!
// (12) E is Number. K is Number. The constraint
(K extends E) is satisfied.
// Method signature: containsV3(Number, Number[])
// Method call signature: containsV3(Double, Integer[])
assert Utilities.<Number, Number>containsV3(30.0, intArray) == false;
// (13) E is Integer. K is Number.
// The constraint (K extends E) is not satisfied.
// assert Utilities.<Integer, Number>
// containsV3(30.5, intArray) == false; // Compile-time Error!
// (14) E is Number. K is Integer. The constraint
(K extends E) is satisfied.
// Method signature: containsV3(Integer, Number[])
// Method call signature: containsV3(Double, Integer[])
// assert Utilities.<Number, Integer>
// containsV3(30.5, intArray) == false; // Compile-time Error!
// (15) Incorrect no. of type parameters.
// assert Utilities.<Number> containsV3(30.5, intArray) == false; // Error!
}
}
A generic method (also called polymorphic method) is implemented like an ordinary method, except that one or more formal type parameters are specified immediately preceding the return type. In the case of a generic constructor, the formal parameters are specified before the class name in the constructor header. Much of what applies to generic methods in this regard, also applies to generic constructors.
The method containsV1() at (1) below is a non-generic method to determine the membership of an arbitrary key in an arbitrary array of objects. (We will declare all static generic methods in a class called Utilities, unless otherwise stated.)
static boolean containsV1(Object key, Object[] array) { // (1) Non-generic version
for(Object element : array)
if(key.equals(element)) return true;
return false;
}
The method declaration at (1) is too general in the sense that it does not express any relationship between the key and the array. This kind of type dependency between parameters can be achieved by using generic methods. The method containsV2() at (2) below is a generic method to determine the membership of a key of type E in an array of type E. The type Object in (1) has been replaced by the type parameter E in (2), with the formal type parameter E being specified before the return type, in the same way as for a generic type.
static <E> boolean containsV2(E key, E[] array) { // (2) Generic version
for(E element : array)
if(key.equals(element)) return true;
return false;
}
As with the generic types, a formal type parameter can have a bound, which is a type (i.e., not a type parameter). A formal type parameter can be used in the return type, the formal parameter list, and the method body. It can also be used to specify bounds in the formal type parameter list.
A generic method need not be declared in a generic type. If declared in a generic type, a generic instance method can also use the type parameters of the generic type, as any other non-generic instance methods of the generic type. A generic static method is only able to use it own type parameters.
Given the following class declaration:
public class Utilities {
static <E_1,..., E_k> void genericMethod(P_1 p_1,..., P_m p_m) { ... }
// ...
}
Note that in the method declaration above, a type P_i may or may not be from the list of type variables E_1, ..., E_k. We can the call the method in various ways. One main difference from calling a non-generic method is that the actual type parameters can be specified before the method name in the call to a generic method. In the method calls shown below, <A_1,..., A_k> are the actual type parameters and (a_1,..., a_m) are the actual arguments. The specification <A_1,..., A_k> of the actual type parameters, if specified, must be in its entirety. If the specification of the actual type parameters is omitted, then the compiler infers the actual type parameters.
The following method calls can occur in any static or non-static context where the class Utilities is accessible:
Utilities ref;
ref.<A_1,..., A_k>genericMethod(a_1,..., a_m);
Utilities.<A_1,..., A_k>genericMethod(a_1,..., a_m);
The following method calls can only occur in a non-static context of the class Utilities:
this.<A_1,..., A_k>genericMethod(a_1,..., a_m); // Non-static context
super.<A_1,..., A_k>genericMethod(a_1,..., a_m); // Non-static context
Utilities.super.<A_1,..., A_k>genericMethod(a_1,..., a_m); // Non-static context
Another difference from calling non-generic methods is that, if the actual type parameters are explicitly specified, the syntax of a generic static method call requires an explicit reference, or the raw type. When the actual type parameters are not explicitly specified, the syntax of a generic method call is similar to that of a non-generic method call.
Here are some examples of calls to the containsV2() method (declared above at (2)) where the actual parameter is specified explicitly. We can see from the method signature and the method call signature that the method can be applied to the arguments in (1), (2), and (3), but not in (4). In (5) we must specify a reference or the class name, because the actual type parameter is specified explicitly.
Integer[] intArray = {10, 20, 30};
// (1) E is Integer.
// Method signature: containsV2(Integer, Integer[])
// Method call signature: containsV2(Integer, Integer[])
assert Utilities.<Integer>containsV2(20, intArray) == true;
// (2) E is Number.
// Method signature: containsV2(Number, Number[])
// Method call signature: containsV2(Double, Integer[])
assert Utilities.<Number>containsV2(30.5, intArray) == false;
// (3) E is Comparable<Integer>.
// Method signature: containsV2(Comparable<Integer>, Comparable<Integer>[])
// Method call signature: containsV2(Integer, Integer[])
assert Utilities.<Comparable<Integer>> containsV2(20, intArray) == true;
// (4) E is Integer.
// Method signature: containsV2(Integer, Integer[])
// Method call signature: containsV2(Double, Integer[])
assert Utilities.<Integer>containsV2(30.5, intArray) == false; // Error!
assert <Integer>containsV2(20, intArray) == true; // (5) Syntax error
Here are some examples of calls where the compiler infers the actual type parameters from the method call. Since both the key and the element type are Integer, the compiler infers that the actual type parameter is Integer at (6). In (7), where the key type is Double and the element type is Integer, the compiler infers the actual type parameter to be some subtype of Number, i.e., the first common supertype of Double and Integer. In (8), the compiler infers the actual type parameter to be some subtype of Object. In all cases below, the method is applicable to the arguments.
// (6) E is inferred to be Integer.
// Method signature: containsV2(Integer, Integer[])
// Method call signature: containsV2(Integer, Integer[])
assert Utilities.containsV2(20, intArray) == true;
// (7) E is inferred to be ? extends Number.
// Method signature: containsV2(? extends Number, ? extends Number[])
// Method call signature: containsV2(Double, Integer[])
assert Utilities.containsV2(30.5, intArray) == false;
// (8) E is inferred to be ? extends Object.
// Method signature: containsV2(? extends Object, ? extends Object[])
// Method call signature: containsV2(String, Integer[])
assert Utilities.containsV2("Hi", intArray) == false;
In (8), if we had specified the actual type parameter explicitly to be Integer, the compiler would flag an error:
// Method signature: containsV2(Integer, Integer[])
// Method call signature: containsV2(String, Integer[])
assert Utilities.<Integer>containsV2("Hi", intArray) == false; // (9) Error!
We can explicitly specify the key type to be a subtype of the element type by introducing a new formal parameter and a bound on the key type:
The following calls at (10) and (11) now result in a compile-time error, as the key type is not a subtype of the element type:
assert Utilities.containsV3("Hi", intArray) == false; // (10) Compile-time error!
assert Utilities.containsV3(30.5, intArray) == false; // (11) Compile-time error!
The examples below illustrate how constraints come into play in method calls. In (12) the constraint is satisfied and the method signature is applicable to the arguments. In (13) the constraint is not satisfied, therefore the call is rejected. In (14) the constraint is satisfied, but the method signature is not applicable to the arguments. The call in (15) is rejected because the number of actual type parameters specified in the call is incorrect.
// (12) E is Number. K is Number. The constraint (K extends E)
is satisfied.
// Method signature: containsV3(Number, Number[])
// Method call signature: containsV3(Double, Integer[])
assert Utilities.<Number, Number>containsV3(30.0, intArray) == false;
// (13) E is Integer. K is Number. The constraint (K extends E)
is not satisfied.
assert Utilities.<Integer, Number>
containsV3(30.5, intArray) == false; // Compile-time Error!
// (14) E is Number. K is Integer. The constraint (K extends E)
is satisfied.
// Method signature: containsV3(Integer, Number[])
// Method call signature: containsV3(Double, Integer[])
assert Utilities.<Number, Integer>
containsV3(30.5, intArray) == false; // Compile-time Error!
// (15) Incorrect no. of type parameters.
assert Utilities.<Number> containsV3(30.5, intArray) == false; // Error!
We cannot change the order of the formal type parameters in the formal type parameter specification, as shown below. This is an example of an illegal forward reference to a formal type parameter. The type parameter E is used in the constraint (K extends E), but has not yet been declared.
static <K extends E, E> // Illegal
forward reference.
boolean containsV3(K key, E[] array) { ... }
Typically, the dependencies among the parameters of a method and its return type are expressed by formal parameters. Here are some examples:
public static <K,V> Map<V,List<K>> toMultiMap(Map<K,V> origMap) { ... } // (16)
public static <N> Set<N> findVerticesOnPath(Map<N,Collection<N>> graph,
N startVertex) { ... } // (17)
The method header at (16) expresses the dependency that the map returned by the method has the values of the original map as keys, and its values are lists of keys of the original map, i.e. the method creates a multimap. In the method header at (17), the type parameter N specifies that the element type of the set of vertices to be returned, the type of the keys in the map, the element type of the collections that are values of the map, and the type of the start vertex, are the same.
As we have seen, a wildcard can represent a family of types. However, the compiler needs to have a more concrete notion of a type than a wildcard in order to do the necessary type checking. Internally, the compiler represents the wildcard by some anonymous, but specific, type. Although this type is unknown, it belongs to the family of types represented by the wildcard. This specific, but unknown, type is called the capture of the wildcard.
Compiler messages about erroneous usage of wildcards often refer to the capture of a wildcard. Here are some examples of such error messages, based on compiling the following code:
// Filename: WildcardCapture.java
...
Node<?> anyNode; // (1)
Node<? super Number> supNumNode; // (2)
Node<Integer> intNode = anyNode; // (3) Compile-time error!
Node<? extends Number> extNumNode = supNumNode; // (4) Compile-time error!
anyNode.setData("Trash"); // (5) Compile-time error!
The assignment at (3) results in the following error message:
WildcardCapture.java:9: incompatible types
found : Node<capture#10 of ?>
required: Node<java.lang.Integer>
Node<Integer> intNode = anyNode; // (3) Compile-time error!
^
The type of the reference anyNode is Node<capture#10 of ?>. The string
“capture#10 of ?” is the designation used by the compiler for the type capture of the wildcard (?) at (3). The number 10 in “capture#10 of
?” distinguishes it from the type capture of any other occurrences of wildcards in the statement. The type of the reference intNode is Node<Integer>. The reference value of a Node<capture#10 of ?> cannot be assigned to a Node<Integer> reference. Whatever the type capture of the wildcard is, it cannot be guaranteed to be Integer, and the assignment is rejected. To put it another way, the assignment involves a narrowing reference conversion, requiring an explicit cast which is not provided: Node<?> is the supertype of all invocations of the generic class Node<E>.
The error message below for the assignment at (4) shows the type capture of the lower bounded wildcard at (4) to be "capture#311 of ? super java.lang.Number". Figure 14.5, p. 678, also shows that the Node<capture#311 of ? super java.lang.Number> and Node<? extends java.lang.Number> types are unrelated.
The method call at (5) results in the following error message:
WildcardCapture.java:11: setData(capture#351 of ?) in Node<capture#351 of ?>
cannot be applied to (java.lang.String)
anyNode.setData("Trash"); // (5) Compile-time error!
^
The type of the reference anyNode is Node<capture#351 of ?> and the type of the formal parameter in the method declaration is "capture#351 of
?". The type of the actual parameter in the method call is String, which is not compatible with
“capture#351 of ?”. The call is not allowed. As we have seen earlier, with a <?> reference we cannot put anything into a data structure.
If we have the following method in the class MyStack:
public static <T> void move(MyStack<? super T> dstStack,
MyStack<? extends T> srcStack) {
while (!srcStack.isEmpty())
dstStack.push(srcStack.pop());
}
and we try to compile the following client code:
MyStack<?> anyStack;
MyStack.move(anyStack, anyStack); // Compile-time error!
the compiler issues the following error message:
MyStackUser.java:67: <T>move(MyStack<? super T>,MyStack<? extends T>) in MyStack
cannot be applied to (MyStack<capture#774 of ?>,MyStack<capture#371 of ?>)
MyStack.move(anyStack, anyStack); // Compile-time error!
^
The error message shows that each occurrence of a wildcard in a statement is represented by a distinct type capture. We see that the signature of the move() method is move(MyStack<? super T>, MyStack<? extends T>). The type of the reference anyStack is MyStack<?>. The static types of the two arguments in the method call are MyStack<capture#774 of ?> and MyStack<capture#371 of ?>. The numbers in the type capture names differentiate between the type captures of different wildcard occurrences. The signature of the argument list is (MyStack<capture#774 of ?>, MyStack<capture#371 of ?>). The type parameter T cannot be inferred from the types of the arguments, as the stacks are considered to be of two different types and, therefore, the call is rejected.
Consider the following non-generic method which does not compile:
static void fillWithFirstV1(List<?> list) {
Object firstElement = list.get(0); // (1)
for (int i = 1; i < list.size(); i++)
list.set(i, firstElement); // (2) Compile-time error
}
The method should fill any list passed as argument with the element in its first position. The call to the set() method is not permitted, as a set operation is not possible with a <?> reference (see Table 14.3, p. 684). Using the wildcard ? to parameterize the list does not work. We can replace the wild card with a type parameter of a generic method, as follows:
static <E> void fillWithFirstOne(List<E> list) {
E firstElement = list.get(0); // (3)
for (int i = 1; i < list.size(); i++)
list.set(i, firstElement); // (4)
}
Since the type of the argument is List<E>, we can set and get objects of type E from the list. We have also changed the type of the reference firstElement from Object to E in order to set the first element in the list.
It turns out that if the first method fillWithFirstV1() is re-implemented with a call to the generic method fillWithFirstOne(). It all works well:
static void fillWithFirstV2(List<?> list) {
fillWithFirstOne(list); // (5) Type conversion
}
The wildcard in the argument of the fillWithFirstV1() has a type capture. In the call to the fillWithFirstOne() method at (5), this type capture is converted to the type E. This conversion is called capture conversion, and it comes into play under certain conditions, which are beyond the scope of this book.
We have seen that the subtype relationship is invariant for the unbounded type parameter <T>:
Collection<Number> colNum;
Set<Number> setNum;
Set<Integer> setInt;
colNum = setNum; // (1) Set<Number> <: Collection<Number>
colNum = setInt; // (2) Compile-time error!
The same is true when concrete parameterized types are used as actual type parameters, implementing what are called nested parameterized types, i.e., using parameterized types as type parameters.
Collection<Collection<Number>> colColNum; // Collection
of Collections of Number
Set<Collection<Number>> setColNum; // Set of
Collections of Number
Set<Set<Integer>> setSetInt; // Set of
Sets of Integer
colColNum = setColNum; // (3) Set
<Collection<Number>> <:
// Collection<Collection<Number>>
colColNum = setSetInt; // (4) Compile-time error!
setColNum = setSetInt; // (5) Compile-time error!
Again, we can use the upper bounded wildcard to induce subtype covariance. The upper bounded wildcard is applied at the top level in the code below. The assignment below at (8) is not compatible, because Set<Set<Integer>> is not a subtype of Collection<? extends Collection<Number>>.
Collection<? extends Collection<Number>> colExtColNum;
colExtColNum = colColNum; // (6) Collection<
Collection<Number>> <:
// Collection<?
extends Collection<Number>>
colExtColNum = setColNum; // (7) Set<Collection
<Number>> <:
// Collection<?
extends Collection<Number>>
colExtColNum = setSetInt; // (8) Compile-time error!
In the code below, the wildcard is applied at the inner-most level:
Collection<Collection<? extends Number>> colColExtNum;
colColExtNum = colColNum; // (9) Compile-time error!
colColExtNum = setColNum; // (10) Compile-time error!
colColExtNum = setSetInt; // (11) Compile-time error!
The assignments above show that the upper bounded wildcard induces subtype covariance only at the top level. In (9), type A (=Collection<Number>) is a subtype of type B (=Collection<? extends Number>), but because subtype covariance relationship does not hold between parameterized types, the type Collection<A>(=Collection<Collection<Number>>) is not a subtype of Collection<B> (= Collection<Collection<? extends Number>>).
The above discussion also applies when a parameterized type has more than one type parameter:
Map<Number, String> mapNumStr;
Map<Integer, String> mapIntStr;
mapNumStr = mapIntStr; // (12) Compile-time error!
Again, the upper bounded wildcard can only be used at the top level to induce subtype covariance:
Map<Integer, ? extends Collection<String>> mapIntExtColStr;
Map<Integer, Collection<? extends String>> mapIntColExtStr;
Map<Integer, Collection<String>> mapIntColStr;
Map<Integer, Set<String>> mapIntSetStr;
mapIntExtColStr = mapIntColStr;// (13) Map<Integer,
Collection<String>> <:
// Map<Integer, ?
extends Collection<String>>
mapIntExtColStr = mapIntSetStr;// (14) Map<Integer,
Set<String>> <:
// Map<Integer, ?
extends Collection<String>>
mapIntColStr = mapIntSetStr; // (15) Compile-time error!
mapIntColExtStr = mapIntColStr; // (16) Compile-time error!
mapIntColExtStr = mapIntSetStr; // (17) Compile-time error!
We now examine the implications of using wildcard parameterized types as formal parameters of a method.
We want to add a method in the class MyStack<E> (Example 14.7, p. 695) for moving the elements of a source stack to the current stack. Here are three attempts at implementing such a method for the class MyStack<E>:
public void moveFromV1(MyStack<E> srcStack) { // (1)
while (!srcStack.isEmpty())
this.push(srcStack.pop());
}
public void moveFromV2(MyStack<? extends E> srcStack) { // (2)
while (!srcStack.isEmpty())
this.push(srcStack.pop());
}
public void moveFromV3(MyStack<? super E> srcStack) { // (3) Compile-time error!
while (!srcStack.isEmpty())
this.push(srcStack.pop());
}
Given the following three stacks:
MyStack<Number> numStack = new MyStack<Number>(); // Stack of Number
numStack.push(5.5); numStack.push(10.5); numStack.push(20.5);
MyStack<Integer> intStack1 = new MyStack<Integer>(); // Stack of Integer
intStack1.push(5); intStack1.push(10); intStack1.push(20);
MyStack<Integer> intStack2 = new MyStack<Integer>(); // Stack of Integer
intStack2.push(15); intStack2.push(25); intStack2.push(35);
we can only move elements between stacks of the same type with the method at (1):
intStack1.moveFromV1(intStack2);
numStack.moveFromV1(intStack2); // Compile-time error!
The compile-time error above is due to the fact that MyStack<Integer> is not a subtype of MyStack<Number>. However, we can move elements from a stack of type MyStack<? extends E> to the current stack using the method at (2). This is possible because a reference of a type MyStack<? extends E> can refer to a stack with objects of type E or its subclass and the get operation (i.e., the pop() method) is permissible, returning an object which has an actual type bounded by the upper bound E. The returned object can always be put into a stack of type E or its supertype.
intStack1.moveFromV2(intStack2);
numStack.moveFromV2(intStack2);
The method at (3) will only allow Objects to be popped from a stack of type MyStack<? super E>, which could only be pushed onto a stack of type Object. Since E cannot be determined at compile time, the push() operation on the current stack is not permitted. Of the first two methods, the method at (2) is more flexible in permitting the widest range of calls.
Similarly, we can add a method in the class MyStack<E> for moving the elements of the current stack to a destination stack:
public void moveToV1(MyStack<E> dstStack) { // (3)
while (!this.isEmpty())
dstStack.push(this.pop());
}
public void moveToV2(MyStack<? extends E> dstStack) { // (4)
while (!this.isEmpty())
dstStack.push(this.pop()); // Compile-time error!
}
public void moveToV3(MyStack<? super E> dstStack) { // (5)
while (!this.isEmpty())
dstStack.push(this.pop());
}
In the method at (4), the reference of type MyStack<? extends E> does not allow any set operations (in this case, the push() method) on the destination stack. The method at (5) provides the most flexible solution, as a reference of type MyStack<? super E> permits set operations for objects of type E or its subtypes:
intStack1.moveToV1(intStack2);
intStack1.moveToV1(numStack); // Compile-time error!
intStack1.moveToV3(intStack2);
intStack1.moveToV3(numStack);
Based on the discussion above, we can write a generic method for moving elements from a source stack to a destination stack. The following method signature is preferable, where objects of type E or its subtypes can be popped from the source stack and pushed onto a destination stack of type E or its supertype:
public static <T> void move(MyStack<? super T> dstStack, // (6)
MyStack<? extends T> srcStack) {
while (!srcStack.isEmpty())
dstStack.push(srcStack.pop());
}
// Client code
MyStack.move(intStack2, intStack1);
MyStack.move(numStack, intStack1);
MyStack.move(intStack2, numStack); // Compile-time error!
It is a common idiom to use wildcards as shown above in the method at (6), as the upper bounded wildcard (? extends Type) can be used to get objects from a data structure, and the lower bounded wildcard (? super Type) can be used to set objects in a data structure. Using wildcards in the method signature can increase the utility of a method, especially when explicit type parameters are specified in the method call.
Another common idiom in programming with generics is using the Comparable<T> interface as a bound and parameterizing it with the lower bounded wildcard (? super T) to allow for greater flexibility in doing comparisons. In the following two method declarations, the Comparable<T> interface is used as a bound, but parameterized differently:
static <T extends Comparable<T>> T max
(T obj1, T obj2) { ... } // (1)
static <T extends Comparable<? super T>> T superMax(T obj1, T obj2) { ... } // (2)
The two methods are declared at (1) and (2) in Example 14.9, and can be used to find the maximum of two objects that are comparable. Both methods are applied to objects of subclasses of two different superclasses (see Figure 14.6). The superclass ProgrammerCMP implements the Comparable<ProgrammerCMP> interface, which is inherited by its subclasses JProgrammerCMP and CProgrammerCMP. The implication being that the objects of different subclasses can also be compared with each other. However, the superclass Programmer leaves the implementation of the Comparable<E> interface to its subclasses JProgrammer and CProgrammer. The implication in this case being that the objects of different subclasses cannot be compared with one another.
The important thing to note in Example 14.9 is that the method max() does not allow objects of a subclass to be compared with one another, when no explicit type parameter is specified in the method call. For example, we cannot compare two JProgrammerCMPs as shown at (4), because they are not Comparable<JProgrammerCMP>. They are Comparable<ProgrammerCMP>, which is not the same thing. If the actual type parameter is explicitly specified as ProgrammerCMP, as shown at (5), the comparison is permitted.
jProgCMP = max(jProgCMP, jProgCMP); // (4) Compile-time Error!
progCMP = WhoIsComparble.<ProgrammerCMP>max(jProgCMP, jProgCMP); // (5)
If the superMax() method with the lower bounded wildcard (? super T) is used, the situation above does not arise. The constraint is Comparable<? super JProgrammerCMP>, and Comparable<ProgrammerCMP> is a subtype of Comparable<? super JProgrammerCMP>. Since the subclass JProgrammerCMP is a subtype of Comparable<ProgrammerCMP>, the subclass satisfies the constraint and its objects can be compared. In all other respects the two methods are equivalent, but the superMax() method is preferable.
Similarly, the Comparator used by the following method can be parameterized with the lower bounded wildcard for greater flexibility:
public static <T> T max(T obj1, T obj2, Comparator<? super T> comp) { // (3)
return (comp.compare(obj1, obj2) < 0) ? obj2 : obj1;
}
Example 14.9 Flexible Comparisons
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
/** Comparison in superclass */
abstract class ProgrammerCMP implements Comparable
<ProgrammerCMP> {
protected String name;
protected int loc; // Lines of code
ProgrammerCMP(String name, int loc) {
this.name = name; this.loc = loc;
}
public int compareTo(ProgrammerCMP that) {
return this.loc < that.loc ? - 1 :
this.loc == that.loc ? 0 : 1 ;
}
}
class JProgrammerCMP extends ProgrammerCMP {
JProgrammerCMP (int loc) { super("JProgrammerCMP", loc); }
}
class CProgrammerCMP extends ProgrammerCMP {
CProgrammerCMP (int loc) { super("CProgrammerCMP", loc); }
}
/** Comparison in subclasses */
abstract class Programmer {
protected String name;
protected int loc; // Lines of code
Programmer(String name, int loc) { this.name = name; this.loc = loc; }
}
class JProgrammer extends Programmer implements Comparable
<JProgrammer>{
JProgrammer (int loc) { super("JProgrammer", loc); }
public int compareTo(JProgrammer that) {
return this.loc < that.loc ?
- 1 : this.loc == that.loc ? 0 : 1 ;
}
}
class CProgrammer extends Programmer implements Comparable
<CProgrammer> {
CProgrammer (int loc) { super("CProgrammer", loc); }
public int compareTo(CProgrammer that) {
return this.loc < that.loc ? - 1 : this.loc == that.loc ? 0 : 1 ;
}
}
/** Tests generic methods */
public class WhoIsComparable {
public static <T extends Comparable<T>> T max(T obj1, T obj2) { // (1)
return (obj1.compareTo(obj2) < 0) ? obj2 : obj1;
}
public static <T extends Comparable<? super T>> T // (2)
superMax(T obj1, T obj2) {
return (obj1.compareTo(obj2) < 0) ? obj2 : obj1;
}
public static <T> T
max(T obj1, T obj2, Comparator<? super T> comp) { // (3)
return (comp.compare(obj1, obj2) < 0) ? obj2 : obj1;
}
public static void main(String[] args) {
JProgrammerCMP jProgCMP = new JProgrammerCMP(1000);
CProgrammerCMP cProgCMP = new CProgrammerCMP(50);
JProgrammer jProg = new JProgrammer(1000);
CProgrammer cProg = new CProgrammer(50);
ProgrammerCMP progCMP;
Programmer prog;
/* Using <T extends Comparable<T>> T max(T, T) method */
// Comparison in superclass
jProgCMP = max(jProgCMP, jProgCMP); // (4) Compile-time Error!
progCMP = WhoIsComparable.<ProgrammerCMP>max(jProgCMP, jProgCMP); // (5)
progCMP = max(jProgCMP, cProgCMP);
// Comparison in subclasses
jProg = max(jProg, jProg);
jProg = WhoIsComparable.<JProgrammer>max(jProg, jProg);
prog = max(jProg, cProg); // Expected error.
/* Using <T extends Comparable<? super T>> T superMax(T, T) method */
// Comparison in superclass
jProgCMP = superMax(jProgCMP, jProgCMP); // (6)
progCMP = WhoIsComparable.<ProgrammerCMP>superMax(jProgCMP, jProgCMP);
progCMP = superMax(jProgCMP, cProgCMP);
// Comparison in subclasses
jProg = superMax(jProg, jProg);
jProg = WhoIsComparable.<JProgrammer>superMax(jProg, jProg);
prog = superMax(jProg, cProg); // Expected error.
}
}
The classes MonoNode and BiNode are declared in Example 14.3, p. 667, and Example 14.4, p. 669, respectively:
class MonoNode<E> implements IMonoLink<E> {
private E data; // Data
private IMonoLink<E> next; // Reference to next node
// (1)
// ...
}
class BiNode<E> extends MonoNode<E> implements IBiLink<E> {
private IBiLink<E> previous; // Reference to previous node
// (2)
// ...
}
Note that the next field has the type IMonoLink<E>, but the previous field has the type IBiLink<E>. This means that when traversing a linked structure constructed from nodes that implement the IBiLink<E> interface, we have to be careful. The method traverseBinTree() below traverses a binary tree constructed from such nodes. The method prints the data in the nodes. Note that it is necessary to cast the reference value returned by the getNext() method, as shown at (3).
public static <T> void traverseBinTree(IBiLink<T> root) {
if (root.getPrevious() != null)
traverseBinTree(root.getPrevious());
System.out.print(root.getData() + ", ");
if (root.getNext() != null)
traverseBinTree((IBiLink<T>)root.getNext()); // (3) Cast necessary.
}
Example 14.10 declares a class called RecNode. The header of this class at (1) is declared as follows:
abstract class RecNode<E, T extends RecNode<E, T>>
The class specifies two type parameters: E and T. The type parameter E stands for the type of the data in the node, (2). The type parameter T stands for the type of the next field in the node, (3). It has the bound RecNode<E, T>, meaning that T must be a subtype of the bound, i.e., of RecNode<E, T>. In other words, the class RecNode can only be parameterized by its subclasses. The two parameters E and T are used in the class for their respective purposes.
Example 14.10 Using Recursive Bounds
abstract class RecNode<E, T extends RecNode<E, T>> { // (1)
private E data; // (2)
private T next; // (3)
RecNode(E data, T next) {
this.data = data;
this.next = next;
}
public void setData(E obj) { data = obj; }
public E getData() { return data; }
public void setNext(T next) { this.next = next; }
public T getNext() { return next; }
public String toString() {
return this.data + (this.next == null ? "" : ", "
+ this.next);
}
}
final class RecBiNode<E> extends RecNode<E, RecBiNode<E>> { // (4)
private RecBiNode<E> previous; // Reference to
previous node // (5)
RecBiNode(E data, RecBiNode<E> next, RecBiNode<E> previous) {
super(data, next);
this.previous = previous;
}
public void setPrevious(RecBiNode<E> previous) { this.previous = previous; }
public RecBiNode<E> getPrevious() { return this.previous; }
public String toString() {
return (this.previous == null? "" :
this.previous + ", ") +
this.getData() +
(this.getNext() == null? "" : ", " + this.getNext());
}
}
Example 14.10 declares another class called RecBiNode. The header of this class at (4) is declared as follows:
final class RecBiNode<E> extends RecNode<E, RecBiNode<E>>
Note that the class has only one type parameter, E, that represents the data type in the node. The class extends the RecNode class, which is parameterized with the data type E and the type RecBiNode<E> to represent the type of the next field in the superclass RecNode. The class RecBiNode also declares a previous field of type RecBiNode<E> at (5), and the corresponding get and set methods. The upshot of this class declaration is that, for a node of type RecBiNode<E>, both the next and the previous fields have the same type as a node of this class. The traversal method can now be written without using any casts, passing it a node of the subtype RecBiNode<E>:
public static <T> void traverseBinTree(RecBiNode<T> root) { // (2)
if (root.getPrevious() != null)
traverseBinTree(root.getPrevious());
System.out.print(root.getData() + ", ");
if (root.getNext() != null)
traverseBinTree(root.getNext()); // No cast necessary!
}
The class declaration at (1) in Example 14.10 uses what is called a recursive bound in its constraint T extends RecNode<E,T>. New subtypes of the class RecNode can be implemented using this idiom, and the type of the next field will be the same as the subtype.
Earlier in this chapter we saw the constraint T extends Comparable<T>, which is also a recursive bound. Another example of recursive bounds is the declaration of the Enum<E extends Enum<E>> class in the Java Standard Library.
Understanding translation by type erasure helps to understand the restrictions and limitations that arise when using generics in Java. Although the compiler generates generic-free byte code, we can view the process as a source-to-source translation that generates non-generic code from generic code.
The translated code has no information about type parameters, i.e., the type parameters have been erased—hence the term, type erasure. This involves replacing the usage of the type parameters with concrete types and inserting suitable type conversions to ensure type correctness. In certain situations, bridge methods are also inserted for backward compatibility.
The process of determining the erasure of a type, i.e., what a type in the source code should be replaced with, uses the following rules:
1. Drop all type parameter specifications from parameterized types.
2. Replace any type parameter as follows:
(a) Replace it with the erasure of its bound, if it has one.
(b) Replace it with Object, if it has none.
(c) Replace it with the erasure of the first bound, if it has multiple bounds.
Table 14.4 shows examples of translation by erasure for some representative types, and the rules that are applied.
The following code mixes legacy and generic code. Note that a ClassCastException is expected at (5) because the type-safety of the stack of String has been compromised.
// Pre-erasure code
List<String> strList = new ArrayList<String>(); // (0)
List list = strList; // (1) Assignment to non-generic reference is ok.
strList = list; // (2) warning: unchecked conversion
strList.add("aha"); // (3) Method call type-safe.
list.add(23); // (4) warning: [unchecked] unchecked call
to add(E)
// as a member of the raw type
java.util.List
System.out.println(strList.get(1).length()); // (5) ClassCastException
It is instructive to compare the corresponding lines of code in the pre-erasure code above and the post-erasure results shown below. A cast is inserted to convert from Object type to String type in (5′). This is necessary because post-erasure code can only get an Object from the list, and in order to call the length() method, the reference value of this object must be converted to String. It is this cast that is the cause of the exception at runtime.
// Post-erasure code
List strList = new ArrayList(); // (0')
List list = strList; // (1')
strList = list; // (2')
strList.add("aha"); // (3')
list.add(Integer.valueOf(23)); // (4')
System.out.println(((String)strList.get(1)).length()); // (5')
Bridge methods are inserted in subclasses by the compiler to ensure that overriding of method works correctly. The canonical example is the implementation of the Comparable interface. The post-erasure code of the class CmpNode<E> from Section 14.6 on page 684 is shown below. A second compareTo() method has been inserted by the compiler at (2), whose method signature is compareTo(Object). This is necessary because, without this method, the class would not implement the Comparable interface, as the compareTo() method of the interface would not be overridden correctly.
class CmpNode extends Node implements Comparable {
CmpNode(Object data, CmpNode next) {
super(data, next);
}
public int compareTo(CmpNode node2) { // (1)
return this.getData().compareTo(node2.getData());
}
public int compareTo(Object node2) { // (2)
return this.compareTo((CmpNode)node2); // Calls the method at (1).
}
}
Such a bridge method cannot be invoked in the source code, and is provided for backward compatibility with legacy code. There are Java decompilers readily available that can be used to examine the code generated by the compiler.
Method signatures play a crucial role in overloading and overriding of methods. The method signature comprises the method name and the formal parameter list. Two methods (or constructors) have the same signature if both of the following conditions are fulfilled:
• they have the same name
• they have the same formal parameter types
Two methods (or constructors) have the same formal parameter types if both of the following conditions are fulfilled:
• they have the same number of formal parameters and type parameters
• the formal parameters and the bounds of the type parameters are the same after the occurrences of formal parameters in one are substituted with the corresponding types from the second.
The signature of a method m() is a subsignature of the signature of another method n(), if either one of these two conditions hold:
• Method n() has the same signature as method m(), or
• The signature of method m() is the same as the erasure of the signature of method n().
The signatures of the two methods m() and n() are override-equivalent if either one of these two conditions hold:
• The signature of method m() is a subsignature of the signature of method n(), or
• The signature of method n() is a subsignature of the signature of method m().
Given the definitions above, we can now state that two methods are overloaded if they have the same name, but their signatures are not override-equivalent. Given the following three generic method declarations in a class:
static <T> void merge (MyStack<T> s1, MyStack<T> s2) { /*...*/ }
static <T> void merge (MyStack<T> s1, MyStack<? extends T> s2)
{ /*...*/ }
static <T> void merge (MyStack<T> s1, MyStack<? super T> s2)
{ /*...*/ }
After erasure, the signature of all three methods is:
merge(MyStack, MyStack)
i.e., the signatures of the methods are override-equivalent, hence these methods are not overloaded. A class cannot contain two methods with override-equivalent signatures, and the compiler will report an error.
These three methods:
static <T> void merge (Node<T> s1, MyStack<T> s2) { /*...*/ }
static <T> void merge (MyStack<T> s1, MyStack<? extends T> s2)
{ /*...*/ }
static <T> void merge (MyStack<T> s1, Node<? super T> s2)
{ /*...*/ }
have the following signatures after erasure, respectively:
merge (Node, MyStack)
merge (MyStack, MyStack)
merge (MyStack, Node)
We can see that no two signatures are override-equivalent. Therefore, the three methods are overloaded.
The declaration of the class Sup below shows some variations on the method signature. The resulting signature of the method header (which includes the method signature) is shown after erasure in the comment corresponding to the method.
class Sup<T> {
void doIt(boolean b) { } // (1) void doIt(boolean)
void doIt(T t) { } // (2) void doIt(Object)
List<StringBuilder> doIt(StringBuilder sb) { // (3) List doIt(StringBuilder)
return null;
}
<E extends Comparable<E>> void doIt(E element) // (4) void doIt(Comparable)
{ }
<E> E doIt(MyStack<? extends E> stack) { // (5) Object doIt(MyStack)
return null;
}
}
Adding any of the following method declarations to the class Sup would be an error, as each one of these method declarations has a method signature that is the same as one of the methods already in the class, i.e., the signatures are override-equivalent.
void doIt(Object obj) { } // (2') void doIt(Object)
<E extends StringBuilder> List<E> doIt(E sb) { // (3') List doIt(StringBuilder)
return null;
}
void doIt(Comparable<T> element) { } // (4') void doIt(Comparable)
<E> E doIt(MyStack<? super E> stack) { // (5') Object doIt(MyStack)
return null;
}
The following conditions should be satisfied in order for a subtype method to override a supertype method:
• The signature of the subtype method is a subsignature of the signature of the supertype method (which is discussed in this subsection)
• Their return types should be compatible (Section 7.2, p. 288)
• Their throws clauses should be compatible (Section 6.9, p. 259)
Here we discuss the implication of method signatures for overriding.
We can solicit the aid of the compiler to ensure that a method declaration overrides an inherited method correctly. If a method declaration is preceded by the annotation @Override, the compiler will issue an error if the method does not override an inherited method.
Example 14.11 illustrates the use of this annotation. The intention in the class CmpNode is to override the equals() method from the Object class and the compareTo() method from the Comparable interface. The error messages alert us to the fact that the annotated methods do not override any inherited methods. The method signatures are not subsignatures of any method signatures that are inherited. The formal parameters are not correct for overriding in (1) and (2). They should be as shown at (1′) and (2′).
Example 14.11 Using the @Override Annotation
class CmpNode<E extends Comparable
<E>>
extends Node<E> implements Comparable<CmpNode<E>> {
CmpNode(E data, CmpNode<E> next) {
super(data, next);
}
@Override
public boolean equals(CmpNode node2) { // (1) Compile-time error.
//public boolean equals(Object node2) { // (1') Correct header.
return this.compareTo(node2) == 0;
}
@Override
public int compareTo(Object node2) { // (2) Compile-time error.
//public int compareTo(CmpNode<E> node2) { // (2') Correct header
return this.getData().compareTo(node2.getData());
}
}
Compiling the class CmpNode:
>javac CmpNode.java
...
CmpNode.java:8: method does not override or implement
a method from a supertype
@Override
^
...
CmpNode.java:14: method does not override or implement
a method from a supertype
@Override
^
In Example 14.12, the signature at (1′) is the same as the signature at (1): set(Integer). The signature at (2′) is the same as the erasure of the signature at (2): set(List). The method at (2′) shows a non-generic subtype method overriding a supertype method that uses generics. This is needed for legacy code: legacy supertypes can be generified without it having consequences for any subtypes, as the signature of a subtype method that overrides a supertype method will be the same as the erasure of the signature of this supertype method.
Example 14.12 Subsignatures
class SupA {
public void set(Integer ref) {/*...*/} // (1)
public void set(List<Integer> list) {/*...*/} // (2)
}
class SubA extends SupA {
@Override
public void set(Integer iRef) {/*...*/} // (1') same as at (1)
@Override
public void set(List list) {/*...*/} // (2') same as the erasure at (2)
}
In Example 14.13, both the subclasses SubB1 and SubB2 are subtypes of the concrete supertype SupB<Number>, i.e., T is Number in SupB<T>. The signatures of the methods in SubB1 are the same as the signatures of the methods in SupB, therefore, the methods are overridden. After erasure, the methods in SupB are equivalent to:
public void set(Object t) {/*...*/} // (1)
public Object get() {return null;} // (2)
The compiler adds the following bridge method in SubB1 in order for overriding to work properly at runtime:
public void set(Object t) {set((Number)t);} // (1')
It does not add a bridge method for the get() method in SubB1, because of covariant return: the return type Number for the method get() in SubB1 is a subtype of the return type Object of the method get() in SupB.
Example 14.13 Overriding from Generic Supertype
class SupB<T> {
public void set(T t) {/*...*/} // (1)
public T get() {return null;} // (2)
}
class SubB1 extends SupB<Number> {
@Override
public void set(Number num) {/*...*/} // (1a) Overrides
@Override
public Number get() {return 0;} // (2a) Overrides
}
class SubB2 extends SupB<Number> {
public void set(Object obj) {/*...*/} // (1b) Error: same erasure
public void set(Long l) {/*...*/} // (1c) Overloads
public Object get() {return 0;} // (2b) Error: incompatible return type
}
We now examine the methods in SubB2. The set() method at (1b) has the same erasure as the set() method at (1) in the supertype SupB. If overriding were allowed, the bridge method added would result in two methods with the same signature set(Object) in SubB2. Two methods with the same signature are not permitted in the same class—called a name clash, therefore (1b) is not allowed.
The method set() at (1c) is overloaded because its signature is different from the other set() methods in SubB2 and SupB. The method get() at (2b) has the return type Object, while the get() method in SupB<Number> has the return type Number. The return types are not covariant, and (2b) is rejected.
Example 14.14 shows a typical error where a generic supertype is extended, but its parameterization is missing in the extends clause of the subtype, as shown at (2). The set() method in SubZ neither overrides nor overloads the method at (1). Both methods have the same signature after erasure: set(Object). Adding a bridge method in SubZ would result in a name clash. (1a) is rejected.
The subsignature requirement for overriding means that the signature of the subtype method must either be the same as that of the supertype method, or it must be the same as the erasure of the signature of the supertype method. Note the implication of the last sentence: the signature of the subtype method must be the same as the erasure of the supertype method, not the other way around. The converse is neither overloading nor overriding, but a name clash and reported as an error.
The subsignature requirement also implies that a generic subtype method cannot override a non-generic supertype method. In other words, genericity cannot be added to an inherited method. This case is illustrated in Example 14.15. It is the erasures of the signatures of the generic methods in the subtype that are the same as the signatures of the non-generic methods in the supertype. Overriding requires the converse. A name clash is generally the reason why neither overriding nor overloading is permitted.
Example 14.15 Genericity Cannot Be Added to Inherited Methods
class SupJ {
public void set(Object obj) {/*...*/}// (1)
public Object get() {return null;} // (2)
}
class SubJ extends SupJ {
public <S> void set(S s) {/*...*/} // (1a) Error: same erasure
public <S> S get() {return null;} // (2a) Error: same erasure
}
Concrete parameterized types are used by the compiler and then translated by erasure to their raw types, losing information about the parameterization in the process. In other words, only the raw types of these concrete parameterized types are available at runtime. For example, List<Integer> and List<String> are both erased to the raw type List. The same applies to unbounded parameterized types: List<E> is erased to List.
Non-generic types are not affected by type erasure and, therefore, have not lost any information and are, therefore, available fully at runtime. For example, the types Integer and String remain intact and are present unchanged at runtime.
Types that are completely available at runtime are known as reifiable types, i.e., type erasure has not removed any important information about them (see Table 14.5). Types whose information has been affected by erasure are called non-reifiable types (see Table 14.6).
Note that unbounded wildcard parameterized types (Node<?>, MyStack<?>) are reifiable, whereas concrete parameterized types (Node<Number>, MyStack<String>) and bounded wildcard parameterized types (Node<? extends Number>, MyStack<? super String>) are non-reifiable.
As we shall see in the rest of this section, certain operations in Java are only permitted on reifiable types (as their type information is fully intact and available at runtime), and not on non-reifiable types (as their type information is not fully available at runtime, since it has been affected by type erasure).
Instance tests require type information at runtime, i.e., these are runtime tests that require reifiable types. An instance test against a non-reifiable type is not permitted and always generates a compile-time error.
In (1) below, we want to determine whether the object referenced by obj is an instance of the concrete parameterized type MyStack<Integer>, i.e., whether it is a stack of Integer:
The post-erasure code for (1) is equivalent to the following statement:
boolean isIntStack = obj instanceof MyStack; // (1')
The statement in (1′) cannot perform the instance test expected in (1), as erasure has removed the information about the concrete type parameter Integer, i.e., the type MyStack<Integer> is non-reifiable. The compiler issues an error, because the JVM will only be able to find a stack of the erasure type (MyStack) and not a stack of a parameterized type (MyStack<Integer>).
Given that T is a formal type parameter, the following code will also not compile, as the arguments of the instanceof operator are non-reifiable types:
Object thingy;
...
boolean isT = thingy instanceof T; // Compile-time error!
boolean isTStack = obj instanceof MyStack<T>; // Compile-time error!
If we just wanted to determine that an instance was some stack, the instance test can be performed against the raw type or the unbounded wildcard parameterized type, as these types are reifiable:
boolean isRawStack = obj instanceof MyStack;
boolean isAnyStack = obj instanceof MyStack<?>; // Preferable.
For non-generic code, if the instance test is true, the cast is safe to apply:
Number num = 2008;
if (num instanceof Integer) {
int i = (Integer) num;
}
Since it is not possible to test that an object is an instance of a non-reifiable type, it is also not possible to check the cast to such a type at runtime. A non-reifiable type could have lost important type information during erasure and the cast may not have the desired affect at runtime. A cast to a non-reifiable type is generally flagged as an unchecked cast warning, and the cast is replaced by a cast to its erasure. Again, the compiler permits casts to allow interoperability between legacy code and generic code—usually with a warning.
The following code shows why a warning is necessary. The reference value of a Number node, declared at (1), is assigned to a reference of type Node<?> at (2). This reference is cast to a Node<String> and its reference value is assigned to a reference of type Node<String> at (3). A String is set as data in the node at (4). The data is retrieved from the node via the numNode reference and assigned to a Number reference at (5).
Node<Number> numNode = new Node<Number>(20, null); // (1)
Node<?> anyNode = numNode; // (2)
Node<String> strNode = (Node<String>) anyNode; // (3)
Unchecked cast
strNode.setData("Peekaboo"); // (4)
Number num = numNode.getData(); // (5) ClassCastException
The erasure of the assignment at (3) is equivalent to the following assignment, with the cast succeeding at runtime:
Node strNode = (Node) anyNode; // (3')
However, a ClassCastException occurs at (5) because a String cannot be assigned to a Number. The compiler warns of potential problems by issuing an unchecked cast warning at (3).
The types Node<String> and Node<Number> are unrelated. That is the reason why the Number node in the above example was compromised by going through a node of type Node<?>. As we would expect, a cast between unrelated types results in a compile-time error:
strNode = (Node<String>) numNode; // Compile-time error
If we are casting a generic supertype to a generic subtype, where the parameterization is identical, the cast is safe and no warning is issued:
// BiNode<E> is a subtype of MonoNode<E>
MonoNode<String> monoStrNode = new BiNode<String>("Hi", null, null);
BiNode<String> biStrNode = (BiNode<String>) monoStrNode; //
Ok. No warning.
The method castaway() below shows examples of casting an Object reference that refers to a node of type String, declared at (2).
@SuppressWarnings("unchecked") // (1) Suppress warnings in (4),(6),(7).
public static void castaway() {
Object obj = new Node<String>("one", null); // (2)
Node<String> node1 = obj; // (3)
Compile-time error!
Node<String> node2 = (Node<String>) obj; // (4)
Unchecked cast
Node<String> node3 = (Node<?>) obj; // (5) Compile-time error!
Node<String> node4 = (Node<String>)(Node<?>) obj; // (6) Unchecked cast
Node<String> node5 = (Node) obj; // (7)
Unchecked conversion
Node<?> node6 = (Node) obj; // (8)
Node<?> node7 = (Node<?>)obj; // (9)
}
It is instructive to see what warnings and errors are issued by the compiler. The compile-time error at (3) is due to incompatible types: an Object cannot be assigned to a Node<String> reference. The compiler issues an unchecked cast warning at (3) because of the cast from an Object to the concrete parameterized type Node<String>. The compile-time error at (5) is due to incompatible types: a Node<?> cannot be assigned to a Node<String> reference. There are two casts in (6): an Object is cast to Node<?>, which in turn is cast to Node<String>. The cast to Node<?> is permitted, but the second cast results in an unchecked cast warning. Note that an assignment of a Node<?> to a Node<String> is not permitted, but a cast is permitted with a warning. (8) and (9) show that casting to the raw type or to the unbounded wildcard is always permitted, since both types are reifiable.
We have used the annotation @SuppressWarnings("unchecked") at (1) to suppress the unchecked warning in the method castaway(). Use of this annotation is recommended when we know that unchecked cast warnings are inevitable in a language construct (a type declaration, a field, a method, a parameter, a constructor, a local variable). Any unchecked warnings reported by the compiler are then those that were not documented using this annotation. The use of an unbounded wildcard is recommended in casts, rather than using raw types, as it provides for stricter type checking.
Array store checks are based on the element type being a reifiable type, in order to ensure that subtype covariance between array types is not violated at runtime. In the code below, the element type of the array is String and the array store check at (1) disallows the assignment, resulting in an ArrayStoreException, because the reference value of a Double cannot be stored in a String reference.
String[] strArray = new String[] {"Hi", "Hello", "Howdy"};
Object[] objArray = strArray; // String[] is a subtype of Object[]
objArray[0] = 2010.5; // (1) ArrayStoreException
We cannot instantiate a formal type parameter, nor can we create an array of such a type:
// T is a formal type parameter.
T t = new T(); // Compile-time error!
T[] anArray = new T[10]; // Compile-time error!
It is also not possible to create an array whose element type is a concrete or a bounded wildcard parameterized type:
// An array of Lists of String
List<String>[] list1 = { // Compile-time error
Arrays.asList("one", "two"), Arrays.asList("three", "four")
};
List<String>[] list2 = new List<String>[] { // Compile-time error
Arrays.asList("one", "two"), Arrays.asList("three", "four")
};
// An array of Lists of any subtype of Number
List<? extends Number>[] list3
= new List<? extends Number>[] { // Compile-time error
Arrays.asList(20.20, 60.60), Arrays.asList(2008, 2009)
};
Unbounded wildcard parameterized types are allowed as element types, because these types are essentially equivalent to the raw types (see Section 14.5, p. 679):
Note that we can always declare a reference of a non-reifiable type. It is creating arrays of these types that is not permitted.
class MyIntList extends ArrayList<Integer> { } // A
reifiable subclass.
// Client code
List<Integer>[] arrayOfLists = new MyIntList[5]; // Array of Lists of Integer
List<Integer[]> listOfArrays
= new ArrayList<Integer[]>(); // List of Arrays of Integer
The class MyStack<E> in Example 14.7, p. 695, implements a method to convert a stack to an array:
// Copy to array as many elements as possible.
public E[] toArray(E[] toArray) { // (11)
Node<E> thisNode = tos;
for (int i = 0; thisNode != null && i < toArray.length; i++) {
toArray[i] = thisNode.getData();
thisNode = thisNode.getNext();
}
return toArray;
}
Note that the array is passed as parameter, because we cannot create an array of the parameter type, as the following version of the method shows:
public E[] toArray2() {
E[] toArray = new E[numOfElements]; // Compile-time error
int i = 0;
for (E data : this) {
toArray[i++] = data;
}
return toArray;
}
The third version below uses an array of Object. The cast is necessary in order to be compatible with the return type. However, the cast is to a non-reifiable type, resulting in an unchecked cast warning:
public E[] toArray3() {
E[] toArray = (E[])new Object[numOfElements]; // (1) Unchecked cast warning
int i = 0;
for (E data : this) { toArray[i++] = data; }
return toArray;
}
The method implementation above has a serious problem, even though the code compiles. We get a ClassCastException at (2) below, because we cannot assign the reference value of an Object[] to an Integer[] reference:
MyStack<Integer> intStack = new MyStack<Integer>();
intStack.push(9); intStack.push(1); intStack.push(1);
Integer[] intArray = intStack.toArray3(); // (2) ClassCastException
The final and correct version of this method uses reflection to create an array of the right element type:
@SuppressWarnings("unchecked")
public E[] toArray4(E[] toArray) {
if (toArray.length != numOfElements) {
toArray = (E[])java.lang.reflect.Array.newInstance( // (3)
toArray.getClass().getComponentType(),
numOfElements); // Suppressed
unchecked warning
}
int i = 0;
for (E data : this) { toArray[i++] = data; }
return toArray;
}
The method is passed an array whose element type is looked up through reflection, and an array of this element type (and right size) is created at (3). The method newInstance() of the Array class creates an array of specified element type and size. The element type is looked up through the class literal of the array supplied as argument. The unchecked cast warning is suppressed, because we know it is unavoidable. We will not go into the nitty-gritty details of using reflection here.
The client code now works as expected. We pass an array of zero length, and let the method create the array.
MyStack<Integer> intStack = new MyStack<Integer>();
intStack.push(9); intStack.push(1); intStack.push(1);
Integer[] intArray = intStack.toArray4(new Integer[0]); // (3) OK.
The next example demonstrates the danger of casting an array of a reifiable type to an array of non-reifiable type. An array of the raw type List (reifiable type) is created at (1), and cast to an array of List<Double> (non-reifiable type). The cast results in an unchecked cast warning. The first element of the array of List<Double> is initialized with a list of Double at (2). The reference value of this array is assigned to a reference of type List<? extends Number> at (3). Using this reference, the array of Double in the first element of the array is replaced with a list of Integer. Using the alias arrayOfListsOfDouble of type List<Double>[], the first element in the first list of the array (an Integer) is assigned to a Double reference. Since the types are incompatible, a ClassCastException is thrown at (5). Note that the array store check at (4) succeeds, because the check is against the reified element type of the array, List, and not List<Double>.
List<Double>[] arrayOfListsOfDouble
= (List<Double>[]) new List[1]; // (1) Unchecked cast warning!
arrayOfListsOfDouble[0] = Arrays.asList(10.10); // (2) Initialize
List<? extends Number>[] arrayofListsOfExtNums = arrayOfListsOfDouble; // (3)
arrayofListsOfExtNums[0] = Arrays.asList(10); // (4) Array storage check ok
Double firstOne = arrayOfListsOfDouble[0].get(0); // (5) ClassCastException!
Because varargs are treated as arrays, generics have implications for varargs (Section 3.8, p. 90). Most of the workarounds for arrays are not applicable, as array creation is implicit for varargs. In a method call, implicit creation of a generic array with the varargs results in an unchecked generic array creation warning—and type-safety is no longer guaranteed.
The method asStack() below has a varargs parameter at (1) whose type is a nonreifiable type T. The method pushes the specified elements on to the specified stack.
public static <T> void asStack(MyStack<T> stack, T...elements) { // (1)
for (T element : elements) {
stack.push(element);
}
}
The method above is called by the client code below at (4). The idea is to initialize a stack of stacks of Integer with a stack of Integer. An implicit generic array (new MyStack<Integer>[] { intStack
}) is created by the compiler, which is passed in the method call at (4). The compiler also issues an unchecked array creation warning, but the code compiles and runs without any problems.
/* Client code */
// (2) Create a stack of stacks of Integer:
MyStack
<MyStack<Integer>> stackOfStacks = new MyStack<MyStack<Integer>>();
// (3) Create a stack of Integer:
MyStack<Integer> intStack = new MyStack<Integer>();
intStack.push(2008); intStack.push(2009);
// Initializes the stack of stacks with the stack of Integer.
MyStack.asStack(stackOfStacks, intStack); // (4) Unchecked array creation!
intStack = stackOfStacks.pop(); // (5) Pop the stack of stacks of Integer.
int tos = intStack.pop(); // (6) Pop the stack of Integer.
assert tos == 2008;
The implicit array passed as argument is available as an array of a non-reifiable type in the body of the method asStack(). The integrity of this array can be compromised by making the array store check report a false positive, i.e., succeed when the store operation should normally fail. This is demonstrated by the method declaration below, in the assignment statement at (1a), where the contents of the elements array are changed before they are copied to the specified stack.
public static <T> void asStackMalicious(MyStack<T> stack, T...elements) {
// Compromise the elements array:
MyStack<Double> doubleStack = new MyStack<Double>();
doubleStack.push(20.20);
elements[0] = (T) doubleStack;// (1a) Array store check
can be a false positive.
// Copy from array:
for (T element : elements) {
stack.push(element);
}
}
A partial erasure for the method asStackMalicious() is shown below.
public static void asStackMalicious(MyStack stack, Object...elements) {
// Compromise the elements array:
MyStack doubleStack = new MyStack();
doubleStack.push(Double.valueOf(20.20));
elements[0] = (Object) doubleStack; // (1b)
...
}
Note that the cast succeeds for any object at (1b). If we now call the method asStackMalicious(), instead of the method asStack() at (4) in the client code above, the code compiles with an unchecked cast warning at (1a), plus the generic array creation warning in the client code at (4).
MyStack.asStackMalicious(stackOfStacks, intStack); // (4') Unchecked warning!
At runtime, the reference elements in the method asStackMalicious() refers to the implicit array created in the call, i.e., new MyStack[] { intStack
}. The signature of the method call at runtime is equivalent to:
asStackMalicious(MyStack, MyStack[])
The assignment at (1a) succeeds, as the actual runtime element type of the elements array is MyStack, and the type of the value we want to assign is MyStack. The element type of the stack has been erased. When the code is run, the array store check succeeds at (1a), as does the assignment at (5). The error is only discovered after a ClassCastException is thrown at (6), because a Double cannot be assigned to an Integer. The general rule is to avoid varargs in methods where the parameter is of a non-reifiable type.