Java Generics and Collections, 2nd Edition

Chapter 4. Effective Generics

A Note for Early Release Readers

With Early Release ebooks, you get books in their earliest form—the author’s raw and unedited content as they write—so you can take advantage of these technologies long before the official release of these titles.

This will be the 8th chapter of the final book. Please note that the GitHub repo will be made active later on.

If you have comments about how we might improve the content and/or examples in this book, or if you notice missing material within this chapter, please reach out to the editor at [e-mail].

This chapter contains advice on how to use generics effectively in practical coding. We consider checked collections, security issues, specialized classes, and binary compatibility. The title of this section is an homage to Joshua Bloch’s book, Effective Java.

Use Checked Collections to Enforce Security

It is important to be aware that the guarantees offered by generic types apply only if there are no unchecked warnings. This means that generic types are useless for ensuring security in code written by others, since you have no way of knowing whether that code raised unchecked warnings when it was compiled.

Say we have a class that defines an order, with a subclass that defines an authenticated order:

class Order { ... }
class AuthenticatedOrder extends Order { ... }

Interfaces specify suppliers and processors of orders. Here the supplier is required to provide only authenticated orders, while the processor handles all kinds of orders:

interface OrderSupplier {
  public void addOrders(List<AuthenticatedOrder> orders);
}
interface OrderProcessor {
  public void processOrders(List<? extends Order> orders);
}

From the types involved, you might think that the following broker guarantees that only authenticated orders can pass from the supplier to the processor:

class NaiveBroker {
  public void connect(OrderSupplier supplier,
                      OrderProcessor processor)
  {
    List<AuthenticatedOrder> orders =
      new ArrayList<AuthenticatedOrder>();
    supplier.addOrders(orders);
    processor.processOrders(orders);
  }
}

But a devious supplier may, in fact, supply unauthenticated orders:

class DeviousSupplier implements OrderSupplier {
  public void addOrders(List<AuthenticatedOrder> orders) {
    List raw = orders;
    Order order = new Order(); // not authenticated
    raw.add(order); // unchecked call
  }
}

Compiling the devious supplier will issue an unchecked warning, but the broker has no way of knowing this.

Incompetence can cause just as many problems as deviousness. Any code that issues unchecked warnings when compiled could cause similar problems, perhaps simply because the author made a mistake. In particular, legacy code may raise such problems, as described in the previous section.

The correct solution is for the broker to pass a checked list to the supplier:

class WaryBroker {
  public void connect(OrderSupplier supplier,
                      OrderProcessor processor)
  {
    List<AuthenticatedOrder> orders =
        new ArrayList<AuthenticatedOrder>();
    supplier.addOrders(
        Collections.checkedList(orders, AuthenticatedOrder.class));
    processor.processOrders(orders);
  }
}

Now a class cast exception will be raised if the supplier attempts to add anything to the list that is not an authenticated order.

Checked collections are not the only technique for enforcing security. If the interface that supplies orders returns a list instead of accepting a list, then the broker can use the empty loop technique of the previous section to ensure that lists contain only authorized orders before passing them on. One can also use specialization, as described in the next section, to create a special type of list that can contain only authorized orders.

Specialize to Create Reifiable Types

Parameterized types are not reifiable, but some operations, such as instance tests, casting, and array creation apply only to reifiable types. In such cases, one workaround is to create a specialized version of the parameterized type. Specialized versions can be created either by delegation (that is, wrappers) or by inheritance (that is, subclassing), and we discuss each in turn.

Example 4-1 shows how to specialize lists to strings; specializing to other types is similar. We begin by specializing the List interface to the desired type:

interface ListString extends List<String> {}

Example 4-1. Specialize to create reifiable types

interface ListString extends List<String> {}

class ListStrings {
  public static ListString wrap(final List<String> list) {
    class Random extends AbstractList<String>
      implements ListString, RandomAccess {
      public int size() { return list.size(); }
      public String get(int i) { return list.get(i); }
      public String set(int i, String s) { return list.set(i,s); }
      public String remove(int i) { return list.remove(i); }
      public void add(int i, String s) { list.add(i,s); }
    }
    class Sequential extends AbstractSequentialList<String>
      implements ListString {
        public int size() { return list.size(); }
        public ListIterator<String> listIterator(int index) {
        ListIterator<String> it = list.listIterator(index);
        return new ListIterator<>() {
          public void add(String s) { it.add(s); }
          public boolean hasNext() { return it.hasNext(); }
          public boolean hasPrevious() { return it.hasPrevious(); }
          public String next() { return it.next(); }
          public int nextIndex() { return it.nextIndex(); }
          public String previous() { return it.previous(); }
          public int previousIndex() { return it.previousIndex(); }
          public void remove() { it.remove(); }
          public void set(String s) { it.set(s); }
        };
      }
    }
    return list instanceof RandomAccess ? new Random() : new Sequential();
  }
}

class ArrayListString extends ArrayList<String> implements ListString {
  public ArrayListString() { super(); }
  public ArrayListString(Collection<? extends String> c) { super(c); }
  public ArrayListString(int capacity) { super(capacity); }
}

This declares ListString (an unparameterized type, hence reifiable) to be a subtype of List<String> (a parameterized type, hence not reifiable). Thus, every value of the first type also belongs to the second, but not conversely. The interface declares no new methods; it simply specializes the existing methods to the parameter type String.

Delegation To specialize by delegation, we define a static method wrap that takes an argument of type List<String> and returns a result of type ListString. In line with the Java platform convention of placing static utility methods in a class named for the associated interface (e.g. java.util.Collections for the interface Collection), we place the method wrap in a class called ListStrings.

Here is an example of its use:

List<? extends List<?>> lists =
  Arrays.asList(
    ListStrings.wrap(Arrays.asList("one","two")),
    Arrays.asList(3,4),
    Arrays.asList("five","six"),
    ListStrings.wrap(Arrays.asList("seven","eight"))
  );
ListString[] array = new ListString[2];
int i = 0;
for (List<?> list : lists)
  if (list instanceof ListString)
    array[i++] = (ListString)list;
assert Arrays.toString(array).equals("[[one, two], [seven, eight]]");

This creates a list of lists, then scans it for those lists that implement ListString and places those into an array. Array creation, instance tests, and casts now pose no problems, as they act on the reifiable type ListString rather than the nonreifiable type List<String>. Observe that a List<String> that has not been wrapped will not be recognized as an instance of ListString; this is why the third list in the list of lists is not copied into the array.

The ListStrings class is straightforward to implement, although some care is required to preserve good performance. The Java Collections Framework specifies that whenever a list supports fast random access it should implement the marker interface RandomAccess, to allow generic algorithms to perform well when applied to either random or sequential access lists. It also provides two abstract classes, AbstractList and AbstractSequentialList, suitable for defining random and sequential access lists (these “skeletal implementations” are discussed in more detail in “Customize Collections Using the Abstract Classes”). For example, ArrayList implements RandomAccess and extends AbstractList, while LinkedList extends AbstractSequentialList. Class AbstractList defines the methods of the List interface in terms of five abstract methods that provide random access and must be defined in a subclass (size, get, set, add, remove). Similarly, class AbstractSequentialList defines all methods of the List interface in terms of two abstract methods—size and listIterator—that provide sequential access and must be defined in a subclass.

The wrap method checks whether the given list implements the interface RandomAccess. If so, it returns an instance of class Random that extends AbstractList and implements RandomAccess, and otherwise it returns an instance of class Sequential that extends AbstractSequentialList. Class Random implements the five methods that must be provided by a subclass of AbstractList. Similarly, class Sequential implements the two methods that must be provided by a subclass of AbstractSequentialList, where the second of these returns a class that implements the nine methods of the ListIterator interface. Implementing the list iterator by delegation instead of simply returning the original list iterator improves the security properties of the wrapper, as discussed below. All of these methods are implemented straightforwardly by delegation.

The wrap method returns a view of the underlying list that will raise a class cast exception if any attempt is made to insert an element into the list that is not of type String. These checks are similar to those provided by the checkedList wrapper. However, for wrap the relevant casts are inserted by the compiler (one reason for implementing the nine methods of the listIterator interface by delegation is to ensure that these casts are inserted), while for checked lists the casts are performed by reflection. Generics usually render these checks redundant, but they can be helpful in the presence of legacy code or unchecked warnings, or when dealing with security issues such as those discussed in “Use Checked Collections to Enforce Security”.

The code shown here was designed to balance power against brevity (it’s only around thirty lines), but other variations are possible. A less complete version might implement only random access if one could guarantee it was never applied to a sequential access list, or vice versa. A more efficient version might skip the use of AbstractList and Abstract-SequentialList, and instead directly delegate all 25 methods of the List interface together with the toString method (see the source code for Collections.checkedList for a model). You also might want to provide additional methods in the ListString interface, such as an unwrap method that returns the underlying List<String>, or a version of subList that returns a ListString rather than a List<String> by recursively applying wrap to the delegated call.

Inheritance To specialize by inheritance, we declare a specialized class that implements the specialized interface and inherits from a suitable implementation of lists. Example 4-1 shows an implementation that specializes ArrayList, which we repeat here:

class ArrayListString extends ArrayList<String> implements ListString {
  public ArrayListString() { super(); }
  public ArrayListString(Collection<? extends String> c) { super(c); }
  public ArrayListString(int capacity) { super(capacity); }
}

The code is quite compact. All methods are inherited from the superclass, so we only need to define specialized constructors. If the only constructor required was the default constructor, then the class body could be completely empty!

The previous example still works if we create the initial list using inheritance rather than delegation:

List<? extends List<?>> lists =
  Arrays.asList(
    new ArrayListString(Arrays.asList("one","two")),
    Arrays.asList(3,4),
    Arrays.asList("five","six"),
    new ArrayListString(Arrays.asList("seven","eight"))
  );
ListString[] array = new ListString[2];
int i = 0;
for (List<?> list : lists)
  if (list instanceof ListString)
    array[i++] = (ListString) list;
assert Arrays.toString(array).equals("[[one, two], [seven, eight]]");

As before, array creation, instance tests, and casts now pose no problem.

However, delegation and inheritance are not interchangeable. Specialization by delegation creates a view of an underlying list, while specialization by inheritance constructs a new list. Further, specialization by delegation has better security properties than specialization by inheritance. Here is an example:

List<String> original = new ArrayList<String>();
ListString delegated = ListStrings.wrap(original);
ListString inherited = new ArrayListString(original);
delegated.add("one");
inherited.add("two");
try {
  ((List)delegated).add(3); // unchecked, class cast error
} catch (ClassCastException e) {}
((List)inherited).add(4); // unchecked, no class cast error!
assert original.toString().equals("[one]");
assert delegated.toString().equals("[one]");
assert inherited.toString().equals("[two, 4]");

Here an original list serves as the basis for two specialized lists, one created by delegation and one by inheritance. Elements added to the delegated list appear in the original, but elements added to the inherited list do not. Type checking normally would prevent any attempt to add an element that is not a string to any object of type List<String>, specialized or not, but such attempts may occur in the presence of legacy code or unchecked warnings. Here we cast to a raw type and use an unchecked call to attempt to add an integer to the delegated and inherited lists. The attempt on the delegated list raises a class cast exception, while the attempt on the inherited list succeeds. To force the second attempt to fail, we should wrap the inherited list using checkedList, as described in [Link to Come].

Another difference is that inheritance can only be applied to a public implementation that can be subclassed (such as ArrayList or LinkedList), whereas delegation can create a view of any list (including lists returned by methods such as Arrays.asList or Collections.immutableList, or by the subList method on lists).

The security properties of specialization by inheritance can be improved by declaring a specialized signature for any method that adds an element to the list or sets an element:

class ArrayListString extends ArrayList<String> implements ListString {
  public ArrayListString() { super(); }
  public ArrayListString(Collection<? extends String> c) { this.addAll(c); }
  public ArrayListString(int capacity) { super(capacity); }
  public boolean addAll(Collection<? extends String> c) {
    for (String s : c) {} // check that c contains only strings
    return super.addAll(c);
  }
  public boolean add(String element) { return super.add(element); }
  public void add(int index, String element) { super.add(index, element); }
  public String set(int index, String element) {
   return super.set(index, element);
  }
}

Now, any attempt to add or set an element that is not a string will raise a class cast exception. However, this property depends on a subtle implementation detail, namely that any other methods that add or set an element—for instance, the add method in listIterator—are implemented in terms of the methods specialized above. (This is an instance of the fragile base class problem explained in “Customize Collections Using the Abstract Classes”.) In general, if security is desired, delegation is more robust.

Other Types Specialization at other types works similarly. For example, replacing String by Integer in Example 4-1 gives an interface ListInteger and classes ListIntegers and ArrayListInteger. This even works for lists of lists. For example, replacing String by ListString in Example 4-1 gives an interface ListListString and classes ListListStrings and ArrayListListString.

However, specialization at wildcard types can be problematic. Say we wanted to specialize both of the types List<Number> and List<? extends Number>. We might expect to use the following declarations:

// illegal
interface ListNumber extends List<Number>, ListExtendsNumber {}
interface ListExtendsNumber extends List<? extends Number> {}

This falls foul of two problems: the first interface extends two different interfaces with the same erasure, which is not allowed (see “How Erasure Works”), and the second interface has a supertype with a wildcard at the top level, which is also not allowed (see [Link to Come]). The only workaround is to avoid specialization of types containing wildcards; fortunately, this should rarely be a problem.

Maintain Binary Compatibility

As we have stressed, generics are implemented via erasure in order to ease evolution. When evolving legacy code to generic code, we want to ensure that the newly-generified code will work with any existing code, including class files for which we do not have the source. When this is the case, we say that the legacy and generic versions are binary compatible.

Binary compatibility is guaranteed if the erasure of the signature of the generic code is identical to the signature of the legacy code and if both versions compile to the same bytecode. Usually, this is a natural consequence of generification, but in this section we look at some of the corner cases that can cause problems.

Some examples for this section were taken from internal Sun notes written by Mark Reinhold.

Adjusting the Erasure One corner case arises in connection with the generification of the max method in the Collections class. We discussed this case in Sections “Maximum of a Collection” and “Multiple Bounds”, but it is worth a quick review.

Here is the legacy signature of this method:

// legacy version
public static Object max(Collection coll)

And here is the natural generic signature, using wildcards to obtain maximum flexibility (see “Maximum of a Collection”):

// generic version -- breaks binary compatibility
public static <T extends Comparable<? super T>>
T max(Collection<? extends T> coll)

But this signature has the wrong erasure—its return type is Comparable rather than Object. In order to get the right signature, we need to fiddle with the bounds on the type parameter, using multiple bounds (see “Multiple Bounds”). Here is the corrected version:

// generic version -- maintains binary compatibility
public static <T extends Object & Comparable<? super T>>
  T max(Collection<? extends T> coll)

When there are multiple bounds, the leftmost bound is taken for the erasure. So the erasure of T is now Object, giving the result type we require.

Some problems with generification arise because the original legacy code contains less-specific types than it might have. For example, the legacy version of max might have been given the return type Comparable, which is more specific than Object, and then there would have been no need to adjust the type using multiple bounds.

Bridges Another important corner case arises in connection with bridges. Again, Comparable provides a good example.

Most legacy core classes that implement Comparable provide two overloads of the compareTo method: one with the argument type Object, which overrides the compareTo method in the interface; and one with a more-specific type. For example, here is the relevant part of the legacy version of Integer:

// legacy version
public class Integer implements Comparable {
  public int compareTo(Object o) { ... }
  public int compareTo(Integer i) { ... }
  ...
}

And here is the corresponding generic version:

// generic version -- maintains binary compatibility
public final class Integer implements Comparable<Integer> {
  public int compareTo(Integer i) { ... }
  ...
}

Both versions have the same bytecode, because the compiler generates a bridge method for compareTo with an argument of type Object (see “Bridges”).

However, some legacy code contains only the Object method. (Previous to generics, some programmers thought this was cleaner than defining two methods.) Here is the legacy version of javax.naming.Name.

// legacy version
public interface Name extends Comparable {
  public int compareTo(Object o);
  ...
}

In fact, names are compared only with other names, so we might hope for the following generic version:

// generic version -- breaks binary compatibility
public interface Name extends Comparable<Name> {
  public int compareTo(Name n);
  ...
}

However, choosing this generification breaks binary compatibility. Since the legacy class contains compareTo(Object) but not compareTo(Name), it is quite possible that users may have declared implementations of Name that provide the former but not the latter. Any such class would not work with the generic version of Name given above. The only solution is to choose a less-ambitious generification:

// generic version -- maintains binary compatibility
public interface Name extends Comparable<Object> {
  public int compareTo(Object o) { ... }
  ...
}

This has the same erasure as the legacy version and is guaranteed to be compatible with any subclass that the user may have defined.

In the preceding case, if the more-ambitious generification is chosen, then an error will be raised at run time, because the implementing class does not implement compareTo(Name).

But in some cases the difference can be insidious: rather than raising an error, a different value may be returned! For instance, Name may be implemented by a class SimpleName, where a simple name consists of a single string, base, and comparing two simple names compares the base names. Further, say that SimpleName has a subclass ExtendedName, where an extended name has a base string and an extension. Comparing an extended name with a simple name compares only the base names, while comparing an extended name with another extended name compares the bases and, if they are equal, then compares the extensions. Say that we generify Name and SimpleName so that they define compareTo(Name), but that we do not have the source for ExtendedName. Since it defines only compareTo(Object), client code that calls compareTo(Name) rather than compareTo(Object) will invoke the method on SimpleName (where it is defined) rather than ExtendedName (where it is not defined), so the base names will be compared but the extensions ignored. This is illustrated in Examples Example 4-2 and Example 4-3.

The lesson is that extra caution is in order whenever generifying a class, unless you are confident that you can compatibly generify all subclasses as well. Note that you have more leeway if generifying a class declared as final, since it cannot have subclasses.

Also note that if the original Name interface declared not only the general overload compareTo(Object), but also the more-specific overload compareTo(Name), then the legacy versions of both SimpleName and ExtendedName would be required to implement compareTo(Name) and the problem described here could not arise.

Covariant Overriding Another corner case arises in connection with covariant overriding (see “Covariant Overriding”). Recall that one method can override another if the arguments match exactly but the return type of the overriding method is a subtype of the return type of the other method.

An application of this is to the clone method:

class Object {
  public Object clone() { ... }
  ...
}

Here is the legacy version of the class HashSet:

// legacy version
class HashSet {
  public Object clone() { ... }
...
}

For the generic version, you might hope to exploit covariant overriding and choose a more-specific return type for clone:

// generic version -- breaks binary compatibility
class HashSet {
  public HashSet clone() { ... }
  ...
}

Example 4-2. Legacy code for simple and extended names

interface Name extends Comparable {
  public int compareTo(Object o);
}

class SimpleName implements Name {
  private String base;
  public SimpleName(String base) {
    this.base = base;
  }
  public int compareTo(Object o) {
    return base.compareTo(((SimpleName)o).base);
  }
}

class ExtendedName extends SimpleName {
  private String ext;
  public ExtendedName(String base, String ext) {
    super(base); this.ext = ext;
  }
  public int compareTo(Object o) {
    int c = super.compareTo(o);
    if (c == 0 && o instanceof ExtendedName)
      return ext.compareTo(((ExtendedName)o).ext);
    else
      return c;
  }
}

class Client {
  public static void main(String[] args) {
    Name m = new ExtendedName("a","b");
    Name n = new ExtendedName("a","c");
    assert m.compareTo(n) < 0;
  }
}

Example 4-3. Generifying simple names and the client, but not extended names

interface Name extends Comparable<Name> {
  public int compareTo(Name o);
}
class SimpleName implements Name {
  private String base;
  public SimpleName(String base) {
    this.base = base;
  }
  public int compareTo(Name o) {
    return base.compareTo(((SimpleName)o).base);
  }
}
// use legacy class file for ExtendedName
class Test {
  public static void main(String[] args) {
    Name m = new ExtendedName("a","b");
    Name n = new ExtendedName("a","c");
    assert m.compareTo(n) == 0; // answer is now different!
  }
}

However, choosing this generification breaks binary compatibility. It is quite possible that users may have defined subclasses of HashSet that override clone. Any such subclass would not work with the generic version of HashSet given previously. The only solution is to choose a less-ambitious generification:

// generic version -- maintains binary compatibility
class HashSet {
  public Object clone() { ... }
...
}

This is guaranteed to be compatible with any subclass that the user may have defined. Again, you have more freedom if you can also generify any subclasses, or if the class is final.

Avoid Single-Use Type Variables

The type parameters to generic methods are normally present to express some constraint on the type of the method arguments or its return value. For example, a method to sum the values in a collection could constrain its parameter to be a collection of Number instances:

public static <T extends Number> void sum(Collection<T> c);

Alternatively any type may be acceptable, but some relationship needs to be enforced between different parameters or between a parameter and the return type. For example the java.util.Collections method synchronizedList accepts any list type, but the return value must be of the same type:

public static <T> List<T> synchronizedList(List<T> list);

Occasionally, however, a generic method has no such constraint. For example, the Collections method shuffle, which randomly permutes the elements of a list, can accept a list of any type. It might be tempting to declare it in the same way as the examples above:

public static <T> void shuffle(List<T> list);

and in fact this declaration is perfectly legal. But it is an obscure and confusing way to convey the meaning that the list type is unconstrained; in this situation, a wildcard expresses the same meaning in a more concise and explicit way:

public static void shuffle(List<?> list);

The key advantage to using a wildcard is the reduction of cognitive load on developers using the method API. A reader seeing a type parameter naturally looks for the constraints that it represents. By contrast, a wildcard immmediately conveys the message that there are no constraints on this type.

Use Generic Helper Methods to Capture a Wildcard

In “Wildcard Capture”, we saw that a naïve implementation of the method Collections.reverse fails because the compiler will not permit references of the type Object to be assigned to elements of a List<?>:

public static void reverse(List<?> list) {
  List<Object> tmp = new ArrayList<>(list);
  for (int i = 0; i < list.size(); i++) {
    list.set(i, tmp.get(list.size()-i-1));  // compile-time error
  }
}

This fails because it is not legal to write from the copy back into the original: we are trying to write from a list of objects into a list of unknown type.

Capture.java:8: error: incompatible types: Object cannot be converted to CAP#1
	    list.set(i, tmp.get(list.size()-i-1));  // compile-time error
	                       ^
  where CAP#1 is a fresh type-variable: CAP#1 extends Object from capture of ?

If, however, the temporary list is given the same type as the method parameter, the method compiles without error:

public static<T> void reverse(List<T> list) {
  List <T> tmp = new ArrayList<>(list);
  for (int i = 0; i < list.size(); i++) {
    list.set(i, tmp.get(list.size()-i-1));
  }
}

Now the problem is the one just described, in “Avoid Single-Use Type Variables”: the public API of reverse defines a type variable without any semantics.

The solution is to combine the two implementations: expose the wildcard declaration as the public API, and implement it by calling the generic method as a private helper method:

public static void reverse(List<?> list) { rev(list); }

private static <T> void rev(List<T> list) {
  List<T> tmp = new ArrayList<>(list);
  for (int i = 0; i < list.size(); i++) {
    list.set(i, tmp.get(list.size()-i-1));
  }
}

This technique is often useful when defining methods whose declarations contain wildcards.

Cast Through Raw Types When Necessary

Casting through a raw type is a way of evading the constraints of the generic type system. Those constraints exist for a reason, so of course this technique comes with a price: casting back from a raw type to a generic type generates an unchecked warning, and the programmer bears the full responsibility of preventing run-time class cast exceptions. Nonetheless, it can be useful when you need to work around the limitations of Java’s generic type system.

As an example, consider how you could modify the technique of wildcard capture. The helper method used in the section above carries small costs in efficiency, in the form of increased class file and code cache sizes and the performance overhead of an extra method call. These are not normally significant, but it may be necessary for critical code in intensively-used libraries to make every possible optimization. So the Collections method reverse uses a raw type, in code equivalent to this:

@SuppressWarnings({"rawtypes", "unchecked"})
public static void reverse(List<?> list) {
   List rawList = list;
   List tmp = new ArrayList(rawList);
   for (int i = 0; i < rawList.size(); i++) {
      rawList.set(i, tmp.get(rawList.size()-i-1));
   }
}

Using raw types in this way avoids creating and calling an extra method just to get the generic types to work, at the cost of generating unchecked warnings, which have to be suppressed. It is unusual for this to be worthwhile, but it is a useful technique to know for cases in which performance and code size are critical.

Use Generic Array Types With Care

In [Link to Come] we saw that a generic array type, like List<Integer>[] in [Link to Come], is a kind of convenient fiction: because the parametric type is non-reifiable, the array component type is a raw List, so it is possible to assign a List of some other non-reifiable type into the array without causing a compile-time error or even a run-time ArrayStoreException. The Principle of Indecent Exposure warns against exposing such a generic array type outside the context in which the array was created, because the type system provides no safety in this case.

Handled with care, however, generic array types can be useful. For example, consider constructing a non-binary tree, in which each node can have an arbitrary number of child nodes. Usually, you would model a node with a list of children:

class ListTreeNode<T> {
    private T data;
    private final List<ListTreeNode<T>> children;
    public ListTreeNode(T data) {
        this.data = data;
        children = new ArrayList<>();
    }
    public void addChild(ListTreeNode<T> child) { this.children.add(child); }
    public void removeChild(ListTreeNode<T> child) { this.children.remove(child); }
    public T getData() { return data; }
    public List<ListTreeNode<T>> getChildren() { return children; }
}

but in a performance-critical application, one in which the number of child nodes could be very large, you might prefer to use an array to contain the child node references. Now adding and removing children becomes impossible, but data values and entire child nodes can be replaced:

class ArrayTreeNode<T> {
    private T data;
    private final ArrayTreeNode<T>[] children;
    public ArrayTreeNode(T data, int childCount) {
        this.data = data;
        this.children = (ArrayTreeNode<T>[]) new ArrayTreeNode[childCount];  // unchecked cast of a raw type
    }
    public void replaceData(T newData) { this.data = newData; }
    public void replaceChild(ArrayTreeNode<T> child, int index) { this.children[index] = child; }
    public ArrayTreeNode<T>[] getChildren() { return children; }
}

and this will all work perfectly well, provided references to the generic array are contained within the class, where the dangers of using a covariant subclass of the array are clearly visible. If, however, the API contravenes the Principle of Indecent Exposure, as the method getChildren does, client code runs the risk of unexpected class cast exceptions:

ArrayTreeNode<Integer> integerNode = new ArrayTreeNode<>(3, 2);
ArrayTreeNode<? extends Number>[] numberTreeNodes = integerNode.getChildren();
numberTreeNodes[0] = new ArrayTreeNode<>(1.0, 2);
Integer data = numberTreeNodes.getChildren()[0].getData();  // class cast exception

Use Type Tokens for Operations Requiring Run-time Type Information

We saw in [Link to Come] that a type token of the form Class<T> can be used to create an array of T. This is an example of a general technique useful in implementing generic methods and classes that need to access or instantiate types specified at run time. For example, a generic factory method specified for classes having a no-argument constructor could look like this:

public static <T> T createInstanceParameterised(Class<T> clazz) throws NoSuchMethodException,
            InvocationTargetException, InstantiationException, IllegalAccessException {
    Constructor<T> constructor = clazz.getDeclaredConstructor();
    constructor.setAccessible(true);
    return constructor.newInstance();
}

A non-parameterised version of createInstance would work equally well at run time:

public static Object createInstanceWildcard(Class<?> clazz) throws NoSuchMethodException,
            InvocationTargetException, InstantiationException, IllegalAccessException {
    Constructor<?> constructor = clazz.getDeclaredConstructor();
    constructor.setAccessible(true);
    return constructor.newInstance();
}

But the parameterised version is type safe, so no cast is necessary when using it:

class Foo {};
Foo f1 = createInstanceParameterised(Foo.class);
Foo f2 = (Foo) createInstanceWildcard(Foo.class)    // unchecked

Besides object creation, type tokens can also be used for type-safe access to objects whose type is unknown at compile time. For example, consider implementing a registry in which each type token is mapped to a list of objects of that type:

public class TypeSafeRegistry {
    private Map<Class<?>, List<?>> typeSafeRegistry = new HashMap<>();

    public <T> void addObject(Class<T> type, T object) {
        getObjects(type).add(object);
    }

    @SuppressWarnings("unchecked")
    public <T> List<T> getObjects(Class<T> type) {
        List<?> untypedList = typeSafeRegistry.computeIfAbsent(type, k -> new ArrayList<>());
        return (List<T>) untypedList; // unchecked cast
    }
}

Although the cast in the method getObjects is unchecked, we can be confident that it is safe, because the method addObject will only accept objects whose type matches the type of the token being used as a key.