Re: Generics Problem
On Mon, 25 Aug 2008, Jim Garrison wrote:
I'm stuck trying to implement a recursive data structure (a simple tree)
using generics, where at each level of the tree the contained object
type may vary. For example, the object contained at the root node of
the tree is of type A; all of A's children contain objects of type B.
All children of any second-level object (i.e. all the grandchildren of
A) are of type C.
How about this:
import java.util.List ;
// your A, B, C classes
class A {}
class B {}
class C {}
public interface Node<V, N extends Node> {
public V getValue() ;
public List<N> getChildren() ;
public void addChild(N child) ;
}
// this class exists only to be a bottom type for the structure
// instances will never exist
class NullNode implements Node<Object, NullNode> {
public Object getValue() {return null ;}
public List<NullNode> getChildren() {return null ;}
public void addChild(NullNode child) {}
}
interface RootNode extends Node<A, Node<B, Node<C, NullNode>>> {
}
Your trouble is then the visitor.
Or rather, it isn't. The solution is actually very simple - you implement
the Visitor pattern as it is originally and properly defined, by putting
the traversal code inside Node. Define a visitor interface:
interface Visitor {
public void visit(Node n) ;
}
Add a method 'accept' to Node:
public interface Node<V, N extends Node> {
// skip existing methods
public void accept(Visitor v) ;
}
Which you can implement like this:
class NodeImpl<V, N extends Node> implements Node<V, N> {
// skip other methods
public void accept(Visitor v) {
v.visit(this) ;
for (N child: getChildren()) {
child.accept(v) ;
}
}
}
And you're done.
This compiles without warnings for me, even with -Xlint, but i'm on 1.5
right now - i'm not 100% sure this will be okay under 1.6. There are
unbound references to Node in there, which i'm surprised are okay. You
might need to declare visit as taking Node<?, ?>. That certainly works
under 1.5.
tom
--
It's almost over now.