Recursive Type Bounds Revisited
The class MonoNode and the interface IMonoLink<E> are declared in Example 11.3, p. 572, and the class BiNode and the interface IBilink<E> are declared in Example 11.5, p. 574. See also Figure 11.1, p. 574.
class MonoNode<E> implements IMonoLink<E> {
private E data; // Data
private IMonoLink<E> next; // Reference to next node (1)
// …
}
class BiNode<E> extends MonoNode<E> implements IBiLink<E> {
private IBiLink<E> previous; // Reference to previous node (2)
// …
}
Note that the next field has the type IMonoLink<E>, but the previous field has the type IBiLink<E>, and that the type IBiLink<E> is a subtype of the type IMonoLink<E>. This means that when iterating over a linked structure constructed from nodes that implement the IBiLink<E> interface, we have to be careful. The method traverseBinTree() below traverses a binary tree constructed from such nodes. The method prints the data in the nodes. Note that it is necessary to cast the reference value returned by the getNext() method, as shown at (3), from the supertype IMonoLink<E> to the subtype IBiLink<E>.
public static <E> void traverseBinTree(IBiLink<E> root) {
if (root.getPrevious() != null)
traverseBinTree(root.getPrevious());
System.out.print(root.getData() + “, “);
if (root.getNext() != null)
traverseBinTree((IBiLink<E>)root.getNext()); // (3) Cast necessary.
}
Example 11.11 declares a class called RecNode. The header of this class at (1) is declared as follows:
abstract class RecNode<E, T extends RecNode<E, T>>
The class specifies two type parameters: E and T. The type parameter E stands for the type of the data in the node, (2). The type parameter T stands for the type of the next field in the node, (3). It has the upper bound RecNode<E, T>, meaning that T must be a subtype of the bound—that is, of RecNode<E, T>. In other words, the class RecNode can only be parameterized by itself or its subclasses. The two parameters E and T are used in the class for their respective purposes.
Example 11.11 Using Recursive Bounds
abstract class RecNode<E, T extends RecNode<E, T>> { // (1)
private E data; // (2)
private T next; // (3)
RecNode(E data, T next) {
this.data = data;
this.next = next;
}
public void setData(E obj) { data = obj; }
public E getData() { return data; }
public void setNext(T next) { this.next = next; }
public T getNext() { return next; }
@Override public String toString() {
return this.data + (this.next == null ? “” : “, ” + this.next);
}
}
final class RecBiNode<E> extends RecNode<E, RecBiNode<E>> { // (4)
private RecBiNode<E> previous; // Reference to previous node // (5)
RecBiNode(E data, RecBiNode<E> next, RecBiNode<E> previous) {
super(data, next);
this.previous = previous;
}
public void setPrevious(RecBiNode<E> previous) { this.previous = previous; }
public RecBiNode<E> getPrevious() { return this.previous; }
@Override public String toString() {
return (this.previous == null? “” : this.previous + “, “) +
this.getData() + (this.getNext() == null? “” : “, ” + this.getNext());
}
}
Example 11.11 declares another class, called RecBiNode. The header of this class at (4) is declared as follows:
final class RecBiNode<E> extends RecNode<E, RecBiNode<E>>
Note that the class has only one type parameter, E, that represents the data type in the node. The class extends the RecNode class, which is parameterized with the data type E and the type RecBiNode<E> to represent the type of the next field in the superclass RecNode. The class RecBiNode also declares a previous field of type RecBiNode<E> at (5), and the corresponding getter and setter methods. The upshot of this class declaration is that, for a node of type RecBiNode<E>, both the next and the previous fields have the same type as a node of this class. The traversal method can now be written without using any casts, passing it a node of the subtype RecBiNode<E>:
public static <E> void traverseBinTree(RecBiNode<E> root) { // (2)
if (root.getPrevious() != null)
traverseBinTree(root.getPrevious());
System.out.print(root.getData() + “, “);
if (root.getNext() != null)
traverseBinTree(root.getNext()); // No cast necessary!
}
The class declaration at (1) in Example 11.11 uses what is called a recursive type bound in its constraint T extends RecNode<E,T>. New subtypes of the class RecNode can be implemented using this idiom, and the type of the next field will be the same as the subtype, as in the case of the subtype RecBiNode<E>. Recursive type bounds allow subclasses to use their own type, avoiding explicit casts to convert from the superclass.
Earlier in this chapter we saw an example of a recursive type bound defined by the constraint T extends Comparable<T>. Another example of a recursive type bound is the declaration of the Enum<E extends Enum<E>> class in the Java standard library.
Leave a Reply