• An Observation:
  • We can treat any object generically using the type Object (since it is an ancestor of all classes) but this isn't "type safe"
• Parameterized Classes:
  • Class/interface declarations can be parameterized
  • Attributes and methods can use the parameterized type as if it were an actual type
• What This Accomplishes:
  • We can tell the compiler what kind of Object is appropriate

• A Common Need:
  • When constructing the parameterized class, you want to restrict the types that can be used as type arguments (i.e., place a bound/limit/restriction on the classes that can be "bound to")
• The Solution:
  • List the parameter name followed by extends, followed by, what are unfortunately called, the bounding types (separated by an &)
• A Notes:
  • The term extends was probably a bad choice since any class that either extends the bounding type or implements the bounding type can be used (which is why there can be more than one)
  • Only one class can be a bounding type and it must appear first in the list; the list can contain multiple interfaces

• Some Terminology and Process Details:
  • Reifiable/Non-Reifiable Types
  • Type Erasure
  • Heap Pollution
• Wildcards:
  • Covariance: ? extends Type
  • Contravariance: ? super Type

• Common Meaning:
  • Making a thing real; bringing a thing into being
• Type Systems:
  • A type is reifiable if information about it is fully available at run-time

• Defined:
  • The replacement of the type parameter in a generic type with its bound (if bounded) or Object (if unbounded)
• Rationale:
  • Byte code was not changed when parameterized classes were introduced
  • Eliminate run-time overhead
• Implications:
  • Type information is not available at run-time (so, for example, parameterized collections are not reifiable)
  • Some limitations must be imposed at compile-time

• Defined:
  • When a variable of a type refers to an object that is not of that type
• Possible Causes:
  • Mixing raw and parameterized types
  • Unchecked casts
  • Type erasure

• Primitive Type or Reference Type?
  • Arrays are reference types
• Reifiable?
  • Arrays are reifiable

Assignment of Elements

    Number[] n = new Number[10];
    
    n[0] = Integer.valueOf(1);  // An Integer "is a" Number
    n[1] = Double.valueOf(1.0); // A Double "is a" Number
  

Assignment of Arrays

    Number[] n = new Number[10];
    Integer[] i = new Integer[5];
    
    // Won't compile because a Number[] "is not a" Integer[]
    i = n;

    // Will compile because an Integer[] "is a" Number[]    
    n = i; 
  

Compile-Time vs. Run-Time

    Number[] n;
    Integer[] i = new Integer[10];
    
    i[0] = Integer.valueOf(5);
    i[1] = Integer.valueOf(6);
    
    n = i;

    // Will compile and run
    n[2] = Integer.valueOf(7);
    
    // Will compile but will throw an ArrayStoreException at run-time
    // to prevent heap pollution
    n[3] = Double.valueOf(7.5);
  

• Conclusions:
  • Because arrays are reifiable reference types, some checks can be performed at run-time
• So?
  • Because parameterized collections are non-reifiable reference types, some behavior must be prevented at compile-time (more on this later)

• An Example:
  • We want to write a Statistics class that can, among other things, find the maximum and minimum of a data set
• A Seemingly Workable Design:
  • Use an Ordered interface to characterize the data
  • Write min() and max() methods that are passed List<Ordered> objects

The Ordered Interface

javaexamples/parameterized/wildcards/v1/Ordered.java

/**
 * The requirements of objects that can be ordered.
 *
 * @author  Prof. David Bernstein, James Madison University
 * @version 1.0
 */
public interface Ordered
{
    /**
     * Compare this object to the given object. Return -1 if this
     * is "less than" other, 0 if they are "equal", and 1 if this 
     * is "greater than" other.
     *
     * @return -1, 0, or 1 as appropriate
     */
    public abstract int compareTo(Ordered other);
}        

The Statistics Class

javaexamples/parameterized/wildcards/v1/Statistics.java

import java.util.*;

/**
 * A utility class for calculating descriptive statistics.
 *
 * @author  Prof. David Bernstein, James Madison University
 * @version 1.0
 */
public class Statistics
{
  /**
   * Find the maximum of some data points.
   *
   * @param data  The data points
   */
  public static Ordered max(List<Ordered> data)
  {
    Ordered max;

    if (data == null || data.size() == 0) 
      throw new IllegalArgumentException();

    if (data.size() == 1) return data.get(0);

    max = data.get(0);        
    for (int i=1; i<data.size(); i++)
    {
      Ordered  current = data.get(i); 
      if (current.compareTo(max) > 0) max = current;
    }
    return max;
  }
}        

• The Problem with this Design:
  • An invocation of max() that is passed a List of objects that implements Ordered (e.g., List<Person> where Person implements Ordered) will not compile because the List class must ensure that its elements are Person objects, not Ordered objects (a type of class invariance)
• What's Needed:
  • A way to relax the restrictions

• Wildcards:
  • ? represents an unknown type
• Upper Bounded Wildcards:
  • Limits the unknown type to be a specialization (or realization) of the bound
• Syntax:
  • ? extends B where B, the upper bound, can be a class or interface (and "extends" means "extends or implements")

• One Interpretation of "Upper Bound":
  • Create a UML class model with Object (the root node) at the top and descendants at lower levels
  • The bound is as far up the tree as you can go
• Another Interpretation of "Upper Bounds":
  • A class defines a set of objects
  • The bound is the largest allowed set/class

A Revised Statistics Class

javaexamples/parameterized/wildcards/v2/Statistics.java

import java.util.*;

/**
 * A utility class for calculating descriptive statistics.
 *
 * @author  Prof. David Bernstein, James Madison University
 * @version 2.0
 */
public class Statistics
{
  /**
   * Find the maximum of some data points.
   *
   * @param data  The data points
   */
  public static Ordered max(List<? extends Ordered> data)
  {
    Ordered max;
    
    if (data == null || data.size() == 0) 
      throw new IllegalArgumentException();

    if (data.size() == 1) return data.get(0);

    max = data.get(0);        
    for (int i=1; i<data.size(); i++)
    {
      Ordered  current = data.get(i); 
      if (current.compareTo(max) > 0) max = current;
    }
    return max;
  }
}        

• Recall:
  • Type erasure makes parameterized collections non-reifiable
• Implication:
  • They are restricted to be "read only" when upper bounded

Mimicking the Array Example with Lists

      List<? extends Number>  n = new ArrayList<Number>();
      List<Integer> i = new ArrayList<Integer>();
      
      i.add(Integer.valueOf(5));
      i.add(Integer.valueOf(6));
      
      // Will compile because Integer "is a" ? extends Number 
      n = i;

      // Can't be checked at run-time because of type erasure
      // so must be prevented at compile time (i.e., won't compile
      // because "the type is not applicable for the argument")
      n.add(Double.valueOf(7.5));
  

• Motivation:
  • The compareTo() method is not type safe because it only ensures that this and other are both Ordered (but not necessarily of the same type)
  • This can be improved by parameterizing Ordered
• Added Benefit:
  • The max() and min() methods can now return an object of appropriate type
• A Complication:
  • The parameterized type of the interface gets more complicated

A Revised Ordered Interface

javaexamples/parameterized/wildcards/v3/Ordered.java

/**
 * The requirements of objects that can be ordered.
 *
 * @author  Prof. David Bernstein, James Madison University
 * @version 3.0
 */
// Note: It can't be <T extends Ordered> because Ordered must have a parameter 
public interface Ordered<T extends Ordered<T>>
{
    /**
     * Compare this object to the given object. Return -1 if this
     * is "less than" other, 0 if they are "equal", and 1 if this 
     * is "greater than" other.
     *
     * @return -1, 0, or 1 as appropriate
     */
    public abstract int compareTo(Ordered<T> other);
}        

A Further Revised Statistics Class

javaexamples/parameterized/wildcards/v3/Statistics.java

import java.util.*;

/**
 * A utility class for calculating descriptive statistics.
 *
 * @author  Prof. David Bernstein, James Madison University
 * @version 3.0
 */
public class Statistics
{
  /**
   * Find the maximum of some data points.
   *
   * @param data  The data points
   */
  public static <T extends Ordered<T>> T max(List<? extends T> data)
  {
    T max;

    if (data == null || data.size() == 0) 
      throw new IllegalArgumentException();

    if (data.size() == 1) return data.get(0);

    max = data.get(0);        
    for (int i=1; i<data.size(); i++)
    {
      T  current = data.get(i); 
      if (current.compareTo(max) > 0) max = current;
    }
    return max;
  }
}
        

• An Example:
  • We want to write a method that populates a collection with the bounding rectangles of some enemies in a video game
• Existing Components:
  • A Rectangle class
  • A Shape interface that is realized by the Rectangle class
• An Adequate Design:
  • Make both the formal and actual parameters List<Rectangle>

The Initial Implementation

  // The method
  public void populateBoundsList(List<Rectangle> bounds)
  {
    // In an appropriate loop
    {
      Rectangle r;

      // Construct the Rectangle

      bounds.add(r);
    }
  }  

  // The invoker
  finder.populateBoundsList(new ArrayList<Rectangle>());
  

• An Issue:
  • An invoker may not need all of the capabilities of the Rectangle class, it may only need the capabilities of the Shape interface
• An Incorrect "Fix":
  • Make the formal parameter a List<Shape>

The Incorrect "Fix"

  // The method
  public void populateBoundsList(List<Shape> bounds)
  {
    // In an appropriate loop
    {
      Rectangle r;

      // Construct the Rectangle

      bounds.add(r);
    }
  }  

  // The new invoker will compile
  finder.populateBoundsList(new ArrayList<Shape>());

  // The old invoker will not compile
  finder.populateBoundsList(new ArrayList<Rectangle>());
  

• A Thought:
  • Use an upper bound wildcard
• An Alternative Incorrect "Fix":
  • Make the formal parameter a List<? extends Shape>

The Incorrect "Fix"

  // The method
  public void populateBoundsList(List<? extends Shape> bounds)
  {
    // In an appropriate loop
    {
      Rectangle r;

      // Construct the Rectangle

      // Won't compile because bounds is "read only" to prevent
      // heap pollution
      bounds.add(r);
    }
  }  

  // The new invoker will compile
  finder.populateBoundsList(new ArrayList<Shape>());

  // The old invoker will compile
  finder.populateBoundsList(new ArrayList<Rectangle>());
  

• What's Needed:
  • A way to indicate that the formal parameter can be an ancestor of the given type
• In Other Words:
  • A lower bounded wildcard

• Lower Bounded Wildcards:
  • Limits the unknown type to be a generalization of the bound
• Syntax:
  • ? super B where B is the lower bound

• One Interpretation of "Lower Bound":
  • Create a UML class model with Object (the root node) at the top and descendants at lower levels
  • The bound is as far down the tree as you can go
• Another Interpretation of "Lower Bounds":
  • A class defines a set of objects
  • The bound is the smallest allowed set/class

The Example Revisited

  // The flexible version of the method
  public void populateBoundsList(List<? super Rectangle> bounds)
  {
    // In an appropriate loop
    {
      Rectangle r;

      // Construct the Rectangle

      bounds.add(r);
    }
  }  

  // The new invoker will compile because it is assured that
  // the elements will implement Shape
  finder.populateBoundsList(new ArrayList<Shape>());

  // The old invoker will compile because it is assured that
  // the elements will be Rectangle objects
  finder.populateBoundsList(new ArrayList<Rectangle>());
  

• Recall:
  • Type erasure makes parameterized collections non-reifiable
• Implication:
  • They are restricted to be "write only" when lower bounded

A Different Version of the Example with Lists

      List<Integer>  i = new ArrayList<Integer>();
      List<Number>   n = new ArrayList<Number>();
      List<? super Integer> other;

      other = i;
      
      // Will compile because i can treat the element as an Integer
      other.add(Integer.valueOf(1));
      
      // Won't compile because the element could be any ancestor
      // of Integer
      Integer i2i = other.get(0);
      Number  i2n = other.get(0);
      
      other = n;
      
      // Will compile because n can treat the element as a Number
      other.add(Integer.valueOf(1));
      
      // Won't compile because the element could be any ancestor
      // of Integer
      Integer n2i = other.get(0);
      Number  n2n = other.get(0);
  

• PECS:
  • From the standpoint of a method that is passed a collection: "producer extends, consumer super"
• Explained:
  • If the collection produces objects of type T (i.e., the method gets objects from the collection) then it can be of type <? extends T> (because it can produce more specialized objects)
  • If the collection consumes objects of type T (i.e., the method adds objects to the collection) then it can be of type <? super T> (because it can consume more generalized objects)