/*
* Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
* ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*
*/
package javax.swing.tree;
// ISSUE: this class depends on nothing in AWT -- move to java.util?
import java.beans.
Transient;
import java.io.*;
import java.util.*;
/**
* A <code>DefaultMutableTreeNode</code> is a general-purpose node in a tree data
* structure.
* For examples of using default mutable tree nodes, see
* <a
href="https://docs.oracle.com/javase/tutorial/uiswing/components/tree.html">How to Use Trees</a>
* in <em>The Java Tutorial.</em>
*
* <p>
*
* A tree node may have at most one parent and 0 or more children.
* <code>DefaultMutableTreeNode</code> 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.
* <p>
* This class provides enumerations for efficiently traversing a tree or
* subtree in various orders or for following the path between two nodes.
* A <code>DefaultMutableTreeNode</code> may also hold a reference to a user object, the
* use of which is left to the user. Asking a <code>DefaultMutableTreeNode</code> for its
* string representation with <code>toString()</code> returns the string
* representation of its user object.
* <p>
* <b>This is not a thread safe class.</b>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.
* <p>
* 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.
*
* <p>
* <strong>Warning:</strong>
* Serialized objects of this class will not be compatible with
* future Swing releases. The current serialization support is
* appropriate for short term storage or RMI between applications running
* the same version of Swing. As of 1.4, support for long term storage
* of all JavaBeans™
* has been added to the <code>java.beans</code> package.
* Please see {@link java.beans.XMLEncoder}.
*
* @see MutableTreeNode
*
* @author Rob Davis
*/
public class
DefaultMutableTreeNode implements
Cloneable,
MutableTreeNode,
Serializable
{
private static final long
serialVersionUID = -4298474751201349152L;
/**
* An enumeration that is always empty. This is used when an enumeration
* of a leaf node's children is requested.
*/
static public final
Enumeration<
TreeNode>
EMPTY_ENUMERATION
=
Collections.
emptyEnumeration();
/** this node's parent, or null if this node has no parent */
protected
MutableTreeNode parent;
/** array of children, may be null if this node has no children */
protected
Vector children;
/** optional user object */
transient protected
Object userObject;
/** true if the node is able to have children */
protected boolean
allowsChildren;
/**
* Creates a tree node that has no parent and no children, but which
* allows children.
*/
public
DefaultMutableTreeNode() {
this(null);
}
/**
* Creates a tree node with no parent, no children, but which allows
* children, and initializes it with the specified user object.
*
* @param userObject an Object provided by the user that constitutes
* the node's data
*/
public
DefaultMutableTreeNode(
Object userObject) {
this(
userObject, true);
}
/**
* Creates a tree node with no parent, no children, initialized with
* the specified user object, and that allows children only if
* specified.
*
* @param userObject an Object provided by the user that constitutes
* the node's data
* @param allowsChildren if true, the node is allowed to have child
* nodes -- otherwise, it is always a leaf node
*/
public
DefaultMutableTreeNode(
Object userObject, boolean
allowsChildren) {
super();
parent = null;
this.
allowsChildren =
allowsChildren;
this.
userObject =
userObject;
}
//
// Primitives
//
/**
* Removes <code>newChild</code> 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 <code>childIndex</code>.
* <code>newChild</code> must not be null and must not be an ancestor of
* this node.
*
* @param newChild the MutableTreeNode to insert under this node
* @param childIndex the index in this node's child array
* where this node is to be inserted
* @exception ArrayIndexOutOfBoundsException if
* <code>childIndex</code> is out of bounds
* @exception IllegalArgumentException if
* <code>newChild</code> is null or is an
* ancestor of this node
* @exception IllegalStateException if this node does not allow
* children
* @see #isNodeDescendant
*/
public void
insert(
MutableTreeNode newChild, int
childIndex) {
if (!
allowsChildren) {
throw new
IllegalStateException("node does not allow children");
} else if (
newChild == null) {
throw new
IllegalArgumentException("new child is null");
} else if (
isNodeAncestor(
newChild)) {
throw new
IllegalArgumentException("new child is an ancestor");
}
MutableTreeNode oldParent = (
MutableTreeNode)
newChild.
getParent();
if (
oldParent != null) {
oldParent.
remove(
newChild);
}
newChild.
setParent(this);
if (
children == null) {
children = new
Vector();
}
children.
insertElementAt(
newChild,
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 <code>MutableTreeNode</code>.
*
* @param childIndex the index in this node's child array
* of the child to remove
* @exception ArrayIndexOutOfBoundsException if
* <code>childIndex</code> is out of bounds
*/
public void
remove(int
childIndex) {
MutableTreeNode child = (
MutableTreeNode)
getChildAt(
childIndex);
children.
removeElementAt(
childIndex);
child.
setParent(null);
}
/**
* Sets this node's parent to <code>newParent</code> but does not
* change the parent's child array. This method is called from
* <code>insert()</code> and <code>remove()</code> to
* reassign a child's parent, it should not be messaged from anywhere
* else.
*
* @param newParent this node's new parent
*/
@
Transient
public void
setParent(
MutableTreeNode newParent) {
parent =
newParent;
}
/**
* Returns this node's parent or null if this node has no parent.
*
* @return this node's parent TreeNode, or null if this node has no parent
*/
public
TreeNode getParent() {
return
parent;
}
/**
* Returns the child at the specified index in this node's child array.
*
* @param index an index into this node's child array
* @exception ArrayIndexOutOfBoundsException if <code>index</code>
* is out of bounds
* @return the TreeNode in this node's child array at the specified index
*/
public
TreeNode getChildAt(int
index) {
if (
children == null) {
throw new
ArrayIndexOutOfBoundsException("node has no children");
}
return (
TreeNode)
children.
elementAt(
index);
}
/**
* Returns the number of children of this node.
*
* @return an int giving the number of children of this node
*/
public int
getChildCount() {
if (
children == null) {
return 0;
} else {
return
children.
size();
}
}
/**
* 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
* <code>-1</code>. This method performs a linear search and is O(n)
* where n is the number of children.
*
* @param aChild the TreeNode to search for among this node's children
* @exception IllegalArgumentException if <code>aChild</code>
* is null
* @return an int giving the index of the node in this node's child
* array, or <code>-1</code> if the specified node is a not
* a child of this node
*/
public int
getIndex(
TreeNode aChild) {
if (
aChild == null) {
throw new
IllegalArgumentException("argument is null");
}
if (!
isNodeChild(
aChild)) {
return -1;
}
return
children.
indexOf(
aChild); // linear search
}
/**
* 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.
*
* @return an Enumeration of this node's children
*/
public
Enumeration children() {
if (
children == null) {
return
EMPTY_ENUMERATION;
} else {
return
children.
elements();
}
}
/**
* Determines whether or not this node is allowed to have children.
* If <code>allows</code> is false, all of this node's children are
* removed.
* <p>
* Note: By default, a node allows children.
*
* @param allows true if this node is allowed to have children
*/
public void
setAllowsChildren(boolean
allows) {
if (
allows !=
allowsChildren) {
allowsChildren =
allows;
if (!
allowsChildren) {
removeAllChildren();
}
}
}
/**
* Returns true if this node is allowed to have children.
*
* @return true if this node allows children, else false
*/
public boolean
getAllowsChildren() {
return
allowsChildren;
}
/**
* Sets the user object for this node to <code>userObject</code>.
*
* @param userObject the Object that constitutes this node's
* user-specified data
* @see #getUserObject
* @see #toString
*/
public void
setUserObject(
Object userObject) {
this.
userObject =
userObject;
}
/**
* Returns this node's user object.
*
* @return the Object stored at this node by the user
* @see #setUserObject
* @see #toString
*/
public
Object getUserObject() {
return
userObject;
}
//
// Derived methods
//
/**
* 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.
*/
public void
removeFromParent() {
MutableTreeNode parent = (
MutableTreeNode)
getParent();
if (
parent != null) {
parent.
remove(this);
}
}
/**
* Removes <code>aChild</code> from this node's child array, giving it a
* null parent.
*
* @param aChild a child of this node to remove
* @exception IllegalArgumentException if <code>aChild</code>
* is null or is not a child of this node
*/
public void
remove(
MutableTreeNode aChild) {
if (
aChild == null) {
throw new
IllegalArgumentException("argument is null");
}
if (!
isNodeChild(
aChild)) {
throw new
IllegalArgumentException("argument is not a child");
}
remove(
getIndex(
aChild)); // linear search
}
/**
* Removes all of this node's children, setting their parents to null.
* If this node has no children, this method does nothing.
*/
public void
removeAllChildren() {
for (int
i =
getChildCount()-1;
i >= 0;
i--) {
remove(
i);
}
}
/**
* Removes <code>newChild</code> from its parent and makes it a child of
* this node by adding it to the end of this node's child array.
*
* @see #insert
* @param newChild node to add as a child of this node
* @exception IllegalArgumentException if <code>newChild</code>
* is null
* @exception IllegalStateException if this node does not allow
* children
*/
public void
add(
MutableTreeNode newChild) {
if(
newChild != null &&
newChild.
getParent() == this)
insert(
newChild,
getChildCount() - 1);
else
insert(
newChild,
getChildCount());
}
//
// Tree Queries
//
/**
* Returns true if <code>anotherNode</code> 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 <code>anotherNode</code> is null, this method returns false. This
* operation is at worst O(h) where h is the distance from the root to
* this node.
*
* @see #isNodeDescendant
* @see #getSharedAncestor
* @param anotherNode node to test as an ancestor of this node
* @return true if this node is a descendant of <code>anotherNode</code>
*/
public boolean
isNodeAncestor(
TreeNode anotherNode) {
if (
anotherNode == null) {
return false;
}
TreeNode ancestor = this;
do {
if (
ancestor ==
anotherNode) {
return true;
}
} while((
ancestor =
ancestor.
getParent()) != null);
return false;
}
/**
* Returns true if <code>anotherNode</code> 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 <code>anotherNode</code> is null, returns
* false. This operation is at worst O(h) where h is the distance from the
* root to <code>anotherNode</code>.
*
* @see #isNodeAncestor
* @see #getSharedAncestor
* @param anotherNode node to test as descendant of this node
* @return true if this node is an ancestor of <code>anotherNode</code>
*/
public boolean
isNodeDescendant(
DefaultMutableTreeNode anotherNode) {
if (
anotherNode == null)
return false;
return
anotherNode.
isNodeAncestor(this);
}
/**
* Returns the nearest common ancestor to this node and <code>aNode</code>.
* Returns null, if no such ancestor exists -- if this node and
* <code>aNode</code> are in different trees or if <code>aNode</code> is
* null. A node is considered an ancestor of itself.
*
* @see #isNodeAncestor
* @see #isNodeDescendant
* @param aNode node to find common ancestor with
* @return nearest ancestor common to this node and <code>aNode</code>,
* or null if none
*/
public
TreeNode getSharedAncestor(
DefaultMutableTreeNode aNode) {
if (
aNode == this) {
return this;
} else if (
aNode == null) {
return null;
}
int
level1,
level2,
diff;
TreeNode node1,
node2;
level1 =
getLevel();
level2 =
aNode.
getLevel();
if (
level2 >
level1) {
diff =
level2 -
level1;
node1 =
aNode;
node2 = this;
} else {
diff =
level1 -
level2;
node1 = this;
node2 =
aNode;
}
// Go up the tree until the nodes are at the same level
while (
diff > 0) {
node1 =
node1.
getParent();
diff--;
}
// Move up the tree until we find a common ancestor. Since we know
// that both nodes are at the same level, we won't cross paths
// unknowingly (if there is a common ancestor, both nodes hit it in
// the same iteration).
do {
if (
node1 ==
node2) {
return
node1;
}
node1 =
node1.
getParent();
node2 =
node2.
getParent();
} while (
node1 != null);// only need to check one -- they're at the
// same level so if one is null, the other is
if (
node1 != null ||
node2 != null) {
throw new
Error ("nodes should be null");
}
return null;
}
/**
* Returns true if and only if <code>aNode</code> is in the same tree
* as this node. Returns false if <code>aNode</code> is null.
*
* @see #getSharedAncestor
* @see #getRoot
* @return true if <code>aNode</code> is in the same tree as this node;
* false if <code>aNode</code> is null
*/
public boolean
isNodeRelated(
DefaultMutableTreeNode aNode) {
return (
aNode != null) && (
getRoot() ==
aNode.
getRoot());
}
/**
* 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
* <code>getLevel()</code> because it must effectively traverse the entire
* tree rooted at this node.
*
* @see #getLevel
* @return the depth of the tree whose root is this node
*/
public int
getDepth() {
Object last = null;
Enumeration enum_ =
breadthFirstEnumeration();
while (
enum_.
hasMoreElements()) {
last =
enum_.
nextElement();
}
if (
last == null) {
throw new
Error ("nodes should be null");
}
return ((
DefaultMutableTreeNode)
last).
getLevel() -
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.
*
* @see #getDepth
* @return the number of levels above this node
*/
public int
getLevel() {
TreeNode ancestor;
int
levels = 0;
ancestor = this;
while((
ancestor =
ancestor.
getParent()) != null){
levels++;
}
return
levels;
}
/**
* Returns the path from the root, to get to this node. The last
* element in the path is this node.
*
* @return 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.
*/
public
TreeNode[]
getPath() {
return
getPathToRoot(this, 0);
}
/**
* 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.
*
* @param aNode the TreeNode to get the path for
* @param depth an int giving the number of steps already taken towards
* the root (on recursive calls), used to size the returned array
* @return an array of TreeNodes giving the path from the root to the
* specified node
*/
protected
TreeNode[]
getPathToRoot(
TreeNode aNode, int
depth) {
TreeNode[]
retNodes;
/* Check for null, in case someone passed in a null node, or
they passed in an element that isn't rooted at root. */
if(
aNode == null) {
if(
depth == 0)
return null;
else
retNodes = new
TreeNode[
depth];
}
else {
depth++;
retNodes =
getPathToRoot(
aNode.
getParent(),
depth);
retNodes[
retNodes.length -
depth] =
aNode;
}
return
retNodes;
}
/**
* 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.
*/
public
Object[]
getUserObjectPath() {
TreeNode[]
realPath =
getPath();
Object[]
retPath = new
Object[
realPath.length];
for(int
counter = 0;
counter <
realPath.length;
counter++)
retPath[
counter] = ((
DefaultMutableTreeNode)
realPath[
counter])
.
getUserObject();
return
retPath;
}
/**
* Returns the root of the tree that contains this node. The root is
* the ancestor with a null parent.
*
* @see #isNodeAncestor
* @return the root of the tree that contains this node
*/
public
TreeNode getRoot() {
TreeNode ancestor = this;
TreeNode previous;
do {
previous =
ancestor;
ancestor =
ancestor.
getParent();
} while (
ancestor != null);
return
previous;
}
/**
* 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.
*
* @return true if this node is the root of its tree
*/
public boolean
isRoot() {
return
getParent() == null;
}
/**
* 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.
*
* @see #preorderEnumeration
* @return the node that follows this node in a preorder traversal, or
* null if this node is last
*/
public
DefaultMutableTreeNode getNextNode() {
if (
getChildCount() == 0) {
// No children, so look for nextSibling
DefaultMutableTreeNode nextSibling =
getNextSibling();
if (
nextSibling == null) {
DefaultMutableTreeNode aNode = (
DefaultMutableTreeNode)
getParent();
do {
if (
aNode == null) {
return null;
}
nextSibling =
aNode.
getNextSibling();
if (
nextSibling != null) {
return
nextSibling;
}
aNode = (
DefaultMutableTreeNode)
aNode.
getParent();
} while(true);
} else {
return
nextSibling;
}
} else {
return (
DefaultMutableTreeNode)
getChildAt(0);
}
}
/**
* Returns the node that precedes this node in a preorder traversal of
* this node's tree. Returns <code>null</code> if this node is the
* first node of the traversal -- the root of the tree.
* This is an inefficient way to
* traverse the entire tree; use an enumeration, instead.
*
* @see #preorderEnumeration
* @return the node that precedes this node in a preorder traversal, or
* null if this node is the first
*/
public
DefaultMutableTreeNode getPreviousNode() {
DefaultMutableTreeNode previousSibling;
DefaultMutableTreeNode myParent = (
DefaultMutableTreeNode)
getParent();
if (
myParent == null) {
return null;
}
previousSibling =
getPreviousSibling();
if (
previousSibling != null) {
if (
previousSibling.
getChildCount() == 0)
return
previousSibling;
else
return
previousSibling.
getLastLeaf();
} else {
return
myParent;
}
}
/**
* Creates and returns an enumeration that traverses the subtree rooted at
* this node in preorder. The first node returned by the enumeration's
* <code>nextElement()</code> method is this node.<P>
*
* Modifying the tree by inserting, removing, or moving a node invalidates
* any enumerations created before the modification.
*
* @see #postorderEnumeration
* @return an enumeration for traversing the tree in preorder
*/
public
Enumeration preorderEnumeration() {
return new
PreorderEnumeration(this);
}
/**
* Creates and returns an enumeration that traverses the subtree rooted at
* this node in postorder. The first node returned by the enumeration's
* <code>nextElement()</code> method is the leftmost leaf. This is the
* same as a depth-first traversal.<P>
*
* Modifying the tree by inserting, removing, or moving a node invalidates
* any enumerations created before the modification.
*
* @see #depthFirstEnumeration
* @see #preorderEnumeration
* @return an enumeration for traversing the tree in postorder
*/
public
Enumeration postorderEnumeration() {
return new
PostorderEnumeration(this);
}
/**
* 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 <code>nextElement()</code> method is this node.<P>
*
* Modifying the tree by inserting, removing, or moving a node invalidates
* any enumerations created before the modification.
*
* @see #depthFirstEnumeration
* @return an enumeration for traversing the tree in breadth-first order
*/
public
Enumeration breadthFirstEnumeration() {
return new
BreadthFirstEnumeration(this);
}
/**
* 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 <code>nextElement()</code> method is the leftmost leaf.
* This is the same as a postorder traversal.<P>
*
* Modifying the tree by inserting, removing, or moving a node invalidates
* any enumerations created before the modification.
*
* @see #breadthFirstEnumeration
* @see #postorderEnumeration
* @return an enumeration for traversing the tree in depth-first order
*/
public
Enumeration depthFirstEnumeration() {
return
postorderEnumeration();
}
/**
* Creates and returns an enumeration that follows the path from
* <code>ancestor</code> to this node. The enumeration's
* <code>nextElement()</code> method first returns <code>ancestor</code>,
* then the child of <code>ancestor</code> 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 <code>ancestor</code>, inclusive. Each <code>nextElement()</code>
* message is O(1).<P>
*
* Modifying the tree by inserting, removing, or moving a node invalidates
* any enumerations created before the modification.
*
* @see #isNodeAncestor
* @see #isNodeDescendant
* @exception IllegalArgumentException if <code>ancestor</code> is
* not an ancestor of this node
* @return an enumeration for following the path from an ancestor of
* this node to this one
*/
public
Enumeration pathFromAncestorEnumeration(
TreeNode ancestor) {
return new
PathBetweenNodesEnumeration(
ancestor, this);
}
//
// Child Queries
//
/**
* Returns true if <code>aNode</code> is a child of this node. If
* <code>aNode</code> is null, this method returns false.
*
* @return true if <code>aNode</code> is a child of this node; false if
* <code>aNode</code> is null
*/
public boolean
isNodeChild(
TreeNode aNode) {
boolean
retval;
if (
aNode == null) {
retval = false;
} else {
if (
getChildCount() == 0) {
retval = false;
} else {
retval = (
aNode.
getParent() == this);
}
}
return
retval;
}
/**
* Returns this node's first child. If this node has no children,
* throws NoSuchElementException.
*
* @return the first child of this node
* @exception NoSuchElementException if this node has no children
*/
public
TreeNode getFirstChild() {
if (
getChildCount() == 0) {
throw new
NoSuchElementException("node has no children");
}
return
getChildAt(0);
}
/**
* Returns this node's last child. If this node has no children,
* throws NoSuchElementException.
*
* @return the last child of this node
* @exception NoSuchElementException if this node has no children
*/
public
TreeNode getLastChild() {
if (
getChildCount() == 0) {
throw new
NoSuchElementException("node has no children");
}
return
getChildAt(
getChildCount()-1);
}
/**
* Returns the child in this node's child array that immediately
* follows <code>aChild</code>, which must be a child of this node. If
* <code>aChild</code> is the last child, returns null. This method
* performs a linear search of this node's children for
* <code>aChild</code> and is O(n) where n is the number of children; to
* traverse the entire array of children, use an enumeration instead.
*
* @see #children
* @exception IllegalArgumentException if <code>aChild</code> is
* null or is not a child of this node
* @return the child of this node that immediately follows
* <code>aChild</code>
*/
public
TreeNode getChildAfter(
TreeNode aChild) {
if (
aChild == null) {
throw new
IllegalArgumentException("argument is null");
}
int
index =
getIndex(
aChild); // linear search
if (
index == -1) {
throw new
IllegalArgumentException("node is not a child");
}
if (
index <
getChildCount() - 1) {
return
getChildAt(
index + 1);
} else {
return null;
}
}
/**
* Returns the child in this node's child array that immediately
* precedes <code>aChild</code>, which must be a child of this node. If
* <code>aChild</code> is the first child, returns null. This method
* performs a linear search of this node's children for <code>aChild</code>
* and is O(n) where n is the number of children.
*
* @exception IllegalArgumentException if <code>aChild</code> is null
* or is not a child of this node
* @return the child of this node that immediately precedes
* <code>aChild</code>
*/
public
TreeNode getChildBefore(
TreeNode aChild) {
if (
aChild == null) {
throw new
IllegalArgumentException("argument is null");
}
int
index =
getIndex(
aChild); // linear search
if (
index == -1) {
throw new
IllegalArgumentException("argument is not a child");
}
if (
index > 0) {
return
getChildAt(
index - 1);
} else {
return null;
}
}
//
// Sibling Queries
//
/**
* Returns true if <code>anotherNode</code> is a sibling of (has the
* same parent as) this node. A node is its own sibling. If
* <code>anotherNode</code> is null, returns false.
*
* @param anotherNode node to test as sibling of this node
* @return true if <code>anotherNode</code> is a sibling of this node
*/
public boolean
isNodeSibling(
TreeNode anotherNode) {
boolean
retval;
if (
anotherNode == null) {
retval = false;
} else if (
anotherNode == this) {
retval = true;
} else {
TreeNode myParent =
getParent();
retval = (
myParent != null &&
myParent ==
anotherNode.
getParent());
if (
retval && !((
DefaultMutableTreeNode)
getParent())
.
isNodeChild(
anotherNode)) {
throw new
Error("sibling has different parent");
}
}
return
retval;
}
/**
* 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
* <code>1</code>).
*
* @return the number of siblings of this node
*/
public int
getSiblingCount() {
TreeNode myParent =
getParent();
if (
myParent == null) {
return 1;
} else {
return
myParent.
getChildCount();
}
}
/**
* 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.
*
* @see #children
* @return the sibling of this node that immediately follows this node
*/
public
DefaultMutableTreeNode getNextSibling() {
DefaultMutableTreeNode retval;
DefaultMutableTreeNode myParent = (
DefaultMutableTreeNode)
getParent();
if (
myParent == null) {
retval = null;
} else {
retval = (
DefaultMutableTreeNode)
myParent.
getChildAfter(this); // linear search
}
if (
retval != null && !
isNodeSibling(
retval)) {
throw new
Error("child of parent is not a sibling");
}
return
retval;
}
/**
* 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.
*
* @return the sibling of this node that immediately precedes this node
*/
public
DefaultMutableTreeNode getPreviousSibling() {
DefaultMutableTreeNode retval;
DefaultMutableTreeNode myParent = (
DefaultMutableTreeNode)
getParent();
if (
myParent == null) {
retval = null;
} else {
retval = (
DefaultMutableTreeNode)
myParent.
getChildBefore(this); // linear search
}
if (
retval != null && !
isNodeSibling(
retval)) {
throw new
Error("child of parent is not a sibling");
}
return
retval;
}
//
// Leaf Queries
//
/**
* Returns true if this node has no children. To distinguish between
* nodes that have no children and nodes that <i>cannot</i> have
* children (e.g. to distinguish files from empty directories), use this
* method in conjunction with <code>getAllowsChildren</code>
*
* @see #getAllowsChildren
* @return true if this node has no children
*/
public boolean
isLeaf() {
return (
getChildCount() == 0);
}
/**
* 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.
*
* @see #isLeaf
* @see #isNodeDescendant
* @return the first leaf in the subtree rooted at this node
*/
public
DefaultMutableTreeNode getFirstLeaf() {
DefaultMutableTreeNode node = this;
while (!
node.
isLeaf()) {
node = (
DefaultMutableTreeNode)
node.
getFirstChild();
}
return
node;
}
/**
* 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.
*
* @see #isLeaf
* @see #isNodeDescendant
* @return the last leaf in the subtree rooted at this node
*/
public
DefaultMutableTreeNode getLastLeaf() {
DefaultMutableTreeNode node = this;
while (!
node.
isLeaf()) {
node = (
DefaultMutableTreeNode)
node.
getLastChild();
}
return
node;
}
/**
* Returns the leaf after this node or null if this node is the
* last leaf in the tree.
* <p>
* In this implementation of the <code>MutableNode</code> 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.
* <p>
* 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 <code>depthFirstEnumeration</code>
* to enumerate the nodes in the tree and use <code>isLeaf</code>
* on each node to determine which are leaves.
*
* @see #depthFirstEnumeration
* @see #isLeaf
* @return returns the next leaf past this node
*/
public
DefaultMutableTreeNode getNextLeaf() {
DefaultMutableTreeNode nextSibling;
DefaultMutableTreeNode myParent = (
DefaultMutableTreeNode)
getParent();
if (
myParent == null)
return null;
nextSibling =
getNextSibling(); // linear search
if (
nextSibling != null)
return
nextSibling.
getFirstLeaf();
return
myParent.
getNextLeaf(); // tail recursion
}
/**
* Returns the leaf before this node or null if this node is the
* first leaf in the tree.
* <p>
* In this implementation of the <code>MutableNode</code> 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.
* <p>
* 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 <code>depthFirstEnumeration</code>
* to enumerate the nodes in the tree and use <code>isLeaf</code>
* on each node to determine which are leaves.
*
* @see #depthFirstEnumeration
* @see #isLeaf
* @return returns the leaf before this node
*/
public
DefaultMutableTreeNode getPreviousLeaf() {
DefaultMutableTreeNode previousSibling;
DefaultMutableTreeNode myParent = (
DefaultMutableTreeNode)
getParent();
if (
myParent == null)
return null;
previousSibling =
getPreviousSibling(); // linear search
if (
previousSibling != null)
return
previousSibling.
getLastLeaf();
return
myParent.
getPreviousLeaf(); // tail recursion
}
/**
* Returns the total number of leaves that are descendants of this node.
* If this node is a leaf, returns <code>1</code>. This method is O(n)
* where n is the number of descendants of this node.
*
* @see #isNodeAncestor
* @return the number of leaves beneath this node
*/
public int
getLeafCount() {
int
count = 0;
TreeNode node;
Enumeration enum_ =
breadthFirstEnumeration(); // order matters not
while (
enum_.
hasMoreElements()) {
node = (
TreeNode)
enum_.
nextElement();
if (
node.
isLeaf()) {
count++;
}
}
if (
count < 1) {
throw new
Error("tree has zero leaves");
}
return
count;
}
//
// Overrides
//
/**
* Returns the result of sending <code>toString()</code> to this node's
* user object, or the empty string if the node has no user object.
*
* @see #getUserObject
*/
public
String toString() {
if (
userObject == null) {
return "";
} else {
return
userObject.
toString();
}
}
/**
* Overridden to make clone public. Returns a shallow copy of this node;
* the new node has no parent or children and has a reference to the same
* user object, if any.
*
* @return a copy of this node
*/
public
Object clone() {
DefaultMutableTreeNode newNode;
try {
newNode = (
DefaultMutableTreeNode)super.clone();
// shallow copy -- the new node has no parent or children
newNode.
children = null;
newNode.
parent = null;
} catch (
CloneNotSupportedException e) {
// Won't happen because we implement Cloneable
throw new
Error(
e.
toString());
}
return
newNode;
}
// Serialization support.
private void
writeObject(
ObjectOutputStream s) throws
IOException {
Object[]
tValues;
s.
defaultWriteObject();
// Save the userObject, if its Serializable.
if(
userObject != null &&
userObject instanceof
Serializable) {
tValues = new
Object[2];
tValues[0] = "userObject";
tValues[1] =
userObject;
}
else
tValues = new
Object[0];
s.
writeObject(
tValues);
}
private void
readObject(
ObjectInputStream s)
throws
IOException,
ClassNotFoundException {
Object[]
tValues;
s.
defaultReadObject();
tValues = (
Object[])
s.
readObject();
if(
tValues.length > 0 &&
tValues[0].
equals("userObject"))
userObject =
tValues[1];
}
private final class
PreorderEnumeration implements
Enumeration<
TreeNode> {
private final
Stack<
Enumeration>
stack = new
Stack<
Enumeration>();
public
PreorderEnumeration(
TreeNode rootNode) {
super();
Vector<
TreeNode>
v = new
Vector<
TreeNode>(1);
v.
addElement(
rootNode); // PENDING: don't really need a vector
stack.
push(
v.
elements());
}
public boolean
hasMoreElements() {
return (!
stack.
empty() &&
stack.
peek().
hasMoreElements());
}
public
TreeNode nextElement() {
Enumeration enumer =
stack.
peek();
TreeNode node = (
TreeNode)
enumer.
nextElement();
Enumeration children =
node.
children();
if (!
enumer.
hasMoreElements()) {
stack.
pop();
}
if (
children.
hasMoreElements()) {
stack.
push(
children);
}
return
node;
}
} // End of class PreorderEnumeration
final class
PostorderEnumeration implements
Enumeration<
TreeNode> {
protected
TreeNode root;
protected
Enumeration<
TreeNode>
children;
protected
Enumeration<
TreeNode>
subtree;
public
PostorderEnumeration(
TreeNode rootNode) {
super();
root =
rootNode;
children =
root.
children();
subtree =
EMPTY_ENUMERATION;
}
public boolean
hasMoreElements() {
return
root != null;
}
public
TreeNode nextElement() {
TreeNode retval;
if (
subtree.
hasMoreElements()) {
retval =
subtree.
nextElement();
} else if (
children.
hasMoreElements()) {
subtree = new
PostorderEnumeration(
children.
nextElement());
retval =
subtree.
nextElement();
} else {
retval =
root;
root = null;
}
return
retval;
}
} // End of class PostorderEnumeration
final class
BreadthFirstEnumeration implements
Enumeration<
TreeNode> {
protected
Queue queue;
public
BreadthFirstEnumeration(
TreeNode rootNode) {
super();
Vector<
TreeNode>
v = new
Vector<
TreeNode>(1);
v.
addElement(
rootNode); // PENDING: don't really need a vector
queue = new
Queue();
queue.
enqueue(
v.
elements());
}
public boolean
hasMoreElements() {
return (!
queue.
isEmpty() &&
((
Enumeration)
queue.
firstObject()).
hasMoreElements());
}
public
TreeNode nextElement() {
Enumeration enumer = (
Enumeration)
queue.
firstObject();
TreeNode node = (
TreeNode)
enumer.
nextElement();
Enumeration children =
node.
children();
if (!
enumer.
hasMoreElements()) {
queue.
dequeue();
}
if (
children.
hasMoreElements()) {
queue.
enqueue(
children);
}
return
node;
}
// A simple queue with a linked list data structure.
final class
Queue {
QNode head; // null if empty
QNode tail;
final class
QNode {
public
Object object;
public
QNode next; // null if end
public
QNode(
Object object,
QNode next) {
this.
object =
object;
this.
next =
next;
}
}
public void
enqueue(
Object anObject) {
if (
head == null) {
head =
tail = new
QNode(
anObject, null);
} else {
tail.
next = new
QNode(
anObject, null);
tail =
tail.
next;
}
}
public
Object dequeue() {
if (
head == null) {
throw new
NoSuchElementException("No more elements");
}
Object retval =
head.
object;
QNode oldHead =
head;
head =
head.
next;
if (
head == null) {
tail = null;
} else {
oldHead.
next = null;
}
return
retval;
}
public
Object firstObject() {
if (
head == null) {
throw new
NoSuchElementException("No more elements");
}
return
head.
object;
}
public boolean
isEmpty() {
return
head == null;
}
} // End of class Queue
} // End of class BreadthFirstEnumeration
final class
PathBetweenNodesEnumeration implements
Enumeration<
TreeNode> {
protected
Stack<
TreeNode>
stack;
public
PathBetweenNodesEnumeration(
TreeNode ancestor,
TreeNode descendant)
{
super();
if (
ancestor == null ||
descendant == null) {
throw new
IllegalArgumentException("argument is null");
}
TreeNode current;
stack = new
Stack<
TreeNode>();
stack.
push(
descendant);
current =
descendant;
while (
current !=
ancestor) {
current =
current.
getParent();
if (
current == null &&
descendant !=
ancestor) {
throw new
IllegalArgumentException("node " +
ancestor +
" is not an ancestor of " +
descendant);
}
stack.
push(
current);
}
}
public boolean
hasMoreElements() {
return
stack.
size() > 0;
}
public
TreeNode nextElement() {
try {
return
stack.
pop();
} catch (
EmptyStackException e) {
throw new
NoSuchElementException("No more elements");
}
}
} // End of class PathBetweenNodesEnumeration
} // End of class DefaultMutableTreeNode