commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Kief Morris <k...@bitbull.com>
Subject Re: [Collections] TreeNode, TreeIterator, IdentityHashSet proposed collections
Date Sun, 31 Mar 2002 13:50:53 GMT
> I realised that the
> difference between the two implementations is that
> you view the tree as a
> single 'flat' collection (which happens to be a
> Map). Tree allows the values
> to be added and removed without ever really knowing
> much about the structure
> of the tree.  In fact, you go further in your
> Javadoc and say that
> applications shouldn't know about the TreeEntry
> class.
> 
> My implementation views the tree as nodes - there is
> no single object
> representing the whole tree. 

Yes, I noticed this difference too, but had been thinking we could reconcile them. As I think
on it some more, maybe it's not such an easy thing.

My rationale was to make Tree look and act the same as other collections: users would add
and retrieve Objects without having to know anything about how the Tree code maintains the
relationships. This is consistent with other collections in commons and the JDK. 

For example, a linked list works very much the way a tree does, but the JDK LinkedList class
hides its Entry code in an inner class. Users can't call a next() or prev() method, they have
to use the standard List methods, and don't generally know it's any different from an Array
backed List.

Once I looked at it this way, using a Map to represent the Tree internally made sense. It
keeps the implementation fairly small, using only a single Map, rather than a full List for
every node. 

I was thinking that modifying my approach to achieve the functionality of yours would be simple,
just remove the requirement for a named key for each node, and use Lists for the internal
representation of nodes so order can be preserved. My key, flawed, assumption was that hiding
the entry structure from the user was the "right" thing to do, and wouldn't lose any real
functionality: given a node, you can easily retrieve its children by using a get(Object parent)
method. A node's parent could be gotten with getParent(Object node). The internal code would
handle the details, and the user wouldn't suffer any more than they do from not being able
to get inside the LinkedList implementation.

The flaw in my thinking is that it assumes each node is a unique object, so internal code
can implement those methods with traversals or map lookups. This works for my application,
and would probably be useful for others too, but I'm sure some people are going to want to
store a single object at more than one place in a tree. But I can't see how to allow this
without exposing the internal nodes, because otherwise there is no way to uniquely indentify
which occurrence of the Object to get children or a parent for.

> 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.

So, TreeNode should be available for users who need the functionality, and Tree implementations
for those who want a Collections-style interface and don't need duplicate node objects. Maybe
Tree should have a less generic name?

I still think my internal-Map implementation is more efficient if users won't need to get
at the internal node structure, but a TreeNode implementation of Tree would be useful for
those who want a container for the Tree but still want to get at nodes.

Kief


--
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