commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Kief Morris <unknownyaba...@yahoo.com>
Subject Re: [Collections] TreeNode, TreeIterator, IdentityHashSet proposed collections
Date Sun, 31 Mar 2002 11:29:19 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 we're looking at it backwards.

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 turning around the way we've been
approaching this: let's leave TreeNode as it is, and
I'll scrap the guts of my Tree implementations and
replace them with TreeNode. This way TreeNode is
available for those who need to get their hands on the
nodes, and Tree will offer a Collection-based
interface for those who don't. 

Kief


__________________________________________________
Do You Yahoo!?
Yahoo! Greetings - send holiday greetings for Easter, Passover
http://greetings.yahoo.com/

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