Trees in the Java Collections framework

Discussion in 'Java' started by Joona I Palaste, Jun 8, 2004.

  1. 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 () ------------- 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
     
    Joona I Palaste, Jun 8, 2004
    #1
    1. Advertising

  2. Joona I Palaste wrote:

    > 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
     
    John C. Bollinger, Jun 8, 2004
    #2
    1. Advertising

  3. John C. Bollinger <> scribbled the following:
    > Joona I Palaste wrote:
    >> 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.


    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.

    --
    /-- Joona Palaste () ------------- Finland --------\
    \-- http://www.helsinki.fi/~palaste --------------------- rules! --------/
    "Insanity is to be shared."
    - Tailgunner
     
    Joona I Palaste, Jun 8, 2004
    #3
  4. Joona I Palaste wrote:
    > John C. Bollinger <> scribbled the following:
    >>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.


    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
     
    John C. Bollinger, Jun 8, 2004
    #4
  5. Joona I Palaste

    Neal Gafter Guest

    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.

    Joona I Palaste wrote:
    > 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?
    >
     
    Neal Gafter, Jun 9, 2004
    #5
  6. Joona I Palaste

    Chris Uppal Guest

    Joona I Palaste wrote:

    > 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
     
    Chris Uppal, Jun 9, 2004
    #6
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Doug Poland
    Replies:
    9
    Views:
    748
    VisionSet
    Sep 27, 2003
  2. Pif

    Trees in java

    Pif, Apr 6, 2004, in forum: Java
    Replies:
    1
    Views:
    441
    Manolo
    Apr 6, 2004
  3. David Moskowitz
    Replies:
    3
    Views:
    550
    David Moskowitz
    Feb 23, 2006
  4. jacob navia

    Binary search trees (AVL trees)

    jacob navia, Jan 3, 2010, in forum: C Programming
    Replies:
    34
    Views:
    1,458
    Dann Corbit
    Jan 8, 2010
  5. mutex
    Replies:
    0
    Views:
    222
    mutex
    Jul 27, 2003
Loading...

Share This Page