Daniel: Notes on Generic Types in Java

source: http://www.ntu.edu.sg/home/ehchua/programming/java/JavaGeneric.html
yet another insignificant Programming Notes
by ehchua

In generics, instead of pass arguments, we pass type information (inside the angle brackets <>).
The primary usage of generics is to abstract over types when working with collections (Read "The Collection Framework" if necessary).

For example, the class ArrayList is designed (by the class designer) to take a generics type <E> as follows:

public class ArrayList<E> implements List<E> .... {
   // Constructor
   public ArraList() { ...... }

   // Public methods
   public boolean add(E e) { ...... }
   public void add(int index, E element) { ...... }
   public boolean addAll(int index, Collection<? extends E> c)
   public abstract E get(int index) { ...... }
   public E remove(int index)
   .......
}

downcast problem - not type-safe

.Suppose, for example, you wish to define an ArrayList of String. In theadd(Object) operation, the String will be upcasted implicitly into Object by the compiler. During retrieval, however, it is the programmer's responsibility to downcast the Object back to an String explicitly. If you inadvertently added in a non-String object. the compiler cannot detect the error, but the downcasting will fail at runtime

2.1 Generics Classes

JDK 1.5 introduces the so-called generics to resolve this problem. Generics allow you to abstract over types. You can design a class with a generic type, and provide the specific type information during the instantiation. The compiler is able to perform the necessary type checking during compile time and ensure that no type-casting error occurs at runtime. This is known as type-safety.

(avoid using Object and Downcasting)

Take a look at the declaration of interface java.util.List<E>:

public interface List<E> extends Collection<E> {
   boolean add(E o);
   void add(int index, E element);
   boolean addAll(Collection<? extends E> c);
   boolean containsAll(Collection<?> c);
   ......
}

<E> is called the formal "type" parameter, which can be used for passing "type" parameters during the actual instantiation.

The mechanism is similar to passing arguments to parameters

Formal Type Parameter Naming Convection (just Naming Convention)

Use an uppercase single-character for formal type parameter. For example,

<E> for an element of a collection;
<T> for type;
<K, V> for key and value.
<N> for number
S,U,V, etc. for 2nd, 3rd, 4th type parameters

Example of Generic Class

In this example, a class called GenericBox, which takes a generic type parameter E, holds a conetent of type E. The constructor, getter and setter work on the parameterized type E. The toString() reveals the actual type of the content.

public class GenericBox<E> {
   // Private variable
   private E content;
 
   // Constructor
   public GenericBox(E content) {
      this.content = content;
   }
 
   public E getContent() {
      return content;
   }
 
   public void setContent(E content) {
      this.content = content;
   }
 
   public String toString() {
      return content + " (" + content.getClass() + ")";
   }
}

In fact, the compiler replaces (compilers job) all reference to parameterized type E with Object, performs the type check, and insert the required downcast operators. For example, the GenericBox is compiled as follows (which is compatible with codes without generics):

(Object + Downcasting + Checking are done by compiler)

Continue with our "type-safe" ArrayList...

Let's return to the MyArrayList example. With the use of generics, we can rewrite our program as follows:

// A dynamically allocated array with generics
public class MyGenericArrayList<E> {
   private int size;     // number of elements
   private Object[] elements;
   
   public MyGenericArrayList() {  // constructor
      elements = new Object[10];  // allocate initial capacity of 10
      size = 0;
   }
   
   public void add(E e) {
      if (size < elements.length) {
         elements[size] = e;
      } else {
         // allocate a larger array and add the element, omitted
      }
      ++size;
   }
   
   public E get(int index) {
      if (index >= size)
         throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
      return (E)elements[index];
   }
   
   public int size() { return size; }
}

Behind the scene, generics are implemented by the Java compiler as a front-end conversion called erasure, which translates or rewrites code that uses generics into non-generic code (to ensure backward compatibility). This conversion erases all generic type information.

2.2 Generic Methods

Methods can be defined with generic types as well (similar to generic class). For example,

public static <E> void ArrayToArrayList(E[] a, ArrayList<E> lst) {
   for (E e : a) lst.add(e);
}

A generic method can declare formal type parameters (e.g. <E>, <K,V>) preceding the return type. The formal type parameters can then be used asplaceholders for return type, method's parameters and local variables within a generic method, for proper type-checking by compiler.

out: lst

2.3 Wildcards

Consider the following lines of codes:

ArrayList<Object> lst = new ArrayList<String>();

It causes a compilation error "incompatible types", as ArrayList<String> is not an ArrayList<Object>.

This error is against our intuition on polymorphism, as we often assign a subclass instance to a superclass reference.

Consider these two statements:

List<String> strLst = new ArrayList<String>();   // 1
List<Object> objLst = strList;                   // 2 - Compilation Error

Line 2 generates a compilation error. But if line 2 succeeds and some arbitrary objects are added into objLst, strLst will get "corrupted" and no longer contains only Strings. (objLst and strLst have the same reference.)

Because of the above, suppose we want to write a method called printList(List<.>) to print the elements of a List. If we define the method asprintList(List<Object> lst), then it can only accept an argument of List<object>, but not List<String> or List<Integer>. For example,

import java.util.*;
public class TestGenericWildcard {
   
   public static void printList(List<Object> lst) {  // accept List of Objects only, 
                                                     // not List of subclasses of object
      for (Object o : lst) System.out.println(o);
   }
   
   public static void main(String[] args) {
      List<Object> objLst = new ArrayList<Object>();
      objLst.add(new Integer(55));
      printList(objLst);   // matches
   
      List<String> strLst = new ArrayList<String>();
      strLst.add("one");
      printList(strLst);  // compilation error
   }
}

Unbounded Wildcard <?>

To resolve this problem, a wildcard (?) is provided in generics, which stands for any unknown type. For example, we can rewrite our printList() as follows to accept a List of any unknown type.

public static void printList(List<?> lst) {
  for (Object o : lst) System.out.println(o);
}

Upperbound Wildcard <? extends type>

The wildcard <? extends type> stands for type and its sub-type. For example,

public static void printList(List<? extends Number> lst) {
  for (Object o : lst) System.out.println(o);
}

List<? extends Number> accepts List of Number and any subtype of Number, e.g., List<Integer> and List<Double>.

Clearly, <?> can be interpreted as <? extends Object>, which is applicable to all Java classes.

Another example,

// List<Number> lst = new ArrayList<Integer>();  // Compilation Error
List<? extends Number> lst = new ArrayList<Integer>();

Lowerbound Wildcard <? super type>

The wildcard <? super type> matches type, as well as its super-type. In other words, it specifies the lower bound.

2.4 Bounded Generics (Generics with Upperbound)

A bounded parameter type is a generic type that specifies a bound for the generic, in the form of <T extends ClassUpperBound>, e.g., <T extends Number> accepts Number and its subclasses (such as Integer and Double).

Example

The method add() takes a type parameter <T extends Number>, which accepts Number and its subclasses (such as Integer and Double).

public class MyMath {
   public static <T extends Number> double add(T first, T second) {
      return first.doubleValue() + second.doubleValue();
   }
 
   public static void main(String[] args) {
      System.out.println(add(55, 66));     // int -> Integer
      System.out.println(add(5.5f, 6.6f)); // float -> Float
      System.out.println(add(5.5, 6.6));   // double -> Double
   }
}

END

Daniel

Pages

Thursday, May 23, 2013

Notes on Generic Types in Java