echopoint.tree
Class DefaultMutableTreeNode<M>

java.lang.Object
  echopoint.tree.DefaultMutableTreeNode<M>

All Implemented Interfaces:

MutableTreeNode<M>, TreeNode, Serializable

public class DefaultMutableTreeNode<M>
extends Object
implements MutableTreeNode<M>

A DefaultMutableTreeNode is a general-purpose node in a tree data structure. A tree node may have at most one parent and 0 or more children. DefaultMutableTreeNode provides operations for examining and modifying a node's parent and children and also operations for examining the tree that the node is a part of. A node's tree is the set of all nodes that can be reached by starting at the node and following all the possible links to parents and children. A node with no parent is the root of its tree; a node with no children is a leaf. A tree may consist of many subtrees, each node acting as the root for its own subtree.

This class provides enumerations for efficiently traversing a tree or subtree in various orders or for following the path between two nodes.

A DefaultMutableTreeNode may also hold a reference to a user object, the use of which is left to the user. Asking a DefaultMutableTreeNode for its string representation with toString() returns the string representation of its user object.

This is not a thread safe class.If you intend to use a DefaultMutableTreeNode (or a tree of TreeNodes) in more than one thread, you need to do your own synchronizing. A good convention to adopt is synchronizing on the root node of a tree.

While DefaultMutableTreeNode implements the MutableTreeNode interface and will allow you to add in any implementation of MutableTreeNode not all of the methods in DefaultMutableTreeNode will be applicable to all MutableTreeNodes implementations. Especially with some of the enumerations that are provided, using some of these methods assumes the DefaultMutableTreeNode contains only DefaultMutableNode instances. All of the TreeNode/MutableTreeNode methods will behave as defined no matter what implementations are added.

Since:

3.0.0b3

Version:

$Id: DefaultMutableTreeNode.java 213 2009-06-03 16:34:13Z sptrakesh $

Author:

Brad Baker, Rakesh Vidyadharan 2009-05-29

See Also:

Serialized Form

Field Summary

protected String	actionCommand this node's action command
protected boolean	allowsChildren true if the node is able to have children
protected Vector<TreeNode>	children Array of children, may be null if this node has no children
static Enumeration<TreeNode>	EMPTY_ENUMERATION An enumeration that is always empty.
protected MutableTreeNode	parent this node's parent, or null if this node has no parent
protected M	userObject optional user object

Constructor Summary

DefaultMutableTreeNode()
Creates a tree node that has no parent and no children, but which allows children.

DefaultMutableTreeNode(M userObject)
Creates a tree node with no parent, no children, but which allows children, and initializes it with the specified user object.

DefaultMutableTreeNode(M userObject, boolean allowsChildren)
Creates a tree node with no parent, no children, initialized with the specified user object, and that allows children only if specified.

Method Summary

void	add(MutableTreeNode newChild) Removes newChild from its parent and makes it a child of this node by adding it to the end of this node's child array.
Enumeration<TreeNode>	breadthFirstEnumeration() Creates and returns an enumeration that traverses the subtree rooted at this node in breadth-first order.
Enumeration<TreeNode>	children() Creates and returns a forward-order enumeration of this node's children.
Enumeration<TreeNode>	depthFirstEnumeration() Creates and returns an enumeration that traverses the subtree rooted at this node in depth-first order.
String	getActionCommand() Returns the Action command string associated with this node
boolean	getAllowsChildren() Returns true if this node is allowed to have children.
TreeNode	getChildAfter(TreeNode aChild) Returns the child in this node's child array that immediately follows aChild, which must be a child of this node.
TreeNode	getChildAt(int index) Returns the child at the specified index in this node's child array.
TreeNode	getChildBefore(TreeNode aChild) Returns the child in this node's child array that immediately precedes aChild, which must be a child of this node.
int	getChildCount() Returns the number of children of this node.
int	getDepth() Returns the depth of the tree rooted at this node -- the longest distance from this node to a leaf.
TreeNode	getFirstChild() Returns this node's first child.
DefaultMutableTreeNode	getFirstLeaf() Finds and returns the first leaf that is a descendant of this node -- either this node or its first child's first leaf.
int	getIndex(TreeNode aChild) Returns the index of the specified child in this node's child array.
TreeNode	getLastChild() Returns this node's last child.
DefaultMutableTreeNode	getLastLeaf() Finds and returns the last leaf that is a descendant of this node -- either this node or its last child's last leaf.
int	getLeafCount() Returns the total number of leaves that are descendants of this node.
int	getLevel() Returns the number of levels above this node -- the distance from the root to this node.
DefaultMutableTreeNode	getNextLeaf() Returns the leaf after this node or null if this node is the last leaf in the tree.
DefaultMutableTreeNode	getNextNode() Returns the node that follows this node in a preorder traversal of this node's tree.
DefaultMutableTreeNode	getNextSibling() Returns the next sibling of this node in the parent's children array.
TreeNode	getParent() Returns this node's parent or null if this node has no parent.
TreeNode[]	getPath() Returns the path from the root, to get to this node.
protected TreeNode[]	getPathToRoot(TreeNode aNode, int depth) Builds the parents of node up to and including the root node, where the original node is the last element in the returned array.
DefaultMutableTreeNode	getPreviousLeaf() Returns the leaf before this node or null if this node is the first leaf in the tree.
DefaultMutableTreeNode	getPreviousNode() Returns the node that precedes this node in a preorder traversal of this node's tree.
DefaultMutableTreeNode	getPreviousSibling() Returns the previous sibling of this node in the parent's children array.
TreeNode	getRoot() Returns the root of the tree that contains this node.
TreeNode	getSharedAncestor(DefaultMutableTreeNode aNode) Returns the nearest common ancestor to this node and aNode.
int	getSiblingCount() Returns the number of siblings of this node.
M	getUserObject()
Object[]	getUserObjectPath() Returns the user object path, from the root, to get to this node.
void	insert(MutableTreeNode newChild, int childIndex) Removes newChild from its present parent (if it has a parent), sets the child's parent to this node, and then adds the child to this node's child array at index childIndex.
boolean	isLeaf() Returns true if this node has no children.
boolean	isNodeAncestor(TreeNode anotherNode) Returns true if anotherNode is an ancestor of this node -- if it is this node, this node's parent, or an ancestor of this node's parent.
boolean	isNodeChild(TreeNode aNode) Returns true if aNode is a child of this node.
boolean	isNodeDescendant(DefaultMutableTreeNode anotherNode) Returns true if anotherNode is a descendant of this node -- if it is this node, one of this node's children, or a descendant of one of this node's children.
boolean	isNodeRelated(DefaultMutableTreeNode aNode) Returns true if and only if aNode is in the same tree as this node.
boolean	isNodeSibling(TreeNode anotherNode) Returns true if anotherNode is a sibling of (has the same parent as) this node.
boolean	isRoot() Returns true if this node is the root of the tree.
Enumeration<TreeNode>	pathFromAncestorEnumeration(TreeNode ancestor) Creates and returns an enumeration that follows the path from ancestor to this node.
Enumeration<TreeNode>	postorderEnumeration() Creates and returns an enumeration that traverses the subtree rooted at this node in postorder.
Enumeration<TreeNode>	preorderEnumeration() Creates and returns an enumeration that traverses the subtree rooted at this node in preorder.
void	remove(int childIndex) Removes the child at the specified index from this node's children and sets that node's parent to null.
void	remove(MutableTreeNode aChild) Removes aChild from this node's child array, giving it a null parent.
void	removeAllChildren() Removes all of this node's children, setting their parents to null.
void	removeFromParent() Removes the subtree rooted at this node from the tree, giving this node a null parent.
void	setActionCommand(String newActionCommand) Sets this node's action command to newActionCommand
void	setAllowsChildren(boolean allows) Determines whether or not this node is allowed to have children.
void	setParent(MutableTreeNode newParent) Sets this node's parent to newParent but does not change the parent's child array.
void	setUserObject(M userObject) Sets the user object for this node to userObject.
String	toString() Returns the result of sending toString() to this node's user object, or null if this node has no user object.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Detail

actionCommand

protected String actionCommand

this node's action command

parent

protected MutableTreeNode parent

this node's parent, or null if this node has no parent

children

protected Vector<TreeNode> children

Array of children, may be null if this node has no children

userObject

protected transient M userObject

optional user object

allowsChildren

protected boolean allowsChildren

true if the node is able to have children

EMPTY_ENUMERATION

public static final Enumeration<TreeNode> EMPTY_ENUMERATION

An enumeration that is always empty. This is used when an enumeration of a leaf node's children is requested.

Constructor Detail

DefaultMutableTreeNode

public DefaultMutableTreeNode()

Creates a tree node that has no parent and no children, but which allows children.

DefaultMutableTreeNode

public DefaultMutableTreeNode(M userObject)

Creates a tree node with no parent, no children, but which allows children, and initializes it with the specified user object.

Parameters:

userObject - an Object provided by the user that constitutes the node's data

DefaultMutableTreeNode

public DefaultMutableTreeNode(M userObject,
                              boolean allowsChildren)

Creates a tree node with no parent, no children, initialized with the specified user object, and that allows children only if specified.

Parameters:

userObject - an Object provided by the user that constitutes the node's data

allowsChildren - if true, the node is allowed to have child nodes -- otherwise, it is always a leaf node

Method Detail

add

public void add(MutableTreeNode newChild)

Removes newChild from its parent and makes it a child of this node by adding it to the end of this node's child array.

Parameters:

newChild - The child node to add.

Throws:

IllegalArgumentException - if newChild is null

IllegalStateException - if this node does not allow children

breadthFirstEnumeration

public Enumeration<TreeNode> breadthFirstEnumeration()

Creates and returns an enumeration that traverses the subtree rooted at this node in breadth-first order. The first node returned by the enumeration's nextElement() method is this node.

Modifying the tree by inserting, removing, or moving a node invalidates any enumerations created before the modification.

Returns:

an enumeration for traversing the tree in breadth-first order

children

public Enumeration<TreeNode> children()

Creates and returns a forward-order enumeration of this node's children. Modifying this node's child array invalidates any child enumerations created before the modification.

Specified by:

children in interface TreeNode

Returns:

an Enumeration of this node's children

depthFirstEnumeration

public Enumeration<TreeNode> depthFirstEnumeration()

Creates and returns an enumeration that traverses the subtree rooted at this node in depth-first order. The first node returned by the enumeration's nextElement() method is the leftmost leaf. This is the same as a postorder traversal.

Modifying the tree by inserting, removing, or moving a node invalidates any enumerations created before the modification.

Returns:

an enumeration for traversing the tree in depth-first order

getActionCommand

public String getActionCommand()

Returns the Action command string associated with this node

Specified by:

getActionCommand in interface TreeNode

Returns:

The action command string associated with this node

getAllowsChildren

public boolean getAllowsChildren()

Returns true if this node is allowed to have children.

Specified by:

getAllowsChildren in interface TreeNode

Returns:

true if this node allows children, else false

getChildAfter

public TreeNode getChildAfter(TreeNode aChild)

Returns the child in this node's child array that immediately follows aChild, which must be a child of this node. If aChild is the last child, returns null. This method performs a linear search of this node's children for aChild and is O(n) where n is the number of children; to traverse the entire array of children, use an enumeration instead.

Parameters:

aChild - The child node from which the next node is to be retrieved.

Returns:

the child of this node that immediately follows aChild

Throws:

IllegalArgumentException - if aChild is null or is not a child of this node

getChildAt

public TreeNode getChildAt(int index)

Returns the child at the specified index in this node's child array.

Specified by:

getChildAt in interface TreeNode

Parameters:

index - an index into this node's child array

Returns:

the TreeNode in this node's child array at the specified index

Throws:

ArrayIndexOutOfBoundsException - if index is out of bounds

getChildBefore

public TreeNode getChildBefore(TreeNode aChild)

Returns the child in this node's child array that immediately precedes aChild, which must be a child of this node. If aChild is the first child, returns null. This method performs a linear search of this node's children for aChild and is O(n) where n is the number of children.

Parameters:

aChild - The node from which the node before is to be retrieved.

Returns:

the child of this node that immediately precedes aChild

Throws:

IllegalArgumentException - if aChild is null or is not a child of this node

getChildCount

public int getChildCount()

Returns the number of children of this node.

Specified by:

getChildCount in interface TreeNode

Returns:

an int giving the number of children of this node

getDepth

public int getDepth()

Returns the depth of the tree rooted at this node -- the longest distance from this node to a leaf. If this node has no children, returns 0. This operation is much more expensive than getLevel() because it must effectively traverse the entire tree rooted at this node.

Returns:

the depth of the tree whose root is this node

getFirstChild

public TreeNode getFirstChild()

Returns this node's first child. If this node has no children, throws NoSuchElementException.

Returns:

the first child of this node

Throws:

NoSuchElementException - if this node has no children

getFirstLeaf

public DefaultMutableTreeNode getFirstLeaf()

Finds and returns the first leaf that is a descendant of this node -- either this node or its first child's first leaf. Returns this node if it is a leaf.

Returns:

the first leaf in the subtree rooted at this node

getIndex

public int getIndex(TreeNode aChild)

Returns the index of the specified child in this node's child array. If the specified node is not a child of this node, returns -1. This method performs a linear search and is O(n) where n is the number of children.

Specified by:

getIndex in interface TreeNode

Parameters:

aChild - the TreeNode to search for among this node's children

Returns:

an int giving the index of the node in this node's child array, or -1 if the specified node is a not a child of this node

Throws:

IllegalArgumentException - if aChild is null

getLastChild

public TreeNode getLastChild()

Returns this node's last child. If this node has no children, throws NoSuchElementException.

Returns:

the last child of this node

Throws:

NoSuchElementException - if this node has no children

getLastLeaf

public DefaultMutableTreeNode getLastLeaf()

Finds and returns the last leaf that is a descendant of this node -- either this node or its last child's last leaf. Returns this node if it is a leaf.

Returns:

the last leaf in the subtree rooted at this node

getLeafCount

public int getLeafCount()

Returns the total number of leaves that are descendants of this node. If this node is a leaf, returns 1. This method is O(n) where n is the number of descendants of this node.

Returns:

the number of leaves beneath this node

getLevel

public int getLevel()

Returns the number of levels above this node -- the distance from the root to this node. If this node is the root, returns 0.

Returns:

the number of levels above this node

getNextLeaf

public DefaultMutableTreeNode getNextLeaf()

Returns the leaf after this node or null if this node is the last leaf in the tree.

In this implementation of the MutableNode interface, this operation is very inefficient. In order to determine the next node, this method first performs a linear search in the parent's child-list in order to find the current node.

That implementation makes the operation suitable for short traversals from a known position. But to traverse all of the leaves in the tree, you should use depthFirstEnumeration to enumerate the nodes in the tree and use isLeaf on each node to determine which are leaves.

Returns:

The leaf after this node or null.

getNextNode

public DefaultMutableTreeNode getNextNode()

Returns the node that follows this node in a preorder traversal of this node's tree. Returns null if this node is the last node of the traversal. This is an inefficient way to traverse the entire tree; use an enumeration, instead.

Returns:

Return the node that follows this node.

getNextSibling

public DefaultMutableTreeNode getNextSibling()

Returns the next sibling of this node in the parent's children array. Returns null if this node has no parent or is the parent's last child. This method performs a linear search that is O(n) where n is the number of children; to traverse the entire array, use the parent's child enumeration instead.

Returns:

Return the next sibling from the parent node.

getParent

public TreeNode getParent()

Returns this node's parent or null if this node has no parent.

Specified by:

getParent in interface TreeNode

Returns:

this node's parent TreeNode, or null if this node has no parent

getPath

public TreeNode[] getPath()

Returns the path from the root, to get to this node. The last element in the path is this node.

Returns:

an array of TreeNode objects giving the path, where the first element in the path is the root and the last element is this node.

getPathToRoot

protected TreeNode[] getPathToRoot(TreeNode aNode,
                                   int depth)

Builds the parents of node up to and including the root node, where the original node is the last element in the returned array. The length of the returned array gives the node's depth in the tree.

Parameters:

aNode - the TreeNode to get the path for

depth - an int giving the number of steps already taken towards the root (on recursive calls), used to size the returned array

Returns:

an array of TreeNodes giving the path from the root to the specified node

getPreviousLeaf

public DefaultMutableTreeNode getPreviousLeaf()

Returns the leaf before this node or null if this node is the first leaf in the tree.

In this implementation of the MutableNode interface, this operation is very inefficient. In order to determine the previous node, this method first performs a linear search in the parent's child-list in order to find the current node.

That implementation makes the operation suitable for short traversals from a known position. But to traverse all of the leaves in the tree, you should use depthFirstEnumeration to enumerate the nodes in the tree and use isLeaf on each node to determine which are leaves.

Returns:

The previous leaf node based on the position of this node.

getPreviousNode

public DefaultMutableTreeNode getPreviousNode()

Returns the node that precedes this node in a preorder traversal of this node's tree. Returns null if this node is the first node of the traveral -- the root of the tree. This is an inefficient way to traverse the entire tree; use an enumeration, instead.

Returns:

The preivous node based on the position of this node.

getPreviousSibling

public DefaultMutableTreeNode getPreviousSibling()

Returns the previous sibling of this node in the parent's children array. Returns null if this node has no parent or is the parent's first child. This method performs a linear search that is O(n) where n is the number of children.

Returns:

the sibling of this node that immediately precedes this node

getRoot

public TreeNode getRoot()

Returns the root of the tree that contains this node. The root is the ancestor with a null parent.

Returns:

The root of the tree.

getSharedAncestor

public TreeNode getSharedAncestor(DefaultMutableTreeNode aNode)

Returns the nearest common ancestor to this node and aNode. Returns null, if no such ancestor exists -- if this node and aNode are in different trees or if aNode is null. A node is considered an ancestor of itself.

Parameters:

aNode - The node for which the common ancestor is to be retrieved.

Returns:

The common ancestor of this node and the specified node.

getSiblingCount

public int getSiblingCount()

Returns the number of siblings of this node. A node is its own sibling (if it has no parent or no siblings, this method returns 1).

Returns:

the number of siblings of this node

getUserObject

public M getUserObject()

Returns:

Returns this node's user object.

getUserObjectPath

public Object[] getUserObjectPath()

Returns the user object path, from the root, to get to this node. If some of the TreeNodes in the path have null user objects, the returned path will contain nulls.

Returns:

The array of user objects.

insert

public void insert(MutableTreeNode newChild,
                   int childIndex)

Removes newChild from its present parent (if it has a parent), sets the child's parent to this node, and then adds the child to this node's child array at index childIndex. newChild must not be null and must not be an ancestor of this node.

Specified by:

insert in interface MutableTreeNode<M>

Parameters:

newChild - The child to add.

childIndex - The index at which to add the child.

isLeaf

public boolean isLeaf()

Returns true if this node has no children. To distinguish between nodes that have no children and nodes that cannot have children (e.g. to distinguish files from empty directories), use this method in conjunction with getAllowsChildren

Specified by:

isLeaf in interface TreeNode

Returns:

true if the receiver is a leaf.

isNodeAncestor

public boolean isNodeAncestor(TreeNode anotherNode)

Returns true if anotherNode is an ancestor of this node -- if it is this node, this node's parent, or an ancestor of this node's parent. (Note that a node is considered an ancestor of itself.) If anotherNode is null, this method returns false. This operation is at worst O(h) where h is the distance from the root to this node.

Parameters:

anotherNode - The node to check.

Returns:

true if the specified node is an ancestor.

isNodeChild

public boolean isNodeChild(TreeNode aNode)

Returns true if aNode is a child of this node. If aNode is null, this method returns false.

Parameters:

aNode - The node to check.

Returns:

true if aNode is a child of this node; false if aNode is null

isNodeDescendant

public boolean isNodeDescendant(DefaultMutableTreeNode anotherNode)

Returns true if anotherNode is a descendant of this node -- if it is this node, one of this node's children, or a descendant of one of this node's children. Note that a node is considered a descendant of itself. If anotherNode is null, returns false. This operation is at worst O(h) where h is the distance from the root to anotherNode.

Parameters:

anotherNode - The node to check.

Returns:

true is the node is a descendent of this node.

isNodeRelated

public boolean isNodeRelated(DefaultMutableTreeNode aNode)

Returns true if and only if aNode is in the same tree as this node. Returns false if aNode is null.

Parameters:

aNode - The node to check.

Returns:

true if the node is in the same tree.

isNodeSibling

public boolean isNodeSibling(TreeNode anotherNode)

Returns true if anotherNode is a sibling of (has the same parent as) this node. A node is its own sibling. If anotherNode is null, returns false.

Parameters:

anotherNode - node to test as sibling of this node

Returns:

true if anotherNode is a sibling of this node

isRoot

public boolean isRoot()

Returns true if this node is the root of the tree. The root is the only node in the tree with a null parent; every tree has exactly one root.

Returns:

true if this node is the root of its tree

pathFromAncestorEnumeration

public Enumeration<TreeNode> pathFromAncestorEnumeration(TreeNode ancestor)

Creates and returns an enumeration that follows the path from ancestor to this node. The enumeration's nextElement() method first returns ancestor, then the child of ancestor that is an ancestor of this node, and so on, and finally returns this node. Creation of the enumeration is O(m) where m is the number of nodes between this node and ancestor, inclusive. Each nextElement() message is O(1).

Modifying the tree by inserting, removing, or moving a node invalidates any enumerations created before the modification.

Parameters:

ancestor - The ancestor node from which the path is to be generated.

Returns:

The enumeration of nodes.

postorderEnumeration

public Enumeration<TreeNode> postorderEnumeration()

Creates and returns an enumeration that traverses the subtree rooted at this node in postorder. The first node returned by the enumeration's nextElement() method is the leftmost leaf. This is the same as a depth-first traversal.

Modifying the tree by inserting, removing, or moving a node invalidates any enumerations created before the modification.

Returns:

The post order enumeration for this node.

preorderEnumeration

public Enumeration<TreeNode> preorderEnumeration()

Creates and returns an enumeration that traverses the subtree rooted at this node in preorder. The first node returned by the enumeration's nextElement() method is this node.

Modifying the tree by inserting, removing, or moving a node invalidates any enumerations created before the modification.

Returns:

The enumeration of nodes.

remove

public void remove(int childIndex)

Removes the child at the specified index from this node's children and sets that node's parent to null. The child node to remove must be a MutableTreeNode.

Specified by:

remove in interface MutableTreeNode<M>

Parameters:

childIndex - the index in this node's child array of the child to remove

Throws:

ArrayIndexOutOfBoundsException - if childIndex is out of bounds

remove

public void remove(MutableTreeNode aChild)

Removes aChild from this node's child array, giving it a null parent.

Specified by:

remove in interface MutableTreeNode<M>

Parameters:

aChild - a child of this node to remove

Throws:

IllegalArgumentException - if aChild is null or is not a child of this node

removeAllChildren

public void removeAllChildren()

Removes all of this node's children, setting their parents to null. If this node has no children, this method does nothing.

removeFromParent

public void removeFromParent()

Removes the subtree rooted at this node from the tree, giving this node a null parent. Does nothing if this node is the root of its tree.

Specified by:

removeFromParent in interface MutableTreeNode<M>

setActionCommand

public void setActionCommand(String newActionCommand)

Sets this node's action command to newActionCommand

Parameters:

newActionCommand - this node's new action command

setAllowsChildren

public void setAllowsChildren(boolean allows)

Determines whether or not this node is allowed to have children. If allows is false, all of this node's children are removed.

Note: By default, a node allows children.

Parameters:

allows - true if this node is allowed to have children

setParent

public void setParent(MutableTreeNode newParent)

Sets this node's parent to newParent but does not change the parent's child array. This method is called from insert() and remove() to reassign a child's parent, it should not be messaged from anywhere else.

Specified by:

setParent in interface MutableTreeNode<M>

Parameters:

newParent - this node's new parent

setUserObject

public void setUserObject(M userObject)

Sets the user object for this node to userObject.

Specified by:

setUserObject in interface MutableTreeNode<M>

Parameters:

userObject - The user object of the receiver

toString

public String toString()

Returns the result of sending toString() to this node's user object, or null if this node has no user object.

Overrides:

toString in class Object