12 December 2008

Java and generics

This is a question about how to use Java.

Let's say you abstract the notion of a tree in an interface.

interface Tree {
  public Tree getLeft();
  public Tree getRight();

Now you can implement various types of trees and put the common operations in only one place. But, the interface doesn't quite capture what a tree is, because you don't want mixed trees.

interface Tree<T extends Tree> {
  public T getLeft();
  public T getRight();

Now you can guarantee statically that the children have the same type as the parent:

final class IntTree implements Tree<IntTree> {
  private IntTree L, R;
  private int data;
  public IntTree(IntTree L, int data, IntTree R) {
    this.L = L;
    this.data = data;
    this.R = R;
  @Override public IntTree getLeft() { return L; }
  @Override public IntTree getRight() { return R; }
  public int getData() { return data; }

A utility class that works only for homogeneous trees looks like this:

class Trees<T extends Tree<T>> {
  public int countNodes(T t) {
    if (t == null) return 0;
    return 1 + countNodes(t.getLeft()) + countNodes(t.getRight());

Question: What do I do if I want to have a generic operation that does something special for one type of tree? Usually one would inspect the runtime type, but the following doesn't work.

class TreeProcessor<T extends Tree<T>> {
  public int countOrSum(T t) {
    if (t == null) return 0;
    int result = countOrSum(t.getLeft()) + countOrSum(t.getRight());
    result += t instanceof IntTree? ((IntTree)t).getData() : 1;
    return result;

PS: In my case, the special thing I wanted to do is run some debugging code that computes and prints some information. For "normal operation" there's no need to do anything special, because the operations really are "generic".


rgrig said...

I was explaining this to a friend (Fint) and he quickly found a solution: do "Object s = t;" and then use "s" for the instanceof and casting stuff.

Still, does anyone know why did the designers of Java decide not to compile the code above?

Jim Apple said...


I think you can use t.getClass.isInstance(IntTree())

This has something to do with type erasure and the fact that generics were bolted on after the fact, but I can't remember why.

Radu Grigore said...

For the record: this does compile now (1.7.0_95).

Post a Comment

Note: (1) You need to have third-party cookies enabled in order to comment on Blogger. (2) Better to copy your comment before hitting publish/preview. Blogger sometimes eats comments on the first try, but the second works. Crazy Blogger.