Java Generics
History
Java supports generics as of version 1.5
Before
list of integers List
list of strings List
list of lists of strings List
After
list of integers List<Integer>
list of strings List<String>
list of lists of strings List<List<String>>
«Now compiler can track what we have list of»
Terms
Term | Example |
Parameterized type | List<String> |
Actual type parameter | String |
Generic type | List<E> |
Formal type parameter | E |
Unbounded wildcard type | List<?> |
Raw type | List |
Bounded type parameter | <E extends Number> |
Recursive type bound | <T extends Comparable<T>> |
Bounded wildcard type | List<? extends Number> |
Generic method | static <E> List<E> asList (E[] a) |
Type token | List.class |
Before-after generics
// before generics
List words = new ArrayList();
words.add("Hello ");
words.add("world!");
String s = ((String)words.get(0))+((String)words.get(1))
assert s.equals("Hello world!");
// with generics
List<String> words = new ArrayList<String>();
words.add("Hello ");
words.add("world!");
String s = words.get(0)+words.get(1); // no explicit casts
assert s.equals("Hello world!");
«since generics are implemented by erasure
at bytecode level, two sources above will be identical»
Use raw types in..
class literals
List.class // legal
String[].class // legal
int.class // legal
List<String>.class // illegal since erasure
List<?>.class // illegal
instanceof operator
if (o instanceof Set) {
Set<?> set = (Set<?>) o; // checked cast, no warning
}
Reification
// allocates an array that its components are type of String,
// so we say that it is reified
String[] aStringArray = new String[10];
// allocates a list with no type information,
// Java does not reify generic types
List<String> aStringList = new ArrayList<String>();
Comparing List, List<?>, List<Object>
List unboundedList = new ArrayList<Integer>();
// legal (warning)
List<?> unboundedList = new ArrayList<Integer>();
// legal, partial type-safe
List<?> unboundedList = new ArrayList<?>();
// illegal
List<Object> unboundedList = new ArrayList<Integer>();
// illegal, invariant
« List<sub> is not a subtype of List<super> »
What is the difference?
static int countCommonElements(Set s1, Set s2) {
int result = 0;
for (Object o1 : s1) {
if (s2.contains( o1 ))
result++;
}
return result;
}
static int countCommonElements(Set<?> s1, Set<?> s2) {
int result = 0;
for (Object o1 : s1) {
if (s2.contains( o1 ))
result++;
}
return result;
}
It is guaranteed that there is no typed operation in the second one
Arrays
« sub[] is a subtype of super[], so its covariant »
Object[] anObjectArray = new Integer[10];
// legal, covariant
anObjectArray[0] = new String("abc");
// no type safety, causes runtime exception
// like arrays, raw collection types are not type-safe
List list = new ArrayList();
list.add("one");
list.add(new Integer(1));
String s = (String) list.get(1); // ClassCastException
Boxing-Unboxing
public static int sum (List<Integer> ints) {
int s = 0;
for (int n : ints) { s += n; }
return s;
}
public static Integer sumInteger(List<Integer> ints) {
Integer s = 0;
for (Integer n : ints) { s += n; }
return s;
}
Generify legacy codes
public class Stack {
private Object[] stack;
private int top = 0;
private static final int INITIAL_CAPACITY = 8;
public Stack() {
stack = new Object[INITIAL_CAPACITY];
}
public void push(Object obj) {
ensureCapacity();
stack[top++] = obj;
}
public Object pop() {
if (top == 0) // stack is empty
throw new EmptyStackException();
Object temp = stack[--top];
stack[top]=null;
return temp;
}
public boolean isEmpty(){
return top == 0;
}
public void ensureCapacity() {
if (stack.length == top)
stack = Arrays.copyOf(stack, 2 * top + 1);
}
}
public class GenericStack<E> {
private E[] stack;
private int top = 0;
private static final int INITIAL_CAPACITY = 8;
@SuppressWarnings( "unchecked" )
public GenericStack() {
stack = (E[]) new Object[INITIAL_CAPACITY];
}
public void push(E obj) {
ensureCapacity();
stack[top++] = obj;
}
public E pop() {
if (top == 0) // stack is empty
return null;
E temp = stack[--top];
stack[top]=null;
return temp;
}
public boolean isEmpty(){
return top == 0;
}
public void ensureCapacity() {
if (stack.length == top)
stack = Arrays.copyOf(stack, 2 * top + 1);
}
}
Generic methods
«Static utility methods are good candidates for generification »
Get and Put Principal
// PECS (producer extends, consumer super) principal
public static <T> void copy(
List<? super T> dst, List<? extends T> src ) {
for ( int i = 0; i < src.size(); i++ ) {
dst.set( i, src.get( i ) );
}
}
// usage
List<Object> objs = Arrays.<Object>asList(2, 3.14, "four");
List<Integer> ints = Arrays.asList(5, 6);
Collections.copy(objs, ints); // type inference
assert objs.toString().equals("[5, 6, four]");
Copy method (alternatives)
public static <T> void copy(
List<T> dst, List<T> src);
public static <T> void copy(
List<T> dst, List<? extends T> src);
public static <T> void copy(
List<? super T> dst, List<T> src);
public static <T> void copy(
List<? super T> dst, List<? extends T> src);
Comparables
public static <T extends Comparable<T>> T
max (List<T> list);
« All comparables and comparators are consumers »
public static <T extends Comparable<? super T>> T
max(List<? extends T> list);
Tips on wildcard types
«Use wildcard types on input parameters for maximum flexibility»
«Do not use a wildcard for an input parameter if you both get and put on that parameter»
« Do not use wildcard types as return types »
Restrictions on Wildcards
Instance Creation
List<?> list = new ArrayList<?>(); // illegal
List<Lis
t<?>> lists = new ArrayList<List<?>>(); // legal
lists.add(Arrays.asList(1,2,3));
lists.add(Arrays.asList("four","five"));
Generic Method Calls
List<?> list = Lists.<?>factory(); // illegal
List<List<?>> list = Lists.<List<?>>factory(); // legal
Supertypes
class AnyList extends ArrayList<?> {...} // illegal
Wildcard capturing
public static <T> void reverse(List<T> list) {
List<T> tmp = new ArrayList<T>(list);
for (int i = 0; i < list.size(); i++) {
list.set(i, tmp.get(list.size() - i - 1));
}
}
public static void reverse(List<?> list) {
List<Object> tmp = new ArrayList<Object>(list);
for (int i = 0; i < list.size(); i++) {
list.set(i, tmp.get(list.size() - i - 1)); // error
}
}
public static void reverse(List<?> list) {
rev(list);
}
private static <T> void rev(List<T> list) {
List<T> tmp = new ArrayList<T>(list);
for (int i = 0; i < list.size(); i++) {
list.set(i, tmp.get(list.size() - i - 1));
}
}
« Here we say that the type variable T has captured the wildcard. This is a generally useful technique when dealing with wildcards, and it is worth knowing. »
Use Checked Collections to Enforce Security
private class Order { }
private class AuthenticatedOrder extends Order { }
..
List<AuthenticatedOrder> checkedList =
new ArrayList<AuthenticatedOrder>();
addChecked(Collections.checkedList(
checkedList, AuthenticatedOrder.class));
..
public void addChecked(List<AuthenticatedOrder> checkedList) {
List raw = checkedList;
Order order = new Order();
raw.add(order); // unchecked call, ClassCastException at runtime
}
http://www.angelikalanger.com/GenericsFAQ/JavaGenericsFAQ.html
Angelika Langer
Effective Java
Joshua Bloch
Java Generics and Collections
Maurice Naftalin and Philip Wadler