You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@commons.apache.org by Stephen Colebourne <sc...@eurobell.co.uk> on 2002/04/01 01:18:06 UTC
Re: [Collections] TreeNode, TreeIterator, IdentityHashSet proposed collections
> > Thus my TreeNode class
> > corresponds most closely
> > to the TreeEntry class of yours, not Tree.
>
> Which suggests the right approach to take is to leave TreeNode as it is,
and consider whether to make an implementation of Tree that uses TreeNode
for its guts.
This was kind of where I was heading. What if the keys in your
implementation became TreeNodes?
public interface Tree extends Map {
// Map methods are used to set/get the values
/** Set value on a node */
put(node, value)
/** Get value from node */
get(node)
/** remove from parent */
remove(node)
/** Get all the tree nodes */
keySet()
/** Get all the values */
values()
// additional Tree methods amend the tree structure
/** Get the root node */
getRootNode()
/** add child */
add(parentNode, childNode, value)
...
}
Internally, Tree would hold TreeEntry objects. Each TreeEntry would have the
node as the key and the value as the value. Would this style of interface
work for you? (It involves no change to TreeNode)
Stephen
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Collections] TreeNode, TreeIterator, IdentityHashSet proposed collections
Posted by Kief Morris <un...@yahoo.com>.
> > Which suggests the right approach to take is to
> leave TreeNode as it is,
> and consider whether to make an implementation of
> Tree that uses TreeNode
> for its guts.
>
> This was kind of where I was heading. What if the
> keys in your
> implementation became TreeNodes?
I'm not sure I see the point? I think TreeNode ought
to simply replace TreeEntry. A basic implementation of
Tree would just provide a Collection-based interface
(in the general sense of the word, not the Java sense)
for accessing TreeNodes, no use of keys.
For my application which uses keys, I would subclass
TreeNode to include a key field. The key-based tree
should be an extension of the non-key-based tree (as
James Strachan suggested). But there's no reason to
use keys in the base implementation.
Let me explain why am I using a keyed Map. My
application stores a tree structure in a database, a
hierarchy of topics under which content items can be
posted (think Yahoo directory). When I build my tree,
I use the primary key field from the table as the key,
and I link children and parents based on a references
(i.e. a self-referencing parent_id field in the
table). HTML links for navigating the directory use
this ID to identify the node in the directory, so
being able to do a Tree.get(id) to get the node is
convenient.
I'll start drafting up some code for this.
Kief
__________________________________________________
Do You Yahoo!?
Yahoo! Greetings - send holiday greetings for Easter, Passover
http://greetings.yahoo.com/
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Collections] TreeNode, TreeIterator, IdentityHashSet proposed collections
Posted by Stephen Colebourne <sc...@eurobell.co.uk>.
From: Kief Morris <ki...@bitbull.com>
> Stephen Colebourne typed the following on 12:17 AM 4/7/2002 +0100
> >I have tweaked our two sets of interfaces tonight to produce a
combination
> >that starts to hang together. I don't think I lost any functionality, but
> >they are only the interfaces at the moment. See what you think at
>
> Stephen, my personal situation right now is keeping me from getting into
> this. Why don't you go ahead with submitting TreeNode and related stuff,
> and when I get some more time (probably a few months) I'll dig back into
> this. Sorry to lame out on you.
>
> Kief
OK. I will proceed with implementing the interfaces previously posted. I
will then post the full Tree implementation for wider commons review.
Stephen
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Collections] TreeNode, TreeIterator, IdentityHashSet
proposed collections
Posted by Kief Morris <ki...@bitbull.com>.
Stephen Colebourne typed the following on 12:17 AM 4/7/2002 +0100
>I have tweaked our two sets of interfaces tonight to produce a combination
>that starts to hang together. I don't think I lost any functionality, but
>they are only the interfaces at the moment. See what you think at
Stephen, my personal situation right now is keeping me from getting into
this. Why don't you go ahead with submitting TreeNode and related stuff,
and when I get some more time (probably a few months) I'll dig back into
this. Sorry to lame out on you.
Kief
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Collections] TreeNode, TreeIterator, IdentityHashSet proposed collections
Posted by Stephen Colebourne <sc...@eurobell.co.uk>.
> >Related to this is the question of hashCode and equals methods. (The
other
> >type of collection is a Set, which needs a hashCode). So far, my view is
to
> >use the == check for equals and the identity hashCode (ie. don't
implement
> >either method).
>
> These sounds better than the alternatives you examined and rejected. Have
> you looked at how the Sun or other commons collections implement these?
List and Map both perform equals() by looping around all their contents
comparing values. As I said before, a value only comparison won't do for
TreeNode because it ignores the structure. (Something different might be
possible for Tree, because the keys enable quick access to the whole tree).
> >...we should really
> >have a better toString() implementation anyway - more collections like -
> >including a list of the children.
>
> Yes, I agree the overhead of reflection isn't appropriate for toString.
Maybe
> cache the string value (list of children), and update it when new children
are
> added? Each node could maintain a string list of its children, and when it
> changes it, trigger its parent to do the same.
I think even that is more than we need, how about
TreeNode[x children,value=y]
as a format for TreeNode's toString()?
I have tweaked our two sets of interfaces tonight to produce a combination
that starts to hang together. I don't think I lost any functionality, but
they are only the interfaces at the moment. See what you think at
http://www.scolebourne.eurobell.co.uk/Tree1.zip
Stephen
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Collections] TreeNode, TreeIterator, IdentityHashSet
proposed collections
Posted by Kief Morris <ki...@bitbull.com>.
Sorry for the delay in responding, too much going on outside the coding life.
Stephen Colebourne typed the following on 12:49 AM 4/2/2002 +0100
>> I would suggest it would be better to keep the list
>> holding the children better hidden from the user.
>> Children can be added and removed with methods such as
>> TreeNode.addChild() and TreeNode.removeChild().
>True, provided you only go down one level. By hiding the created child node,
>you cannot add any children to it, which is a bit of a problem.
...
>> A List or Collection of children can be returned from
>> TreeNode, but should be a defensive copy of the
>> internal list.
>I disagree. A dead copy means less to implement, but means we end up adding
>all the List methods to TreeNode. I would suggest that by using a live list
>of children we enable applications to use the full interface of List to
>manipulate that list of children, such as subList() and retainAll() that
>wouldn't be available otherwise. Having an addChild(TreeNode) method on
>TreeNode may well be a good idea for ease of use however.
OK, I'm still uncomfortable with the design, but I see the reasons for it. Having
both the internal nuts and bolts interface of TreeNode and the smooth locked-down
interface of Tree available sounds better and better the more I understand the
practicalities of your approach.
>Related to this is the question of hashCode and equals methods. (The other
>type of collection is a Set, which needs a hashCode). So far, my view is to
>use the == check for equals and the identity hashCode (ie. don't implement
>either method).
These sounds better than the alternatives you examined and rejected. Have
you looked at how the Sun or other commons collections implement these?
>> A question, in ArrayTreeNode.toString() you use a
>> method called Reflection.getShortenedClassName(),
>> which I don't have anywhere in my system (using JDK
>> 1.3). Where does this come from?
>
>Another of my utilities is a set of reflection utilities. In this case the
>code got the class name minus the package name (which ironically doesn't use
>reflection!). Its available on joda.org if you want it, but we should really
>have a better toString() implementation anyway - more collections like -
>including a list of the children.
Yes, I agree the overhead of reflection isn't appropriate for toString. Maybe
cache the string value (list of children), and update it when new children are
added? Each node could maintain a string list of its children, and when it
changes it, trigger its parent to do the same.
Kief
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Collections] TreeNode, TreeIterator, IdentityHashSet proposed collections
Posted by Stephen Colebourne <sc...@eurobell.co.uk>.
> It looks like ArrayTreeNode expects users to access
> and manipulate the children of a node by returning a
> List from getChildren(), which users then use to add,
> delete, and access the child nodes. I don't think this
> follows best practices as seen in the java.util
> collections and other commons collections.
Bear in mind the design was a combination of the swing TreeNode and
MutableTreeNode classes. Merge those two and add collections and you get my
TreeNode.
> I would suggest it would be better to keep the list
> holding the children better hidden from the user.
> Children can be added and removed with methods such as
> TreeNode.addChild() and TreeNode.removeChild(). This
> gives different implementations more flexibility in
> how they store children.
True, provided you only go down one level. By hiding the created child node,
you cannot add any children to it, which is a bit of a problem.
> Where your inner class TreeArrayList now has to check
> that the object passed in implements the appropriate
> interface, instead TreeNode.addChild() could simply
> take that interface as a parameter type and not take
> Object, simplifying the code. TreeArrayList can be
> dispensed with entirely, the methods implemented from
> TreeNode would be able to enforce needed requirements,
> such as setting the parent node.
>
> A List or Collection of children can be returned from
> TreeNode, but should be a defensive copy of the
> internal list.
I disagree. A dead copy means less to implement, but means we end up adding
all the List methods to TreeNode. I would suggest that by using a live list
of children we enable applications to use the full interface of List to
manipulate that list of children, such as subList() and retainAll() that
wouldn't be available otherwise. Having an addChild(TreeNode) method on
TreeNode may well be a good idea for ease of use however.
> It would be useful to add a method
> which returns an Iterator for the children of the
> node.
Don't we get this by having the children as a list? No need to duplicate.
> Also, the current implementation requires manual
> creation of TreeNodes by user code. I would suggest
> having methods which take an Object value parameter,
> and handle TreeNode construction internally. In fact,
> I would make these the default methods, with
> Node-handling methods separately named. e.g.:
This could work, but only if the addChild(Object value) method returned the
TreeNode it had created (otherwise you can't add children to it). But
addChild return TreeNode seems a little odd - maybe the name addChildValue
makes more sense? And my view would be that once you expose TreeNode as a
public interface, the default methods should refer to TreeNode.
> A final suggestion, the base interface TreeNode could
> assume that Collections rather than Lists are used
> internally to store children, to allow a lighter
> implementation for applications which don't care about
> ordering. This would just mean removing the
> getChild(int index) method.
Maybe. The trouble is that we would lose the nice extra methods on List for
manipulations. A ListTreeNode subclass could be written, but there would
then be no guarantees that the children added were ListTreeNodes, and the
getParent method would return TreeNode not ListTreeNode. For my current use
of trees, I only use iterators to access the tree, so a collection would be
fine. In the future, I expect index access to be significant which could be
a hassle.
Related to this is the question of hashCode and equals methods. (The other
type of collection is a Set, which needs a hashCode). So far, my view is to
use the == check for equals and the identity hashCode (ie. don't implement
either method). The alternatives are to return equals/hashcode based on the
value, or to traverse the tree to build a composite equals/hashcode. The
former strikes me as too weak - two nodes are not equal just because their
values are equal, because that ignores the children. The latter could
involve some very lengthy calculations, and doesn't strike me as practical.
This would appear to rule out a Set implementation as an alternative to
List. Given that, it seems to me that an ordered list of children isn't a
big overhead, yet gives many benefits.
> A question, in ArrayTreeNode.toString() you use a
> method called Reflection.getShortenedClassName(),
> which I don't have anywhere in my system (using JDK
> 1.3). Where does this come from?
Another of my utilities is a set of reflection utilities. In this case the
code got the class name minus the package name (which ironically doesn't use
reflection!). Its available on joda.org if you want it, but we should really
have a better toString() implementation anyway - more collections like -
including a list of the children.
I need to grab some sleep now, so I won't go into your API just now.
Stephen
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>
Re: [Collections] TreeNode, TreeIterator, IdentityHashSet proposed collections
Posted by Kief Morris <un...@yahoo.com>.
Stephen, I have some questions/suggestions on your
TreeNode implementation.
It looks like ArrayTreeNode expects users to access
and manipulate the children of a node by returning a
List from getChildren(), which users then use to add,
delete, and access the child nodes. I don't think this
follows best practices as seen in the java.util
collections and other commons collections.
I would suggest it would be better to keep the list
holding the children better hidden from the user.
Children can be added and removed with methods such as
TreeNode.addChild() and TreeNode.removeChild(). This
gives different implementations more flexibility in
how they store children.
Where your inner class TreeArrayList now has to check
that the object passed in implements the appropriate
interface, instead TreeNode.addChild() could simply
take that interface as a parameter type and not take
Object, simplifying the code. TreeArrayList can be
dispensed with entirely, the methods implemented from
TreeNode would be able to enforce needed requirements,
such as setting the parent node.
A List or Collection of children can be returned from
TreeNode, but should be a defensive copy of the
internal list. It would be useful to add a method
which returns an Iterator for the children of the
node.
Also, the current implementation requires manual
creation of TreeNodes by user code. I would suggest
having methods which take an Object value parameter,
and handle TreeNode construction internally. In fact,
I would make these the default methods, with
Node-handling methods separately named. e.g.:
/**
* Add a value to this node's list of children. A
* TreeNode is automatically created and its parent
* set.
* @return Whether the child List was changed.
*/
boolean addChild(Object);
/**
* Add a child Node to this node's list of children.
Its
* parent is automatically set, if it had a different
parent
* previously it is removed from the old parent's list
* of children.
* @return Whether the child List was changed.
*/
boolean addChildNode(TreeNode.Internal);
A final suggestion, the base interface TreeNode could
assume that Collections rather than Lists are used
internally to store children, to allow a lighter
implementation for applications which don't care about
ordering. This would just mean removing the
getChild(int index) method.
A question, in ArrayTreeNode.toString() you use a
method called Reflection.getShortenedClassName(),
which I don't have anywhere in my system (using JDK
1.3). Where does this come from?
Here's my suggested TreeNode:
public interface TreeNode {
/**
* Get the parent of this node
* @return the object that is the parent of this node
*/
TreeNode getParent();
/**
* Add a value to this node's list of
children. A
* TreeNode is automatically created and its
parent
* set.
* @return Whether the child List was changed.
*/
boolean addChild(Object value);
/**
* Add a child Node to this node's list of
children. Its
* parent is automatically set, if it had a
different parent
* previously it is removed from the old
parent's list
* of children.
* @return Whether the child List was changed.
*/
boolean addChildNode(TreeNode.Internal node);
/**
* Remove the first child whose value equals the
supplied object.
* @return Whether the child List was changed.
*/
boolean removeChild(Object value);
/**
* Remove a child node from this node's list of
children.
* @return Whether the child List was changed.
*/
boolean removeChildNode(TreeNode.Internal node);
/**
* Get the child values of this node
* @return an iterator for the child node values.
*/
Iterator children();
/**
* Get the nodes which are children of this node.
* @return an iterator for the child nodes.
*/
Iterator childNodes();
/**
* Returns a Collection of the child values.
Modifying this
* collection will not modify the internal
structure of the
* parent TreeNode.
*/
Collection getChildCollection();
/**
* Returns a Collection of the child nodes.
Modifying this
* collection will not modify the internal
structure of the
* parent TreeNode unless the parent value is
changed.
*/
Collection getChildNodeCollection();
/**
* Get a tree iterator from this node, returns
TreeNodes for
* everything in the subtree below the current
node. Does not
* include the node itself.
* Traversal is depth first.
* @return the tree iterator
*/
Iterator subtree();
/**
* Is this a root node (has no parent)
* @return true if no parent
*/
boolean isRoot();
/**
* Is this a leaf node (has no children)
* @return true if no children
*/
boolean isLeaf();
/**
* Get the user object of this node
* @return the user object value
*/
Object getValue();
/**
* Set the user object of this node
* @param object the new user object value
*/
void setValue(Object object);
/**
* TreeNode implementors should implement
TreeNode.Internal
* instead of just TreeNode. This interface hides the
public
* but unsafe setParent method
*/
public interface Internal extends TreeNode {
/**
* Set the parent of this node
* @param node the new parent node
*/
void setParent(TreeNode node);
}
}
__________________________________________________
Do You Yahoo!?
Yahoo! Greetings - send holiday greetings for Easter, Passover
http://greetings.yahoo.com/
--
To unsubscribe, e-mail: <ma...@jakarta.apache.org>
For additional commands, e-mail: <ma...@jakarta.apache.org>