Tree design with generics

[bengali]

Hi,

i would like to model a Tree in Java but with the requirements that
every node
of the same level is of the same Node subtype.

I thought about using Generics and therefore, i designed the following
abstract class:

/**
* <T> child node type
* <K> parent node type
*/

class abstract Node<T extends Node,K extends Node> {

private K parentNode;

private List<T> childrenNodes = new ArrayList<T>();

public void addChildNode(T node) {
childrenNodes.add(node);
}

public K getParent() {
return parentNode;
}

public abstract void retrieveChildrenNodes();

}

with for instance the following implementation:

public FirstLevel extends Node<SecondLevel,Node> {
private Object firstLevelAttribute;

public void retrieveChildrenNodes() {
...
}

}

public SecondLevel extends Node<ThirdLevel,FirstLevel) {
....
public void retrieveChildrenNodes() {
...
}

}

But of course, i am unable to express the following:
- That the type of the parent node can be of Void type (for the
root node for instance).
- I get warnings for the FirstLevel class since one of its
parameterized types is
of type Node without parameterized types.
(public FirstLevel extends Node<SecondLevel,Node> )

Having parameterized type would allow me if given a node of a level
to navigate in the tree between children and parent without casting
and work with the specific attributes
of each level type.

So if you have any idea how i could model this data structure...

Thanks,
bengalister.

 

[lscharen]

So if you have any idea how i could model this data structure...

You won't be able to do this for a general Tree unless you restrict
the depth of the Tree to d level and then create d different Node
types like you've shown. If this is appropriate for your application,
I'd say keep going in the direction you've chose.

If you have so support a tree of arbitrary depth, I would create a
Tree data structure with an extra array that holds the class type of
the first element inserted at a particular depth. Any subsequent
insertions would just need to check against this list. Once a level
of the tree has no nodes, clear the list.

If you know the exact class types that each level requires, then just
set the type list statically. Something like the following (off the
top of my head, so don't expect this to compile cleanly)


public class MyTree<E>
{
public class TreeNode
{
protected int depth;
protected E element;
protected ListNode parent;
protected List<E> children = new ArrayList<E>();

public TreeNode( E element, TreeNode parent, int depth )
{
this.element = element;
this.depth = depth;
this.parent = parent;
}
}

private List<Class<E>> depthTypeList = new ArrayList<Class<E>>();
private List<Integer> depthCount = new ArrayList<Integer>();
private TreeNode<E> root = null;
int maxDepth = 0;

public void insert( E element )
{
if ( root == null )
{
root = new TreeNode( element, null, 0 );
depthTypeList.add( element.class );
depthCount.add( 1 );
maxDepth++;
return;
}

// Use whatever method to find the insertion point
// for the new element.
TreeNode parent = findInsertionPoint( element );
TreeNode child = new TreeNode( element, parent, parent.depth +
1 );

// Check against the class type. If this is the first element
// at this level, extend the lists
if ( child.depth > depthTypeList.size() )
{
depthTypeList.add( element.class );
depthCount.add( 1 );
maxDepth++;
}
else
{
Class<E> type = depthTypeList.get( child.depth );
if ( type != null && !element.class.equals( type ))
throw new Exception( "Invalid type for depth " +
child.depth );

depthCount.set( child.depth, depthCount.get( child.depth ) +
1 );
}
}

public void remove( E element )
{
// Find the TreeNode that contains the element
TreeNode node = findTreeNode( element );

// Break the links
node.parent.children.remove( node );
node.parent = null;

// Update the class information
int depth = node.depth;
int count = depthCount.get( depth );

depthCount.set( depth, count - 1 );

// If this was the last node from a row, clear the class type
if ( count == 1 )
depthTypeList.set( depth, null );
}
}

 

[Patricia Shanahan]

Hi,

i would like to model a Tree in Java but with the requirements that
every node
of the same level is of the same Node subtype.

Why encode the level in the type? It seems more like an attribute.

public SecondLevel extends Node<ThirdLevel,FirstLevel) {
...
public void retrieveChildrenNodes() {
...
}
....
But of course, i am unable to express the following:
- That the type of the parent node can be of Void type (for the
root node for instance).

Why not simply a Node reference with value null?

Patricia