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 Section 18.3 and Section 18.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 Stack classes (e.g., "Stack of Double," "Stack of Integer," "Stack of Character," "Stack of Employee," etc.). 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 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 it to a primitive type variable.
Figure 18.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. (You will create a generic class with two type parameters in Exercise 18.8.) Type parameter E is used throughout the Stack class declaration to represent the element type. [ Note: This example implements a Stack as an array.]
Figure 18.7. Generic class Stack declaration.
(This item is displayed on page 881 in the print version)
|
1 // Fig. 18.7: Stack.java 2 // Generic class Stack. 3 4 public class Stack< E > 5 { 6 private final int size; // number of elements in the stack 7 private int top; // location of the top element 8 private E[] elements; // array that stores stack elements 9 10 // no-argument constructor creates a stack of the default size 11 public Stack() 12 { 13 this( 10 ); // default stack size 14 } // end no-argument Stack constructor 15 16 // constructor creates a stack of the specified number of elements 17 public Stack( int s ) 18 { 19 size = s > 0 ? s : 10; // set size of Stack 20 top = -1; // Stack initially empty 21 22 elements = ( E[] ) new Object[ size ]; // create array 23 } // end Stack constructor 24 25 // push element onto stack; if successful, return true; 26 // otherwise, throw FullStackException 27 public void push( E pushValue ) 28 { 29 if ( top == size - 1 ) // if stack is full 30 throw new FullStackException( String.format( 31 "Stack is full, cannot push %s", pushValue ) ); 32 33 elements[ ++top ] = pushValue; // place pushValue on Stack 34 } // end method push 35 36 // return the top element if not empty; else throw EmptyStackException 37 public E pop() 38 { 39 if ( top == -1 ) // if stack is empty 40 throw new EmptyStackException( "Stack is empty, cannot pop" ); 41 42 return elements[ top-- ]; // remove and return top element of Stack 43 } // end method pop 44 } // end class Stack< E > |
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 represents 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";
which places a String in an array that should contain only Integers, which would lead to runtime problems when the Stack is manipulated. 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 2734) first determines whether an attempt is being made to push an element onto a full Stack. If so, lines 3031 throw a FullStackException. Class FullStackException is declared in Fig. 18.8. If the Stack is not full, line 33 increments the top counter and places the argument in that location of array elements.
Figure 18.8. FullStackException class declaration.
|
1 // Fig. 18.8: FullStackException.java 2 // Indicates a stack is full. 3 public class FullStackException extends RuntimeException 4 { 5 // no-argument constructor 6 public FullStackException() 7 { 8 this( "Stack is full" ); 9 } // end no-argument FullStackException constructor 10 11 // one-argument constructor 12 public FullStackException( String exception ) 13 { 14 super( exception ); 15 } // end one-argument FullStackException constructor 16 } // end class FullStackException |
Method pop (lines 3743) 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. 18.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.
Figure 18.9. EmptyStackException class declaration.
|
1 // Fig. 18.9: EmptyStackException.java 2 // Indicates a stack is full. 3 public class EmptyStackException extends RuntimeException 4 { 5 // no-argument constructor 6 public EmptyStackException() 7 { 8 this( "Stack is empty" ); 9 } // end no-argument EmptyStackException constructor 10 11 // one-argument constructor 12 public EmptyStackException( String exception ) 13 { 14 super( exception ); 15 } // end one-argument EmptyStackException constructor 16 } // end class EmptyStackException |
Classes FullStackException (Fig. 18.8) and EmptyStackException (Fig. 18.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. 18.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. 18.10) that uses the Stack generic class. Lines 910 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 2544), testPopDouble (lines 4767), testPushInteger (lines 7089) and testPopInteger (lines 92112) to demonstrate the two Stacks in this example.
Figure 18.10. Generic class Stack test program.
(This item is displayed on pages 883 - 886 in the print version)
|
1 // Fig. 18.10: StackTest.java 2 // Stack generic class test program. 3 4 public class StackTest 5 { 6 private double[] doubleElements = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6 }; 7 private int[] integerElements = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }; 8 9 private Stack< Double > doubleStack; // stack stores Double objects 10 private Stack< Integer > integerStack; // stack stores Integer objects 11 12 // test Stack objects 13 public void testStacks() 14 { 15 doubleStack = new Stack< Double >( 5 ); // Stack of Doubles 16 integerStack = new Stack< Integer >( 10 ); // Stack of Integers 17 18 testPushDouble(); // push double onto doubleStack 19 testPopDouble(); // pop from doubleStack 20 testPushInteger(); // push int onto intStack 21 testPopInteger(); // pop from intStack 22 } // end method testStacks 23 24 // test push method with double stack 25 public void testPushDouble() 26 { 27 // push elements onto stack 28 try 29 { 30 System.out.println( " Pushing elements onto doubleStack" ); 31 32 // push elements to Stack 33 for ( double element : doubleElements ) 34 { 35 System.out.printf( "%.1 f ", element ); 36 doubleStack.push( element ); // push onto doubleStack 37 } // end for 38 } // end try 39 catch ( FullStackException fullStackException ) 40 { 41 System.err.println(); 42 fullStackException.printStackTrace(); 43 } // end catch FullStackException 44 } // end method testPushDouble 45 46 // test pop method with double stack 47 public void testPopDouble() 48 { 49 // pop elements from stack 50 try 51 { 52 System.out.println( " Popping elements from doubleStack" ); 53 double popValue; // store element removed from stack 54 55 // remove all elements from Stack 56 while ( true ) 57 { 58 popValue = doubleStack.pop(); // pop from doubleStack 59 System.out.printf( "%.1 f ", popValue ); 60 } // end while 61 } // end try 62 catch( EmptyStackException emptyStackException ) 63 { 64 System.err.println(); 65 emptyStackException.printStackTrace(); 66 } // end catch EmptyStackException 67 } // end method testPopDouble 68 69 // test push method with integer stack 70 public void testPushInteger() 71 { 72 // push elements to stack 73 try 74 { 75 System.out.println( " Pushing elements onto intStack" ); 76 77 // push elements to Stack 78 for ( int element : integerElements ) 79 { 80 System.out.printf( "%d ", element ); 81 integerStack.push( element ); // push onto integerStack 82 } // end for 83 } // end try 84 catch ( FullStackException fullStackException ) 85 { 86 System.err.println(); 87 fullStackException.printStackTrace(); 88 } // end catch FullStackException 89 } // end method testPushInteger 90 91 // test pop method with integer stack 92 public void testPopInteger() 93 { 94 // pop elements from stack 95 try 96 { 97 System.out.println( " Popping elements from intStack" ); 98 int popValue; // store element removed from stack 99 100 // remove all elements from Stack 101 while ( true ) 102 { 103 popValue = integerStack.pop(); // pop from intStack 104 System.out.printf( "%d ", popValue ); 105 } // end while 106 } // end try 107 catch( EmptyStackException emptyStackException ) 108 { 109 System.err.println(); 110 emptyStackException.printStackTrace(); 111 } // end catch EmptyStackException 112 } // end method testPopInteger 113 114 public static void main( String args[] ) 115 { 116 StackTest application = new StackTest(); 117 application.testStacks(); 118 } // end main 119 } // end class StackTest
|
Method testPushDouble (lines 2544) 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. 18.8) to indicate that the Stack is full. Lines 3943 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 3031 of the file Stack.java (Fig. 18.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 4767) 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 5761) continues until the stack is empty (i.e., until an EmptyStackException occurs), which causes the program to proceed to the catch block (lines 6266) 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 18.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 7089) invokes Stack method push to place values onto integerStack until it is full. Method testPopInteger (lines 92112) 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 18.11 declares generic method testPush (lines 2646) to perform the same tasks as testPushDouble and testPushInteger in Fig. 18.10that is, push values onto a Stack< T >. Similarly, generic method testPop (lines 4969) performs the same tasks as testPopDouble and testPopInteger in Fig. 18.10that is, pop values off a Stack< T >. Note that the output of Fig. 18.11 precisely matches the output of Fig. 18.10.
Figure 18.11. Passing a generic type Stack to a generic method.
(This item is displayed on pages 887 - 889 in the print version)
|
1 // Fig. 18.11: StackTest2.java 2 // Stack generic class test program. 3 4 public class StackTest2 5 { 6 private Double[] doubleElements = { 1.1, 2.2, 3.3, 4.4, 5.5, 6.6 }; 7 private Integer[] integerElements = 8 { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 }; 9 10 private Stack< Double > doubleStack; // stack stores Double objects 11 private Stack< Integer > integerStack; // stack stores Integer objects 12 13 // test Stack objects 14 public void testStacks() 15 { 16 doubleStack = new Stack< Double >( 5 ); // Stack of Doubles 17 integerStack = new Stack< Integer >( 10 ); // Stack of Integers 18 19 testPush( "doubleStack", doubleStack, doubleElements ); 20 testPop( "doubleStack", doubleStack ); 21 testPush( "integerStack", integerStack, integerElements ); 22 testPop( "integerStack", integerStack ); 23 } // end method testStacks 24 25 // generic method testPush pushes elements onto a Stack 26 public < T > void testPush( String name, Stack< T > stack, 27 T[] elements ) 28 { 29 // push elements onto stack 30 try 31 { 32 System.out.printf( " Pushing elements onto %s ", name ); 33 34 // push elements onto Stack 35 for ( T element : elements ) 36 { 37 System.out.printf( "%s ", element ); 38 stack.push( element ); // push element onto stack 39 } 40 } // end try 41 catch ( FullStackException fullStackException ) 42 { 43 System.out.println(); 44 fullStackException.printStackTrace(); 45 } // end catch FullStackException 46 } // end method testPush 47 48 // generic method testPop pops elements from a Stack 49 public < T > void testPop( String name, Stack< T > stack ) 50 { 51 // pop elements from stack 52 try 53 { 54 System.out.printf( " Popping elements from %s ", name ); 55 T popValue; // store element removed from stack 56 57 // remove elements from Stack 58 while ( true ) 59 { 60 popValue = stack.pop(); // pop from stack 61 System.out.printf( "%s ", popValue ); 62 } // end while 63 } // end try 64 catch( EmptyStackException emptyStackException ) 65 { 66 System.out.println(); 67 emptyStackException.printStackTrace(); 68 } // end catch EmptyStackException 69 } // end method testPop 70 71 public static void main( String args[] ) 72 { 73 StackTest2 application = new StackTest2(); 74 application.testStacks(); 75 } // end main 76 } // end class StackTest2
|
The testStacks method (lines 1423) creates the Stack< Double > (line 16) and Stack< Integer > (line 17) objects. Lines 1922 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 68 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 2646) uses type parameter T (specified at line 26) to represent the data type stored in the Stack< T >. The generic method takes three argumentsa 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 Tthe 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 4969) takes two argumentsa String that represents the name of the Stack< T > object for output purposes and a reference to an object of type Stack< T >.