9 Generics

Often in large applications, the same operations must be performed on objects of unrelated classes. A typical solution is to use Object references to accommodate objects of any type.

Let us consider the problme of representing pairs of values different types (e.g. int, String, etc.). If we use Object as universal reference type, a possible solution is:

Listing 9.1: Class Pair, Object-based version

public class Pair {
    Object a, b;
    public Pair(Object a, Object b ) {  
    this.a=a; 
    this.b=b;
    }
    Object first(){ return a; }
    Object second(){ return b; }
}

Of course the use of Object allows any type, provided it is a class type. Therefore primitives will be handled through wrapper classes.

An example of usage of the above Object-based solution

1Pair sp = new Pair("One", "Two");
Pair ip = new Pair(1,2);

2String a = (String) sp.second();
int i = (Integer) ip.first();

3String b = (String) ip.second();

4Pair mixpair = new Pair(1,"Two");
Pair pairmix = new Pair("One",2);

5Object o = mixpair.second();
if(o instanceof Integer i){
  // ...
}

1: Object allows usage with diverse types
2: though you need explicit down-casts
3: down-casts are checked at run-time and my result in a ClassCastException
4: no check is possible at compile time about homogeneity of elements
5: thus extra code is required for safety

While Object references enable great flexibility, their use brings cumbersome code:

several explicit casts are required,
compile-time checks are limited
down-casts can be checked at run-time only

A possible solution is to use generic types, which are implemented in Java using the generics syntax.

9.1 Generic Types

The generic alternative to the previous version (Listing 9.1) is shwon in Listing 9.2 below.

Listing 9.2: Class Pair, generics version

public class Pair<T> {
    private T a, b;
    public Pair(T a, T b) {
        this.a = a;  
        this.b = b;
    }
    public T first(){ 
        return a;
    }
    public T second(){
        return b;
    }
    public void set1st(T x){
        a = x;
    }
    public void set2nd(T x){
        b = x;
    }
}

The generic declaration includes the <T> type parameter declaration. The generic class has T whenever that object-based version had Object

The generics version of the class can be used as follows:

1Pair<String> sp = new Pair<>("Four", "Two");
Pair<Integer> ip = new Pair<>(4, 2);

2Pair<String> mixp = new Pair<>(4, "Two");

3String a = sp.second();
int b = ip.first();
4String bs = ip.second();

1: Declaration is slightly longer since the actual type must be provided
2: Compiler is able to check types are compatible
3: Use is more compact and safer since methods return the right type and auto-unboxing can be triggered
4: Compiler checks type matching

Use of generics leads to code that is:

safer
more compact
easier to understand
equally performing

9.1.1 Generic type syntax

Generic types can be declared using the following syntax:

(class|interface) Name <P1 {,P2, ...}>

types can be either class or interface
type parameters, P1, P2 …: represent types (classes or interfaces)

The type parameter are usually indicated with single uppercase letters. More in detail the convention is

T(ype), for the general case of a type
R(eturn), when the type represents the return type
E(lement), when the type represents the type of elements withing a container
K(ey), when the type represents the key type in a map or dictionary ADT
V(alue), when the type represents the value type in a map or dictionary ADT

Reference type parameter must match the class parameter used in instantiation, e.g.

1Pair<String> p=new Pair<String>("a","b");
2Pair<String> q=new Pair<>("a","b");

1: complete declaration for both variable declaration and instantiation
2: the diamond operator <> lets the compiler infer the type in the instantiation

The diamond operator is available since Java 7.

9.1.2 Generic Library Interfaces

All standard interfaces and classes have been defined as generics since Java 5.

9.1.2.1 Generic `Comparable`

The generic Comparable interface is defined as follows

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

Without generics the implementation of Comparable looks like:

public class Student implements Comparable{
  int id;
  public int compareTo(Object o){
1    Student other = (Student)o;
    return this.id – other.id;
  }
}

1: a cast is required

With generics the above code becomes:

public class Student implements Comparable<Student> {
  int id;
  public int compareTo(Student other){
    return this.id – other.id;
  }}

9.1.2.2 Generic `Comparator`

Similarly, the Comparator interface is defined as follows:

Listing 9.3: Comparator interface

public interface Comparator<T>{
  int compare(T a, T b);
}

Thus defining a comparator is very easy, e.g. for sorting strings by length:

Comparator<String> csl = (s1,s2) -> s1.length() - s2.length();

9.1.2.3 Generic `Iterator`

The generic Iterable and Iterator interfaces are defined as follows:

public interface Iterable<E>{
  Iterator<E> iterator();
}

public interface Iterator<E>{
  E next();
  boolean hasNext();
}

Note the use of letter E since iterators are meant to browse the elements in a container.

An example of usage of the two interfaces to iterate on a sequence of random numbers can be rewritten as:

Listing 9.4: Iterable class RandomSeq, generic version

class RandomSeq implements Iterable<Double> {
    private double[] values;
    public RandomSeq(int n){
        values = new double[n];
        for(int i=0; i<n; ++i)
            values[i] = Math.random();
    }

    public Iterator<Double> iterator() {
        return new Iterator<Double>(){
            private int next=0;
            public boolean hasNext() { 
                return next < values.length;
            }
            public Double next() { 
                return values[next++];
            }
        };
    }
}

The usage of such classe is then very simple and readable:

With generics:

Random seq = new Random(10,5,10);
for(double v : seq){
  System.out.println(v);
}

Especially when compared to the one using the non generic version:

Random seq = new Random(10,5,10);
for(Object e : seq){
  double v = ((Double)e).doubleValue();
  System.out.println(v);
}

9.2 Generic Methods

9.2.1 Example

Method that need to operate on any type of element usually use Object typed arguments. For instance the following method removes a given element from an array then shift left the element to the right and filling with null

public static 
Object remove(Object[] ary, Object el){
    for(int i=0; i<ary.length; ++i){
        if(ary[i]!=null && ary[i].equals(el)){
            Object removed = ary[i];
            ary[i] = null;
            return removed;
    }   }
   return null;
}

The above method can be used as follows:

String[] words = { "There", "must", "be", "some", "way", "out", "of", "here" };
Integer[] numbers = { 1, 1, 2, 3, 5, 8, 13, 21, 34 };
1String f = (String)remove(words,"some");
Integer i = (Integer)remove(numbers,13);

2String oo =(String)remove(numbers,8);

1: down-casts are required to convert to the right type
2: down-casts are checked at run-time and can result in ClassCastException

The alternative generic method can be written as

1public static <E>
2E remove(E[] ary, E el){
    for(int i=0; i<ary.length; ++i){
        if(ary[i]!=null && ary[i].equals(el)){
            E removed = ary[i];
            ary[i] = null;
            return removed;
        }   
    }
    return null;
}

1: the type parameter <E> represents the type of the array elements
2: Object is replaced by E

The code using this new version does not require any down-cast.

String[] words = { "There", "must", "be", "some", "way", "out", "of", "here" };
Integer[] numbers = { 1, 1, 2, 3, 5, 8, 13, 21, 34 };

1String f = remove(words,"some");
Integer i = remove(numbers, 13);
2String oo = remove(numbers, 8);
String t = remove(words,8);

1: down-cast are not required since the type are correct
2: compiler checks type compatibility and issue error when cannot convert

9.2.2 Generic method syntax

The syntax for declaring a generic type is as follows

modifiers <P1 {,P2 ... }> type name( arguments )

The parameter types are declared before the return type.

The method arguments can be:

primitive types
regular types, i.e. classes and interfaces
a type parameter, e.g. P1, P2 etc.
a generic type parameterized with the method’s type parameter, e.g. type<T>

9.3 Type Variance

We must be careful about inheritance when generic types are involved.

In general if A extends B then for the generics instantiate with such actual type arguments, the language can implement

Covariance: elements inheritance implies containers inheritance, i.e.

\[A~\mathtt{extends}~B \implies Container<A>~ \mathtt{extends}~Container<B>\]

This is safe for reading but unsafe for writing elements of the container
Contravariance: elements inheritance implies inverse containers inheritance, i.e.

\[A~\mathtt{extends}~B \implies Container<B>~ \mathtt{extends}~Container<A>\]

This is safe for writing but unsafe for reading elements in the container.
Invariance: elements inheritance does not imply container inheritance, this option guarantees type safety in any case but is is less flexible!

In Java, generics types are invariant. For instance, fact Integer extends Object does not imply Pair<Integer> extends Pair<Object>. Invariance leads to compilation errors:

Pair<Integer> pi = new Pair<>(0,1);
Pair<Object> pn = pi;

compiler cannot convert due to generics type invariance

To understand better the alternatives. If Java had implemented covariance for generics (as it does for arrays), it would results in type clashes as a consequence of writing in container.

Pair<Integer> pi = new Pair<>(1,2);
1Pair<Number> pn = pi;
2Number o=pn.first();
3pn.set1st(1.0);
4Integer i=pi.first();

1: This assignment would be allowed if generic types were covariant
2: reading a value from the container is ok
3: writing a Double into an Integer pair is a problem
4: this statement considered correct by the compiler, at run-time generates an error

On the other hand, if generics were contravariant, it would lead to type clashes as a consequence of reading from container

Pair<Number> pn = new Pair<>(1.0,2.0);
1Pair<Integer> pi=pn;
2pn.set1st(Integer.valueOf(42));
3Integer i = pi.second();

1: This assignment would be allowed if generic types were contravariant
2: writing a value to the container is ok
3: this statement considered correct by the compiler, at run-time generates an error

It is important to remember that differently from generics, Java considers arrays covariant.

Wrongly assuming co-variance could lead to an attempt to write a universal print method for pairs like the following one:

void printPair(Pair<Object> p) {
  System.out.println(p.first()+ "-" + p.second());
}

Unfortunately such a method won’t work with, e.g. Pair,

Pair<Integer> p = new Pair<>(7,4);
1printPair(p);

1: the compiler cannot convert due to generics invariance

A more suitable way to write a universal method is to make it generic:

<T> void printPair(Pair<T> p) {
  System.out.println(p.first()+ "-" + p.second());
}

Even if declared as generic, the method in practice is not generic, the type T is never mentioned in the method. The compiler treats it like an Object and uses the relative toString() method to perform the concatenation.

9.4 Wildcards

The problem with regular generic methods is that type checking is present but it can be by-passed:

<T> void resetPair(Pair<T> p) {
1  Object zero = Integer.valueOf(0);
  p.set1st((T)zero);
  p.set2nd((T)zero);
}

1: the compiler issues a warning of an unchecked cast but still accepts the code

The problem is that the above code could lead to an usafe code:

Pair<String> ps = new Pair<>("one","two");
1resetPair(ps);
2String s = ps.first();

1: the method with the “wrong” cast is executed without any problem
2: a ClassCastException is thrown here

The exception is raised later and not where the actual forced cast was done in resetPair() method.

Sometimes when a method is formally generic but just for the purpose of being universal and thus it should not be using the type parameter in any way since it is as if it were unknown. It is possible to explicitly express this condition using the wildcard: ?. The wildcard is usually pronounce as unknown.

void resetPair(Pair<?> p) {
1  Object zero = Integer.valueOf(0);
  p.set1st(zero);
  p.set2nd(zero);
}

1: the compiler issues an error since it cannot cast Object to an unknown type

In this case the more strict checks of the compiler forbid creating a method that performs any unsafe operation.

The syntax of the wildacard does not required declaring any type parameter since it is treated ad unknown.

The ? (unknown) type is literally unknown therefore the compiler treats it in the safest possible way:

Only methods from Object are allowed
Assignment to an unknown reference is considered illegal

9.5 Bounded Types

The type parameters used in generics (types and methods) are unbounded by default, i.e. there are no constraints on the types that can be substituted for them.

The safe assumption for any type parameter T is that T extends Object. When the compiler checks the type usage, references of a type parameter T are considered to be able to provide the members that are defined in class Object (e.g., equals()). No other method can be called since at compile time the actual type of T is unknown.

This can be a problem since sometimes the methods implement algorithm the require specific behaviors from the objects. For instance, to find the max value in an array:

public static <T> void max(T ary[]){
    T max = null;
    for(T current : ary){
1        if( max==null || ((Comparable)max).compareTo(current)<0){
            max = current;
        }   
    }
    return max;
}

1: the method compareTo() is not defined for type T, that is assumed to be Object

It is possible to possible to provide a constraint on a generic parameter, making it a bounded type

public static <T extends Comparable> void max(T ary[]){
    T max = null;
    for(T current : ary){
1        if( max==null || max.compareTo(current)<0){
            max = current;
        }
    }
    return max;
}

1: the compiler assumes T extends Comparable thus allows calling CompareTo()

Upper bounds express constraints on type parameter’s base class with the following syntax:

<T extends B { & B2 & ... } >

this means that at compile time, class T can be replaced only with types extending B – including B itself – and the other bounds, B2, … In this case B is called the upper bound

Lower bounds express constraints on type parameters’s derived classes. Lower bounds can be provided only for unknown type.

The possible syntax for using bounded wildcards are:

<?> unknown, unbounded
<? extends B> upper bound: only sub-types of B, including B
<? super D> lower bound: only super-types of D, including D

For instance to allow a conversion, a bounded wildcard must be used

double sumUB(Pair<? extends Number> p){
1  return p.first().doubleValue()+p.second().doubleValue();
}

1: compiler considers p as a Pair<Number> thus allows calling doubleValue()

9.6 Type Erasure

The implementation of generic types in Java aims at simplicity and efficiency. For each generic type declaration the compiler generates only one class. The generated class is obtained from the generic type by erasing the type parameters.

The classes corresponding to generic types are generated through a procedure called type erasure, the resulting class is called a raw type. The name of the raw type of generic class G<T> is G, i.e. the class name without the type parameters.

In general, each reference to the parameters is substituted with the parameter erasure. Erasure of a parameter is the erasure of its first boundary If no boundary is provided then the erasure is Object:

For: <T> T -> Object
For: <T extends Number> -> T -> Number
For: <T extends Number & Comparable> -> T -> Number

9.6.1 Erasure consequences

Since there is only one class, within the methods there is no information available about the type parameters, in fact they have been erased. The actual value of type parameter is known only to the user of a generic type. Compiler applies checks only when a generic type is used, not within it.

Whenever a generic or a parameter is used a cast is added to its erasure. To avoid inconsistencies and wrong expectations:

instanceof cannot be used on generic types
instanceof is valid for G or G<?>

It is not possible to instantiate an object of the type parameter from within the class

class Triplet<T> {
        private T[] triplet;
        Triplet(T a, T b, T c){
            triplet = new T[]{a,b,c};
        }
}

The type parameter cannot be used in any way inside the raw type

Overloads and ovverrides are checked by compiler after type erasure

class Example<T, U> {
1  void m(T t, U u){}
2  void m(U u, T t){}
3  void mm(T t){}
4  void mm(U u){}
5     U mm(T t){}
}

1: the erasure of both T and U is Object
2: the erasure of both T and U is Object, so this is a duplicate of the previous
3: the erasure of T is Object
4: the erasure of U is Object, so this is a duplicate of the previous
5: the erasure of both T and U is Object but signature does not include the return type, so this is a duplicate of the two previous

Inheritance together with generic types leads to several possibilities, in particular it is not possible to implement twice the same generic interface with different types

Given a base class implementi Comparable<T>

class Student implements Comparable<Student> {..}

The derived class implementing the same interace:

class MasterStudent extends Student     
        implements Comparable<MasterStudent> { .. }

Although the two interface differ in the type parameter, their erasure is the same, therefore it is considered a second implementation of the same interface.

9.6.2 Type inference

Upon generic method invocation, the compiler infers the type argument. The inferred type is called the capture.

In general, it is possible to explicitly indicate the capture, using what is called a type witness, although often useless, e.g. Arrays.<Student>sort(sv);

Inference of the capture is based on both the target type and the argument type

9.7 Use of Generics in Practice

9.7.1 Functional Interfaces

Predefined interfaces defined in java.util.function are all defined as generic types.

Specialized versions are defined for primitive types ( int, long, double, boolean )

Functions: ToTypeFunction, Type1ToType2Function
Suppliers: TypeSupplier
Predicate: TypePredicate
Consumer: TypeConsumer

For instance the IntFunction is defined as:

Listing 9.5: IntFunction functional interface

interface IntFunction<R> {
  R apply(int value);
}

And it can be implemented using an instance method of object reference:

String hexDigits = "0123456789ABCDEF";
IntFunction<Character> hex = hexDigits::charAt;
System.out.println("Hex for 10 : " + hex.apply(10) );

It can be also implemented as a constructor method reference

IntFunction<Integer> builder = Integer::new;
Integer i = builder.build(1);

As another example, the ToIntFunction is defined as:

Listing 9.6: ToIntFunction functional interface

interface ToIntFunction<T> {
  int applyAsInt(T x);
}

And it can be implemented using an instance method reference

ToIntFunction<String> f = String::length;
for(String s : words){
  System.out.println(f.apply(s));
}

Functional interfaces provides also default and static factory methods that allow composing and building new implementations.

As far as the Predicate interface is concerned, the composition methods are

default Predicate<T> and(Predicate<T> o)
default Predicate<T> or(Predicate<T> o)
default Predicate<T> negate()

As an example, the method negate() can be defined as follows:

Listing 9.7: Implementation of Predicate.negate()

default Predicate<T> negate(){
    return o -> !this.test(o);
}

The Function interface provides:

default <V> Function<T,V> andThen(Function<R,V> after)
default <V> Function<V,R> compose(Function<V,T> before)

As an example, the method compose() can be defined as follows:

Listing 9.8: Implementation of Function.compose()

default <V> Function<V,R> compose(Function<V,T> before){
    return x -> this.apply(before.apply(x));
}

9.7.2 Comparing

If we want to reorder the two elements in a pair so that the first is smaller or equal than the second we could write the following method that makes use of a Comparator:

<T> void sort(Pair<T> p, Comparator<T> cmp) {
    if(cmp.compare(p.first(),p.second()) > 0){
        T tmp = p.first();
        p.set1st(p.second());
        p.set2nd(tmp);
    }
}

The method can be used as follows

Pair<Integer> pi = new Pair<>(4,2);
Comparator ci=(i1,i2)-> i1.compareTo(i2);
Comparator<Number> cn = (n1,n2)->
                    Double.compare(n1.doubleValue(),
                                   n2.doubleValue());

1sort(pi, ci);
2sort(pi, cn);

1: ok, the two actual arguments match the method declaration
2: the method is not applicable for the argument: Comparator<Number> since a Comparator<Integer> was required

The compiler signals an error, but still it should be correct since a Comparator<Number> is capable of comparing also Integer objects.

The solution is to use an unknown with a lower bound:

<T> void sort(Pair<T> p, Comparator<? super T> cmp) {
    if(cmp.compare(p.first(),p.second()) > 0){
        T tmp = p.first();
        p.set1st(p.second());
        p.set2nd(tmp);
    }
}

With this version, sort(pi, cn) is correct because the compiler makes the following captures:

T : Integer
? : Number which is a super of Integer

According to this approach we can conclude that the sort() method of Arrays that accepts comparable objects should be defined as:

static <T extends Comparable<? super T>> void sort(T[] list);

Actually, for backward compatibility reasons, in class Array the methdo is defined as:

public static void sort(Object[] a)

As a consequence, no compile time check can be performed.

On the contrary, as expected, the sort() method that accepts a Comparator object is effectively defined as follows:

static <T> void sort(T[] a, Comparator<? super T> cmp)

So, in this case the compiler can perform the required checks and ensure correct behavior at run-time.

9.7.3 Generic Comparators

Interface java.util.Comparator

Listing 9.9: Comparator interface

public interface Comparator<T>{
  int compare(T a, T b);
}

Arrays.sort(sv, (a,b) -> a.id – b.id );

Arrays.sort(sv, new Comparator<Student>(){
    public void compare(Student a, Student b){
  return a.id – b.id 
});

Comparator factory

Most comparators take some information out of the objects to be compared Typically through a getter Such values are primitive or are comparable using their natural order (i.e. Comparable) Such comparator can be generated starting from a key getter functional object:

static <T,U extends Comparable<U>> 
Comparator<T> comparing(Function<T,U> keyGetter)

Comparator.comparing

Arrays.sort(sv,comparing(Student::getId));

Requires import static java.util.Comparator.*

static <T,U extends Comparable<? super U>> 
Comparator<T> comparing(Function<T,U> keyGetter){
  return (a,b) -> keyGetter.apply(a).
                        compareTo(keyGetter.apply(b));
}

Comparator.comparingInt

Arrays.sort(sv,comparingInt(Student::getId))

static <T,U extends Comparable<? super U>> Comparator<T> 
 comparingInt(ToIntFunction<T,U> keyGetter){
  return (a,b) -> keyGetter.applyAsInt(a) -                                 keyGetter.applyAsInt(b);
}

Performance

Table 9.1: Relative performance of different comparator

Comparator	Time
`(a,b)-> a.id - b.id`	100
`(a,b)-> a.getId() - b.getId()`	120
`comparingInt(Student::getId)`	135
`comparing(Student::getId)`	185

It is interesting to look at a summary of how Comparator evolved during the history of Java.

Since Java 2 (1998):

Arrays.sort(sv,new Comparator(){
 public int compare(Object a, Object b){
    return ((Student)a).id–((Student)b).id; 
 }});

Since Java 5 (2005)

Arrays.sort(sv,new Comparator<Student>(){
 public int compare(Student a, Student b){
    return a.getId() - b.getId(); 
 }});

Since Java 8 (2014), lambda expression:

Arrays.sort(sv,(a,b)->a.getId()-b.getId());

method reference

Arrays.sort(sv,comparing(Student::getId));

Functional interface composition Reverse order method Not a Comparator method!

static <T> Comparator<T> 
  reverse(Comparator<T> cmp){
        return (a,b) -> cmp.compare(b,a);
}

Arrays.sort(sv,reverse(comparing(Student::getId)));

Comparator composition Reverse order Default method Comparator.reversed()

default <T> Comparator<T> reversed(){
  return (a,b) -> this.compare(b,a);
}

Arrays.sort(sv, comparing(Student::getId).reversed());

Comparator composition Multiple criteria Default method Comparator.thenComparing()

default <T> Comparator<T> 
            thenComparing(Comparator<T> other){
  return (a,b) -> { 
            int r = this.compare(a,b);
            if(r!=0) return r;
            else return other.compare(a,b);
}

Comparator composition Multiple criteria

default <U extends Comparable<U> 
Comparator<T> thenComparing(Function<T,U> ke){
  return (a,b) -> { 
     int r = this.compare(a,b);
     if(r!=0) return r;
   return ke.apply(a).compareTo(ke.apply(b));
}

Comparator composition

Arrays.sort(sv,(a,b)-> {
        int l = a.last.compareTo(b.last);
        if(l!=0) return l;
        return a.first.compareTo(b.first);
}));

Arrays.sort(sv,
    comparing(Student::getLast).
    thenComparing(Student::getFirst));

9.8 Wrap-up

Generics allow defining type parameter for methods and classes with <T> syntax
The same code can work with several different types
Primitive types must be replaced by wrappers
Generics containers are type invariant
Wildcard, ? (read as unknown)
Generics are implemented by type erasure
Most checks are performed at compile time