13.3 PARAMETERIZED CLASSES IN JAVA

13.3 PARAMETERIZED CLASSES IN JAVA

As was mentioned in the introduction, Java container classes typically store all items as Object references. Although this keeps the language simple, it does create an extra burden on the programmer who has to remember to cast an item back to its correct type when it is extracted from the container. Forgetting to do so or using an incorrect cast can result in a run-time error caused by the throwing of a ClassCastExeption.

To get around this limitation of Java, an extension to Java has been put forward by Bracha, Odersky, Stoutamire, and Wadler [8, 9]. This extension, known as GJ (for Generic Java), presently comes with its own compiler that can be invoked through two different aliases, gjc and gjcr, the former for the compilation of the user-defined parameterized types and the latter if you also wish to use the GJ version of the java.util package. By invoking gjcr, you can use the generic versions of the Java container classes as opposed to their standard versions. The letter ‘r’ in gjcr stands for "retrofitted", since the container classes in the GJ-supplied java.util package can be thought of as the retrofitted versions of the standard containers.

In what follows, we will first show a simple Java program in which a List is used to store various items. We will show that if the cast used at the time of extracting these items from the list is incorrect, you will get a run-time error. Here is the program:

 
 //ListMixedType.java import java.util.*; class ListMixedType {     public static void main(String[] args) {         List list = new ArrayList();         list.add("one");         list.add("two");         list.add("three");         // list.add(new Integer(4));                              //(A)         ListIterator iter = list.listIterator();         while ( iter.hasNext() )             System.out.println( (String) iter.next() );           //(B)     } } 
 

As you'd expect, this program compiles and runs fine. But if you uncomment the commented out statement in line (A), the program would still compile fine, but now you'd get a run-time error. The source of the error would be the statement in line (B) where we are casting each extracted list item to the String type. The run-time will throw a ClassCastException when it tries to cast an Integer type to a String type for the last item in the list.

Let's now consider the GJ version of this program. In the program shown below, the type List of the previous program becomes the type List<String> in line (C), and the type ArrayList becomes ArrayList<String> in the same line:

 
 //ListGeneric.java import java.util.*; class ListGeneric {     public static void main(String[] args) {         List<String> list = new ArrayList<String>();                   //(C)         list.add("one");         list.add("two");         list.add("three");         // list.add(new Integer(4));                                   //(D)         ListIterator iter = list.listIterator();         while (iter.hasNext())             System.out.println(iter.next());                           //(E)     } } 
 

There are two most important observations to be made about this program: (1) Now we do not have to use a cast when we extract items from the list in line (E); compare line (E) of this program with line (B) of the earlier program. And, (2) If we uncomment the commented out statement in line (D), the error will be trapped at compile time. Both of these are steps in the right direction for writing good code.

The GJ program shown above will not compile with the usual javac compiler, since that compiler knows nothing about parameterized types such as List<String>. You compile this program with the gjcr compiler command. As instructed in the installation documents for the GJ software, the compile command gjcr has to be set up as an alias for executing the class gjc.Main. On the author's Linux machine, the command gjcr is aliased in the following manner:

     alias gjcr 'java -cp ".:/home/kak/gj/classes" gjc.Main    \        -bootclasspath "/home/kak/gj/classes:                  \           /opt/jdk1.3/jdk1.3/jre/lib/rt.jar:                  \           /opt/jdk1.3/jdk1.3/jre/lib/i18n.jar"' 

where all the four lines shown are actually a single line of text in a .cshrc file. As the reader can see, the compilation with gjcr consists of invoking the java application launcher on gjc.Main. Note that in order to find the class Main, you have to supply the classpath, which in the case above, consists of /home/kak/gj/classes, as specified.^[5]

The reader should also take note of the bootclasspath specified in the alias for gjcr. This is needed because you want the system to load the GJ version of the java.util package, as opposed to the version that comes with the standard Java platform. Since the GJ version of this package is in the directory /home/kak/gj/classes/java, the combination of the string /home/kak/gj/classes in the bootclasspath and the package name java.util will ensure that the system will access and load the right thing. The other two pathnames in the bootclasspath are for the JAR files containing the standard Java platform.

13.3.1 Creating Your Own Parameterized Types in Java

To show how you can create your own parameterized types in Java, we will take the reader through the linked list example again. We will first show a LinkedList class; this will be a minimalist version of its implementation in the java.collections package. We will then show its generic version by parameterizing the class header and its implementation. All of the code we show in this section is from a tutorial by Bracha, Odersky, Stoutamire and Wadler [8].

The program shown below first declares two interfaces, Collection and Iterator, in lines (A) and (B), respectively. The former declares the public interface of the LinkedList class and the latter a means to walk though a linked list. The class LinkedList provides implementations for the methods of the interface Collection. The method iterator() of this interface is implemented by creating in line (G) an anonymous class of type Iterator; the anonymous class provides implementations for the methods declared in the interface Iterator. An object whose type is the same as that of the anonymous class is then returned by the method iterator() in line (F).

LinkedList uses the nested class Node for the individual nodes of a linked list. As explained in Chapter 3, if we had to refer to the nested class outside the class LinkedList, we would need to use its full name, which is LinkedList.Node.

Here is the code for the LinkedList class:

 
 //LinkedList.java // code by Bracha, Odersky, Stoutamire, and Wadler interface Collection {                                              //(A)     public void add(Object x);     public Iterator iterator(); }      interface Iterator {                                           //(B)         public Object next();         public boolean hasNext();      }      class NoSuchElementException extends RuntimeException {}       //(C)      class LinkedList implements Collection {                       //(D)          protected class Node {                                     //(E)              Object item;              Node next = null;              Node(Object item) {this.item = item;}         }         protected Node head = null, tail = null;         public LinkedList() {}         public void add(Object item) {             if (head == null) {                 head = new Node(item);                 tail = head;             }             else {                 tail.next = new Node(item);                 tail = tail.next;             }         }         public Iterator iterator() {                                  //(F)             return new Iterator() {                                   //(G)                     protected Node ptr = head;                     public boolean hasNext() {return ptr!= null;}                     public Object next() {                         if ( ptr!= null ) {                             Object item = ptr.item;                             ptr = ptr.next;                             return item;                         } else throw new NoSuchElementException();                     }             };         }      } // end of class LinkedList class Test {     public static void main(String[] args) {         String str = "";         //int list         LinkedList intList = new LinkedList();         intList.add(new Integer(0));         intList.add(new Integer(1));         intList.add(new Integer(2));         Iterator int_it = intList.iterator();         while ( int_it.hasNext())             str += ((Integer) int_it.next()).intValue() + " ";        //(H)         System.out.println(str);               // 0 1 2         //string list         LinkedList stringList = new LinkedList();         stringList.add("zero");         stringList.add("one");         stringList.add("two");         str = "";         Iterator string_it = stringList.iterator();         while (string_it.hasNext())             str += (String) string_it.next() + " ";                   //(I)         System.out.println(str);               // zero one two         // string list treated as int list         // gives rise to run-time exception         // Integer w = (Integer) stringList.iterator().next();        //(J)     } } 
 

You can compile and run this program in the usual manner—that is, by using javac for compilation and java for execution. As was the case in the previous subsection when we used the ArrayList container, if you uncomment the last statement in line (J) above, you'll still be able to compile the program, but you'll get a run-time error.

Shown below is a version of the program that uses parameterized types. It first declares the parameterized interfaces Collection<T> and Iterator<T> in lines (A) and (B), respectively, and then goes on to provide an implementation for the parameterized class LinkedList<T> in line (D). The flow of logic in the program is exactly the same as in the unparameterized version shown before, except that now we do not use casts when extracting items from the list in lines (H) and (I). For a parameterized class, the scope of the parameter is the entire class, excluding static members and static initializers.^[6] So even though the nested class for the nodes of a linked list is named just Node, it inherits the type parameter T from the scope. The full name of the nested class is LinkedList<T>.Node.

 
 //LinkedListGeneric.java // code by Bracha, Odersky, Stoutamire, and Wadler interface Collection<T> {                                    //(A)     public void add(T x);     public Iterator<T> iterator(); } interface Iterator<T> {                                      //(B)     public T next();     public boolean hasNext(); } class NoSuchElementException extends RuntimeException {}     //(C) class LinkedList<T> implements Collection<T> {               //(D)     protected class Node {                                   //(E)         T item;         Node next = null;         Node(T item) {this.item = item;}     }     protected Node head = null, tail = null;     public LinkedList() {}     public void add(T item) {         if (head == null) {            head = new Node(item);            tail = head;         }         else {             tail.next = new Node(item);             tail = tail.next;         }     }     public Iterator<T> iterator() {                          //(F)         return new Iterator<T>() {                           //(G)                 protected Node ptr = head;                 public boolean hasNext() { return ptr != null; }                 public T next() {                     if (ptr != null) {                         T item = ptr.item;                         ptr = ptr.next;                         return item;                     } else throw new NoSuchElementException();                }           };     } } class Test {     public static void main(String[] args) {         String str = "";         //int list         LinkedList<Integer> intList = new LinkedList<Integer>();         intList.add(new Integer(0));         intList.add(new Integer(1));         intList.add(new Integer(2));         Iterator<Integer> int_it = intList.iterator();         while (int_it.hasNext())             str += int_it.next().intValue() + " ";             //(H)         System.out.println(str);                // 0 1 2         //string list         LinkedList<String> stringList = new LinkedList<String>();         stringList.add("zero");         stringList.add("one");         stringList.add("two");         str = "";         Iterator<String> string_it = stringList.iterator();         while (string_it.hasNext())             str += string_it.next() + "";                      //(I)         System.out.println(str);                // zero one two         // string list treated as int list         // gives rise to compile-time error         // Integer w = stringList.iterator().next();           //(J)     } } 
 

Note also that the commented out statement in line (J), if uncommented, will now cause a compile-time error, where the same would have caused a run-time error in the previous version of the program.

You can use the gjcr alias to compile this program, as in the previous subsection. However, since you will not be using any of retrofitted classes in the GJ version of the java.util package, you do not need to specify a bootclasspath. So, you can also use the gjc compiler, which on the author's Linux machine is defined as an alias as follows:

      alias gjc 'java -cp ".:/home/kak/gj/classes" gjc.Main' 

13.3.2 Parameterization of Methods

Continuing with the examples provided by Bracha et al. [8], we will now show how a Java method can be parameterized. This we will do by first showing a max method written using standard Java for determining the maximum value held by a container. Next we will show a GJ version of the same method. Reflecting the organization of the Java collection library, the max method will be defined as a static method for a Collections class for both cases. The method max would obviously need to scan the container, comparing the current item with the previously known maximum value. So we'd need to make available to max a comparison mechanism, which, in the spirit of the Java collection library, could consist of a Comparator object:

 
 //CollectionMax.java // code by Bracha, Odersky, Stoutamire, and Wadler // with inconsequential changes by the author interface Comparator {     public int compare(Object x, Object y); } class IntComparator implements Comparator {     public int compare(Object x, Object y) {         return ((Integer) x).intValue() - ((Integer) y).intValue();     } } class Collections {     public static Object max(Collection xs, Comparator comp) {  //(A)         Iterator it = xs.iterator();         Object max = it.next();         while (it.hasNext()) {             Object next = it.next();             if (comp.compare(max, next) < 0) max = next;         }         return max;     } } class Test {     public static void main(String[] args) {         // int list with int comparator:         LinkedList intList = new LinkedList();                  //(B)         intList.add(new Integer(0));         intList.add(new Integer(10));         Integer max =           (Integer) Collections.max(intList, new IntComparator());         System.out.println("Max value: " + max.intValue());         // string list with int comparator:         LinkedList stringList = new LinkedList();         stringList.add("zero");         stringList.add("one");         // the following will give runtime exception         // String str =         // (String) Collections.max(stringList, new IntComparator());     } } 
 

If this program is in the same directory as a compiled version of the previous LinkedList.java file, you can compile the program with javac and run it with the java tool. If not, you'd need to import java.util package so that the program would have access to the Collection interface required in line (A) and the LinkedList class required in line (B).

We will now show a GJ version of the above code. The program below first declares a parameterized interface Comparator. This is followed by the class IntComparator that implements the interface. Of particular interest to us here is the parameterized method max in the class Collections. Note how the method is parameterized by the incorporation of a type parameter, through <T>, just before the name of the method in line (C).

 
 //CollectionMaxGeneric.java // code by Bracha, Odersky, Stoutamire, and Wadler // with inconsequential changes by the author interface Comparator<T> {     public int compare(Object x, Object y);                  //(A) } class IntComparator implements Comparator<Integer> {         //(B)     public int compare(Object x, Object y) {         return ((Integer) x).intValue() - ((Integer) y).intValue();     } } class Collections {     public static <T> T              max(Collection<T> coll, Comparator<T> comp) {   //(C)         Iterator<T> it = coll.iterator();         T max = it.next();         while (it.hasNext()) {             T next = it.next();             if (comp.compare(max, next) < 0) max = next;         }         return max;     } } class Test {     public static void main(String[] args) {         // int list with int comparator         LinkedList<Integer> intList = new LinkedList<Integer>();         intList.add(new Integer(0));         intList.add(new Integer(1));         Integer m =           Collections.max(intList, new IntComparator());         System.out.println("Max value: " + m); // 1         // string list with int comparator         LinkedList<String> stringList = new LinkedList<String>();         stringList.add("zero");         stringList.add("one");         // the following will give compile time error         // String str =         // Collections.max(stringList, new IntComparator());     } } 
 

An important question concerning parameterized methods is regarding what specific type should be assigned to the type parameter. That this is an issue becomes evident if you compare the header of the method

     public static <T> T max(Collection<T> coll, Comparator<T> comp) 

with the call to the method in the main of Test:

      Integer x = Collections.max(stringList, new IntComparator()); 

Unlike C++ invocation of parameterized methods, there does not appear to be a direct mechanism for T to get instantiated to a specific type by the pattern matching of the method header and the function call. For Java, the type parameters in a parameterized method are set by inference to the smallest type parameter that yields a valid call. To illustrate, the first argument in the invocation of max is a Collection<String> and the second argument a Comparator<Integer>, then, obviously, since there is no type that is a common ancestor of the types String and Integer, the inference will fail, resulting in a compile-time error. On the other hand, if the first argument in the invocation was of type Collection<Integer> and the second of type Comparator<Float>, then the smallest type that is consistent with both would be Number;^[7] the type parameter for the method max would then be set to this value. In other words, the method actually invoked by such a call would have the following signature:

      Number max(Collection<Number> arg1, Comparator<Number> arg2) 

This inferencing mechanism obviously will not work for methods that take no arguments or that are intentionally called with null arguments. The reader is referred to [8] for modifications to the inferencing algorithm to account for such situations.

13.3.3 Constraining the Parameters

Sometimes it becomes necessary to place a constraint on the types that can be bound to a type parameter. Following Bracha et al. [8], we will show an example to illustrate this. The example code consists of first showing an alternative implementation of the Collections.max method for computing the maximum value held by a container. Instead of using a Comparator object, this new implementation depends on the container elements to be of type Comparable.^[8] The example then shows a GJ version of this implementation in which it is necessary to place a constraint on the type parameter in the header of max. We start with an abbreviated implementation of the Integer class and have it implement the Comparable interface.

 
 //Integer.java // code by Bracha, Odersky, Stoutamire, and Wadler // with inconsequential changes by the author import java.util.*; interface Comparable {     public int compareTo(Object that);                 //(A) } class Integer implements Comparable {     private int value;     public Integer(int value) { this.value = value; }     public int intValue() { return value; }     public int compareTo( Integer that ) {             //(B)         return this.value - that.value;      }      public int compareTo(Object that) {               //(C)         return this.compareTo((Integer) that);      }      public String toString() { return "" + value; } } class Collections {     public static Comparable max(Collection coll) {         Iterator it = coll.iterator();         Comparable max = (Comparable) it.next();         while (it.hasNext()) {             Comparable next = (Comparable) it.next();             if (max.compareTo(next) < 0) max = next;         }         return max;     } } class Test {     public static void main( String[] args ) {         // int collection         LinkedList intList = new LinkedList();         intList.add(new Integer(0));         intList.add(new Integer(1));         Integer maxVal = (Integer) Collections.max(intList);         System.out.println("Max value:" + maxVal);     // 1      } } 
 

Note that the implementation had to provide two definitions for the compareTo method: the first in line (B) that actually carries out the comparison between two Integer objects, and the second in line (C) that conforms to the syntax dictated by the Comparable interface in line (A), but actually calls the first definition for comparison.

Shown below is the GJ version of this implementation. Note the syntax in the header of the Collections.max method in line (C). The type parameter is now expressed in the following constrained form:

      <T implements Comparable<T> > 

implying that the method can only be invoked if the inferencing algorithm we mentioned in the previous subsection yields a binding for T that is of type Comparable<T>. Here is the code:

 
 //IntegerGeneric.java // code by Bracha, Odersky, Stoutamire, and Wadler // with inconsequential changes by the author interface Comparable<T> {     public int compareTo(T that);                                 //(A) } class Integer implements Comparable<Integer> {     private int value;     public Integer(int value) {this.value = value;}     public int intValue() { return value; }     public int compareTo(Integer that) {                          //(B)         return this.value - that.value;     }     public String toString() { return "" + value; } } class Collections {     public static <T implements Comparable<T>> T                                    max(Collection<T> coll) {      //(C)         Iterator<T> it = coll.iterator();         T max = it.next();         while (it.hasNext()) {             T next = it.next();             if (max.compareTo(next) < 0) max = next;         }         return max;     } } class Test {     public static void main(String[] args) {         // Integer collection         LinkedList<Integer> list = new LinkedList<Integer>();         list.add(new Integer(0));         list.add(new Integer(1));         Integer x = Collections.max(list);         // boolean collection         LinkedList<Boolean> listBool = new LinkedList<Boolean>();         listBool.add(new Boolean(false));         listBool.add(new Boolean(true));         // Boolean b = Collections.max(listBook);                                      // run-time exception    } } 
 

Note that unlike the standard version of this program shown before, the new Integer class needs only one implementation for the compareTo method shown in line (B); the header of the implementation for this method corresponds to the header in the Comparable<T> interface in line (A). In order to be consistent with the standard version of Integer, you'd still need a version of compareTo that takes an Object argument. This version, known as the bridge method, is automatically created by the GJ compiler. The program shown above can be compiled with the gjc compilation command.

^[5]To help the reader better understand the example syntax shown for aliasing the command gjcr, the downloaded GJ software sits in the directory /home/kak/gj of the author's Linux machine. The directory consists of the following subdirectories: classes, doc, and src. The directory classes consists of the subdirectories com, gj, gjc, and java. The class Main that is supplied to java in the above invocation is in the directory gjc. So the combination of the supplied classpath and the class name gjc.Main helps the system to figure out what exactly to execute by invoking the java command.

^[6]This is necessitated by the fact that the different instances of a class may use different values for the type parameters. The syntax for accessing a static member, therefore, remains the same as before; that is, you do not mention the parameter when accessing a static member of an otherwise parameterized class.

^[7]lThe abstract class Number, defined in the java.lang package, is the superclass of the classes Byte, Double, Float, Integer, Long, and Short.

^[8]The reader will recall from Chapters 4 and 5 that when a type implements the Comparable interface by providing an implementation for the compareTo method of the interface, we say the type possesses a natural order.