Core Java

Generic Programming

Slide navigation: Forward with space bar, → arrow key, or PgDn. Backwards with ← or PgUp.

Understand the advantages of generic programming

Why Generic Programming?

• Generic programming = Writing code that can be reused for objects of many different types.
  • Don't want separate classes to collect String and File objects.
  • The generic ArrayList class can collect instances of both classes.
• Before Java had type parameters, ArrayList used inheritance to be usable with multiple classes.

  public class ArrayList // before type parameters
  {
     private Object[] elementData;
     . . .
     public Object get(int i) { . . . }
     public void add(Object o) { . . . }
  }

• Drawbacks: Casts and lack of compile-time error checking.

  ArrayList files = new ArrayList();
  . . .
  String filename = (String) files.get(0);
  files.add(new File(". . ."));
  

Type Parameters

• Type parameters bring compile-time safety.
• Element type supplied in <...>, like this:

  ArrayList<String> files = new ArrayList<>();
  

• No cast required in get method:

  String filename = files.get(0);
  

• Illegal argument to add caught at compile time:

  files.add(new File(". . .")); // Error
  

Who Wants to Be a Generic Programmer?

• Generic classes such as ArrayList are easy to use.
• It is not so easy to implement ArrayList.
  • The class has to work for all element types.
  • Should it be legal to call addAll to add an ArrayList<Manager> to an ArrayList<Employee>?
  • If so, how do you allow that call and disallow the opposite?
• Three skill levels:
  1. Use existing generic classes.
  2. Understand enough about type parameters to resolve problems.
  3. Write generic classes that others can use.

Define a Simple Generic Class

A Pair<T> Class

public class Pair<T>
{
   private T first;
   private T second;

   public Pair() { first = null; second = null; }
   public Pair(T first, T second) { this.first = first; this.second = second; }

   public T getFirst() { return first; }
   public T getSecond() { return second; }

   public void setFirst(T newValue) { first = newValue; }
   public void setSecond(T newValue) { second = newValue; }
}

Type Variables

• The T in public class Pair<T> is a type variable.
• The type variable is used throughout the class definition:

  private T first;
  

• Instantiate the type like Pair<String>, substituting a type for the variable.
• You can think of the result as an ordinary class with these methods:

  String getFirst()
  String getSecond()
  void setFirst(String)
  void setSecond(String)
  

• A class can have multiple type variables:

  public class Pair<T, U>
  {
     T first;
     U second;
     . . .
  }
  

Define generic methods

Generic Methods

• Generic class = Class with type variables.
• Generic method = Method with type variables:

  class ArrayAlg
  {
     public static <T> T getMiddle(T... a)
     {
        return a[a.length / 2];
     }
  }

• When you call a generic method, the actual type comes before the method name:

  String middle = ArrayAlg.<String>getMiddle("John", "Q.", "Public");
  

• But you rarely have to do that. Usually, the compiler infers the type from the argument types:

  String middle = ArrayAlg.getMiddle("John", "Q.", "Public");
  

• Occasionally, something goes wrong:

  double middle = ArrayAlg.getMiddle(3.14, 17.29, 0);
     // Type mismatch: cannot convert from Number&Comparable<?> to double
  

pair1

Know how to place restrictions on type variables

Bounds for Type Variables

• Sometimes, a type variable cannot be instantiated with arbitrary types:

  class ArrayAlg
  {
     public static <T> T min(T[] a) // almost correct
     {
        if (a == null || a.length == 0) return null;
        T smallest = a[0];
        for (int i = 1; i < a.length; i++)
           if (smallest.compareTo(a[i]) > 0) smallest = a[i];
        return smallest;
     }
  }
  

• How do we know that T has a compareTo method?
• Need to restrict T in the method declaration:

  public static <T extends Comparable> T min(T[] a) ...
  

• Now min can be called with arrays of String, LocalDate, and so on, but not Rectangle.
• Note: Comparable also has a type parameter which we will ignore for a little longer.
• A type variable can have multiple bounds:

  T extends Comparable & Cloneable
  

pair2

Understand how generic code is translated to run on the Java virtual machine

Type Erasure

• The Java virtual machine has no notion of generic types or methods.
• Generic classes and methods turn into ordinary classes and methods.
• Type variables are “erased”, yielding a raw type:

  public class Pair
  {
     private Object first;
     private Object second;
     public Pair(Object first, Object second) { . . . }
     public Object getFirst() { return first; }
     public Object getSecond() { return second; }
     public void setFirst(Object newValue) { first = newValue; }
     public void setSecond(Object newValue) { second = newValue; }
  }

• Raw type is Object or first type bound:

  public class Interval<T extends Comparable & Cloneable>
     // T turns into Comparable
  

Cast Insertion

• The compiler inserts casts when a return type has been erased:

  Pair<Employee> buddies = . . .; Employee buddy = buddies.getFirst();

  ⇒

  Pair buddies = . . .; Employee buddy = (Employee) buddies.getFirst();

• Casts are not needed for erased parameter types:

  buddies.setFirst(buddy); // OK to convert Employee to Object
  

• Exception: Multiple bounds require casts to first bound.

Bridge Methods

• Consider this class:

  class DateInterval extends Pair<LocalDate>
  {
     public void setSecond(LocalDate second)
     {
        if (second.compareTo(getFirst()) >= 0)
           super.setSecond(second);
     }
     . . .
  }

• After erasure:

  class DateInterval extends Pair
  

• Two setSecond methods:

  public void setSecond(LocalDate second) { . . . }
  public void setSecond(Object second) { setSecond((LocalDate) second); }
  

• Second method is needed for polymorphism:

  Pair<LocalDate> pair = new DateInterval();
  pair.setSecond(aDate);
  

Bridge Methods

• Bridge methods can get even stranger:

  class DateInterval extends Pair<LocalDate>
  {
     public LocalDate getSecond() { return (LocalDate) super.getSecond().clone(); }
  . . .
  }

• Two methods:

  LocalDate getSecond() // defined in DateInterval
  Object getSecond() // overrides the method defined in Pair

• You could not do this in Java, but it is legal in the virtual machine.

Calling Legacy Code

• When generics were added to Java, a major goal was to interoperate with legacy code.
• Example: Legacy class Department with methods

  ArrayList getEmployees()
  void addAll(ArrayList employees)
  

• This call generates a warning:

  ArrayList<Employee> newHires = . . .;
  dept.addAll(newHires); 
  

• Remedy: Annotate method with @SuppressWarnings("unchecked")
• In the opposite case, can annotate just the variable holding the returned value:

  @SuppressWarnings("unchecked") ArrayList<Employee> result = dept.getEmployees();
  

Be aware of restrictions and limitations of Java generics

Primitive Types

• Since type variables are erased to Object, they don't work for primitive types.
• Remedy 1: Use wrapper classes.
• Remedy 2: Make added versions for primitive types.
  • More painful than originally thought.
  • java.util.function and java.util.stream have lots of baggage for primitive types.
  • Example: Consumer, IntConsumer, LongConsumer, DoubleConsumer

Runtime Type Inquiry

• instanceof tests only work with raw types:

  if (a instanceof Pair<String>) // Error
  

• Casts with parameterized types give a warning:

  Pair<String> p = (Pair<String>) a;
     // Warning--can only test that a is a Pair

• The getClass method returns the raw type:

  Pair<String> stringPair = . . .;
  Pair<Employee> employeePair = . . .;
  if (stringPair.getClass() == employeePair.getClass()) // they are equal
  

Creating Arrays

• You cannot instantiate arrays of parameterized types:

  Pair<String>[] pairs = new Pair<String>[10]; // Error

• Suppose it worked. After erasure:

  Pair[] pairs = new Pair[10];

• An array remembers its component type so that you can't store an element of the wrong type:

  Object[] objects = pairs;
  objects[0] = "Fred";
     // ArrayStoreException: Can't store a String into a Pair[]
  

• But the array only remembers its raw type:

  objects[0] = new Pair<Integer>(...);
     // No ArrayStoreException
  

• Since arrays of generic types are unsound, they are illegal.

Varargs Warnings

• Consider this simple method with variable arguments:

  public static <T> void addAll(ArrayList<T> list, T... moreElements)
  {
     for (T element : moreElements) list.add(element);
  }

• Suppose method is called with generic type instances:

  ArrayList<Pair<String>> stringPairs = . . .;
  Pair<String> pair1 = . . .;
  Pair<String> pair2 = . . .;
  addAll(stringPairs, pair1, pair2);
  

• The arguments are put into an array!
• Could be unsound if the method returned it or passed it on.
• Remedy: Annotate the method with @SafeVarargs

Instantiating Types

• You cannot instantiate a generic type:

  public Pair() { first = new T(); second = new T(); } // Error
  

• Can remedy by making caller pass a constructor expression:

  Pair<String> p = Pair.makePair(String::new);

• Implementation:

  public static <T> Pair<T> makePair(Supplier<T> constr)
  {
     return new Pair<>(constr.get(), constr.get());
  }
  

• The traditional remedy is reflection:

  public static <T> Pair<T> makePair(Class<T> cl) throws . . .
  {
     return new Pair<>(cl.newInstance(), cl.newInstance());
  }
  

• Called like this:

  Pair<String> p = Pair.makePair(String.class);

Constructing Generic Arrays

• Illegal to have generic new expression for arrays since the component type would be erased.
  • Suppose this was legal:

    public static <T extends Comparable> T[] minmax(T[] a)
    {
       T[] mm = new T[2]; // Error
       . . .
    } 
    

  • Erasure would be:

    public static Comparable[] minmax(Comparable[] a)
    {
       Comparable[] mm = new Comparable[2];
       . . .
    } 
    

  • If you call minmax with a String[] array, you would get a Comparable[] array back!
• If the array is only used internally, can use Object[] array and casts:

  public class ArrayList<E>
  {
     private Object[] elements;
     . . .
     @SuppressWarnings("unchecked") public E get(int n) { return (E) elements[n]; }
     public void set(int n, E e) { elements[n] = e; } // no cast needed
  }
  

Constructing Generic Arrays

• Many APIs want to create generic arrays.
  • Example: toArray method of ArrayList
• If you have an existing array, can use reflection:

  public static <T extends Comparable> T[] minmax(T... a)
  {
     T[] mm = (T[]) Array.newInstance(a.getClass().getComponentType(), 2);
     . . .
  }
  

• That's why there are two toArray methods:

  Object[] toArray()
  T[] toArray(T[] result)

• Modern approach uses constructor expression:

  String[] ss = ArrayAlg.minmax(String[]::new, "Tom", "Dick", "Harry");
  

• Implementation:

  public static <T extends Comparable> T[] minmax(IntFunction<T[]> constr, T... a)
  {
     T[] mm = constr.apply(2);
     . . .
  }
  

Static Contexts

• You cannot use type variables in static fields or methods.
• For example, this doesn't work:

  public class Singleton<T>
  {
     private static T singleInstance; // Error
     public static T getSingleInstance() // Error
     {
        if (singleInstance == null) construct new instance of T
        return singleInstance;
     }
  }
  

• If it was legal, you could declare a Singleton<Random> and a Singleton<Logger>.
• But after erasure, there is only one Singleton class and only one static singleInstance field!

Exceptions

• You cannot throw or catch objects of generic type:

  public class Problem<T> extends Exception { /* . . . */ }
     // Error--can't extend Throwable

• You cannot use a type variable in a catch clause:

  public static <T extends Throwable> void doWork(Class<T> t)
  {
     try { do work }
     catch (T e) // Error--can't catch type variable
     { Logger.global.info("It didn't work"); }
  }

• It is ok to use type variables in exception specifications:

  public static <T extends Throwable> void doWork() throws T // OK
  {
     try { do work }
     catch (Throwable realCause)
     {
        t.initCause(realCause);
        throw t;
     }
  }
  

Clashes after Erasure

• You cannot create conditions that lead to name clashes after erasure:

  public class Pair<T>
  {
     public boolean equals(T value) { return first.equals(value) && second.equals(value); }
     . . .
  }
  

• Erased method is boolean equals(Object value), which clashes with the equals method of the Object class!
• More subtle example:

  class Employee implements Comparable<Employee> { . . . }
  class Manager extends Employee implements Comparable<Manager> // Error

• The bridge methods clash:

  public int compareTo(Object other) { return compareTo((Employee) other); }
  public int compareTo(Object other) { return compareTo((Manager) other); }
  

Java 9 News Flash - SafeVarags

• Now SafeVarargs can be applied to private methods:

  @SafeVarargs private <T> void process(T... values)

• Previously, annotation was restricted to static and final methods and constructors.
• Now ok on all methods that can't be overridden.

Understand the interaction between generic types and inheritance

Inheritance and Subtype Relationships

• Manager is a subclass of Employee. Is Pair<Manager> a subclass of Pair<Employee>?
• No subtype relationship between GenericType<Type1> and GenericType<Type2>.
  
  • Necessary for type safety:

    Pair<Manager> managerBuddies = new Pair<>(ceo, cfo);
    Pair<Employee> employeeBuddies = managerBuddies; // illegal, but suppose it wasn't
    employeeBuddies.setFirst(lowlyEmployee);
    

  • Why does it work for arrays?

    Manager[] managerBuddies = { ceo, cfo };
    Employee[] employeeBuddies = managerBuddies; // OK
    employeeBuddies[0] = lowlyEmployee; // ArrayStoreException

Inheritance and Subtype Relationships

• Generic classes can extend or implement other classes:

  public class ArrayList<T> implements List<T>
  

• Raw type is a supertype:

  ArrayList<Manager> bosses = . . .;
  ArrayList rawList = bosses; 
  

  • Is that dangerous? Sure:

    rawList.set(0, new File(". . .")); 
    

  • But no more dangerous than before generics were added to Java.

Wildcard Types

• Wildcard types allow type variance:

  Pair<? extends Employee> pair;

• Can hold a Pair<Employee> or Pair<Manager>.
• Useful to implement methods that work for different kinds of pairs:

  public static void printBuddies(Pair<? extends Employee> pair)
  {
     Employee first = pair.getFirst();
     Employee second = pair.getSecond();
     System.out.println(first.getName() + " and " + second.getName() + " are buddies.");
  }

Use ? extends for Producers

• The parameter Pair<? extends Employee> pair produces data.
• The method reads data from the pair.
• You can't store anything into a Pair<? extends Employee> variable:

  Pair<Manager> managerBuddies = new Pair<>(ceo, cfo);
  Pair<? extends Employee> wildcardBuddies = managerBuddies; // OK
  wildcardBuddies.setFirst(lowlyEmployee); // compile-time error
  

• The Pair<? extends Employee> methods look like this:

  ? extends Employee getFirst()
  void setFirst(? extends Employee)

Supertype Bounds

• Supertype bound: ? super Manager
• Use for pairs that consume data:

  public static void minmaxBonus(Manager[] a, Pair<? super Manager> result)
  {
     . . .
     result.setFirst(min);
     result.setSecond(max);
  }
  

• The Pair<? super Manager methods look like this:

  ? super Manager getFirst()
  void setFirst(? super Manager)

• PECS: Producer extend, consumer super.

Complex Wildcards

• Generic Comparable interface:

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

• Let's use it in min:

  public static <T extends Comparable<T>> T min(T[] a)

• Works fine with String which implements the Comparable<String> interface.
• But it doesn't work with a LocalDate array!
  • LocalDate implements ChronoLocalDate
  • ChronoLocalDate extends Comparable<ChronoLocalDate>
  • LocalDate does not implement Comparable<LocalDate>
• Remedy:

  public static <T extends Comparable<? super T>> T min(T[] a) . . .

Unbounded Wildcards

• Can you do anything with the Pair<?> type?

  ? getFirst()
  void setFirst(?)
  

• Here is an example:

  public static boolean hasNulls(Pair<?> p)
  {
     return p.getFirst() == null || p.getSecond() == null;
  }

• Could have used a generic method:

  public static <T> boolean hasNulls(Pair<T> p)

• But the wildcard looks nicer.

Wildcard Capture

• Write a method that swaps the elements of a pair:

  public static void swap(Pair<?> p)

• The obvious approach doesn't work:

  ? t = p.getFirst(); // Error
  p.setFirst(p.getSecond());
  p.setSecond(t);
  

• Define helper method:

  public static <T> void swapHelper(Pair<T> p)
  {
     T t = p.getFirst();
     p.setFirst(p.getSecond());
     p.setSecond(t);
  }

• Call helper method:

  public static void swap(Pair<?> p) { swapHelper(p); }
  

• We don't know what ? is, but it is a definite type that can be “captured” in the call <definite type>swapHelper.

pairs3

Work with reflection and generic types.

The Generic Class Class

• Class is a generic type.
• String.class is an instance of Class<String>
• Class<T> has some methods with type parameters:

  T newInstance()
  T cast(Object obj)
  T[] getEnumConstants()
  Class<? super T> getSuperclass()
  Constructor<T> getConstructor(Class<?>... parameterTypes)
  Constructor<T> getDeclaredConstructor(Class<?>... parameterTypes)

• Can be useful for type matching:

  public static <T> Pair<T> makePair(Class<T> cl) throws . . .
  {
     return new Pair<>(cl.newInstance(), cl.newInstance());
  }
  

• Called like this:

  Pair<String> p = Pair.makePair(String.class);

Generic Type Information in the Virtual Machine

• Erased types have some faint memory of their origin.
• Raw Pair knows it came from generic Pair<T> class.
• Consider this method:

  public static <T extends Comparable<? super T>> T min(T[] a)

• The Method object of its erasure knows:
  • The generic method has a type parameter called T
  • The type parameter has a subtype bound that is itself a generic type.
  • The bounding type has a wildcard parameter.
  • The wildcard parameter has a supertype bound.
• The java.lang.reflect.Type interface has subinterfaces to analyze generic types at runtime.

genericReflection