Course Map

Agenda

• To understand the objective of generic programming
• To be able to implement generic classes and methods
• To understand the execution of generic methods in the virtual machine
• To know the limitations of generic programming in Java
• To understand the relationship between generic types and inheritance
• To learn how to constrain type variables

Type Variables

Generics is essentially the ability to have type parameters on your type.
They are also called parameterized types or parametric polymorphism.

• Generic programming: creation of programming constructs that can be used with many different types
  • In Java, achieved with inheritance or with type variables
• For example:
  • Type variables: Java's ArrayList (e.g. ArrayList<String>)
  • Inheritance: LinkedList implemented to store objects of any class
• Generic class: declared with a type variable E
• The type variable denotes the element type:

  public class ArrayList<E> // could use "ElementType" instead of E
  {
     public ArrayList() { . . . }
     public void add(E element) { . . . }
     . . .
  }

Hiding Variability with Generic Programming

Instantiating Classes with Type Variables

• Can be instantiated with class or interface types

  ArrayList<BankAccount>
  ArrayList<Measurable>

• Cannot use a primitive type as a type variable

  ArrayList<double> // Wrong!

• Use corresponding wrapper class instead

  ArrayList<Double>

Instantiating Type Variables in Methods

• Supplied type replaces type variable in class interface
• Example: add in ArrayList<BankAccount> has type variable E replaced with BankAccount:

  public void add(BankAccount element)

• Contrast with LinkedList.add:

  public void add(Object element)

Type Variables Increase Safety

• Type variables make generic code safer and easier to read
  • Impossible to add a String into an ArrayList<BankAccount>
  • Can add a String into a LinkedList intended to hold bank accounts

    ArrayList<BankAccount> accounts1 = new ArrayList<BankAccount>();
    LinkedList accounts2 = new LinkedList(); // Should hold BankAccount objects
    accounts1.add("my savings"); // Compile-time error
    accounts2.add("my savings"); // Not detected at compile time
    . . .
    BankAccount account = (BankAccount) accounts2.getFirst(); // Run-time error

Syntax 22.1: Instantiating a Generic Class

GenericClassName<Type1, Type2, . . .>

ArrayList<BankAccount>
HashMap<String, Integer>

Self Check

1. The standard library provides a class HashMap<K, V> with key type K and value type V. Declare a hash map that maps strings to integers.
2. The binary search tree  is an example of generic programming because you can use it with any classes that implement the Comparable interface. Does it achieve genericity through inheritance or type variables?

Answers

1. HashMap<String, Integer>
2. It uses inheritance.

Implementing Generic Classes

• Example: simple generic class that stores pairs of objects

  Pair<String, BankAccount> result
        = new Pair<String, BankAccount>("Harry Hacker", harrysChecking);

• The getFirst and getSecond retrieve first and second values of pair

  String name = result.getFirst();
  BankAccount account = result.getSecond();

• Example of use: return two values at the same time (method returns a Pair)
• Generic Pair class requires two type variables

  public class Pair<T, S>

Good Type Variable Names

Class Pair

public class Pair<T, S>
{
   public Pair(T firstElement, S secondElement)
   {
      first = firstElement;
      second = secondElement;
   }

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

   private T first;
   private S second;
}

Turning LinkedList into a Generic Class

public class LinkedList<E>
{
   . . .
   public E removeFirst()
   {
      if (first == null)
         throw new NoSuchElementException();
      E element = first.data;
      first = first.next;
      return element;
   }
   . . .
   private Node first;

   private class Node
   {
      public E data;
      public Node next;
   }
}

Implementing Generic Classes

• Use type E when you receive, return, or store an element object
• Complexities arise only when your data structure uses helper classes
• If helpers are inner classes, no need to do anything special
• Helper types defined outside generic class need to become generic classes too
  public class ListNode<E>
  

Syntax: Defining a Generic Class

accessSpecifier class GenericClassName<TypeVariable1, TypeVariable2, . . .>
{
   constructors
   methods
   fields
}

public class Pair<T, S>
{
   . . .
}

File LinkedList.java

File ListIterator.java

File ListTester.java

Output

Dick
Harry
Juliet
Nina
Tom

Self Check

3. How would you use the generic Pair class to construct a pair of strings "Hello" and "World"?
4. What change was made to the ListIterator interface, and why was that change necessary?

Answers

3. new Pair<String, String>("Hello", "World")
4. ListIterator<E> is now a generic type. Its interface depends on the element type of the linked list.

Generic Methods

• Generic method: method with a type variable
• Can be defined inside ordinary and generic classes
• A regular (non-generic) method:

  /**
     Prints all elements in an array of strings.
     @param a the array to print
  */
  public static void print(String[] a)
  {
     for (String e : a)
        System.out.print(e + " ");
     System.out.println();
  }

• What if we want to print an array of Rectangle objects instead?

  public static <E> void print(E[] a)
  {
     for (E e : a)
        System.out.print(e + " ");
     System.out.println();
  }

Generic Methods

• When calling a generic method, you need not instantiate the type variables:

  Rectangle[] rectangles = . . .;
  ArrayUtil.print(rectangles);

• The compiler deduces that E is Rectangle
• You can also define generic methods that are not static
• You can even have generic methods in generic classes
• Cannot replace type variables with primitive types
  e.g.: cannot use the generic print method to print an array of type int[]

Syntax: Defining a Generic Method

modifiers <TypeVariable1, TypeVariable2, . . .> returnType methodName(parameters)
{
   body
}

public static <E> void print(E[] a)
{
   . . .
}

Self Check

5. Exactly what does the generic print method print when you pass an array of BankAccount objects containing two bank accounts with zero balances?
6. Is the getFirst method of the Pair class a generic method?

Answers

5. The output depends on the definition of the toString method in the BankAccount class.
6. No–the method has no type parameters. It is an ordinary method in a generic class.

Constraining Type Variables

• Type variables can be constrained with bounds

  public static <E extends Comparable> E min(E[] a)
  {
     E smallest = a[0];
     for (int i = 1; i < a.length; i++)
        if (a[i].compareTo(smallest) < 0) smallest = a[i];
     return smallest;
  }

• Can call min with a String[] array but not with a Rectangle[] array
• Comparable bound necessary for calling compareTo
  Otherwise, min method would not have compiled

Constraining Type Variables

• Very occasionally, you need to supply two or more type bounds

  <E extends Comparable & Cloneable>

• extends, when applied to type variables, actually means "extends or implements"
• The bounds can be either classes or interfaces
• Type variable can be replaced with a class or interface type

Self Check

7. Declare a generic BinarySearchTree class with an appropriate type variable.
8. Modify the min method to compute the minimum of an array of elements that implements the Measurable interface.

Answers

7. public class BinarySearchTree<E extends Comparable>

8. public static <E extends Measurable> E min(E[] a)
   {
      E smallest = a[0];
      for (int i = 1; i < a.length; i++)
         if (a[i].getMeasure() < smallest.getMeasure()) < 0)
            smallest = a[i];
      return smallest;
   }

Wildcard Types

Wildcard Types

• public void addAll(LinkedList<? extends E> other)
  {
     ListIterator<E> iter = other.listIterator();
     while (iter.hasNext()) add(iter.next());
  }

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

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

• static void reverse(List<?> list)

  You can think of that declaration as a shorthand for

  static <T> void reverse(List<T> list)

Raw Types

• The virtual machine works with raw types, not with generic classes
• The raw type of a generic type is obtained by erasing the type variables
• For example, generic class Pair<T, S> turns into the following raw class:

  public class Pair
  {
     public Pair(Object firstElement, Object secondElement)
     {
        first = firstElement;
        second = secondElement;
     }
     public Object getFirst() { return first; }
     public Object getSecond() { return second; }
  
     private Object first;
     private Object second;
  }

Raw Types

• Same process is applied to generic methods:

  public static Comparable min(Comparable[] a)
  {
     Comparable smallest = a[0];
     for (int i = 1; i < a.length; i++)
        if (a[i].compareTo(smallest) < 0) smallest = a[i];
     return smallest;
  }

• Knowing about raw types helps you understand limitations of Java generics
• For example, you cannot replace type variables with primitive types
• To interface with legacy code, you can convert between generic and raw types
• You can not construct new objects of a generic type (new E()) or an array of generic type (new E[])
• You can not use type variables to define static fields, static methods, or static inner classes.
  However you can make static methods and static inner classes as generic ones by adding type parameters.

Self Check

9. What is the erasure of the print method below?

   public static <E> void print(E[] a)
   {
      for (E e : a)
         System.out.print(e + " ");
      System.out.println();
   }

10. What is the raw type of the LinkedList<E> class?

Answers

9. public static void print(Object[] a)
   {
      for (Object e : a)
         System.out.print(e + " ");
      System.out.println();
   }

10. The LinkedList class.