Generics

Goals

Concepts

Language

Javadoc

Lesson

You've learned about various types of data structures, including linked lists, trees, and hash tables. You have made your linked list and hash table general so that they can be used to hold any type of object whatsoever. You accomplished this by making the value held by the linked list nodes, as well as the values in the hash map entries, of type Object. Because all classes in Java derive ultimately from Object, an instance of any class can automatically be widened to the Object type.

Drawbacks to Using Object in Data Structures

This approach is flexible, but it has some drawbacks:

If you were to put an object of an incorrect type into the data structure, when it came time to retrieve the object you would get a nasty ClassCastException when you try to tried to cast the instance to the “correct” type. Let's say you were making a linked list to hold Vehicle instances.

final LinkedList vehicleList = new LinkedListImpl();
vehicleList.add(new Car());
vehicleList.add(new Truck());
vehicleList.add(new Van());

The compiler has no way of stopping you from putting an animal in the list:

vehicleList.add(new Dog()); //WRONG! But the compiler doesn't know.

When it comes time to retrieve the object, you have to know what to cast it to. The compiler isn't going to help you.

final Point point = (Point)vehicleList.get(0);  //Are we casting to the correct type? Who knows?!!

If you cast to the wrong type, the compiler won't know (and you may not realize it) until the program is running.

One way to get around this would be to stop using Object and instead use the specific type you want to store. But this would require substantial code duplication! You would essentially have to write a different class for each type: VehicleLinkedList, AnimalLinkedList, and so on. You might be clever and create a BaseLinkedList class using object, and then in your VehicleLinkedList you could use the BaseLinkedList logic but perform all the casting to the appropriate type. This would still require you to write a different class for each type, and all the manual casting would be error prone. Wouldn't it be nice if you could write a LinkedList implementation just once, and the Java compiler to do all the casting for you automatically for a certain type?

Generics

Java introduced a mechanism called generics to be used with classes such as data structures that are generalized to work with many types, but for which particular instances should be restricted to a certain type. Through generics the compiler will take care of two things for you automatically:

To pull this off takes two steps:

  1. You will create a class that can work with different types. In the declaration of the class, you will provide a generics type variable between angled brackets < and >, such as FooBar<T>. This type variable tells Java that the class can work with different types.
  2. When you instantiate the class, you will tell the compiler what type you want to use with the class for that instance. For example, you might call new FooBar<Animal>(). Java will take care of all the casting for you.

Step 1: Declare and Use Generic Type(s) in Interface/Implementation

Let's see how that might work with a graph Node object, which so far has held a single value of type Object.

Excerpt from example Node implementation.
/** A node in a graph. */
public class Node {

  private final Object value;

  /** @return The value represented by this node. */
  public @Nonnull Object getValue() {
    return value;
  }

  private Node[] links = new Node[0];

  /** Creates a node containing an object.
   * @param value The object to store in the node.
   */
  public Node(@Nonnull final Object value) {
    this.value = checkNotNull(value);
  }

  …

}

The first step in adding generics is to add a generic type variable. Here we'll use V for “value”.

Excerpt from example Node implementation using generics.
/**
 * A node in a graph.
 * @param <V> The type of value held in the node.
 */
public class Node<V> {

  private final V value;

  /** @return The value represented by this node. */
  public @Nonnull V getValue() {
    return value;
  }

  /** Creates a node containing an object.
   * @param value The object to store in the node.
   */
  public Node(@Nonnull final V value) {
    this.value = checkNotNull(value);
  }

  …

}

Step 2: Indicate Generic Type(s) in Instantiation

The second step is to indicate a type for the type variable when the class is instantiated.

final Vehicle vehicle = new Car();
final Node<Vehicle> vehicleNode = new Node<Vehicle>(car);

Now the compiler can start helping us out! It can prevent us from using an Animal as the node value, for example.

final Animal animal = new Dog();
final Node<Vehicle> vehicleNode = new Node<Vehicle>(animal);  //ERROR will not compile

The compiler will also make our lives easier by removing the need for us to do casts.

final Node<Vehicle> vehicleNode = new Node<Vehicle>(new Car());
final Vehicle vehicle = vehicleNode.getValue(); //no need for a cast!

Erasure

It is important for you to understand that Java does not create new classes for Node<Vehicle> and Node<Animal>; there is only one class: Node<V>. In fact, behind the scenes Java still stores the value as an Object! Generics only helps you when you compile your program, letting the Java compiler ensure that you use the correct types and automatically casting for you. But after your program is compiled, no generics information remains! None whatsoever! Your compiled Node<V> class becomes a plain old Node at runtime. This discarding of generics type information after compilation is referred to as erasure.

Capturing

Once you have defined a generics variable, it captures the type provided by the caller and can reuse that type as you would use a normal Java type, even without knowing what the type represents when the generics class is written. Take a LinkedList for example, which is made up of Nodes. If we make a LinkedListImpl<E> with the generics type variable E for “element”, then we will need to use nodes of the same generic type. That is, if someone creates a LinkedList<Car>, the linked list internally will need to use Node<Car>. But how do we do that? Simply pass along the generics type variable to the Node<V>.

Excerpt from example linked list implementation, passing generic type to nodes.
/**
 * Implementation of a linked list.
 * @param <E> The type of element in the list.
 */
public class LinkedListImpl<E> {

  @Override
  public void add(final E element) {
    final Node<E> node = new Node<E>(element);

    //TODO add the node at the end of the linked list

  }

  …

}

Bounds

Basic generics are useful enough, but you can also add constraints on the type that can be used. In previous lessons we have presented an example Racetrack class to race Vehicle instances. As it allowed any Vehicle instance, one could race a Truck with an Airplane. But in real life we usually race vehicles of the same type. There might be a racetrack for cars, and another for go-carts.

You now know how to use generics to specify a type of class to be used for racing in the racetrack. If we were to make a generics Racetrack<T> (using T to represent any “type”), we could instantiate a RaceTrack<Car> or a Racetrack<GoCart>. Unfortunately this approach would also allow us to instantiate a RaceTrack<Point>, and that's something a RaceTrack wouldn't know how to handle. We need to have some way to say that only types that are some subclass of Vehicle can be used in the Racetrack.

Java generics comes with a facility to add a constraint or a bound to a type variable. There are two keywords, extends and super, that you can use to create bounded type variables. The former says that the type used must be the same or a subclass of the indicated type; the latter says that the type used must be the same or a super class of the indicated type. Here is how you could restrict the generics type of Racetrack to only be some Vehicle type.

Racetrack class with bounded generics variable only allowing Vehicle types.
/**
 * Class for racing vehicles.
 * @param <V> The type of vehicle to be raced.
 */
public class Racetrack<V extends Vehicle> {

  /** Races a bunch of vehicles.
   * @param vehicles The vehicles to race.
   */
  public void race(final V... vehicles)   {
    for(final V vehicle : vehicles) {
      vehicle.move();
    }
  }

}

At first glance it might seem that no benefit is gained by restricting V to some type of Vehicle—after all, simply using the Vehicle type itself in the Racetrack.race(Vehicle...) method would prevent non-vehicles from being raced. However using generics allows a racetrack to be created that allows only specific Vehicle types to be used, such as a Racetrack that only allows Cars to be raced.

final Racetrack<Car> racetrack = new Racetrack<Car>();

An example of using super can be found below in the section entitled Interrelated Type Variables.

Wildcards

Unbounded Wildcards

Sometimes we need to use a class that uses generics, but we don't care what type its generics type variable uses; in this case we can use a wildcard type variable. We may want to print out every object in a list, for example. We can use the unbounded wildcard ? character to stand in the place of any generic type. Here is an example using a generics designation in a parameter of a method.

Method accepting an unbounded wildcard in a generics parameter.
/**
 * Prints all objects in a list.
 * @param list The list of things to print.
 */
public static void printAll(@Nonnull final LinkedList<?> list) {
  for(int i=0; i < list.getLength(); i++) {
    System.out.println(list.get(i).toString());
  }
}

Bounded Wildcards

Even if we don't we care exactly what a type is, we still may want to place some constraints on it. We could use a bounded wildcard by adding the keyword extends or super which we discussed earlier.

Method accepting a bounded wildcard in a generics parameter.
/** Determines the average mile-per-gallon of all the vehicles.
 * @param vehicles The list of vehicles.
 * @throws IllegalArgumentException if no vehicles were provided.
 */
public static int calculateMeanMPG(@Nonnull final LinkedList<? extends Vehicle> vehicles) {
  final int vehicleCount = vehicles.getLength();
  checkArgument(vehicleCount > 0);
  int totalMPG = 0;
  for(int i=0; i < vehicleCount; i++) {
    totalMPG += vehicles.get(i).getMPG();
  }
  return totalMPG / vehicleCount;
}

Capturing in Methods

A method can temporarily capture a type, even without knowing what the type is, by specifying the type variable <T> (using whatever type variable you desire) in front of the method. This works similar to an unbounded wildcard, except that you now have a generic type variable you can reuse as necessary.

Capturing Method Parameter Types

Using a captured type in the following example allows us not only to reuse the variable in another generic class, but also to return an object of the correct type—even if we don't know what that type is! As long as all our type constraints aren't broken, Java can confirm that what we are doing is completely type-safe and that we will not get any ClassCastExceptions.

Capturing a generics type in a method signature.
/**
 * Retrieves the first item in a list.
 * @param list The list of things.
 * @return The first item in the list, or <code>null</code> if the list is empty.
 */
public static <E> @Nullable E getFirstItem(@Nonnull final LinkedList<E> list) {
  /* We don't know what type E stands for, but it doesn't matter,
   * because we know that it is the same type for the list and its nodes.
   */
  final LinkedListNode<E> node = list.getFirstNode();
  if(node == null) {
    return null;  //the list is empty
  }
  return node.getValue();
}

We can now use the method for a linked list of any type we want.

final LinkedList<Vehicle> vehicles = new LinkedListImpl<Vehicle>();
vehicles.add(new Car());
vehicles.add(new Truck());
vehicles.add(new GoCart());
final Vehicle firstVehicle = getFirstItem(vehicles);  //generic type from LinkedList<Vehicle> was captured

Capturing in Static Factory Methods

Capturing new generic type variables in a method is a handy way to implement a factory method. The sole purpose of a factory is to create an instance of some class. We call these methods factory methods because they function like a “factory” that produces objects on demand. You can even create a static factory method for a class that will create instances of that same class.

You might think that such a method would be unnecessary and even redundant—after all, isn't creating the class what a constructor is for? But it turns out there are many uses for static factory methods. One benefit is that they provide an opportunity to analyze and manipulate the data to pass to a constructor before instantiation even begins.

To create a class that uses generics by directly calling its constructor, you would have to specify the generic type in the constructor call (or in later versions of Java at least provide the diamond symbol <>). A static factory method allows you to capture the generic type for the method parameters; you will still need to pass this type to the constructor, but you can hide this inside the static factory method itself.

A static factory method then provides a concise and convenient way to create a class instance initialized with data. The method LinkedListImpl.of(T... elements) captures the type of elements, and in the example below uses them to construct a new LinkedList<Vehicle>.

Capturing a generics type in a static factory method.
public class LinkedListImpl<E> {

  /** Static factory method. */
  public static <T> LinkedListImpl<T> of(final T... elements) {
    final LinkedListImpl<T> linkedList = new LinkedListImpl<T>();
    //TODO add elements to list
    return linkedList;
  }

}
final LinkedList<Vehicle> vehicles = LinkedListImpl.of(new Car(), new Truck(), new GoCart());

Capturing Method Return Types

You can capture a generic type even if the only generic type variable used is for the return type. With no other instances of the generic type available in the method signature, you will usually be required to cast some value to the generics type and deal with any resulting warnings.

One use for capturing a generic return type is to provide a type-safe, constant instance of a generics class that can be used with any generics type. Consider an empty linked list that contain no elements and that is read-only (so that no one can add anything to it). Why would we want an empty list? Perhaps we have a method that needs to return a list of items, and if there are no items we could return the existing empty list rather than creating a new list.

Read-only implementation of LinkedList<E>.
public class EmptyLinkedList<E> implements LinkedList<E> {

  @Override public getLength() {
    return 0;
  }

  @Override public add(E element) {
    throw new UnsupportedOperationException("This list is read-only.");
  }

  …
}

By taking advantage of erasure (that is, of the knowledge that at runtime all instances of EmptyLinkedList will be identical regardless of the generic type), we can store a single instance of the empty linked list and provide a method to cast it to the needed type on the fly.

Converting constant EmptyLinkedList<E> instance to captured generic return type.
public class DataStructureUtils {

  //instance of EmptyLinkedList<E>, stored for future use
  private final static LinkedList<Object> EMPTY_LINKED_LIST = new EmptyLinkedList<Object>();

  /** @return A shared instance of a read-only, empty linked list. */
  @SuppressWarnings("unchecked")
  public static <E> LinkedList<E> emptyLinkedList() {
    return (LinkedList<E>)EMPTY_LINKED_LIST;
  }

}
public class Zoo {

  …

  public LinkedList<Animal> getAnimals() {
    if(animalCount == 0) {  //if there are no animals in the zoo
      return DataStructureUtils.emptyLinkedList();
    }
  }

}

Interrelated Type Variables

Sometimes you may want to specify more than one generic type for a class or a method, but one of the types depends on the other. Simply provide the independent type variable(s) first and reference those variables as needed in the dependent types.

Let's say that we create a utility method to insert a Vehicle at the front of some linked list of vehicles, perhaps representing the starting order in a race. What if we tried this?

//TODO fix; only works with lists of the actual Vehicle type
public static void addToFront(@Nonnull final LinkedList<Vehicle> lineup, @Nonnull final Vehicle vehicle) {
  lineup.insert(0, vehicle);    //insert the vehicle at the front
}

Here is how we want to use it:

final LinkedList<Vehicle> lineup = new LinkedListImpl<Vehicle>();
addToFront(lineup, new Car(5));

So far, so good. But what if they were using a LinkedList<Car>? That wouldn't work for LinkedList<Vehicle> in the method signature. So let's try to make the first parameter more flexible:

public static void addToFront(@Nonnull final LinkedList<? extends Vehicle> lineup, @Nonnull final Vehicle vehicle) {
  lineup.insert(0, vehicle);    //ERROR; can't insert Vehicle because the list might be of a Vehicle subclass such as Boat
}

Now that will work with a LinkedList<Car>. But now the second parameter type is too broad—it will allow for example an Airplane, which might not work if they passed in a LinkedList<Car>. So somehow we have to make the second parameter be of the same type as the list passed in. We will need to capture and reuse the generic type variable of the list.

public static <V extends Vehicle> void addToFront(@Nonnull final LinkedList<V> lineup, @Nonnull final V vehicle) {
  lineup.insert(0, vehicle);    //insert the vehicle at the front
}
final LinkedList<Truck> lineup = new LinkedListImpl<Truck>();
addToFront(lineup, new Pickup(10));

So far so good. But what if we want to go further and pass a hash table in which to associate the vehicle with its miles per gallon value so we can look it up quickly (assuming all vehicles get different miles per gallon). We could try this:

public static <V extends Vehicle> void addToFront(@Nonnull final LinkedList<V> lineup, @Nonnull final V vehicle,
    @Nonnull final HashTable<Integer, V> mpgTable) {  //TODO fix; V is not general enough
  lineup.insert(0, vehicle);    //insert the vehicle at the front
  mpgTable.put(vehicle.getMPG(), vehicle);  //map the vehicle to its MPG
}

That looks fine, but it restricts the MPG hash table to whatever type V is! So the following would not work:

final LinkedList<Truck> lineup = new LinkedListImpl<Truck>();
final HashTable<Integer, Vehicle> mpgTable = new HashTable<Integer, Vehicle>();
addToFront(lineup, new Pickup(10), mpgTable);  //TODO error; Vehicle is not type Truck

Somehow we want to allow the caller to pass in a hash table that has any class that is a super type of whatever type V is (the type in the list). We can do that with the super keyword, and we might as well do it for the list as well. It says that, whatever type of vehicle we pass in, the list and map has to be of a generic super type of that vehicle type. For example, if we pass in a Pickup, then the list could be of type Pickup or Truck or even Vehicle, but not Boat. The same goes for the hash table.

public static <V extends Vehicle> void addToFront(@Nonnull final LinkedList<? super V> lineup, @Nonnull final V vehicle,
    @Nonnull final HashTable<Integer, ? super V> mpgTable) {
  lineup.insert(0, vehicle);    //insert the vehicle at the front
  mpgTable.put(vehicle.getMPG(), vehicle);  //map the vehicle to its MPG
}

Now this will work just fine:

final LinkedList<Truck> lineup = new LinkedListImpl<Truck>();
final HashTable<Integer, Pickup> mpgTable = new HashTable<Integer, Pickup>();
addToFront(lineup, new TillerTruck(4), mpgTable);

Lastly what if we wanted to return the given list to the caller? We could simply return lineup, but that would return a type LinkedList<? super V>. What if they passed in a sub-interface of LinkedList<> that had special capabilities—a SpecialList<> type—and we wanted to return the same type? Once again, we could capture that type and then use it in the return statement.

public static <V extends Vehicle, L extends LinkedList<? super V>> L addToFront(@Nonnull final L lineup, @Nonnull final V vehicle,
    @Nonnull final HashTable<Integer, ? super V> mpgTable) {
  lineup.insert(0, vehicle);    //insert the vehicle at the front
  mpgTable.put(vehicle.getMPG(), vehicle);  //map the vehicle to its MPG
  return lineup;  //this is of type L, the captured type that is specified as the return type
}

Review

Gotchas

Think About It

Self Evaluation

Task

Convert your data structures to use generics.

In your Booker application, create another utility method getPublicationByName(…) that takes not only the name of a publication, but also a linked list of publications of the same type (e.g. Book or Periodical) and returns the publication with the given name.

Here is an example of how you might call your new getPublicationByName(…) method:

final Book book = findPublicationByName(LinkedListImpl.of(new Book(…), new Book(…), new Book(…)), "A Tale of Two Cities");
final LinkedList<Magazine> magazines = LinkedListImpl.of(new Magazine(…), new Magazine(…), new Magazine(…));
final Magazine magazine = findPublicationByName(magazines, "Better Homes And Gardens");

See Also

References