/* |
|
* Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved. |
|
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
|
* |
|
* This code is free software; you can redistribute it and/or modify it |
|
* under the terms of the GNU General Public License version 2 only, as |
|
* published by the Free Software Foundation. Oracle designates this |
|
* particular file as subject to the "Classpath" exception as provided |
|
* by Oracle in the LICENSE file that accompanied this code. |
|
* |
|
* This code is distributed in the hope that it will be useful, but WITHOUT |
|
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
|
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
|
* version 2 for more details (a copy is included in the LICENSE file that |
|
* accompanied this code). |
|
* |
|
* You should have received a copy of the GNU General Public License version |
|
* 2 along with this work; if not, write to the Free Software Foundation, |
|
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
|
* |
|
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
* or visit www.oracle.com if you need additional information or have any |
|
* questions. |
|
*/ |
|
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 |