Trees in the Java Collections framework

[Joona I Palaste]

Trees don't fit in the Java Collections framework, as they require the
objects themselves to know about the collection they are in, namely what
their children are.
In all other collections, the order in which the objects are is either
irrelevant (like in sets) or canonical (like in lists) but in trees,
there may be multiple orders chosen by the user of the collection.
What are possible solutions to this? Making the objects inherit a
"TreeNode" interface won't work as it will prevent the same object from
being in several trees simultaneously. Perhaps using wrapper objects as
the nodes, with references pointing to the actual objects?

--
/-- Joona Palaste ([email protected]) ------------- Finland --------\
\-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
"A bee could, in effect, gather its junk. Llamas (no poor quadripeds) tune
and vow excitedly zooming."
- JIPsoft

 

[John C. Bollinger]

Trees don't fit in the Java Collections framework, as they require the
objects themselves to know about the collection they are in, namely what
their children are.
In all other collections, the order in which the objects are is either
irrelevant (like in sets) or canonical (like in lists) but in trees,
there may be multiple orders chosen by the user of the collection.
What are possible solutions to this? Making the objects inherit a
"TreeNode" interface won't work as it will prevent the same object from
being in several trees simultaneously. Perhaps using wrapper objects as
the nodes, with references pointing to the actual objects?

Collections focus on the elements contained. Trees focus on the data
structure. They are thus not comparable, but they can be used together.
Consider TreeSet: it uses a red-black tree to implement the SortedSet
API. A tree that excludes duplicate elements is effectively a Set, and
perhaps could be a SortedSet. One that permits duplicate elements would
probably be a plain Collection. It just doesn't make sense to try to
formulate Tree as an extension of Collection; it's the wrong abstraction.


John Bollinger
(e-mail address removed)

 

[Joona I Palaste]

Collections focus on the elements contained. Trees focus on the data
structure. They are thus not comparable, but they can be used together.
Consider TreeSet: it uses a red-black tree to implement the SortedSet
API. A tree that excludes duplicate elements is effectively a Set, and
perhaps could be a SortedSet. One that permits duplicate elements would
probably be a plain Collection. It just doesn't make sense to try to
formulate Tree as an extension of Collection; it's the wrong abstraction.

Hmm, I think I see your point. Consider a list collection. The
collection knows how many elements it contains, and which element is at
which position. But if you ask an object contained in the list, it
doesn't know the foggiest about where it is in the list, what its
neighbours are, or whether it is in the list at all.
The similar case would hold for trees as well, except the structure of
a tree is not uniquely defined by the number of contained elements -
which is entirely a property of the collection itself, not of its
elements - but instead can vary greatly.
It is possible to make a tree collection work like the list collection.
You just have to dictate a canonical one-dimensional ordering for the
elements, and have methods such as "move element #a from element #b's
child to element #c's child" or "get all element numbers that are
element #d's children". But for the human programmer, having to
maintain separate knowledge about the numbers, in addition to the
elements they refer to, would be too much work.

 

[John C. Bollinger]

Hmm, I think I see your point. Consider a list collection. The
collection knows how many elements it contains, and which element is at
which position. But if you ask an object contained in the list, it
doesn't know the foggiest about where it is in the list, what its
neighbours are, or whether it is in the list at all.
The similar case would hold for trees as well, except the structure of
a tree is not uniquely defined by the number of contained elements -
which is entirely a property of the collection itself, not of its
elements - but instead can vary greatly.
It is possible to make a tree collection work like the list collection.
You just have to dictate a canonical one-dimensional ordering for the
elements, and have methods such as "move element #a from element #b's
child to element #c's child" or "get all element numbers that are
element #d's children". But for the human programmer, having to
maintain separate knowledge about the numbers, in addition to the
elements they refer to, would be too much work.

It's not really about the work for the programmer, rather it's about the
model. The base Collection interface is an abstraction for a collection
of zero or more objects. The Set interface is an abstraction for those
collections in which an element may not be present more than once. The
List interface is an abstraction for those collections that maintain
their elements in a defined order. What would be the property(-ies)
that a Tree collection would add? That the elements are arranged in a
tree? That doesn't seem to rise to the same level of generality.

Perhaps one way to look at it is to ask how Tree's contracts for the
methods defined in the Collection interface would be distinguished from
other Collections'. If you can't answer that clearly and specifically
then it's a good clue that you're not really defining a new kind of
Collection.

My suggestion would be to forget about making Trees be Collections
themselves, but to instead define one or more methods to provide
Collection views your Trees' elements. You could even make the views
mutable (or at least potentially so), which I think might make for a
very flexible API.


John Bollinger
(e-mail address removed)

 

[Neal Gafter]

java.util.TreeSet and java.util.TreeMap are collections that are build using
trees, and allow the user to define the ordering by supplying a Comparator. But
you don't get to examine or manipulate the internal structure of the tree.

 

[Chris Uppal]

Trees don't fit in the Java Collections framework, as they require the
objects themselves to know about the collection they are in, namely what
their children are.

I don't see any particular problem with this.

A Collection's basic purpose is to be a holder of objects. Some Collections
add extra semantics, for instance Set adds the restriction that objects can't
be in the Collection more than once. Lists' added semantics are that the
elements are in specific /order/, and that each objects has a specific
/position/. In neither case does the extra semantics make then any less valid
as Collections. But to have full access to the extra facilities requires extra
methods, for instance if you just add() and object to a Collection that is
actually a List, then it will be added in a default position (at the end), but
Lists have (extra) methods to allow you to specify a non-default position. In
a similar way, when you remove() an item from a List, that has side-effects as
the list maintains its semantics (in this case changing the indices of any
objects that followed the removed one).

In the case of a Tree, you'd get similar effects. Trees would hold a bunch of
objects, and would add further semantics to "know" about the tree-like
interrelations of the objects. Mutable Trees would have to support add(Object)
and add the object at some default position. I'd probably add it as a new root
of the tree (so the data structure would actually be a Forest rather than a
single-rooted Tree). Similarly remove() would either remove the item's
children too, or would move them up a level in the tree (probably not something
to specify as part of the abstract tree interface, different concrete
implementations would have different strategies here). Obviously, you'd have
other Tree-specific methods to do Tree-flavoured operations like asking for the
children of a node, or the parent, or the collection of roots.

Collections are also iterable, so you'd want a default iterator that traversed
the tree in some canonical order (depth-first, pre-order perhaps). But you'd
probably want extra methods that returned Iterators that traverse the tree in
other orders.

As far as concrete implementations go, I think the main split would be between
Trees that maintained the tree-structure internally, and those that presented a
"view" of an externally defined (pre-existing) tree. E.g. an "internal" tree
class might have one or more Maps as part of its implementation, using them to
record which elements were the parents and children of which other elements.
An "external" tree might be pluggable perhaps, taking an Object that
implemented an interface like:
{
Iterator getRootObjects(); // or maybe answer a Collection ?
Object getParentOf();
Iterator getChildrenOf(); // or maybe answer a Collection ?
}
and using that internally to supply the raw data about the shape and contents
of the tree. "External" trees would probably not be mutable. In fact they'd
just be adaptors, giving a Collection and Tree interfaces to some existing
data-structure like, say, a file system.

-- chris