commons-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Kief Morris <>
Subject Re: [Collections] TreeNode, TreeIterator, IdentityHashSet proposed collections
Date Sun, 31 Mar 2002 13:43:14 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

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

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

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.


Do You Yahoo!?
Yahoo! Greetings - send holiday greetings for Easter, Passover

To unsubscribe, e-mail:   <>
For additional commands, e-mail: <>

View raw message