Generic programming is the creation of programming constructs that can be used with many different types. For example, the Java library programmers who implemented the ArrayList class used the technique of generic programming. As a result, you can form array lists that collect elements of different types, such as Array-List<String>, ArrayList<BankAccount>, and so on.

The LinkedList class that we implemented in Section 15.2 is also an example of generic programming—you can store objects of any class inside a LinkedList. That LinkedList class achieves genericity by using inheritance. It uses references of type Object and is therefore capable of storing objects of any class. In contrast, the Array-List class is a generic class: a class with a type parameter that is used to specify the type of the objects that you want to store. (Note that only our LinkedList implementation of Chapter 15 uses inheritance. The standard Java library has a generic LinkedList class that uses type parameters.)

When declaring a generic class, you specify a type variable for each type parameter. Here is how the standard Java library declares the ArrayList class, using the type variable E for the element type:

public class ArrayList<E>
{
   public ArrayList() { ... }
   public void add(E element) { ... }
   ...
}

Here, E is a type variable, not a Java reserved word. You could use another name, such as ElementType, instead of E. However, it is customary to use short, uppercase names for type parameters.

In order to use a generic class, you need to instantiate the type parameter, that is, supply an actual type. You can supply any class or interface type, for example

ArrayList<BankAccount>
ArrayList<Measurable>

However, you cannot substitute any of the eight primitive types for a type parameter. It would be an error to declare an ArrayList<double>. Use the corresponding wrapper class instead, such as ArrayList<Double>.

When you instantiate a generic class, the type that you supply replaces all occur-rences of the type variable in the declaration of the class. For example, the add method for ArrayList<BankAccount> has the type variable E replaced with the type BankAccount:

public void add(BankAccount element)

Contrast that with the add method of the LinkedList class in Chapter 15:

public void add(Object element)

The add method of the generic ArrayList class is safer. It is impossible to add a String object into an ArrayList<BankAccount>, but you can accidentally add a String into a LinkedList that is intended to hold bank accounts.

ArrayList<BankAccount> accounts1 = new ArrayList<BankAccount>();
LinkedList accounts2 = new LinkedList(); // Should hold BankAccount objects
accounts1.add("my savings"); // Compile-time error
accounts2.add("my savings"); // Not detected at compile time

The latter will result in a class cast exception when some other part of the code retrieves the string, believing it to be a bank account:

BankAccount account = (BankAccount) accounts2.getFirst(); // Run-time error

Code that uses the generic ArrayList class is also easier to read. When you spot an ArrayList<BankAccount>, you know right away that it must contain bank accounts. When you see a LinkedList, you have to study the code to find out what it contains.

In Chapters 15 and 16, we used inheritance to implement generic linked lists, hash tables, and binary trees, because you were already familiar with the concept of inheritance. Using type parameters requires new syntax and additional techniques—those are the topic of this chapter.

2. The binary search tree class in Chapter 16 is an example of generic programming because you can use it with any classes that implement the Comparable interface. Does it achieve genericity through inheritance or type parameters?

In this section, you will learn how to implement your own generic classes. We will write a very simple generic class that stores pairs of objects, each of which can have an arbitrary type. For example,

Pair<String, Integer> result = new Pair<String, Integer>("Harry Morgan", 1729);

The getFirst and getSecond methods retrieve the first and second values of the pair.

String name = result.getFirst();
Integer number = result.getSecond();

This class can be useful when you implement a method that computes two values at the same time. A method cannot simultaneously return a String and an Integer, but it can return a single object of type Pair<String, Integer>.

The generic Pair class requires two type parameters, one for the type of the first element and one for the type of the second element.

We need to choose variables for the type parameters. It is considered good form to use short uppercase names for type variables, such as those in the following table:

You place the type variables for a generic class after the class name, enclosed in angle brackets (< and >):

public class Pair<T, S>

When you declare the instance variables and methods of the Pair class, use the variable T for the first element type and S for the second element type:

public class Pair<T, S>
{
   private T first;
   private S second;

   public Pair(T firstElement, S secondElement)
   {
      first = firstElement;
      second = secondElement;
   }
   public T getFirst() { return first; }
   public S getSecond() { return second; }
}

Some people find it simpler to start out with a regular class, choosing some actual types instead of the type parameters. For example,

public class Pair // Here we start out with a pair of String and Integer values
{
   private String first;
   private Integer second;

   public Pair(String firstElement, Integer secondElement)
   {
      first = firstElement;
      second = secondElement;
   }
   public String getFirst() { return first; }
   public Integer getSecond() { return second; }
}

Now it is an easy matter to replace all String types with the type variable S and all Integer types with the type variable T.

This completes the declaration of the generic Pair class. It is ready to use whenever you need to form a pair of two objects of arbitrary types. The following sample program shows how to make use of a Pair for returning two values from a method.

Declaring a Generic Class

ch17/pair/Pair.java

1  /**
2     This class collects a pair of elements of different types.
3  */
4  public class Pair<T, S>
5  {
6     private T first;
7     private S second;
8
9     /**
10        Constructs a pair containing two given elements.
11        @param firstElement the first element
12        @param secondElement the second element
13     */
14     public Pair(T firstElement, S secondElement)
15     {
16        first = firstElement;
17        second = secondElement;
18     }
19
20     /**
21        Gets the first element of this pair.
22        @return  the first element
23     */
24     public T getFirst() { return first; }
25
26     /**
27        Gets the second element of this pair.
28        @return the second element
29     */
30     public S getSecond() { return second; }
31
32     public String toString() { return "(" + first + ", " + second + ")"; }
33  }

ch17/pair/PairDemo.java

1  public class PairDemo
2  {
3     public static void main(String[] args)
4     {
5        String[] names = { "Tom", "Diana", "Harry" };
6        Pair<String, Integer> result = firstContaining(names, "a");
7        System.out.println(result.getFirst());
8        System.out.println("Expected: Diana");
9        System.out.println(result.getSecond());
10        System.out.println("Expected: 1");
11     }
12
13     /**
14        Gets the first String containing a given string, together
15        with its index.
16        @param strings  an array of strings
17        @param sub a string
18        @return a pair (strings[i], i) where strings[i] is the first
19        strings[i] containing str, or a pair (null, −1) if there is no
20        match.
21    */
22    public static Pair<String, Integer> firstContaining(
23        String[] strings, String sub)
24    {
25        for (int i = 0; i < strings.length; i++)
26        {
27            if (strings[i].contains(sub))
28            {
29              return new Pair<String, Integer>(strings[i], i);
30            }
31        }
32        return new Pair<String, Integer>(null, −1);
33    }
34  }

Program Run

Diana
Expected: Diana
1
Expected: 1

4. What is the difference between an ArrayList<Pair<String, Integer>> and a Pair<ArrayList<String>, Integer>?

A generic method is a method with a type parameter. Such a method can occur in a class that in itself is not generic. You can think of it as a template for a set of methods that differ only by one or more types. For example, we may want to declare a method that can print an array of any type:

public class ArrayUtil
{
   /**
      Prints all elements in an array.
      @param a the array to print
   */
   public <T> static void print(T[] a)
   {
      ...
   }
   ...
}

As described in the previous section, it is often easier to see how to implement a generic method by starting with a concrete example. This method prints the elements in an array of strings.

public class ArrayUtil
{
   public static void print(String[] a)
   {
      for (String e : a)
         System.out.print(e + " ");
      System.out.println();
   }
   ...
}

In order to make the method into a generic method, replace String with a type parameter, say E, to denote the element type of the array. Add a type parameter list, enclosed in angle brackets, between the modifiers (public static) and the return type (void):

public static <E> void print(E[] a)
{
   for (E e : a)
      System.out.print(e + " ");
   System.out.println();
}

Declaring a Generic Method

When you call the generic method, you need not specify which type to use for the type parameter. (In this regard, generic methods differ from generic classes.) Simply call the method with appropriate parameters, and the compiler will match up the type parameters with the parameter types. For example, consider this method call:

Rectangle[] rectangles = ...;
ArrayUtil.print(rectangles);

The type of the rectangles parameter is Rectangle[], and the type of the parameter variable is E[]. The compiler deduces that E is Rectangle.

This particular generic method is a static method in an ordinary class. You can also declare generic methods that are not static. You can even have generic methods in generic classes.

As with generic classes, you cannot replace type parameters with primitive types. The generic print method can print arrays of any type except the eight primitive types. For example, you cannot use the generic print method to print an array of type int[]. That is not a major problem. Simply implement a print(int[] a) method in addition to the generic print method.

6. Is the getFirst method of the Pair class a generic method?

It is often necessary to specify what types can be used in a generic class or method. Consider a generic min method that finds the smallest element in an array list of objects. How can you find the smallest element when you know nothing about the element type? You need to have a mechanism for comparing array elements. One solution is to require that the elements belong to a type that implements the Comparable interface. In this situation, we need to constrain the type parameter.

public static <E extends Comparable> E min(E[] a)
{
   E smallest = a[0];
   for (int i = 1; i < a.length; i++)
      if (a[i].compareTo(smallest) < 0) smallest = a[i];
   return smallest;
}

You can call min with a String[] array but not with a Rectangle[] array—the String class implements Comparable, but Rectangle does not.

The Comparable bound is necessary for calling the compareTo method. Had it been omitted, then the min method would not have compiled. It would have been illegal to call compareTo on a[i] if nothing is known about its type. (Actually, the Comparable interface is itself a generic type, but for simplicity we do not supply a type parameter. See Special Topic 17.1 on page 731 for more information.)

Very occasionally, you need to supply two or more type bounds. Then you separate them with the & character, for example

<E extends Comparable & Cloneable>

The extends reserved word, when applied to type parameters, actually means "extends or implements". The bounds can be either classes or interfaces, and the type parameter can be replaced with a class or interface type.

8. Modify the min method to compute the minimum of an array of elements that implements the Measurable interface of Chapter 9.

ArrayList<SavingsAccount> savingsAccounts = new ArrayList<SavingsAccount>();
ArrayList<BankAccount> bankAccounts = savingsAccounts;
   // Not legal, but suppose it was
BankAccount harrysChecking = new CheckingAccount();
   // CheckingAccount is another subclass of BankAccount
bankAccounts.add(harrysChecking); // OK—can add BankAccount object

public void addAll(LinkedList<? extends E> other)
{
   ListIterator<E> iter = other.listIterator();
   while (iter.hasNext()) add(iter.next());
}

public interface Comparable<T>
{
   int compareTo(T other)
}

public static <E extends Comparable<E>> E min(E[] a)

public static <E extends Comparable<? super E>> E min(E[] a)

public static void reverse(List<?> list)

public static <T> void reverse(List<T> list)

Because generic types are a fairly recent addition to the Java language, the virtual machine that executes Java programs does not work with generic classes or methods. Instead, type parameters are "erased", that is, they are replaced with ordinary Java types. Each type parameter is replaced with its bound, or with Object if it is not bounded.

For example, the generic class Pair<T, S> turns into the following raw class:

public class Pair
{
   private Object first;
   private Object second;

   public Pair(Object firstElement, Object secondElement)
   {
      first = firstElement;
      second = secondElement;

}
   public Object getFirst() { return first; }
   public Object getSecond() { return second; }
}

As you can see, the type parameters T and S have been replaced by Object. The result is an ordinary class.

The same process is applied to generic methods. After erasing the type parameter, the min method of the preceding section turns into an ordinary method. Note that in this example, the type parameter is replaced with its bound, the Comparable interface:

public static Comparable min(Comparable[] a)
{
   Comparable smallest = a[0];
   for (int i = 1; i < a.length; i++)
      if (a[i].compareTo(smallest) < 0) smallest = a[i];
   return smallest;
}

Knowing about type erasure helps you understand limitations of Java generics. For example, you cannot construct new objects of a generic type. The following method, which tries to fill an array with copies of default objects, would be wrong:

public static <E> void fillWithDefaults(E[] a)
{
   for (int i = 0; i < a.length; i++)
      a[i] = new E(); // ERROR
}

To see why this is a problem, carry out the type erasure process, as if you were the compiler:

public static void fillWithDefaults(Object[] a)
{
   for (int i = 0; i < a.length; i++)
      a[i] = new Object(); // Not useful
}

Of course, if you start out with a Rectangle[] array, you don't want it to be filled with Object instances. But that's what the code would do after erasing types.

In situations such as this one, the compiler will report an error. You then need to come up with another mechanism for solving your problem. In this particular example, you can supply a default object:

public static <E> void fillWithDefaults(E[] a, E defaultValue)
{
   for (int i = 0; i < a.length; i++)
      a[i] = defaultValue;
}

Similarly, you cannot construct an array of a generic type.

public class Stack<E>
{
   private E[] elements;
   ...
   public Stack()
   {
      elements = new E[MAX_SIZE]; // Error
   }
}

Because the array construction expression new E[] would be erased to new Object[], the compiler disallows it. A remedy is to use an array list instead:

public class Stack<E>
{
   private ArrayList<E> elements;
    ...
   public Stack()
   {
      elements = new ArrayList<E>(); // Ok
   }
   ...
}

Another solution is to use an array of objects and provide a cast when reading elements from the array:

public class Stack<E>
{
   private Object[] elements;
   private int size;
   ...
   public Stack()
   {
      elements = new Object[MAX_SIZE]; // Ok
   }
   ...
   public E pop()
   {
      size--;
      return (E) elements[size];
   }
}

The cast (E) generates a warning because it cannot be checked at run time.

These limitations are frankly awkward. It is hoped that a future version of Java will no longer erase types so that the current restrictions that are the consequence of erasure can be lifted.

10. Could the Stack example be implemented as follows?

public class Stack<E>
{
   private E[] elements;
    ...
   public Stack()
   {
      elements = (E[]) new Object[MAX_SIZE];
   }
   ...
}

public class LinkedList<E>
{
   private static E defaultValue; // ERROR
   ...
   public static List<E> replicate(E value, int n) { ... } // ERROR
   private static class Node { public E data; public Node next; } // ERROR
}

public class LinkedList<E>
{
   ...
   public static <T> List<T> replicate(T value, int n) { ... } // OK
   private static class Node<T> { public T data; public Node<T> next; } // OK
}

<T extends Comparable> int binarySearch(T[] a, T key)

public static <T extends Comparable<? super T>> void sort(List<T> a)

ArrayList<BankAccount> accounts = new ArrayList<BankAccount>();
if (accounts instanceof ArrayList<String>) ...