15. Generics
Objectives
In this chapter you’ll learn:
• To create generic methods that perform identical tasks on arguments of different types.
• To create a generic Stack class that can be used to store objects of any class or interface type.
• To understand how to overload generic methods with non-generic methods or with other generic methods.
• To understand raw types and how they help achieve backward compatibility.
• To use wildcards when precise type information about a parameter is not required in the method body.
• The relationship between generics and inheritance.
Every man of genius sees the world at a different angle from his fellows.
—Havelock Ellis
...our special individuality, as distinguished from our generic humanity.
—Oliver Wendell Holmes, Sr.
Born under one law, to another bound.
—Lord Brooke
You deal in the raw material of opinion, and, if my convictions have any validity, opinion ultimately governs the world.
—Woodrow Wilson
Outline
15.1 Introduction
15.2 Motivation for Generic Methods
15.3 Generic Methods: Implementation and Compile-Time Translation
15.4 Additional Compile-Time Translation Issues: Methods That Use a Type Parameter as the Return Type
15.5 Overloading Generic Methods
15.6 Generic Classes
15.7 Raw Types
15.8 Wildcards in Methods That Accept Type Parameters
15.9 Generics and Inheritance: Notes
15.10 Wrap-Up
15.11 Internet and Web Resources
15.1 Introduction
It would be nice if we could write a single sort method that could sort the elements in an Integer array, a String array or an array of any type that supports ordering (i.e., its elements can be compared). It would also be nice if we could write a single Stack class that could be used as a Stack of integers, a Stack of floating-point numbers, a Stack of Strings or a Stack of any other type. It would be even nicer if we could detect type mismatches at compile time—known as compile-time type safety. For example, if a Stack stores only integers, attempting to push a String on to that Stack should issue a compile-time error.
This chapter discusses generics, which provide the means to create the general models mentioned above. Generic methods and generic classes enable you to specify, with a single method declaration, a set of related methods or, with a single class declaration, a set of related types, respectively. Generics also provide compile-time type safety that allows invalid types to be caught at compile time.
We might write a generic method for sorting an array of objects, then invoke the generic method with Integer arrays, Double arrays, String arrays and so on, to sort the array elements. The compiler could perform type checking to ensure that the array passed to the sorting method contains the same type elements. We might write a single generic Stack class that manipulates a stack of objects, then instantiate Stack objects for a stack of Integers, a stack of Doubles, a stack of Strings and so on. The compiler could perform type checking to ensure that the Stack stores elements of the same type.
Software Engineering Observation 15.1
Generic methods and classes are among Java’s most powerful capabilities for software reuse with compile-time type safety.
This chapter presents generic method and generic class examples. It also considers the relationships between generics and other Java features, such as overloading and inheritance. Chapter 16, Collections, presents an in-depth treatment of the Java Collections Framework’s generic methods and classes. A collection is a data structure that maintains references to many objects. The Java Collections Framework uses generics to allow programmers to specify the exact types of objects that a particular collection will store in a program.
15.2 Motivation for Generic Methods
Overloaded methods are often used to perform similar operations on different types of data. To motivate generic methods, let’s begin with an example (Fig. 15.1) that contains three overloaded printArray methods (lines 7–14, lines 17–24 and lines 27–34). These methods print the string representations of the elements of an Integer array, a Double array and a Character array, respectively. Note that we could have used arrays of primitive types int, double and char in this example. We chose to use arrays of type Integer, Double and Character to set up our generic method example, because only reference types can be used with generic methods and classes.
Fig. 15.1. Printing array elements using overloaded methods.
The program begins by declaring and initializing three arrays—six-element Integer array integerArray (line 39), seven-element Double array doubleArray (line 40) and five-element Character array characterArray (line 41). Then, lines 43–48 output the arrays.
When the compiler encounters a method call, it always attempts to locate a method declaration that has the same method name and parameters that match the argument types in the method call. In this example, each printArray call exactly matches one of the printArray method declarations. For example, line 44 calls printArray with integerArray as its argument. At compile time, the compiler determines argument integerArray’s type (i.e., Integer[]) and attempts to locate a method named printArray that specifies a single Integer[] parameter (lines 7–14) and sets up a call to that method. Similarly, when the compiler encounters the printArray call at line 46, it determines argument doubleArray’s type (i.e., Double[]), then attempts to locate a method named printArray that specifies a single Double[] parameter (lines 17–24) and sets up a call to that method. Finally, when the compiler encounters the printArray call at line 48, it determines argument characterArray’s type (i.e., Character[]), then attempts to locate a method named printArray that specifies a single Character[] parameter (lines 27–34) and sets up a call to that method.
Study each printArray method. Note that the array element type appears in two locations in each method—the method header (lines 7, 17 and 27) and the for statement header (lines 10, 20 and 30). If we were to replace the element types in each method with a generic name—by convention we’ll use E to represent the “element” type—then all three methods would look like the one in Fig. 15.2. It appears that if we can replace the array element type in each of the three methods with a single generic type, then we should be able to declare one printArray method that can display the string representations of the elements of any array that contains objects. Note that the format specifier %s can be used to output any object’s string representation—the object’s toString method will be called implicitly. The method in Fig. 15.2 is similar to the generic printArray method declaration we discuss in Section 15.3.
Fig. 15.2. printArray method in which actual type names are replaced by convention with the generic name E.
15.3 Generic Methods: Implementation and Compile-Time Translation
If the operations performed by several overloaded methods are identical for each argument type, the overloaded methods can be more compactly and conveniently coded using a generic method. You can write a single generic method declaration that can be called with arguments of different types. Based on the types of the arguments passed to the generic method, the compiler handles each method call appropriately.
Figure 15.3 reimplements the application of Fig. 15.1 using a generic printArray method (lines 7–14). Note that the printArray method calls in lines 24, 26 and 28 are identical to those of Fig. 15.1 (lines 44, 46 and 48) and that the outputs of the two applications are identical. This dramatically demonstrates the expressive power of generics.
Fig. 15.3. Printing array elements using generic method printArray.
Line 7 begins method printArray’s declaration. All generic method declarations have a type parameter section delimited by angle brackets (< and >) that precedes the method’s return type (< E > in this example). Each type parameter section contains one or more type parameters (also called formal type parameters), separated by commas. A type parameter, also known as a type variable, is an identifier that specifies a generic type name. The type parameters can be used to declare the return type, parameter types and local variable types in a generic method declaration, and act as placeholders for the types of the arguments passed to the generic method, which are known as actual type arguments. A generic method’s body is declared like that of any other method. Note that type parameters can represent only reference types—not primitive types (like int, double and char). Note, too, that the type parameter names throughout the method declaration must match those declared in the type parameter section. For example, line 10 declares element as type E, which matches the type parameter (E) declared in line 7. Also, a type parameter can be declared only once in the type parameter section but can appear more than once in the method’s parameter list. For example, the type parameter name E appears twice in the following method’s parameter list:
public static < E > void printTwoArrays( E[] array1, E[] array2 )
Type-parameter names need not be unique among different generic methods.
Common Programming Error 15.1
When declaring a generic method, failing to place a type parameter section before the return type of a method is a syntax error—the compiler will not understand the type parameter name when it is encountered in the method.
Method printArray’s type parameter section declares type parameter, E, as the placeholder for the array element type that printArray will output. Note that E appears in the parameter list as the array element type (line 7). The for statement header (line 10) also uses E as the element type. These are the same two locations where the overloaded printArray methods of Fig. 15.1 specified Integer, Double or Character as the array element type. The remainder of printArray is identical to the versions presented in Fig. 15.1.
Good Programming Practice 15.1
It is recommended that type parameters be specified as individual capital letters. Typically, a type parameter that represents an array element’s type (or other collection) is named E for “element.”
As in Fig. 15.1, the program begins by declaring and initializing six-element Integer array integerArray (line 19), seven-element Double array doubleArray (line 20) and five-element Character array characterArray (line 21). Then the program outputs each array by calling printArray (lines 24, 26 and 28)—once with argument integerArray, once with argument doubleArray and once with argument characterArray.
When the compiler encounters line 24, it first determines argument integerArray’s type (i.e., Integer[]) and attempts to locate a method named printArray that specifies a single Integer[] parameter. There is no such method in this example. Next, the compiler determines whether there is a generic method named printArray that specifies a single array parameter and uses a type parameter to represent the array element type. The compiler determines that printArray (lines 7–14) is a match and sets up a call to the method. The same process is repeated for the calls to method printArray at lines 26 and 28.
Common Programming Error 15.2
If the compiler cannot match a method call to a non-generic or a generic method declaration, a compilation error occurs.
Common Programming Error 15.3
If the compiler does not find a method declaration that matches a method call exactly, but does find two or more generic methods that can satisfy the method call, a compilation error occurs.
In addition to setting up the method calls, the compiler also determines whether the operations in the method body can be applied to elements of the type stored in the array argument. The only operation performed on the array elements in this example is to output the string representation of the elements. Line 11 performs an implicit toString call on every element. To work with generics, every element of the array must be an object of a class or interface type. Since all objects have a toString method, the compiler is satisfied that line 11 performs a valid operation for any object in printArray’s array argument. The toString methods of classes Integer, Double and Character return the string representation of the underlying int, double or char value, respectively.
When the compiler translates generic method printArray into Java bytecodes, it removes the type parameter section and replaces the type parameters with actual types. This process is known as erasure. By default all generic types are replaced with type Object. So the compiled version of method printArray appears as shown in Fig. 15.4—there is only one copy of this code which is used for all printArray calls in the example. This is quite different from other, similar mechanisms, such as C++’s templates, in which a separate copy of the source code is generated and compiled for every type passed as an argument to the method. As we’ll discuss in Section 15.4, the translation and compilation of generics is a bit more involved than what we have discussed in this section.
Fig. 15.4. Generic method printArray after erasure is performed by the compiler.
By declaring printArray as a generic method in Fig. 15.3, we eliminated the need for the overloaded methods of Fig. 15.1, saving 20 lines of code and creating a reusable method that can output the string representations of the elements in any array that contains objects. However, this particular example could have simply declared the printArray method as shown in Fig. 15.4 using an Object array as the parameter. This would have yielded the same results, because any Object can be output as a String. In a generic method, the benefits become apparent when the method also uses a type parameter as the method’s return type, as we demonstrate in the next section.
15.4 Additional Compile-Time Translation Issues: Methods That Use a Type Parameter as the Return Type
Let’s consider a generic method example in which type parameters are used in the return type and in the parameter list (Fig. 15.5). The application uses a generic method maximum to determine and return the largest of its three arguments of the same type. Unfortunately, the relational operator > cannot be used with reference types. However, it is possible to compare two objects of the same class if that class implements the generic interface Comparable< T > (package java.lang). All the type-wrapper classes for primitive types implement this interface. Like generic classes, generic interfaces enable programmers to specify, with a single interface declaration, a set of related types. Comparable< T > objects have a compareTo method. For example, if we have two Integer objects, integer1 and integer2, they can be compared with the expression:
integer1.compareTo( integer2 )
Fig. 15.5. Generic method maximum with an upper bound on its type parameter.
It is the responsibility of the programmer who declares a class that implements Comparable< T > to declare method compareTo such that it compares the contents of two objects of that class and returns the results of the comparison. The method must return 0 if the objects are equal, -1 if object1 is less than object2 or 1 if object1 is greater than object2. For example, class Integer’s compareTo method compares the int values stored in two Integer objects. A benefit of implementing interface Comparable< T > is that Comparable< T > objects can be used with the sorting and searching methods of class Collections (package java.util). We discuss those methods in Chapter 16, Collections. In this example, we’ll use method compareTo in method maximum to help determine the largest value.
Generic method maximum (lines 7–18) uses type parameter T as the return type of the method (line 7), as the type of method parameters x, y and z (line 7), and as the type of local variable max (line 9). The type parameter section specifies that T extends Comparable< T >—only objects of classes that implement interface Comparable< T > can be used with this method. In this case, Comparable is known as the upper bound of the type parameter. By default, Object is the upper bound. Note that type parameter declarations that bound the parameter always use keyword extends regardless of whether the type parameter extends a class or implements an interface. This type parameter is more restrictive than the one specified for printArray in Fig. 15.3, which was able to output arrays containing any type of object. The restriction of using Comparable< T > objects is important, because not all objects can be compared. However, Comparable< T > objects are guaranteed to have a compareTo method.
Method maximum uses the same algorithm that we used in Section 6.4 to determine the largest of its three arguments. The method assumes that its first argument (x) is the largest and assigns it to local variable max (line 9). Next, the if statement at lines 11–12 determines whether y is greater than max. The condition invokes y’s compareTo method with the expression y.compareTo( max ), which returns -1, 0 or 1, to determine y’s relationship to max. If the return value of the compareTo is greater than 0, then y is greater and is assigned to variable max. Similarly, the if statement at lines 14–15 determines whether z is greater than max. If so, line 15 assigns z to max. Then, line 17 returns max to the caller.
In main (lines 20–28), line 23 calls maximum with the integers 3, 4 and 5. When the compiler encounters this call, it first looks for a maximum method that takes three arguments of type int. There is no such method, so the compiler looks for a generic method that can be used and finds generic method maximum. However, recall that the arguments to a generic method must be of a reference type. So the compiler autoboxes the three int values as Integer objects and specifies that the three Integer objects will be passed to maximum. Note that class Integer (package java.lang) implements interface Comparable< Integer > such that method compareTo compares the int values in two Integer objects. Therefore, Integers are valid arguments to method maximum. When the Integer representing the maximum is returned, we attempt to output it with the %d format specifier, which outputs an int primitive type value. So maximum’s return value is output as an int value.
A similar process occurs for the three double arguments passed to maximum in line 25. Each double is autoboxed as a Double object and passed to maximum. Again, this is allowed because class Double (package java.lang) implements the Comparable< Double > interface. The Double returned by maximum is output with the format specifier %.1f, which outputs a double primitive-type value. So maximum’s return value is auto-unboxed and output as a double. The call to maximum in line 27 receives three Strings, which are also Comparable< String > objects. Note that we intentionally placed the largest value in a different position in each method call (lines 23, 25 and 27) to show that the generic method always finds the maximum value, regardless of its position in the argument list.
When the compiler translates generic method maximum into Java bytecodes, it uses erasure (introduced in Section 15.3) to replace the type parameters with actual types. In Fig. 15.3, all generic types were replaced with type Object. Actually, all type parameters are replaced with the upper bound of the type parameter—unless specified otherwise, Object is the default upper bound. The upper bound of a type parameter is specified in the type parameter section. To indicate the upper bound, follow the type parameter’s name with the keyword extends and the class or interface name that represents the upper bound. In method maximum’s type parameter section (Fig. 15.5), we specified the upper bound as type Comparable< T >. Thus, only Comparable< T > objects can be passed as arguments to maximum—anything that is not Comparable< T > will result in compilation errors. Figure 15.6 simulates the erasure of method maximum’s types by showing the method’s source code after the type parameter section is removed and type parameter T is replaced with the upper bound, Comparable, throughout the method declaration. Note that the erasure of Comparable< T > is simply Comparable.
Fig. 15.6. Generic method maximum after erasure is performed by the compiler.
After erasure, the compiled version of method maximum specifies that it returns type Comparable. However, the calling method does not expect to receive a Comparable. Rather, the caller expects to receive an object of the same type that was passed to maximum as an argument—Integer, Double or String in this example. When the compiler replaces the type parameter information with the upper bound type in the method declaration, it also inserts explicit cast operations in front of each method call to ensure that the returned value is of the type expected by the caller. Thus, the call to maximum in line 23 (Fig. 15.5) is preceded by an Integer cast, as in
(Integer) maximum( 3, 4, 5 )
the call to maximum in line 25 is preceded by a Double cast, as in
(Double) maximum( 6.6, 8.8, 7.7 )
and the call to maximum in line 27 is preceded by a String cast, as in
(String) maximum( "pear", "apple", "orange" )
In each case, the type of the cast for the return value is inferred from the types of the method arguments in the particular method call, because, according to the method declaration, the return type and the argument types match.
In this example, you cannot use a method that accepts Objects, because class Object provides only an equality comparison. Also, without generics, you would be responsible for implementing the cast operation. Using generics ensures that the inserted cast will never throw a ClassCastException, assuming that generics are used throughout your code (i.e., you do not mix old code with new generics code).
15.5 Overloading Generic Methods
A generic method may be overloaded. A class can provide two or more generic methods that specify the same method name but different method parameters. For example, generic method printArray of Fig. 15.3 could be overloaded with another printArray generic method with the additional parameters lowSubscript and highSubscript to specify the portion of the array to output.
A generic method can also be overloaded by non-generic methods that have the same method name and number of parameters. When the compiler encounters a method call, it searches for the method declaration that most precisely matches the method name and the argument types specified in the call. For example, generic method printArray of Fig. 15.3 could be overloaded with a version that is specific to Strings, which outputs the Strings in neat, tabular format.
When the compiler encounters a method call, it performs a matching process to determine which method to invoke. The compiler tries to find and use a precise match in which the method names and argument types of the method call match those of a specific method declaration. If there is no such method, the compiler determines whether there is an inexact but applicable matching method.
15.6 Generic Classes
The concept of a data structure, such as a stack, can be understood independently of the element type it manipulates. Generic classes provide a means for describing the concept of a stack (or any other class) in a type-independent manner. We can then instantiate type-specific objects of the generic class. This capability provides a wonderful opportunity for software reusability.
Once you have a generic class, you can use a simple, concise notation to indicate the actual type(s) that should be used in place of the class’s type parameter(s). At compilation time, the Java compiler ensures the type safety of your code and uses the erasure techniques described in Sections 15.3–15.4 to enable your client code to interact with the generic class.
One generic Stack class, for example, could be the basis for creating many logical Stack classes (e.g., “Stack of Double,” “Stack of Integer,” “Stack of Character,” “Stack of Employee”). These classes are known as parameterized classes or parameterized types because they accept one or more parameters. Recall that type parameters represent only reference types, which means that the Stack generic class cannot be instantiated with primitive types. However, we can instantiate a Stack that stores objects of Java’s type-wrapper classes and allow Java to use autoboxing to convert the primitive values into objects. Autoboxing occurs when a value of a primitive type (e.g., int) is pushed onto a Stack that contains wrapper-class objects (e.g., Integer). Auto-unboxing occurs when an object of the wrapper class is popped off the Stack and assigned to a primitive-type variable.
Figure 15.7 presents a generic Stack class declaration. A generic class declaration looks like a non-generic class declaration, except that the class name is followed by a type parameter section (line 4). In this case, type parameter E represents the element type the Stack will manipulate. As with generic methods, the type parameter section of a generic class can have one or more type parameters separated by commas. Type parameter E is used throughout the Stack class declaration to represent the element type. [Note: This example implements a Stack as an array.]
Fig. 15.7. Generic class Stack declaration.
Class Stack declares variable elements as an array of type E (line 8). This array will store the Stack’s elements. We would like to create an array of type E to store the elements. However, the generics mechanism does not allow type parameters in array-creation expressions because the type parameter (in this case, E) is not available at runtime. To create an array with the appropriate type, line 22 in the one-argument constructor creates the array as an array of type Object and casts the reference returned by new to type E[]. Any object could be stored in an Object array, but the compiler’s type-checking mechanism ensures that only objects of the array variable’s declared type can be assigned to the array via any array-access expression that uses variable elements. Yet when this class is compiled using the -Xlint:unchecked option, e.g.,
javac -Xlint:unchecked Stack.java
the compiler issues the following warning message about line 22:
Stack.java:22: warning: [unchecked] unchecked cast
found : java.lang.Object[]
required: E[]
elements = ( E[] ) new Object[ size ]; // create array
The reason for this message is that the compiler cannot ensure with 100% certainty that an array of type Object will never contain objects of types other than E. Assume that E rep-resents type Integer, so that array elements should store Integer objects. It is possible to assign variable elements to a variable of type Object[], as in
Object[] objectArray = elements;
Then any object can be placed into the array with an assignment statement like
objectArray[ 0 ] = "hello";
This places a String in an array that should contain only Integers, which would lead to runtime problems when manipulating the Stack. As long as you do not perform statements like those shown here, your Stack will contain objects of only the correct element type.
Method push (lines 27–34) first determines whether an attempt is being made to push an element onto a full Stack. If so, lines 30–31 throw a FullStackException. Class FullStackException is declared in Fig. 15.8. If the Stack is not full, line 33 increments the top counter and places the argument in that location of array elements.
Fig. 15.8. FullStackException class declaration.
Method pop (lines 37–43) first determines whether an attempt is being made to pop an element from an empty Stack. If so, line 40 throws an EmptyStackException. Class EmptyStackException is declared in Fig. 15.9. Otherwise, line 42 returns the top element of the Stack, then postdecrements the top counter to indicate the position of the next top element.
Fig. 15.9. EmptyStackException class declaration.
Classes FullStackException (Fig. 15.8) and EmptyStackException (Fig. 15.9) each provide the conventional no-argument constructor and one-argument constructor of exception classes (as discussed in Section 13.11). The no-argument constructor sets the default error message, and the one-argument constructor sets a custom exception message.
As with generic methods, when a generic class is compiled, the compiler performs erasure on the class’s type parameters and replaces them with their upper bounds. For class Stack (Fig. 15.7), no upper bound is specified, so the default upper bound, Object, is used. The scope of a generic class’s type parameter is the entire class. However, type parameters cannot be used in a class’s static declarations.
Now, let’s consider the test application (Fig. 15.10) that uses the Stack generic class. Lines 9–10 declare variables of type Stack< Double > (pronounced “Stack of Double”) and Stack< Integer > (pronounced “Stack of Integer”). The types Double and Integer are known as the Stack’s type arguments. They are used by the compiler to replace the type parameters so that the compiler can perform type checking and insert cast operations as necessary. We’ll discuss the cast operations in more detail shortly. Method testStack (called from main) instantiates objects doubleStack of size 5 (line 15) and integerStack of size 10 (line 16), then calls methods testPushDouble (lines 25–44), testPopDouble (lines 47–67), testPushInteger (lines 70–89) and testPopInteger (lines 92–112) to demonstrate the two Stacks in this example.
Fig. 15.10. Generic class Stack test program.
Method testPushDouble (lines 25–44) invokes method push to place the double values 1.1, 2.2, 3.3, 4.4 and 5.5 stored in array doubleElements onto doubleStack. The for loop terminates when the test program attempts to push a sixth value onto doubleStack (which is full, because doubleStack can store only five elements). In this case, the method throws a FullStackException (Fig. 15.8) to indicate that the Stack is full. Lines 39–43 catch this exception and print the stack trace information. The stack trace indicates the exception that occurred and shows that Stack method push generated the exception at lines 30–31 of the file Stack.java (Fig. 15.7). The trace also shows that method push was called by StackTest method testPushDouble at line 36 of StackTest.java, that method testPushDouble was called from method testStacks at line 18 of StackTest.java and that method testStacks was called from method main at line 117 of StackTest.java. This information enables you to determine the methods that were on the method-call stack at the time that the exception occurred. Because the program catches the exception, the Java runtime environment considers the exception to have been handled and the program can continue executing. Note that autoboxing occurs in line 36 when the program tries to push a primitive double value onto the doubleStack, which stores only Double objects.
Method testPopDouble (lines 47–67) invokes Stack method pop in an infinite while loop to remove all the values from the stack. Note in the output that the values indeed pop off in last-in, first-out order (this, of course, is the defining characteristic of stacks). The while loop (lines 57–61) continues until the stack is empty (i.e., until an EmptyStackException occurs), which causes the program to proceed to the catch block (lines 62–66) and handle the exception, so the program can continue executing. When the test program attempts to pop a sixth value, the doubleStack is empty, so the pop throws an EmptyStackException. Auto-unboxing occurs in line 58 when the program assigns the Double object popped from the stack to a double primitive variable. Recall from Section 15.4 that the compiler inserts cast operations to ensure that the proper types are returned from generic methods. After erasure, Stack method pop returns type Object. However, the client code in method testPopDouble expects to receive a double when method pop returns. So the compiler inserts a Double cast, as in
popValue = ( Double ) doubleStack.pop();
to ensure that a reference of the appropriate type is returned, auto-unboxed and assigned to popValue.
Method testPushInteger (lines 70–89) invokes Stack method push to place values onto integerStack until it is full. Method testPopInteger (lines 92–112) invokes Stack method pop to remove values from integerStack until it is empty. Once again, note that the values pop off in last-in, first-out order. During the erasure process, the compiler recognizes that the client code in method testPopInteger expects to receive an int when method pop returns. So the compiler inserts an Integer cast, as in
popValue = ( Integer ) integerStack.pop();
to ensure that a reference of the appropriate type is returned, auto-unboxed and assigned to popValue.
Creating Generic Methods to Test Class Stack< E >
Note that the code in methods testPushDouble and testPushInteger is almost identical for pushing values onto a Stack< Double > or a Stack< Integer >, respectively, and the code in methods testPopDouble and testPopInteger is almost identical for popping values from a Stack< Double > or a Stack< Integer >, respectively. This presents another opportunity to use generic methods. Figure 15.11 declares generic method testPush (lines 26–46) to perform the same tasks as testPushDouble and testPushInteger in Fig. 15.10—that is, push values onto a Stack< T >. Similarly, generic method testPop (lines 49–69) performs the same tasks as testPopDouble and testPopInteger in Fig. 15.10—that is, pop values off a Stack< T >. Note that the output of Fig. 15.11 precisely matches the output of Fig. 15.10.
Fig. 15.11. Passing a generic type Stack to a generic method.
The testStacks method (lines 14–23) creates the Stack< Double > (line 16) and Stack< Integer > (line 17) objects. Lines 19–22 invoke generic methods testPush and testPop to test the Stack objects. Recall that type parameters can represent only reference types. Therefore, to be able to pass arrays doubleElements and integerElements to generic method testPush, the arrays declared in lines 6–8 must be declared with the wrapper types Double and Integer. When these arrays are initialized with primitive values, the compiler autoboxes each primitive value.
Generic method testPush (lines 26–46) uses type parameter T (specified at line 26) to represent the data type stored in the Stack< T >. The generic method takes three arguments—a String that represents the name of the Stack< T > object for output purposes, a reference to an object of type Stack< T > and an array of type T—the type of elements that will be pushed onto Stack< T >. Note that the compiler enforces consistency between the type of the Stack and the elements that will be pushed onto the Stack when push is invoked, which is the real value of the generic method call. Generic method testPop (lines 49–69) takes two arguments—a String that represents the name of the Stack< T > object for output purposes and a reference to an object of type Stack< T >.
15.7 Raw Types
The test programs for generic class Stack in Section 15.6 instantiate Stacks with type arguments Double and Integer. It is also possible to instantiate generic class Stack without specifying a type argument, as follows:
Stack objectStack = new Stack( 5 ); // no type argument specified
In this case, the objectStack is said to have a raw type, which means that the compiler implicitly uses type Object throughout the generic class for each type argument. Thus the preceding statement creates a Stack that can store objects of any type. This is important for backward compatibility with prior versions of Java. For example, the data structures of the Java Collections Framework (see Chapter 16) all stored references to Objects, but are now implemented as generic types.
A raw type Stack variable can be assigned a Stack that specifies a type argument, such as a Stack< Double > object, as follows:
Stack rawTypeStack2 = new Stack< Double >( 5 );
because type Double is a subclass of Object. This assignment is allowed because the elements in a Stack< Double > (i.e., Double objects) are certainly objects—class Double is an indirect subclass of Object.
Similarly, a Stack variable that specifies a type argument in its declaration can be assigned a raw type Stack object, as in:
Stack< Integer > integerStack = new Stack( 10 );
Although this assignment is permitted, it is unsafe because a Stack of raw type might store types other than Integer. In this case, the compiler issues a warning message which indicates the unsafe assignment.
The test program of Fig. 15.12 uses the notion of raw type. Line 14 instantiates generic class Stack with raw type, which indicates that rawTypeStack1 can hold objects of any type. Line 17 assigns a Stack< Double > to variable rawTypeStack2, which is declared as a Stack of raw type. Line 20 assigns a Stack of raw type to Stack< Integer > variable, which is legal but causes the compiler to issue a warning message (Fig. 15.13) indicating a potentially unsafe assignment—again, this occurs because a Stack of raw type might store types other than Integer. Also, each of the calls to generic method testPush and testPop in lines 22–25 results in a compiler warning message (Fig. 15.13). These warnings occur because variables rawTypeStack1 and rawTypeStack2 are declared as Stacks of raw type, but methods testPush and testPop each expect a second argument that is a Stack with a specific type argument. The warnings indicate that the compiler cannot guarantee that the types manipulated by the stacks are the correct types, because we did not supply a variable declared with a type argument. Methods testPush (lines 31–51) and testPop (lines 54–74) are the same as in Fig. 15.11.
Fig. 15.12. Raw type test program.
Fig. 15.13. Warning messages from the compiler.
Figure 15.13 shows the warning messages generated by the compiler (compiled with the -Xlint:unchecked option) when the file RawTypeTest.java (Fig. 15.12) is compiled. The first warning is generated for line 20, which assigned a raw type Stack to a Stack< Integer > variable—the compiler cannot ensure that all objects in the Stack will be Integer objects. The second warning is generated for line 22. Because the second method argument is a raw type Stack variable, the compiler determines the type argument for method testPush from the Double array passed as the third argument. In this case, Double is the type argument, so the compiler expects a Stack< Double > to be passed as the second argument. The warning occurs because the compiler cannot ensure that a raw type Stack contains only Double objects. The warning at line 24 occurs for the same reason, even though the actual Stack that rawTypeStack2 references is a Stack< Double >. The compiler cannot guarantee that the variable will always refer to the same Stack object, so it must use the variable’s declared type to perform all type checking. Lines 23 and 25 each generate warnings because method testPop expects as an argument a Stack for which a type argument has been specified. However, in each call to testPop, we pass a raw type Stack variable. Thus, the compiler indicates a warning because it cannot check the types used in the body of the method.
15.8 Wildcards in Methods That Accept Type Parameters
In this section, we introduce a powerful generics concept known as wildcards. For this purpose, we’ll also introduce a new data structure from package java.util. Chapter 16, discusses the Java Collections Framework, which provides many generic data structures and algorithms that manipulate the elements of those data structures. Perhaps the simplest of these data structures is class ArrayList—a dynamically resizable, array-like data structure. As part of this discussion, you’ll learn how to create an ArrayList, add elements to it and traverse those elements using an enhanced for statement.
Before we introduce wildcards, let’s consider an example that helps us motivate their use. Suppose that you would like to implement a generic method sum that totals the numbers in a collection, such as an ArrayList. You would begin by inserting the numbers in the collection. As you know, generic classes can be used only with class or interface types. So the numbers would be autoboxed as objects of the type-wrapper classes. For example, any int value would be autoboxed as an Integer object, and any double value would be autoboxed as a Double object. We’d like to be able to total all the numbers in the ArrayList regardless of their type. For this reason, we’ll declare the ArrayList with the type argument Number, which is the superclass of both Integer and Double. In addition, method sum will receive a parameter of type ArrayList< Number > and total its elements. Figure 15.14 demonstrates totaling the elements of an ArrayList of Numbers.
Fig. 15.14. Totaling the numbers in an ArrayList< Number >.
Line 11 declares and initializes an array of Numbers. Because the initializers are primitive values, Java autoboxes each primitive value as an object of its corresponding wrapper type. The int values 1 and 3 are autoboxed as Integer objects, and the double values 2.4 and 4.1 are autoboxed as Double objects. Line 12 declares and creates an ArrayList object that stores Numbers and assigns it to variable numberList. Note that we do not have to specify the size of the ArrayList because it will grow automatically as we insert objects.
Lines 14–15 traverse array numbers and place each element in numberList. Method add of class ArrayList appends an element to the end of the collection. Line 17 outputs the contents of the ArrayList as a String. This statement implicitly invokes the ArrayList’s toString method, which returns a string of the form "[ elements ]" in which elements is a comma-separated list of the elements’ string representations. Lines 18–19 display the sum of the elements that is returned by the call to method sum at line 19.
Method sum (lines 23–32) receives an ArrayList of Numbers and calculates the total of the Numbers in the collection. The method uses double values to perform the calculations and returns the result as a double. Line 25 declares local variable total and initializes it to 0. Lines 28–29 use the enhanced for statement, which is designed to work with both arrays and the collections of the Collections Framework, to total the elements of the ArrayList. The for statement assigns each Number in the ArrayList to variable element, then uses method doubleValue of class Number to obtain the Number’s underlying primitive value as a double value. The result is added to total. When the loop terminates, the method returns the total.
Implementing Method sum With a Wildcard Type Argument in Its Parameter
Recall that the purpose of method sum in Fig. 15.14 was to total any type of Numbers stored in an ArrayList. We created an ArrayList of Numbers that contained both Integer and Double objects. The output of Fig. 15.14 demonstrates that method sum worked properly. Given that method sum can total the elements of an ArrayList of Numbers, you might expect that the method would also work for ArrayLists that contain elements of only one numeric type, such as ArrayList< Integer >. So we modified class TotalNumbers to create an ArrayList of Integers and pass it to method sum. When we compile the program, the compiler issues the following error message:
sum(java.util.ArrayList<java.lang.Number>) in TotalNumbersErrors
cannot be applied to (java.util.ArrayList<java.lang.Integer>)
Although Number is the superclass of Integer, the compiler does not consider the parameterized type ArrayList< Number > to be a supertype of ArrayList< Integer >. If it were, then every operation we could perform on ArrayList< Number > would also work on an ArrayList< Integer >. Consider the fact that you can add a Double object to an ArrayList< Number > because a Double is a Number, but you cannot add a Double object to an ArrayList< Integer > because a Double is not an Integer. Thus, the subtype relationship does not hold.
How do we create a more flexible version of method sum that can total the elements of any ArrayList that contains elements of any subclass of Number? This is where wildcard type arguments are important. Wildcards enable you to specify method parameters, return values, variables or fields, etc. that act as supertypes of parameterized types. In Fig. 15.15, method sum’s parameter is declared in line 50 with the type:
ArrayList< ? extends Number >
Fig. 15.15. Wildcard test program.
A wildcard type argument is denoted by a question mark (?), which by itself represents an “unknown type.” In this case, the wildcard extends class Number, which means that the wildcard has an upper bound of Number. Thus, the unknown type argument must be either Number or a subclass of Number. With the parameter type shown here, method sum can receive an ArrayList argument that contains any type of Number, such as ArrayList< Integer > (line 20), ArrayList< Double > (line 33) or ArrayList< Number > (line 46).
Lines 11–20 create and initialize an ArrayList< Integer > called integerList, output its elements and total its elements by calling method sum (line 20). Lines 24–33 perform the same operations for an ArrayList< Double > called doubleList. Lines 37–46 perform the same operations for an ArrayList< Number > called numberList that contains both Integers and Doubles.
In method sum (lines 50–59), although the ArrayList argument’s element types are not directly known by the method, they are known to be at least of type Number, because the wildcard was specified with the upper bound Number. For this reason line 56 is allowed, because all Number objects have a doubleValue method.
Although wildcards provide flexibility when passing parameterized types to a method, they also have some disadvantages. Because the wildcard (?) in the method’s header (line 50) does not specify a type-parameter name, you cannot use it as a type name throughout the method’s body (i.e., you cannot replace Number with ? in line 55). You could, however, declare method sum as follows:
public static <T extends Number> double sum( ArrayList< T > list )
which allows the method to receive an ArrayList that contains elements of any Number subclass. You could then use the type parameter T throughout the method body.
If the wildcard is specified without an upper bound, then only the methods of type Object can be invoked on values of the wildcard type. Also, methods that use wildcards in their parameter’s type arguments cannot be used to add elements to a collection referenced by the parameter.
Common Programming Error 15.4
Using a wildcard in a method’s type parameter section or using a wildcard as an explicit type of a variable in the method body is a syntax error.
15.9 Generics and Inheritance: Notes
Generics can be used with inheritance in several ways:
• A generic class can be derived from a non-generic class. For example, the Object class is a direct or indirect superclass of every generic class.
• A generic class can be derived from another generic class. For example, generic class Stack (in package java.util) is a subclass of generic class Vector (in package java.util). We discuss these classes in Chapter 16.
• A non-generic class can be derived from a generic class. For example, non-generic class Properties (in package java.util) is a subclass of generic class Hashtable (in package java.util). We also discuss these classes in Chapter 16.
• Finally, a generic method in a subclass can override a generic method in a super-class if both methods have the same signatures.
15.10 Wrap-Up
This chapter introduced generics. You learned how to declare generic methods and classes. You learned how backward compatibility is achieved via raw types. You also learned how to use wildcards in a generic method or a generic class. In the next chapter, we demonstrate the interfaces, classes and algorithms of the Java collections framework. As you’ll see, the collections presented all use the generics capabilties you learned here.
15.11 Internet and Web Resources
www.angelikalanger.com/GenericsFAQ/JavaGenericsFAQ.html
A collection of frequently asked questions about Java generics.
java.sun.com/j2se/1.5/pdf/generics-tutorial.pdf
The tutorial Generics in the Java Programming Language by Gilad Bracha (the specification lead for JSR-14 and a reviewer of this book) introduces generics concepts with sample code snippets.
today.java.net/pub/a/today/2003/12/02/explorations.html
today.java.net/pub/a/today/2004/01/15/wildcards.html
The articles Explorations: Generics, Erasure, and Bridging and Explorations: Wildcards in the Generics Specification, each by William Grosso, overview generics features and how to use wildcards.