commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Stephen Colebourne" <scolebou...@eurobell.co.uk>
Subject Re: [Collections][Submit] TreeNode and friends
Date Sat, 25 May 2002 10:57:28 GMT
From: Jack, Paul <pjack@sfaf.org>
> Some Feedback:
>
> TreeNode:
>
> 1.  Should it extend Cloneable?  Some trees might not be
> able to be Cloneable effectively (for instance, a Btree
> backed by a file).

You're probably right. None of the other collections are Clonable in the
interface.

> 2.  I think we should allow setValue to throw an
> UnsupportedOperationException for unmodifiable trees.

Yes, I agree. This probably applies to the children as well.

> 3.  What's the rationale for having equals and hashCode
> be reference based?

The alternative is to compare both the value and children of that node. But
in comparing the children, each child node will compare its value and
children and so on. This would be potentially very expensive. Its also how
JDOM does its equals method.

> 4.  Must tree iterators be depth-first?  The ordered
> traversal for a heap tree isn't depth-first.

No, but depth first is the one I needed ;-)  There are two possibilities
here,
a) Add extra methods for different iteration types
b) Remove the comment that specifies how the iteration is done.

> 5.  How about a valuesIterator method that returns an
> iterator just for the values?

Possible, but again what iteration order? (Actually it is possible as
TreeUtils.valueList(node).iterator();

> TreeNodeIterator
>
> 1.  What's the difference between getParentNode() and
> nextNode().getParentNode()?

None. I've mused over whether TreeIterator really exists or not. I'm open to
removing it if no use can be found for it. However in its current
implementation it could have a previousNode() method added.

> Other Thoughts
>
> 1.  A BinaryTreeNode implementation with convenient
> getLeftChild() and getRightChild() methods.
> 2.  Would it be possible for BinaryTreeNode to somehow
> have a balance() method that could be overridden to
> provide various balancing algorithms?  So then we
> could implement, for instance, RedBlackNode or
> AVLNode.
> 3.  Along these lines, it would be supersexy to
> provide a SortedMap implementation that could be
> backed by any BinaryTreeNode implementation.

I did Physics as a degree, not computer science, so I have no experience in
the area of BinaryTrees/BTree/maps backed by a tree/RedBlack/AVL. However,
the tree API in collections should allow for these things. At the moment I
think I would be comfortable coding the interface but not the
implementation, unless I can copy it from somewhere!

>From your description, it would seem that BinaryTreeNode is a new interface
that is a subinterface of TreeNode with getLeftChild(), getRightChild() and
balance(). RedBlackTreeNode and AVLTreeNode would then implement
BinaryTreeNode.

Stephen





--
To unsubscribe, e-mail:   <mailto:commons-dev-unsubscribe@jakarta.apache.org>
For additional commands, e-mail: <mailto:commons-dev-help@jakarta.apache.org>


Mime
View raw message