JavaSwingJTree and TreeModel: TreeModel


TreeModel

Rooted trees

A TreeModel (nearly) represents a data structure (rooted tree) of (nearly arbitrary) Objects (!= null).

For this discussion, all objects in a rooted tree are called nodes.

In a rooted tree, the nodes are linked in a hierarchical fashion. For each node, there exists a set of nodes that are called its children, and the node itself is called their parent. Each node only has a single parent (i.e. may only be a child of one node). The children may in turn have children and so on. Two nodes which have the same parent are called siblings. A node which has children is called an internal node. If the sets of children are ordered, the tree is called an ordered tree.

A path is a list (i.e. ordered) of nodes, each (except the first) being a child of the previous. If two different nodes can be contained in a path of the tree, the first is called an ancestor of the second, the second a descendant of the first (A node may also be considered an ancestor and a descendant of itself, then these definitions become "proper ancestor" and "proper descendant", but I won't use that). No node may be an ancestor of itself (i.e. there can be no circularities in the structure).

There is one distinguished node, the root of the tree, which is not a child of any other node. Each node defines a new rooted tree (the subtree rooted at the node), the tree which only consists of its descendants and itself as the subtree's root.

A forest is a collection of rooted trees. The subtrees rooted at node's children may be considered a forest.

Depending on the actual structure, there may be two kinds of nodes, those that may have child nodes, and those that may not. In TreeModel terminology, the latter are called leaves (It is common to call nodes in general leaves if they have no children (The notion of being "allowed" to have children may not even exist). These are called external nodes here.).

Rooted trees and TreeModel

Except for one important difference, a TreeModel represents an ordered tree whose structure may change with time. The children sets are indexed by the standard zero-based integer indices.

This major difference is that in TreeModel, a node need not have a unique parent. It may be a child of multiple other nodes. This is rarely useful, though, because it doesn't fit together well with dynamic changes, see below. (It is reasonable to assume that there no node may be an ancestor of itself, otherwise there would exist infinite loop paths.) Still, the collection of a node's children remain sets - each node can only be contained once (i.e. there exists a unique index for each node for each parent). Otherwise, TreeModel wouldn't have any similarity to a tree structure any more, and there would not be a way to distinguish these locations unless one resorts to identifying them not only by TreePaths but also by indices, and that is really ugly (indices change all of the time). It would also make things much more complicate (in a real tree structure, one wouldn't even need TreePaths to identify a node) See (#4465854) (with a somewhat silly evaluation, instead of just stating "This is not possibly in a tree structure").

So as a static structure, a TreeModel is a (connected) directed graph which is acyclic with a high probability and which has a total order on all edges that leave an element, a boolean function "leaf" on all nodes that only have incoming edges, and a "root" element; by starting there one can reach all other elements. As a dynamic structure, that concept doesn't work.

As now a node may be contained multiple times in the structure, I use the term location for a specific occurence of a node (Regard the TreeModel as completely expanded in a JTree, then location makes sense).

This possibility isn't very useful, but complicates managing TreeModels at some places.

The tree structure introduced on the collection of objects is external, i.e. it is possible (and common) that the objects don't know or don't know explicitly that they are part of a TreeModel.

In order to be able to work properly with TreeModels (and because there are places where the current JTree implementation requires it), the following constraints should be imposed on the objects in a TreeModel:

Paths and TreePath

A TreePath represents paths starting with the root of the TreeModel. It uniquely identifies a location. It is often used to walk from a given location up towards the root. TreeModel cannot be used for this, as (except for valueForPathChanged) it takes node and not location arguments, and there may be multiple paths to a node. Usually one wants to store locations and not nodes; then TreePaths are used.

A TreePath is implemented as a singly-linked list that can be walked up towards the root. It is immutable.


TreeNode and DefaultTreeModel

(see specifications: TreeNode; DefaultTreeModel)

These have no connection to general TreeModels. They are only mentioned here because by default they are always used, and to make the differences clear.

A TreeNode object actually represents the rooted tree whose root it is. A structure built from TreeNodes is linked internally: The information about children and parent is (logically) stored in the node itself (and the node may be inspected directly) and not introduced externally by a TreeModel.

Thus, a TreeNode may only be contained in one tree structure and, it being a real rooted tree, uniquely defines a location.

TreeNodes (unless specifically implemented otherwise) are (in general) not observable and don't have know anything about firing events etc. They are similar in concept the other classes in java.util (like List, Map), though less thoroughly specified and with a JDK1.1 interface style.

The definition of a leaf in TreeNode is different from the one TreeModel uses: A TreeNode is a leaf iff it does not have any children.

MutableTreeNodes can be structurally modified, which is not possible for a generic TreeModel.

DefaultTreeModel maps a subtree rooted at a certain TreeNode to a TreeModel (which is needed to display the tree structure in a JTree).

DefaultTreeModel cannot possibly know about any changes one makes in the TreeNode structure on its own. You either have to use the (rather limited) methods in DefaultTreeModel to modify the structure, or notify the DefaultTreeModel of occurred changes, thus causing it to fire the events.

DefaultTreeModel is the only provided implementation of TreeModel.


TreeModel query methods

(see also specification)

All query methods take nodes as arguments. A constraint for these arguments is that the caller must have obtained them (directly or indirectly) by inspecting the model or being given them by an event. This allows for creation of nodes only when really needed (see below). Otherwise each method would have to inspect each object whether it is equal to one of those that have not even been created.

Object getRoot()

Access the root node of the TreeModel.

In theory, this method may return null to represent a totally empty tree.

Before 1.4, JTree has assumed that this is not so (One of the first things it does for a new model is to call model.isLeaf(model.getRoot())). So to have TreeModels that should be displayed inJTrees, one had to provide at least a dummy root (which may be made invisible by tree.setRootVisible(false)), or handle null being passed to isLeaf and return true then (or the JTree will try expand 'null').

boolean isLeaf(Object node)

Is the node a leaf (i.e. does it not allow children)?

Even if this method returns false (for a node that may not possibly have any children), it must be possible to invoke getChildCount(node), which then (of course) returns 0.

The main difference for JTree is that leaf nodes cannot be expanded, while non-leaf nodes always can (even if they have no children).

This behaviour is different from TreeNode, where a leaf is a node that has no children. Only TreeNodes that have !getAllowsChildren() may not have children.

DefaultTreeModel maps TreeModel.isLeaf() either to TreeNode.isLeaf() or TreeNode.getAllowsChildren(), usually the latter is preferable, as otherwise every node without children is a leaf, while getAllowsChildren() can be set differently for each TreeNode (for example DefaultMutableTreeNode.setAllowsChildren()).

int getChildCount(Object parent)

The number of children of parent.

This method may be called for leaf nodes, where it must return 0. Thus if one does not want to distinguish between nodes that just have no children and those that cannot have children (as in standard tree algorithms), one can just proceed.

It may be preferable to call isLeaf() before anyway because then the TreeModel doesn't actually have to figure out how many children the parent has.

Object getChild(Object parent, int index)

the child of parent at index.

This call can only be made if either getChildCount(parent) has been made or an event has been received (or some other knowledge about the specific TreeModel) that can guarantee that index is a valid.

Of course this method may not return null as null is not a valid node.

It is reasonable to throw an exception if the index is not valid because the caller definitely has a bug.

int getIndexOfChild(Object parent, Object child)

This method isn't really needed. A TreeModel inspector may as well write an explicit loop. The only real advantage of the method seems to be that it may be a lot faster if the loop is done internally.

Unfortunately this method specification does not state whether child also has to be a child of the parent in order to invoke this method, or even whether child has to be already obtained from the model for the call to be valid. So callers that want to get the index of a child and don't know anything about it have to loop over getChild(), like the following code, instead of using getIndexOfChild(). An implementation of getIndexOfChild() may actually be similar.

public static int getIndexOfChild(TreeModel data, Object parent, Object child)
{
    for (int count = data.getChildCount(parent), i = 0; i < count; i++)
        if (data.getChild(parent, i).equals(child)) // safe because it may not return null.
            return i;
    return -1;
}

DefaultTreeModel assumes that the child at least is a TreeNode, otherwise throws a ClassCastException.

Lazy creation of nodes

TreeModel allows to only create the node objects on demand. The tree structure can only be walked down from the root. The following discussion assumes that the leaf state of node remains the same, if not, you have a dynamic TreeModel, see there.

It is possible to create children for a parent node:

Accessing TreePaths

For static TreeModels, the model itself doesn't have to care about TreePaths at all. If it is dynamic, it needs to create TreePaths for its nodes itself for firing events.

On the other hand, for a client of a TreeModel (in a JTree context), knowledge of a TreePath for a node is much more useful than just knowing the node. JTree methods for expanding, selection, scrolling to etc. locations need the TreePath. If possible, the model should offer a method to get the (or a specific) tree path for a given node. How that is exactly done depends strongly on the model itself. It is easier if the model can map each node to its parent, then one only needs to loop upwards until the root is found and then loop downwards, creating TreePaths by TreePath.pathByAddingChild() on the way.

DefaultTreeModel has getPathToRoot(), but it returns an array, not a TreePath directly.

Examples of static TreeModels

MapTreeModel - builds TreeModel structure from information stored in a Map.

FileTreeModel - reflects a file/directory structure, creates nodes on demand.


(C) 2001-2009 Christian Kaufhold (swing@chka.de)