Java Generics

https://docs.oracle.com/javase/tutorial/java/generics/why.html
https://docs.oracle.com/javase/tutorial/java/generics/methods.html
https://docs.oracle.com/javase/tutorial/java/generics/inheritance.html
https://docs.oracle.com/javase/tutorial/java/generics/genTypeInference.html
https://docs.oracle.com/javase/tutorial/java/generics/wildcards.html
https://docs.oracle.com/javase/tutorial/java/generics/upperBounded.html


Generics enable types (classes and interfaces) to be parameters when defining classes, interfaces and methods. 

Type parameters provide a way for you to re-use the same code with different inputs. 

The inputs to type parameters are types.

Stronger type checks at compile time.

  A Java compiler applies strong type checking to generic code and issues errors if the code violates type safety. 

  Fixing compile-time errors is easier than fixing runtime errors, which can be difficult to find.

Elimination of casts.

List<String> list = new ArrayList<String>();
list.add("hello");
String s = list.get(0);   // no cast

Enabling programmers to implement generic algorithms.

By using generics, programmers can implement generic algorithms that work on collections of different types, can be customized, and are type safe and easier to read.

Generic Types

A generic type is a generic class or interface that is parameterized over types. 

A generic class is defined with the following format:

class name<T1, T2, ..., Tn> { /* ... */ }

The type parameter section, delimited by angle brackets (<>), follows the class name. It specifies the type parameters (also called type variables) T1, T2, ..., and Tn.

Example:

Before:

public class Box {
    private Object object;

    public void set(Object object) { this.object = object; }
    public Object get() { return object; }
}

After:

/**
 * Generic version of the Box class.
 * @param <T> the type of the value being boxed
 */
public class Box<T> {
    // T stands for "Type"
    private T t;

    public void set(T t) { this.t = t; }
    public T get() { return t; }
}

As you can see, all occurrences of Object are replaced by T. A type variable can be any non-primitive type you specify: any class type, any interface type, any array type, or even another type variable.

Type Parameter Naming Conventions

By convention, type parameter names are single, uppercase letters. This stands in sharp contrast to the variable naming conventions that you already know about, and with good reason: Without this convention, it would be difficult to tell the difference between a type variable and an ordinary class or interface name.

The most commonly used type parameter names are:

• E - Element (used extensively by the Java Collections Framework)
• K - Key
• N - Number
• T - Type
• V - Value
• S,U,V etc. - 2nd, 3rd, 4th types

Invoking and Instantiating a Generic Type

Box<Integer> integerBox;

Type Parameter and Type Argument Terminology: Many developers use the terms "type parameter" and "type argument" interchangeably, but these terms are not the same. When coding, one provides type arguments in order to create a parameterized type. Therefore, the T in Foo<T> is a type parameter and the String in Foo<String> f is a type argument. This lesson observes this definition when using these terms.

The Diamond




In Java SE 7 and later, you can replace the type arguments required to invoke the constructor of a generic class with an empty set of type arguments (<>) as long as the compiler can determine, or infer, the type arguments from the context. This pair of angle brackets, <>, is informally called the diamond. For example, you can create an instance of Box<Integer> with the following statement:




Box<Integer> integerBox = new Box<>();

Multiple Type Parameters

public interface Pair<K, V> {
    public K getKey();
    public V getValue();
}

public class OrderedPair<K, V> implements Pair<K, V> {

    private K key;
    private V value;

    public OrderedPair(K key, V value) {
 this.key = key;
 this.value = value;
    }

    public K getKey() { return key; }
    public V getValue() { return value; }
}

Pair<String, Integer> p1 = new OrderedPair<String, Integer>("Even", 8);

OrderedPair<String, Integer> p1 = new OrderedPair<>("Even", 8);

Parameterized Types


You can also substitute a type parameter (i.e., K or V) with a parameterized type (i.e., List<String>). For example, using the OrderedPair<K, V> example:



OrderedPair<String, Box<Integer>> p = new OrderedPair<>("primes", new Box<Integer>(...));

Generic Methods

Generic methods are methods that introduce their own type parameters. This is similar to declaring a generic type, but the type parameter's scope is limited to the method where it is declared. Static and non-static generic methods are allowed, as well as generic class constructors.

public class Util {
    public static <K, V> boolean compare(Pair<K, V> p1, Pair<K, V> p2) {
        return p1.getKey().equals(p2.getKey()) &&
               p1.getValue().equals(p2.getValue());
    }
}

Bounded Type Parameters

To declare a bounded type parameter, list the type parameter's name, followed by the extends keyword, followed by its upper bound, which in this example is Number. Note that, in this context, extends is used in a general sense to mean either "extends" (as in classes) or "implements" (as in interfaces).

public class Box<T> {

    private T t;          

    public void set(T t) {
        this.t = t;
    }

    public T get() {
        return t;
    }

    public <U extends Number> void inspect(U u){
        System.out.println("T: " + t.getClass().getName());
        System.out.println("U: " + u.getClass().getName());
    }

    public static void main(String[] args) {
        Box<Integer> integerBox = new Box<Integer>();
        integerBox.set(new Integer(10));
        integerBox.inspect("some text"); // error: this is still String!
    }
}

Multiple Bounds


A type parameter can have multiple bounds:


<T extends B1 & B2 & B3>

A type variable with multiple bounds is a subtype of all the types listed in the bound. If one of the bounds is a class, it must be specified first. For example:



Class A { /* ... */ }
interface B { /* ... */ }
interface C { /* ... */ }

class D <T extends A & B & C> { /* ... */ }


If bound A is not specified first, you get a compile-time error:



class D <T extends B & A & C> { /* ... */ }  // compile-time error

Generic Methods and Bounded Type Parameters


Bounded type parameters are key to the implementation of generic algorithms. Consider the following method that counts the number of elements in an array T[] that are greater than a specified element elem.


public static <T> int countGreaterThan(T[] anArray, T elem) {
    int count = 0;
    for (T e : anArray)
        if (e > elem)  // compiler error
            ++count;
    return count;
}


The implementation of the method is straightforward, but it does not compile because the greater than operator (>) applies only to primitive types such as short, int, double, long, float, byte, and char. You cannot use the > operator to compare objects. To fix the problem, use a type parameter bounded by the Comparable<T> interface:



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


The resulting code will be:



public static <T extends Comparable<T>> int countGreaterThan(T[] anArray, T elem) {
    int count = 0;
    for (T e : anArray)
        if (e.compareTo(elem) > 0)
            ++count;
    return count;
}

Generics, Inheritance, and Subtypes


As you already know, it is possible to assign an object of one type to an object of another type provided that the types are compatible. For example, you can assign an Integer to an Object, since Object is one of Integer's supertypes:



Object someObject = new Object();
Integer someInteger = new Integer(10);
someObject = someInteger;   // OK


In object-oriented terminology, this is called an "is a" relationship. Since an Integer is a kind of Object, the assignment is allowed. But Integer is also a kind of Number, so the following code is valid as well:



public void someMethod(Number n) { /* ... */ }

someMethod(new Integer(10));   // OK
someMethod(new Double(10.1));   // OK


The same is also true with generics. You can perform a generic type invocation, passing Number as its type argument, and any subsequent invocation of add will be allowed if the argument is compatible with Number:



Box<Number> box = new Box<Number>();
box.add(new Integer(10));   // OK
box.add(new Double(10.1));  // OK


Now consider the following method:



public void boxTest(Box<Number> n) { /* ... */ }


What type of argument does it accept? By looking at its signature, you can see that it accepts a single argument whose type is Box<Number>. But what does that mean? Are you allowed to pass in Box<Integer> or Box<Double>, as you might expect? The answer is "no", because Box<Integer> and Box<Double> are not subtypes of Box<Number>.

This is a common misunderstanding when it comes to programming with generics, but it is an important concept to learn.







Box<Integer> is not a subtype of Box<Number> even though Integer is a subtype of Number.

Note: Given two concrete types A and B (for example, Number and Integer), MyClass<A> has no relationship to MyClass<B>, regardless of whether or not A and B are related. The common parent of MyClass<A> and MyClass<B> is Object.

Generic Classes and Subtyping

You can subtype a generic class or interface by extending or implementing it. The relationship between the type parameters of one class or interface and the type parameters of another are determined by the extends and implements clauses.



Using the Collections classes as an example, ArrayList<E> implements List<E>, and List<E> extends Collection<E>. So ArrayList<String> is a subtype of List<String>, which is a subtype of Collection<String>. So long as you do not vary the type argument, the subtyping relationship is preserved between the types.





A sample Collections hierarchy



Now imagine we want to define our own list interface, PayloadList, that associates an optional value of generic type P with each element. Its declaration might look like:


interface PayloadList<E,P> extends List<E> {
  void setPayload(int index, P val);
  ...
}




The following parameterizations of PayloadList are subtypes of List<String>:

PayloadList<String,String>
PayloadList<String,Integer>
PayloadList<String,Exception>




A sample PayloadList hierarchy

Type Inference



Type inference is a Java compiler's ability to look at each method invocation and corresponding declaration to determine the type argument (or arguments) that make the invocation applicable. The inference algorithm determines the types of the arguments and, if available, the type that the result is being assigned, or returned. Finally, the inference algorithm tries to find the most specific type that works with all of the arguments.

To illustrate this last point, in the following example, inference determines that the second argument being passed to the pick method is of type Serializable:



static <T> T pick(T a1, T a2) { return a2; }
Serializable s = pick("d", new ArrayList<String>());




<T> tells compiler this is a generic method

type inference will check if "d" and new ArrayList<String>() are both Serializable, if they are will run pick function, and assign the result back to s.

Type Inference and Generic Methods







Type Inference and Instantiation of Generic Classes

You can replace the type arguments required to invoke the constructor of a generic class with an empty set of type parameters (<>) as long as the compiler can infer the type arguments from the context. This pair of angle brackets is informally called the diamond.



For example, consider the following variable declaration:



Map<String, List<String>> myMap = new HashMap<String, List<String>>();




You can substitute the parameterized type of the constructor with an empty set of type parameters (<>):


Map<String, List<String>> myMap = new HashMap<>();




Note that to take advantage of type inference during generic class instantiation, you must use the diamond. In the following example, the compiler generates an unchecked conversion warning because the HashMap() constructor refers to the HashMap raw type, not the Map<String, List<String>> type:


Map<String, List<String>> myMap = new HashMap(); // unchecked conversion warning

Target Types

The Java compiler takes advantage of target typing to infer the type parameters of a generic method invocation. The target type of an expression is the data type that the Java compiler expects depending on where the expression appears. Consider the method Collections.emptyList, which is declared as follows:



static <T> List<T> emptyList();





Consider the following assignment statement:


List<String> listOne = Collections.emptyList();





This statement is expecting an instance of List<String>; this data type is the target type

Wildcards (?)


In generic code, the question mark (?), called the wildcard, represents an unknown type. The wildcard can be used in a variety of situations: as the type of a parameter, field, or local variable; sometimes as a return type (though it is better programming practice to be more specific). The wildcard is never used as a type argument for a generic method invocation, a generic class instance creation, or a supertype.

Upper Bounded Wildcards

You can use an upper bounded wildcard to relax the restrictions on a variable. For example, say you want to write a method that works on List<Integer>, List<Double>, and List<Number>; you can achieve this by using an upper bounded wildcard.



To declare an upper-bounded wildcard, use the wildcard character ('?'), followed by the extends keyword, followed by its upper bound. Note that, in this context, extends is used in a general sense to mean either "extends" (as in classes) or "implements" (as in interfaces).



To write the method that works on lists of Number and the subtypes of Number, such as Integer, Double, and Float, you would specify List<? extends Number>. The term List<Number> is more restrictive than List<? extends Number> because the former matches a list of type Number only, whereas the latter matches a list of type Number or any of its subclasses.

Consider the following process method:



public static void process(List<? extends Foo> list) { /* ... */ }





The upper bounded wildcard, <? extends Foo>, where Foo is any type, matches Foo and any subtype of Foo. The process method can access the list elements as type Foo:


public static void process(List<? extends Foo> list) {
    for (Foo elem : list) {
        // ...
    }
}

The sumOfList method returns the sum of the numbers in a list:


public static double sumOfList(List<? extends Number> list) {
    double s = 0.0;
    for (Number n : list)
        s += n.doubleValue();
    return s;
}

List<Integer> li = Arrays.asList(1, 2, 3);
System.out.println("sum = " + sumOfList(li));

List<Double> ld = Arrays.asList(1.2, 2.3, 3.5);
System.out.println("sum = " + sumOfList(ld));

Lower Bounded Wildcards

The Upper Bounded Wildcards section shows that an upper bounded wildcard restricts the unknown type to be a specific type or a subtype of that type and is represented using the extends keyword. In a similar way, a lower bounded wildcard restricts the unknown type to be a specific type or a super type of that type.

A lower bounded wildcard is expressed using the wildcard character ('?'), following by the super keyword, followed by its lower bound: <? super A>.

---

Note: You can specify an upper bound for a wildcard, or you can specify a lower bound, but you cannot specify both.

---

Say you want to write a method that puts Integer objects into a list. To maximize flexibility, you would like the method to work on List<Integer>, List<Number>, and List<Object> — anything that can hold Integervalues.

To write the method that works on lists of Integer and the supertypes of Integer, such as Integer, Number, and Object, you would specify List<? super Integer>. The term List<Integer> is more restrictive than List<? super Integer> because the former matches a list of type Integer only, whereas the latter matches a list of any type that is a supertype of Integer.

The following code adds the numbers 1 through 10 to the end of a list:

public static void addNumbers(List<? super Integer> list) {
    for (int i = 1; i <= 10; i++) {
        list.add(i);
    }
}

Unbounded Wildcards

The unbounded wildcard type is specified using the wildcard character (?), for example, List<?>. This is called a list of unknown type. There are two scenarios where an unbounded wildcard is a useful approach:

• If you are writing a method that can be implemented using functionality provided in the Object class.
• When the code is using methods in the generic class that don't depend on the type parameter. For example, List.size or List.clear. In fact, Class<?> is so often used because most of the methods in Class<T> do not depend on T.

Consider the following method, printList:

public static void printList(List<Object> list) {
    for (Object elem : list)
        System.out.println(elem + " ");
    System.out.println();
}

The goal of printList is to print a list of any type, but it fails to achieve that goal — it prints only a list of Object instances; it cannot print List<Integer>, List<String>, List<Double>, and so on, because they are not subtypes of List<Object>. To write a generic printList method, use List<?>:

public static void printList(List<?> list) {
    for (Object elem: list)
        System.out.print(elem + " ");
    System.out.println();
}

Because for any concrete type A, List<A> is a subtype of List<?>, you can use printList to print a list of any type:

List<Integer> li = Arrays.asList(1, 2, 3);
List<String>  ls = Arrays.asList("one", "two", "three");
printList(li);
printList(ls);

---

Note: The Arrays.asList method is used in examples throughout this lesson. This static factory method converts the specified array and returns a fixed-size list.

---

It's important to note that List<Object> and List<?> are not the same. You can insert an Object, or any subtype of Object, into a List<Object>. But you can only insert null into a List<?>. The Guidelines for Wildcard Use section has more information on how to determine what kind of wildcard, if any, should be used in a given situation.

Wildcards and Subtyping

As described in Generics, Inheritance, and Subtypes, generic classes or interfaces are not related merely because there is a relationship between their types. However, you can use wildcards to create a relationship between generic classes or interfaces.

Given the following two regular (non-generic) classes:

class A { /* ... */ }
class B extends A { /* ... */ }

It would be reasonable to write the following code:

B b = new B();
A a = b;

This example shows that inheritance of regular classes follows this rule of subtyping: class B is a subtype of class A if B extends A. This rule does not apply to generic types:

List<B> lb = new ArrayList<>();
List<A> la = lb;   // compile-time error

Given that Integer is a subtype of Number, what is the relationship between List<Integer> and List<Number>?
The common parent is List<?>.
Although Integer is a subtype of Number, List<Integer> is not a subtype of List<Number> and, in fact, these two types are not related. The common parent of List<Number> and List<Integer> is List<?>.
In order to create a relationship between these classes so that the code can access Number's methods through List<Integer>'s elements, use an upper bounded wildcard:

List<? extends Integer> intList = new ArrayList<>();
List<? extends Number>  numList = intList;  // OK. List<? extends Integer> is a subtype of List<? extends Number>

Because Integer is a subtype of Number, and numList is a list of Number objects, a relationship now exists between intList (a list of Integer objects) and numList. The following diagram shows the relationships between several List classes declared with both upper and lower bounded wildcards.
A hierarchy of several generic List class declarations.

Type Erasure

Type will be translated during compiling time by Compiler.

Generics were introduced to the Java language to provide tighter type checks at compile time and to support generic programming. To implement generics, the Java compiler applies type erasure to:

• Replace all type parameters in generic types with their bounds or Object if the type parameters are unbounded. The produced bytecode, therefore, contains only ordinary classes, interfaces, and methods.
• Insert type casts if necessary to preserve type safety.
• Generate bridge methods to preserve polymorphism in extended generic types.

Type erasure ensures that no new classes are created for parameterized types; consequently, generics incur no runtime overhead.

Restrictions on Generics

To use Java generics effectively, you must consider the following restrictions:

• Cannot Instantiate Generic Types with Primitive Types
• Cannot Create Instances of Type Parameters
• Cannot Declare Static Fields Whose Types are Type Parameters
• Cannot Use Casts or instanceof With Parameterized Types
• Cannot Create Arrays of Parameterized Types
• Cannot Create, Catch, or Throw Objects of Parameterized Types
• Cannot Overload a Method Where the Formal Parameter Types of Each Overload Erase to the Same Raw Type

Details at: https://docs.oracle.com/javase/tutorial/java/generics/restrictions.html

Note:

Pair<int, char> p = new Pair<>(8, 'a');  // compile-time error , cannot use primitive type

Pair<Integer, Character> p = new Pair<>(8, 'a'); // Okay

Quiz



Write a generic method to count the number of elements in a collection that have a specific property (for example, odd integers, prime numbers, palindromes).

Answer:

public final class Algorithm {
    public static <T> int countIf(Collection<T> c, UnaryPredicate<T> p) {

        int count = 0;
        for (T elem : c)
            if (p.test(elem))
                ++count;
        return count;
    }
}


where the generic UnaryPredicate interface is defined as follows:

public interface UnaryPredicate<T> {
    public boolean test(T obj);
}


For example, the following program counts the number of odd integers in an integer list:

import java.util.*;

class OddPredicate implements UnaryPredicate<Integer> {
    public boolean test(Integer i) { return i % 2 != 0; }
}

public class Test {
    public static void main(String[] args) {
        Collection<Integer> ci = Arrays.asList(1, 2, 3, 4);
        int count = Algorithm.countIf(ci, new OddPredicate());
        System.out.println("Number of odd integers = " + count);
    }
}


The program prints:

Number of odd integers = 2



Will the following class compile? If not, why?

public final class Algorithm {
    public static <T> T max(T x, T y) {
        return x > y ? x : y;
    }
}


Answer: No. The greater than (>) operator applies only to primitive numeric types.

Write a generic method to exchange the positions of two different elements in an array.

Answer:

public final class Algorithm {
    public static <T> void swap(T[] a, int i, int j) {
        T temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}



If the compiler erases all type parameters at compile time, why should you use generics?

Answer: You should use generics because:

The Java compiler enforces tighter type checks on generic code at compile time.
Generics support programming types as parameters.
Generics enable you to implement generic algorithms.


What is the following class converted to after type erasure?

public class Pair<K, V> {

    public Pair(K key, V value) {
        this.key = key;
        this.value = value;
    }

    public K getKey(); { return key; }
    public V getValue(); { return value; }

    public void setKey(K key)     { this.key = key; }
    public void setValue(V value) { this.value = value; }

    private K key;
    private V value;
}


Answer:

public class Pair {

    public Pair(Object key, Object value) {
        this.key = key;
        this.value = value;
    }

    public Object getKey()   { return key; }
    public Object getValue() { return value; }

    public void setKey(Object key)     { this.key = key; }
    public void setValue(Object value) { this.value = value; }

    private Object key;
    private Object value;
}



What is the following method converted to after type erasure?

public static <T extends Comparable<T>>
    int findFirstGreaterThan(T[] at, T elem) {
    // ...
}


Answer:

public static int findFirstGreaterThan(Comparable[] at, Comparable elem) {
    // ...
    }



Will the following method compile? If not, why?

public static void print(List<? extends Number> list) {
    for (Number n : list)
        System.out.print(n + " ");
    System.out.println();
}


Answer: Yes. 

Write a generic method to find the maximal element in the range [begin, end) of a list.

Answer:

import java.util.*;

public final class Algorithm {
    public static <T extends Object & Comparable<? super T>>
        T max(List<? extends T> list, int begin, int end) {

        T maxElem = list.get(begin);

        for (++begin; begin < end; ++begin)
            if (maxElem.compareTo(list.get(begin)) < 0)
                maxElem = list.get(begin);
        return maxElem;
    }
}



Will the following class compile? If not, why?

public class Singleton<T> {

    public static T getInstance() {
        if (instance == null)
            instance = new Singleton<T>();

        return instance;
    }

    private static T instance = null;
}


Answer: No. You cannot create a static field of the type parameter T. 

Given the following classes:

class Shape { /* ... */ }
class Circle extends Shape { /* ... */ }
class Rectangle extends Shape { /* ... */ }

class Node<T> { /* ... */ }


Will the following code compile? If not, why?

Node<Circle> nc = new Node<>();
Node<Shape>  ns = nc;


Answer: No. Because Node<Circle> is not a subtype of Node<Shape>. 

Consider this class:

class Node<T> implements Comparable<T> {
    public int compareTo(T obj) { /* ... */ }
    // ...
}


Will the following code compile? If not, why?

Answer: Yes.

Node<String> node = new Node<>();
Comparable<String> comp = node;



How do you invoke the following method to find the first integer in a list that is relatively prime to a list of specified integers?

public static <T>
    int findFirst(List<T> list, int begin, int end, UnaryPredicate<T> p)


Note that two integers a and b are relatively prime if gcd(a, b) = 1, where gcd is short for greatest common divisor.

Answer:

import java.util.*;

public final class Algorithm {

    public static <T>
        int findFirst(List<T> list, int begin, int end, UnaryPredicate<T> p) {

        for (; begin < end; ++begin)
            if (p.test(list.get(begin)))
                return begin;
        return -1;
    }

    // x > 0 and y > 0
    public static int gcd(int x, int y) {
        for (int r; (r = x % y) != 0; x = y, y = r) { }
            return y;
    }
}


The generic UnaryPredicate interface is defined as follows:

public interface UnaryPredicate<T> {
    public boolean test(T obj);
}


The following program tests the findFirst method:

import java.util.*;

class RelativelyPrimePredicate implements UnaryPredicate<Integer> {
    public RelativelyPrimePredicate(Collection<Integer> c) {
        this.c = c;
    }

    public boolean test(Integer x) {
        for (Integer i : c)
            if (Algorithm.gcd(x, i) != 1)
                return false;

        return c.size() > 0;
    }

    private Collection<Integer> c;
}

public class Test {
    public static void main(String[] args) throws Exception {

        List<Integer> li = Arrays.asList(3, 4, 6, 8, 11, 15, 28, 32);
        Collection<Integer> c = Arrays.asList(7, 18, 19, 25);
        UnaryPredicate<Integer> p = new RelativelyPrimePredicate(c);

        int i = ALgorithm.findFirst(li, 0, li.size(), p);

        if (i != -1) {
            System.out.print(li.get(i) + " is relatively prime to ");
            for (Integer k : c)
                System.out.print(k + " ");
            System.out.println();
        }
    }
}


The program prints:

11 is relatively prime to 7 18 19 25