Generics: one class for many types

Since your first ArrayList you have written ArrayList<String> and List<Integer>, with the angle brackets as part of the recipe: they say what the list holds. This lesson explains them. You will write your own classes and methods that take a type in angle brackets, see how that turns a crash at run time into an error the compiler reports first, and find out what Java keeps of those types once the program runs.

A box that holds anything#

Picture a class whose only job is to hold one thing: a box. You put something in, and later you take it out. You want one Box class for every kind of thing, names one day and numbers the next.

Before generics, there was one way to write that. Every class extends Object, as you saw in inheritance, so a variable of type Object can refer to any object at all. A box that stores an Object can hold anything.

It prints Hello, Sana and Age next year: 15. Step through it and watch the memory view: there are two Box objects, each with a field called item, one holding a String and one an Integer. Java boxed the 14 into an Integer for you, because an Object field can only hold objects.

Now look at the two lines that take something out. get() returns Object, so all Java knows is that some object came back. To use it as a String you downcast it with (String), and to use the age as a number you cast it with (Integer). Every read needs a cast.

When the wrong thing goes in

The casts are tedious, and they hide a worse problem: nothing stops a value of the wrong type from going into a box. Here a later part of the program puts a number into the box of names.

It compiles. When you run it, the first greeting prints Hello, Sana, and the second call stops the program with a ClassCastException: an Integer cannot be cast to a String.

The mistake is on line 7, where 42 went into a box meant for names. The crash happens on line 12, inside a different method. In a real program those two lines could sit in different files, written by different people, and run hours apart. The compiler read both lines and said nothing, because put accepts any Object and the compiler takes your word for every cast.

A generic class: Box<T>#

Here is the same box written with generics. Two things change in the class: the name Box is followed by <T>, and every Object inside becomes T.

The output is the same, and there is no cast anywhere. nameBox.get() hands back a String, and ageBox.get() hands back an Integer, which Java unboxes into the int variable.

Reading the angle brackets

class Box<T> declares a type parameter called T. A type parameter is a placeholder for a type, the way a method parameter is a placeholder for a value. Inside the class, T sits wherever the type of the item goes: the field, the parameter of put and the return type of get. A class that declares type parameters is a generic class.

Box<String> fills the placeholder in. Here String is the type argument, and you read Box<String> aloud as “box of String”. For that box, every T in the class means String: put takes a String and get returns one. Box<Integer> is a box of Integer, made from the same class.

The mistake moves to compile time

Now try the bad line from before, putting 42 into the box of names:

javac refuses to compile the program, and it points at line 5, where the wrong value goes in. It knows nameBox is a box of String, so put on that box takes a String, and 42 is an int. The Note line only says that javac shortened its message, and you can ignore it.

With the Object box, this mistake compiled, ran, and crashed somewhere else. Here it never gets past the compiler, and the error names the line where the bug really is.

Key idea

A type parameter is a placeholder for a type. You write the class once with T, each use fills in a real type, and the compiler checks every value that goes in. A wrong value becomes a compile error instead of a crash.

A type argument must be an object type, never a primitive. You met this rule with ArrayList: Box<int> fails with unexpected type, so you write Box<Integer> and let autoboxing turn each int into an Integer. The section on type erasure shows where the rule comes from.

Now add two methods to the box yourself. The second one uses T twice, as its parameter type and as its return type.

1public class Main {
2    public static void main(String[] args) {
3        Box<String> note = new Box<>();
4        System.out.println(note.isEmpty());
5        System.out.println(note.getOrElse("(no note)"));
6 
7        note.put("Buy milk");
8        System.out.println(note.isEmpty());
9        System.out.println(note.getOrElse("(no note)"));
10 
11        Box<Integer> bonus = new Box<>();
12        int points = 10 + bonus.getOrElse(0);
13        System.out.println(points);
14    }
15}
16 
17class Box<T> {
18    private T item;
19 
20    void put(T item) {
21        this.item = item;
22    }
23 
24    T get() {
25        return item;
26    }
27 
28    boolean isEmpty() {
29        // TODO: a box is empty while it holds null
30        return false;
31    }
32 
33    T getOrElse(T fallback) {
34        // TODO: give back the item, or the fallback if the box is empty
35        return item;
36    }
37}

Two type parameters, and the diamond#

A class can declare more than one type parameter, separated by commas inside the angle brackets. A pair that holds two values of different types needs two:

It prints Sana scored 980 and Ravi: 555-0142. In Pair<String, Integer> the first type argument fills in K and the second fills in V, by position, the same way method arguments fill parameters. So best.key() returns a String and best.value() returns an Integer. The constructor uses the type parameters too: Pair(K key, V value).

Naming type parameters

By convention a type parameter is a single capital letter, so you can tell it from a real class at a glance: T is a placeholder, Task is a class. The Java library keeps to a handful of letters, and other Java programmers expect them:

The diamond

Before Java 7 you wrote the type arguments on both sides: Pair<String, Integer> best = new Pair<String, Integer>("Sana", 980);. Since Java 7 you can leave the brackets after new empty, and the compiler fills them in from the type of the variable. A compiler working out a type you did not write is called type inference, and the empty <> is the diamond you have typed since your first ArrayList.

You have used generic types all along

The library's lists are declared just like your box. List is a generic interface whose declaration begins public interface List<E>, and ArrayList is a generic class whose declaration begins public class ArrayList<E> and which implements List<E>. When you wrote ArrayList<String>, you filled in E with String, so add took a String and get returned one, with no cast in sight.

Generic methods#

Sometimes a single method needs a type parameter while the class around it does not. Say you want the first item of any list: names, scores, anything. You could write firstName, firstScore and one more method for every type. A generic method declares its own type parameter and works for all of them.

It prints Sana 90 and Mia 88. Read the header static <T> T firstOf(List<T> list) from left to right. The <T> just before the return type declares a type parameter that belongs to this one method. Then T is the return type and List<T> is the parameter: give me a list of some type T, and I hand back one T.

The calls never say what T is. The compiler works it out from the argument. names is a List<String>, so in firstOf(names) T is String and the call returns a String. In firstOf(scores) T is Integer. This is type inference again, the same idea as the diamond.

Inside count, the methods you can call on a T are the ones every object has, such as equals and toString, because T could be any type at all. The next section is about asking for more.

Bounded types: asking more of T#

Now write a method that finds the largest item in a list: the highest score, or the word that comes last in alphabetical order. You know compareTo from strings: a.compareTo(b) is negative when a comes first, zero when they are equal, and positive when a comes after. A first attempt:

javac cannot find compareTo, and the last line says why: T extends Object. With nothing else to go on, T could be any type, a Box as easily as a String, and the only methods every type is sure to have are those of Object. compareTo is not one of them.

Comparable: the types that can compare themselves

String, Integer and Double all have compareTo because each one implements a library interface called Comparable. It is a generic interface with a single method, and without its documentation comments it is three lines long:

String implements Comparable<String>, which says that a string can be compared with another string. Integer implements Comparable<Integer>.

Adding a bound

You can tell the compiler that T must be one of these comparable types. Write the requirement after the type parameter, with the word extends:

It prints plum, 95 and 4.25. <T extends Comparable<T>> declares a bounded type parameter: T can be any type that can be compared with other values of type T. The part after extends is the bound. Every T is now sure to have compareTo, so the call inside the loop compiles.

In a bound, extends covers interfaces as well as classes. Comparable is an interface, and you still write extends, never implements.

Key idea

A bound limits which types can fill in a type parameter, and in return lets you call the bound's methods. <T extends Comparable<T>>means “any T that can be compared with another T”, so compareTo works on it.

The bound also checks every call

A bound works in two places. Inside the method it allows compareTo. At each call it checks that the type really qualifies. Here is a Song class with no compareTo, passed to the same max:

Read the reason as two demands that clash. equality constraints: Song says T has to be Song, because that is what the list holds. upper bounds: Comparable<T> says T has to be comparable. Song is not, so no T can meet both. To make songs work with max, Song has to implement Comparable<Song>, which you will do in Comparable, Comparator and sorting.

It prints 12, then 7. Each type brings its own compareTo. Integers compare by value, so 12 is the largest. Strings compare character by character from the left, so "7" beats both "3" and "12", whose first characters come before 7. max is the same code both times; only the compareTo that runs is different.

Now write a bounded method of your own.

1import java.util.List;
2 
3public class Main {
4    public static void main(String[] args) {
5        System.out.println(isSorted(List.of(3, 8, 8, 15)));
6        System.out.println(isSorted(List.of(3, 15, 8)));
7        System.out.println(isSorted(List.of("apple", "kiwi", "plum")));
8        System.out.println(isSorted(List.of("plum", "kiwi")));
9        System.out.println(isSorted(List.of(42)));
10    }
11 
12    static <T extends Comparable<T>> boolean isSorted(List<T> items) {
13        // TODO: return false as soon as an item is larger than the one after it
14        return true;
15    }
16}

Why a List<Integer> is not a List<Number>#

The number wrapper classes share a parent. Integer, Double, Long and the others all extend an abstract library class called Number. Its most useful method is doubleValue(), which gives any number back as a double. An Integer is-a Number, so Number n = 14; compiles: Java boxes 14 into an Integer and stores it in the Number variable.

If every Integer is a Number, is a list of Integers a list of Numbers? It sounds obvious. javac disagrees:

Pretend javac allowed line 7. Then numbers and scores would be two names for one list, like the shared references in object references. Line 8 adds 2.5 through numbers, which is fine for a list of Numbers. But it is the same list as scores, which promised to hold only Integers, and line 9 would take the 2.5 out as an int. The list would break its promise without a single cast in the code, so javac stops the program at the first step, line 7.

Think of a bag of apples. Taking fruit out of it is always fine. But if you hand it to someone as “a bag of fruit”, they may drop a banana in, and the next person who reaches in for an apple gets a banana.

The rule has a name. Generic types are invariant: List<Integer> and List<Number> are two separate types with no is-a link between them, even though Integer is-a Number. The class part can still change: an ArrayList<Integer> is a List<Integer>, because the type argument stays the same.

Wildcards: ? extends and ? super#

Invariance keeps lists honest, and sometimes it gets in the way. A method static double sum(List<Number> numbers) that adds up a list cannot accept a List<Integer>, for the reason you just saw. Yet sum only reads the numbers, and reading an Integer as a Number is always safe. It was adding that caused the trouble.

? extends: a list you read from

Write the parameter as List<? extends Number>. The question mark is a wildcard: it stands for one particular type that the method does not name. ? extends Number means “some type that is Number or a subclass of it”, so a List<Integer>, a List<Double> and a List<Number> all fit. Whatever the real type is, every item in the list is at least a Number, so the method can read each one as a Number.

It prints 253.0 and 6.5: one method, two kinds of list. The cost is that you cannot add to such a list. Inside sum, the list might really be a List<Double>, and then adding an Integer would be the same broken promise as before:

CAP#1is javac's name for the one real type behind the question mark, which this method cannot see (“capture of ? extends Number”). It might be Integer, Double or Number, and 5 only fits some of those, so javac refuses. A ? extends list is for reading. The one value it accepts is null, which fits every type.

? super: a list you write into

The opposite job comes up too. The method below adds ticket numbers 1, 2, 3 and so on to a list. It works for a list of Integers, and it would be just as correct to add the tickets to a list of Numbers or a list of plain Objects, since an Integer is both.

Write that parameter as List<? super Integer>: “a list of some type that is Integer or a superclass of it”. That allows List<Integer>, List<Number> and List<Object>. Each of those can hold an Integer, so adding one is always safe.

It prints [1, 2, 3], [2.5, 1, 2] and [start, 1, 2]. Step through it and watch the three lists grow in the memory view, each one through the same method.

This time reading is the weak side. An item taken out of a List<? super Integer> could be any object, the String "start" included, so get gives you back only an Object.

Both at once: producer extends, consumer super

Many methods use both kinds. Take copying, where every item of one list goes into another. The source list hands items to the method, and the target list takes items from it. Give each parameter the wildcard for its job:

It prints [90, 75, 2.5, 4.0] and [start, 90, 75, 2.5, 4.0]. The parameter from is a producer: the method only takes items out of it, so its type is ? extends T, which accepts a list of T or of any subtype of T. The parameter to is a consumer: the method only puts items into it, so its type is ? super T, which accepts a list of T or of any supertype. That is how one method copies Integers into a list of Numbers, and Numbers into a list of Objects.

Make both parameters a plain List<T> and none of the three calls compiles. For the first one javac reports inference variable T has incompatible equality constraints Number,Integer: T would have to be Integer and Number at the same time.

Java programmers remember the rule with a phrase from Joshua Bloch's book Effective Java: producer extends, consumer super, often shortened to PECS. Before you choose a wildcard, ask what the method does with the parameter: does it take items out, put items in, or both?

Key idea

If a method only reads from a parameter, give it ? extends. If it only writes into it, give it ? super. If it does both, use the exact type.

Type erasure: what is left when the program runs#

The type arguments you write are there for the compiler. javac uses them to check every put and get, and then, as it writes the instructions of the compiled class, it removes them. This step is called type erasure, and it does three things:

• It replaces each type parameter with its bound, or with Object when there is no bound. In Box<T> every T becomes Object. With <T extends Comparable<T>> every T becomes Comparable.
• It drops the type arguments from the code that uses the class. Box<String> and Box<Integer> both become plain Box.
• Wherever your code reads a T and uses it as a particular type, it inserts the cast you used to write by hand.

So the compiled program works much like the Object box from the start of this page, with one difference: every cast in it was added by the compiler, after it checked that the cast cannot fail. Switch between the two views below, and step through the changes one at a time.

Seeing it at run time

Both names come out as ArrayList, and the comparison prints true: the two lists are objects of one and the same class. Nothing inside an ArrayList object records whether it was made as a list of String or a list of Integer. The compiler used that information and then erased it.

What erasure rules out

Because the running program does not know what T is, a few things that look reasonable cannot compile. Here are three of them in one class:

• new T(): to build an object, Java needs its class while the program runs, and T has been erased. There is no class whose constructor it could call.
• thing instanceof List<String>: a list object does not remember its type argument, so this test is impossible. javac words it as an unsafe cast, because instanceof checks whether a cast would work. thing instanceof List<?> compiles, since it only asks whether the object is a list of some kind.
• new T[10], and also new List<String>[3]: an array checks every value stored in it while the program runs, as the ArrayStoreException earlier showed, and it cannot check a type that has been erased. Use an ArrayList<T> instead.

Erasure explains a few more rules you may run into:

Key idea

The compiler checks type arguments and then erases them, so the running program never knows what T is. Anything that would need T while the program runs, such as new T(), instanceof List<String> or new T[10], cannot compile.

Raw types and the unchecked warning

A raw type is a generic type written with no angle brackets at all: List instead of List<String>. Raw types exist so that code written before Java 5 still compiles. Using one switches the checks off, and javac warns you about it. This program uses a raw type to slip a number into a list of names: