Saturday 7 July 2012

Item 26: Favor generic types


It is generally not too difficult to parameterize your collection declarations and make use of the generic types and methods provided by the JDK. Writing your own generic types is a bit more difficult, but it’s worth the effort to learn how.

Consider the simple stack implementation:

// Object-based collection - a prime candidate for generics
public class Stack {
private Object[] elements;
private int size = 0;
private static final int DEFAULT_INITIAL_CAPACITY = 16;
public Stack() {
elements = new Object[DEFAULT_INITIAL_CAPACITY];
}
public void push(Object e) {
ensureCapacity();
elements[size++] = e;
}
public Object pop() {
if (size == 0)
throw new EmptyStackException();
Object result = elements[--size];
elements[size] = null; // Eliminate obsolete reference
return result;
}
public boolean isEmpty() {
return size == 0;
}
private void ensureCapacity() {
if (elements.length == size)
elements = Arrays.copyOf(elements, 2 * size + 1);
}
}

This class is a prime candidate for generification, in other words, for being compatibly enhanced to take advantage of generic types. As it stands, you have to cast objects that are popped off the stack, and those casts might fail at runtime.

The next step is to replace all the uses of the type Object with the appropriate type parameter, and then try to compile the resulting program:

// Initial attempt to generify Stack = won’t compile!
public class Stack<E> {
private E[] elements;
private int size = 0;
private static final int DEFAULT_INITIAL_CAPACITY = 16;
public Stack() {
elements = new E[DEFAULT_INITIAL_CAPACITY];
}
public void push(E e) {
ensureCapacity();
elements[size++] = e;
}
public E pop() {
if (size==0)
throw new EmptyStackException();
E result = elements[--size];
elements[size] = null; // Eliminate obsolete reference
return result;
}
... // no changes in isEmpty or ensureCapacity
}

You’ll generally get at least one error or warning, and this class is no exception. Luckily, this class generates only one error:

Stack.java:8: generic array creation
elements = new E[DEFAULT_INITIAL_CAPACITY];

As explained in Item 25, you can’t create an array of a non-reifiable type, such as E. There are two ways to solve it. The first solution directly circumvents the prohibition on generic array creation: create an array of Object and cast it to the generic array type. Now in place of an error, the compiler will emit a warning. This usage is legal, but it’s not (in general) typesafe:

Stack.java:8: warning: [unchecked] unchecked cast
found : Object[], required: E[]
elements = (E[]) new Object[DEFAULT_INITIAL_CAPACITY];
^

The array in question (elements) is stored in a private field and never returned to the client or passed to any other method. The only elements stored in the array are those passed to the push method, which are of type E, so the unchecked cast can do no harm. Once you’ve proved that an unchecked cast is safe, suppress the warning in as narrow a scope as possible (Item 24).

The second way to eliminate the generic array creation error in Stack is to change the type of the field elements from E[] to Object[]. If you do this, you’ll get a different error:

Stack.java:19: incompatible types
found : Object, required: E
E result = elements[--size];
^

You can change this error into a warning by casting the element retrieved from the array from Object to E:

Stack.java:19: warning: [unchecked] unchecked cast
found : Object, required: E
E result = (E) elements[--size];
^

Because E is a non-reifiable type, there’s no way the compiler can check the cast at runtime. Again, you can easily prove to yourself that the unchecked cast is safe, so it’s appropriate to suppress the warning.

// Little program to exercise our generic Stack
public static void main(String[] args) {
Stack<String> stack = new Stack<String>();
for (String arg : args)
stack.push(arg);
while (!stack.isEmpty())
System.out.println(stack.pop().toUpperCase());
}

The great majority of generic types are like our Stack example in that their type parameters have no restrictions: you can create a Stack<Object>, Stack<int[]>, Stack<List<String>>, or a Stack of any other object reference type. Note that you can’t create a Stack of a primitive type: trying to create a Stack<int> or Stack<double> will result in a compile-time error. This is a fundamental limitation of Java’s generic type system.

There are some generic types that restrict the permissible values of their type parameters. For example, consider java.util.concurrent.DelayQueue, whose declaration looks like this:

class DelayQueue<E extends Delayed> implements BlockingQueue<E>;

The type parameter list (<E extends Delayed>) requires that the actual type parameter E must be a subtype of java.util.concurrent.Delayed. This allows the DelayQueue implementation and its clients to take advantage of Delayed methods on the elements of a DelayQueue, without the need for explicit casting or the risk of a ClassCastException. The type parameter E is known as a bounded type parameter. Note that the subtype relation is defined so that every type is a subtype of itself [JLS, 4.10], so it is legal to create a DelayQueue<Delayed>.

In summary, generic types are safer and easier to use than types that require casts in client code. When you design new types, make sure that they can be used without such casts. This will often mean making the types generic. Generify your existing types as time permits. This will make life easier for new users of these types without breaking existing clients (Item 23).


Reference: Effective Java 2nd Edition by Joshua Bloch