Generics: generic methods, generic classes, wildcards

Generics means writing a class or method without binding it to a particular type, and stating the type when you use it. When you write ArrayList<String>, you are already using a generic class. This week you write your own generic methods and classes. In the exam this topic mostly comes as compile errors (primitive type argument, compareTo on an unbounded T, the List<Integer> vs List<Number> mismatch) and as a “write a generic method / class” question.

Golden rules:

1. A type parameter can only be a reference type. Integer, not int.
2. In a generic method, <T> is written before the return type: static <T> void print(T[] a).
3. With an unbounded T, only Object methods can be called. For compareTo, <T extends Comparable<T>>.
4. A List<Integer> is not a List<Number>. For flexibility, use a wildcard: List<? extends Number>.
5. Type erasure: there is no T at run time; new T() cannot be written.

Why generics?

Without generics, the only way to write shared code was to hold everything as Object. This has two problems: a cast is needed on every read, and a wrong type shows up only at run time (ClassCastException). Generics moves this error to compile time.

Box<String> bs = new Box<>("hello");
String s = bs.get();          // no cast
Integer n = bs.get();         // DOES NOT COMPILE: String cannot be converted to Integer

A test showing why the “raw type” usage from before generics is dangerous: putting an int into an untyped list and reading it as a String list compiles (it only gives a warning) but blows up at run time.

List raw = new ArrayList<String>();   // raw type: warning
raw.add(5);
List<String> typed = raw;
String first = typed.get(0);          // at run time

ClassCastException

Generic methods

The type parameter list (<T>) is written before the return type. The compiler infers what T will be from the arguments at the call (type inference).

static <T> void printArray(T[] items) {
    for (T item : items) System.out.print(item + " ");
    System.out.println();
}
static <T> int countMatches(T[] arr, T target) {
    int n = 0;
    for (T x : arr) if (x.equals(target)) n++;     // equals exists in Object: allowed
    return n;
}
Integer[] ints = {1, 2, 3};
String[] strs = {"a", "b"};
Double[] ds = {1.5, 2.5};
printArray(ints);
printArray(strs);
printArray(ds);
System.out.println(countMatches(new String[]{"x", "y", "x"}, "x"));

1 2 3 
a b 
1.5 2.5 
2

If the array were int[], it could not be called with printArray: T must be a reference type and int[] is not a T[]. That is why we used Integer[] in the examples.

Bounded type parameters

For an unbounded T, the compiler knows only Object’s methods (equals, toString, hashCode). If you want to call compareTo on T, you have to say that T is Comparable:

static <T extends Comparable<T>> T maximum(T a, T b, T c) {
    T max = a;
    if (b.compareTo(max) > 0) max = b;
    if (c.compareTo(max) > 0) max = c;
    return max;
}
System.out.println(maximum(3, 9, 4));
System.out.println(maximum("pear", "apple", "zebra"));
System.out.println(maximum(2.5, -1.0, 2.4));

9
zebra
2.5

Even if the bound is an interface, extends is written (not implements). If you call maximum with a class that is not Comparable, you get a compile error: inference variable T has incompatible bounds.

Generic classes

The type parameter is defined next to the class name and can be used everywhere in the class.

class Box<T> {
    private T content;
    Box(T content) { this.content = content; }
    T get() { return content; }
    void set(T content) { this.content = content; }
    boolean isEmpty() { return content == null; }
    @Override public String toString() { return "Box[" + content + "]"; }
}

Box<String> bs = new Box<>("hello");      // <> diamond: the type is not repeated on the right
Box<Integer> bi = new Box<>(42);
String s = bs.get();
int v = bi.get() + 8;                     // Integer → int (unboxing)
System.out.println(bs + " " + bi + " " + s.length() + " " + v);
bi.set(null);
System.out.println(bi.isEmpty());

Box[hello] Box[42] 5 50
true

Multiple type parameters are separated by commas. By convention a single capital letter is used: T (type), E (element), K (key), V (value), N (number).

class Pair<K, V> {
    private final K key;
    private final V value;
    Pair(K k, V v) { key = k; value = v; }
    K getKey() { return key; }
    V getValue() { return value; }
    Pair<V, K> swap() { return new Pair<>(value, key); }
    @Override public String toString() { return "(" + key + ", " + value + ")"; }
}
Pair<String, Integer> p = new Pair<>("age", 21);
Pair<Integer, String> q = p.swap();
System.out.println(p + " " + q + " " + (q.getKey() + 1));

(age, 21) (21, age) 22

A bound can also be placed at the class level: inside class Stats<T extends Number>, x.doubleValue() can be called. When 4, 5, 9 were added to a Stats<Integer>, the average came out as 6.0. A Stats<String> does not compile.

ArrayList quick review

ArrayList<Integer> list = new ArrayList<>();
list.add(5); list.add(10); list.add(15);
list.add(1, 7);                      // [5, 7, 10, 15]
list.remove(Integer.valueOf(10));    // value: [5, 7, 15]
list.remove(0);                      // index: [7, 15]
System.out.println(list + " size=" + list.size() + " get(1)=" + list.get(1));
System.out.println(list.contains(15) + " " + list.indexOf(15));

[7, 15] size=2 get(1)=15
true 1

PITFALL · which remove(1)? In an ArrayList<Integer>, remove(1) calls the index version because the argument is an int. On the list [10, 20, 30], remove(1) removes 20, the result is [10, 30]. To remove the element whose value is 1, remove(Integer.valueOf(1)).

Introduction to wildcards

Generics are invariant: even though Integer is a subclass of Number, List<Integer> is not a List<Number>. If it were, you could add a Double to an Integer list that behaves like a List<Number>, and the list would be corrupted. For flexibility, the question mark (wildcard) is used:

static double sum(List<? extends Number> list) {
    double s = 0;
    for (Number n : list) s += n.doubleValue();
    return s;
}
static void printAll(List<?> list) {
    for (Object o : list) System.out.print(o + ";");
    System.out.println();
}
static void addNumbers(List<? super Integer> list) {
    list.add(1); list.add(2);
}

System.out.println(sum(List.of(1, 2, 3)) + " " + sum(List.of(0.5, 1.5)));
printAll(List.of("x", 1, 2.0));
List<Number> ln = new ArrayList<>();
addNumbers(ln);
List<Object> lo = new ArrayList<>();
addNumbers(lo);
System.out.println(ln + " " + lo);

6.0 2.0
x;1;2.0;
[1, 2] [1, 2]

TIP · extends to read, super to write. If you only read data from a collection, use ? extends T; if you only put data into it, use ? super T. In this course, the exam usually asks for a sum or average method with ? extends Number.

Type erasure

After the compiler does the type checks, it erases the type arguments; at run time Box<String> and Box<Integer> are the same Box class:

Box<String> b1 = new Box<>("x");
Box<Integer> b2 = new Box<>(1);
System.out.println(b1.getClass() == b2.getClass());
System.out.println(b1.getClass().getSimpleName());

true
Box

That is why there are things you cannot write in generic code:

• new T() and new T[10]: unexpected type; required: class, found: type parameter T
• static T value;: a static field is shared by all Boxes, and it is not clear which T it would be
• obj instanceof Box<String>
• A primitive type argument: Box<int>

Common mistakes

static <T extends Comparable<T>> T maximum(T a, T b, T c) {
    T max = a;
    if (b.compareTo(max) > 0) max = b;
    if (c.compareTo(max) > 0) max = c;
    return max;
}
// in main:
System.out.println(maximum(3, 9, 4));
System.out.println(maximum("pear", "apple", "zebra"));
System.out.println(maximum(2.5, -1.0, 2.4));

static <T> T biggest(T a, T b) {
    return a.compareTo(b) > 0 ? a : b;
}

ArrayList<int> list = new ArrayList<>();

class Pair<K, V> {
    private final K key; private final V value;
    Pair(K k, V v) { key = k; value = v; }
    K getKey() { return key; }
    Pair<V, K> swap() { return new Pair<>(value, key); }
    public String toString() { return "(" + key + ", " + value + ")"; }
}
// in main:
Pair<String, Integer> p = new Pair<>("age", 21);
Pair<Integer, String> q = p.swap();
System.out.println(p + " " + q + " " + (q.getKey() + 1));

static double sum(List<Number> list) { ... }
// in main:
List<Integer> li = new ArrayList<>();
sum(li);

static void fill(List<? extends Number> list) {
    list.add(3);
}

ArrayList<Integer> list = new ArrayList<>();
list.add(5); list.add(10); list.add(15);
list.add(1, 7);
list.remove(Integer.valueOf(10));
list.remove(0);
System.out.println(list + " size=" + list.size());

ArrayList<Integer> nums = new ArrayList<>(List.of(10, 20, 30));
nums.remove(1);
System.out.println(nums);

class Box<T> {
    T make() { return new T(); }
}

Box<String> b1 = new Box<>("x");
Box<Integer> b2 = new Box<>(1);
System.out.println(b1.getClass() == b2.getClass());

import java.util.ArrayList;
import java.util.NoSuchElementException;

public class Stack<E> {
    private final ArrayList<E> items = new ArrayList<>();

    public E pop() {
        if (items.isEmpty()) throw new NoSuchElementException("stack is empty");
        return items.remove(items.size() - 1);
    }
    public E peek() {
        if (items.isEmpty()) throw new NoSuchElementException("stack is empty");
        return items.get(items.size() - 1);
    }
    public boolean isEmpty() { return items.isEmpty(); }
    public int size() { return items.size(); }
}