0001 /*
0002 * Copyright 1997-2006 Sun Microsystems, Inc. All Rights Reserved.
0003 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0004 *
0005 * This code is free software; you can redistribute it and/or modify it
0006 * under the terms of the GNU General Public License version 2 only, as
0007 * published by the Free Software Foundation. Sun designates this
0008 * particular file as subject to the "Classpath" exception as provided
0009 * by Sun in the LICENSE file that accompanied this code.
0010 *
0011 * This code is distributed in the hope that it will be useful, but WITHOUT
0012 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0013 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0014 * version 2 for more details (a copy is included in the LICENSE file that
0015 * accompanied this code).
0016 *
0017 * You should have received a copy of the GNU General Public License version
0018 * 2 along with this work; if not, write to the Free Software Foundation,
0019 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0020 *
0021 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
0022 * CA 95054 USA or visit www.sun.com if you need additional information or
0023 * have any questions.
0024 */
0025
0026 package javax.swing.tree;
0027
0028 // ISSUE: this class depends on nothing in AWT -- move to java.util?
0029
0030 import java.io.*;
0031 import java.util.*;
0032
0033 /**
0034 * A <code>DefaultMutableTreeNode</code> is a general-purpose node in a tree data
0035 * structure.
0036 * For examples of using default mutable tree nodes, see
0037 * <a
0038 href="http://java.sun.com/docs/books/tutorial/uiswing/components/tree.html">How to Use Trees</a>
0039 * in <em>The Java Tutorial.</em>
0040 *
0041 * <p>
0042 *
0043 * A tree node may have at most one parent and 0 or more children.
0044 * <code>DefaultMutableTreeNode</code> provides operations for examining and modifying a
0045 * node's parent and children and also operations for examining the tree that
0046 * the node is a part of. A node's tree is the set of all nodes that can be
0047 * reached by starting at the node and following all the possible links to
0048 * parents and children. A node with no parent is the root of its tree; a
0049 * node with no children is a leaf. A tree may consist of many subtrees,
0050 * each node acting as the root for its own subtree.
0051 * <p>
0052 * This class provides enumerations for efficiently traversing a tree or
0053 * subtree in various orders or for following the path between two nodes.
0054 * A <code>DefaultMutableTreeNode</code> may also hold a reference to a user object, the
0055 * use of which is left to the user. Asking a <code>DefaultMutableTreeNode</code> for its
0056 * string representation with <code>toString()</code> returns the string
0057 * representation of its user object.
0058 * <p>
0059 * <b>This is not a thread safe class.</b>If you intend to use
0060 * a DefaultMutableTreeNode (or a tree of TreeNodes) in more than one thread, you
0061 * need to do your own synchronizing. A good convention to adopt is
0062 * synchronizing on the root node of a tree.
0063 * <p>
0064 * While DefaultMutableTreeNode implements the MutableTreeNode interface and
0065 * will allow you to add in any implementation of MutableTreeNode not all
0066 * of the methods in DefaultMutableTreeNode will be applicable to all
0067 * MutableTreeNodes implementations. Especially with some of the enumerations
0068 * that are provided, using some of these methods assumes the
0069 * DefaultMutableTreeNode contains only DefaultMutableNode instances. All
0070 * of the TreeNode/MutableTreeNode methods will behave as defined no
0071 * matter what implementations are added.
0072 *
0073 * <p>
0074 * <strong>Warning:</strong>
0075 * Serialized objects of this class will not be compatible with
0076 * future Swing releases. The current serialization support is
0077 * appropriate for short term storage or RMI between applications running
0078 * the same version of Swing. As of 1.4, support for long term storage
0079 * of all JavaBeans<sup><font size="-2">TM</font></sup>
0080 * has been added to the <code>java.beans</code> package.
0081 * Please see {@link java.beans.XMLEncoder}.
0082 *
0083 * @see MutableTreeNode
0084 *
0085 * @version 1.32 07/08/07
0086 * @author Rob Davis
0087 */
0088 public class DefaultMutableTreeNode extends Object implements
0089 Cloneable, MutableTreeNode, Serializable {
0090 private static final long serialVersionUID = -4298474751201349152L;
0091
0092 /**
0093 * An enumeration that is always empty. This is used when an enumeration
0094 * of a leaf node's children is requested.
0095 */
0096 static public final Enumeration<TreeNode> EMPTY_ENUMERATION = Collections
0097 .emptyEnumeration();
0098
0099 /** this node's parent, or null if this node has no parent */
0100 protected MutableTreeNode parent;
0101
0102 /** array of children, may be null if this node has no children */
0103 protected Vector children;
0104
0105 /** optional user object */
0106 transient protected Object userObject;
0107
0108 /** true if the node is able to have children */
0109 protected boolean allowsChildren;
0110
0111 /**
0112 * Creates a tree node that has no parent and no children, but which
0113 * allows children.
0114 */
0115 public DefaultMutableTreeNode() {
0116 this (null);
0117 }
0118
0119 /**
0120 * Creates a tree node with no parent, no children, but which allows
0121 * children, and initializes it with the specified user object.
0122 *
0123 * @param userObject an Object provided by the user that constitutes
0124 * the node's data
0125 */
0126 public DefaultMutableTreeNode(Object userObject) {
0127 this (userObject, true);
0128 }
0129
0130 /**
0131 * Creates a tree node with no parent, no children, initialized with
0132 * the specified user object, and that allows children only if
0133 * specified.
0134 *
0135 * @param userObject an Object provided by the user that constitutes
0136 * the node's data
0137 * @param allowsChildren if true, the node is allowed to have child
0138 * nodes -- otherwise, it is always a leaf node
0139 */
0140 public DefaultMutableTreeNode(Object userObject,
0141 boolean allowsChildren) {
0142 super ();
0143 parent = null;
0144 this .allowsChildren = allowsChildren;
0145 this .userObject = userObject;
0146 }
0147
0148 //
0149 // Primitives
0150 //
0151
0152 /**
0153 * Removes <code>newChild</code> from its present parent (if it has a
0154 * parent), sets the child's parent to this node, and then adds the child
0155 * to this node's child array at index <code>childIndex</code>.
0156 * <code>newChild</code> must not be null and must not be an ancestor of
0157 * this node.
0158 *
0159 * @param newChild the MutableTreeNode to insert under this node
0160 * @param childIndex the index in this node's child array
0161 * where this node is to be inserted
0162 * @exception ArrayIndexOutOfBoundsException if
0163 * <code>childIndex</code> is out of bounds
0164 * @exception IllegalArgumentException if
0165 * <code>newChild</code> is null or is an
0166 * ancestor of this node
0167 * @exception IllegalStateException if this node does not allow
0168 * children
0169 * @see #isNodeDescendant
0170 */
0171 public void insert(MutableTreeNode newChild, int childIndex) {
0172 if (!allowsChildren) {
0173 throw new IllegalStateException(
0174 "node does not allow children");
0175 } else if (newChild == null) {
0176 throw new IllegalArgumentException("new child is null");
0177 } else if (isNodeAncestor(newChild)) {
0178 throw new IllegalArgumentException(
0179 "new child is an ancestor");
0180 }
0181
0182 MutableTreeNode oldParent = (MutableTreeNode) newChild
0183 .getParent();
0184
0185 if (oldParent != null) {
0186 oldParent.remove(newChild);
0187 }
0188 newChild.setParent(this );
0189 if (children == null) {
0190 children = new Vector();
0191 }
0192 children.insertElementAt(newChild, childIndex);
0193 }
0194
0195 /**
0196 * Removes the child at the specified index from this node's children
0197 * and sets that node's parent to null. The child node to remove
0198 * must be a <code>MutableTreeNode</code>.
0199 *
0200 * @param childIndex the index in this node's child array
0201 * of the child to remove
0202 * @exception ArrayIndexOutOfBoundsException if
0203 * <code>childIndex</code> is out of bounds
0204 */
0205 public void remove(int childIndex) {
0206 MutableTreeNode child = (MutableTreeNode) getChildAt(childIndex);
0207 children.removeElementAt(childIndex);
0208 child.setParent(null);
0209 }
0210
0211 /**
0212 * Sets this node's parent to <code>newParent</code> but does not
0213 * change the parent's child array. This method is called from
0214 * <code>insert()</code> and <code>remove()</code> to
0215 * reassign a child's parent, it should not be messaged from anywhere
0216 * else.
0217 *
0218 * @param newParent this node's new parent
0219 */
0220 public void setParent(MutableTreeNode newParent) {
0221 parent = newParent;
0222 }
0223
0224 /**
0225 * Returns this node's parent or null if this node has no parent.
0226 *
0227 * @return this node's parent TreeNode, or null if this node has no parent
0228 */
0229 public TreeNode getParent() {
0230 return parent;
0231 }
0232
0233 /**
0234 * Returns the child at the specified index in this node's child array.
0235 *
0236 * @param index an index into this node's child array
0237 * @exception ArrayIndexOutOfBoundsException if <code>index</code>
0238 * is out of bounds
0239 * @return the TreeNode in this node's child array at the specified index
0240 */
0241 public TreeNode getChildAt(int index) {
0242 if (children == null) {
0243 throw new ArrayIndexOutOfBoundsException(
0244 "node has no children");
0245 }
0246 return (TreeNode) children.elementAt(index);
0247 }
0248
0249 /**
0250 * Returns the number of children of this node.
0251 *
0252 * @return an int giving the number of children of this node
0253 */
0254 public int getChildCount() {
0255 if (children == null) {
0256 return 0;
0257 } else {
0258 return children.size();
0259 }
0260 }
0261
0262 /**
0263 * Returns the index of the specified child in this node's child array.
0264 * If the specified node is not a child of this node, returns
0265 * <code>-1</code>. This method performs a linear search and is O(n)
0266 * where n is the number of children.
0267 *
0268 * @param aChild the TreeNode to search for among this node's children
0269 * @exception IllegalArgumentException if <code>aChild</code>
0270 * is null
0271 * @return an int giving the index of the node in this node's child
0272 * array, or <code>-1</code> if the specified node is a not
0273 * a child of this node
0274 */
0275 public int getIndex(TreeNode aChild) {
0276 if (aChild == null) {
0277 throw new IllegalArgumentException("argument is null");
0278 }
0279
0280 if (!isNodeChild(aChild)) {
0281 return -1;
0282 }
0283 return children.indexOf(aChild); // linear search
0284 }
0285
0286 /**
0287 * Creates and returns a forward-order enumeration of this node's
0288 * children. Modifying this node's child array invalidates any child
0289 * enumerations created before the modification.
0290 *
0291 * @return an Enumeration of this node's children
0292 */
0293 public Enumeration children() {
0294 if (children == null) {
0295 return EMPTY_ENUMERATION;
0296 } else {
0297 return children.elements();
0298 }
0299 }
0300
0301 /**
0302 * Determines whether or not this node is allowed to have children.
0303 * If <code>allows</code> is false, all of this node's children are
0304 * removed.
0305 * <p>
0306 * Note: By default, a node allows children.
0307 *
0308 * @param allows true if this node is allowed to have children
0309 */
0310 public void setAllowsChildren(boolean allows) {
0311 if (allows != allowsChildren) {
0312 allowsChildren = allows;
0313 if (!allowsChildren) {
0314 removeAllChildren();
0315 }
0316 }
0317 }
0318
0319 /**
0320 * Returns true if this node is allowed to have children.
0321 *
0322 * @return true if this node allows children, else false
0323 */
0324 public boolean getAllowsChildren() {
0325 return allowsChildren;
0326 }
0327
0328 /**
0329 * Sets the user object for this node to <code>userObject</code>.
0330 *
0331 * @param userObject the Object that constitutes this node's
0332 * user-specified data
0333 * @see #getUserObject
0334 * @see #toString
0335 */
0336 public void setUserObject(Object userObject) {
0337 this .userObject = userObject;
0338 }
0339
0340 /**
0341 * Returns this node's user object.
0342 *
0343 * @return the Object stored at this node by the user
0344 * @see #setUserObject
0345 * @see #toString
0346 */
0347 public Object getUserObject() {
0348 return userObject;
0349 }
0350
0351 //
0352 // Derived methods
0353 //
0354
0355 /**
0356 * Removes the subtree rooted at this node from the tree, giving this
0357 * node a null parent. Does nothing if this node is the root of its
0358 * tree.
0359 */
0360 public void removeFromParent() {
0361 MutableTreeNode parent = (MutableTreeNode) getParent();
0362 if (parent != null) {
0363 parent.remove(this );
0364 }
0365 }
0366
0367 /**
0368 * Removes <code>aChild</code> from this node's child array, giving it a
0369 * null parent.
0370 *
0371 * @param aChild a child of this node to remove
0372 * @exception IllegalArgumentException if <code>aChild</code>
0373 * is null or is not a child of this node
0374 */
0375 public void remove(MutableTreeNode aChild) {
0376 if (aChild == null) {
0377 throw new IllegalArgumentException("argument is null");
0378 }
0379
0380 if (!isNodeChild(aChild)) {
0381 throw new IllegalArgumentException(
0382 "argument is not a child");
0383 }
0384 remove(getIndex(aChild)); // linear search
0385 }
0386
0387 /**
0388 * Removes all of this node's children, setting their parents to null.
0389 * If this node has no children, this method does nothing.
0390 */
0391 public void removeAllChildren() {
0392 for (int i = getChildCount() - 1; i >= 0; i--) {
0393 remove(i);
0394 }
0395 }
0396
0397 /**
0398 * Removes <code>newChild</code> from its parent and makes it a child of
0399 * this node by adding it to the end of this node's child array.
0400 *
0401 * @see #insert
0402 * @param newChild node to add as a child of this node
0403 * @exception IllegalArgumentException if <code>newChild</code>
0404 * is null
0405 * @exception IllegalStateException if this node does not allow
0406 * children
0407 */
0408 public void add(MutableTreeNode newChild) {
0409 if (newChild != null && newChild.getParent() == this )
0410 insert(newChild, getChildCount() - 1);
0411 else
0412 insert(newChild, getChildCount());
0413 }
0414
0415 //
0416 // Tree Queries
0417 //
0418
0419 /**
0420 * Returns true if <code>anotherNode</code> is an ancestor of this node
0421 * -- if it is this node, this node's parent, or an ancestor of this
0422 * node's parent. (Note that a node is considered an ancestor of itself.)
0423 * If <code>anotherNode</code> is null, this method returns false. This
0424 * operation is at worst O(h) where h is the distance from the root to
0425 * this node.
0426 *
0427 * @see #isNodeDescendant
0428 * @see #getSharedAncestor
0429 * @param anotherNode node to test as an ancestor of this node
0430 * @return true if this node is a descendant of <code>anotherNode</code>
0431 */
0432 public boolean isNodeAncestor(TreeNode anotherNode) {
0433 if (anotherNode == null) {
0434 return false;
0435 }
0436
0437 TreeNode ancestor = this ;
0438
0439 do {
0440 if (ancestor == anotherNode) {
0441 return true;
0442 }
0443 } while ((ancestor = ancestor.getParent()) != null);
0444
0445 return false;
0446 }
0447
0448 /**
0449 * Returns true if <code>anotherNode</code> is a descendant of this node
0450 * -- if it is this node, one of this node's children, or a descendant of
0451 * one of this node's children. Note that a node is considered a
0452 * descendant of itself. If <code>anotherNode</code> is null, returns
0453 * false. This operation is at worst O(h) where h is the distance from the
0454 * root to <code>anotherNode</code>.
0455 *
0456 * @see #isNodeAncestor
0457 * @see #getSharedAncestor
0458 * @param anotherNode node to test as descendant of this node
0459 * @return true if this node is an ancestor of <code>anotherNode</code>
0460 */
0461 public boolean isNodeDescendant(DefaultMutableTreeNode anotherNode) {
0462 if (anotherNode == null)
0463 return false;
0464
0465 return anotherNode.isNodeAncestor(this );
0466 }
0467
0468 /**
0469 * Returns the nearest common ancestor to this node and <code>aNode</code>.
0470 * Returns null, if no such ancestor exists -- if this node and
0471 * <code>aNode</code> are in different trees or if <code>aNode</code> is
0472 * null. A node is considered an ancestor of itself.
0473 *
0474 * @see #isNodeAncestor
0475 * @see #isNodeDescendant
0476 * @param aNode node to find common ancestor with
0477 * @return nearest ancestor common to this node and <code>aNode</code>,
0478 * or null if none
0479 */
0480 public TreeNode getSharedAncestor(DefaultMutableTreeNode aNode) {
0481 if (aNode == this ) {
0482 return this ;
0483 } else if (aNode == null) {
0484 return null;
0485 }
0486
0487 int level1, level2, diff;
0488 TreeNode node1, node2;
0489
0490 level1 = getLevel();
0491 level2 = aNode.getLevel();
0492
0493 if (level2 > level1) {
0494 diff = level2 - level1;
0495 node1 = aNode;
0496 node2 = this ;
0497 } else {
0498 diff = level1 - level2;
0499 node1 = this ;
0500 node2 = aNode;
0501 }
0502
0503 // Go up the tree until the nodes are at the same level
0504 while (diff > 0) {
0505 node1 = node1.getParent();
0506 diff--;
0507 }
0508
0509 // Move up the tree until we find a common ancestor. Since we know
0510 // that both nodes are at the same level, we won't cross paths
0511 // unknowingly (if there is a common ancestor, both nodes hit it in
0512 // the same iteration).
0513
0514 do {
0515 if (node1 == node2) {
0516 return node1;
0517 }
0518 node1 = node1.getParent();
0519 node2 = node2.getParent();
0520 } while (node1 != null);// only need to check one -- they're at the
0521 // same level so if one is null, the other is
0522
0523 if (node1 != null || node2 != null) {
0524 throw new Error("nodes should be null");
0525 }
0526
0527 return null;
0528 }
0529
0530 /**
0531 * Returns true if and only if <code>aNode</code> is in the same tree
0532 * as this node. Returns false if <code>aNode</code> is null.
0533 *
0534 * @see #getSharedAncestor
0535 * @see #getRoot
0536 * @return true if <code>aNode</code> is in the same tree as this node;
0537 * false if <code>aNode</code> is null
0538 */
0539 public boolean isNodeRelated(DefaultMutableTreeNode aNode) {
0540 return (aNode != null) && (getRoot() == aNode.getRoot());
0541 }
0542
0543 /**
0544 * Returns the depth of the tree rooted at this node -- the longest
0545 * distance from this node to a leaf. If this node has no children,
0546 * returns 0. This operation is much more expensive than
0547 * <code>getLevel()</code> because it must effectively traverse the entire
0548 * tree rooted at this node.
0549 *
0550 * @see #getLevel
0551 * @return the depth of the tree whose root is this node
0552 */
0553 public int getDepth() {
0554 Object last = null;
0555 Enumeration enum_ = breadthFirstEnumeration();
0556
0557 while (enum_.hasMoreElements()) {
0558 last = enum_.nextElement();
0559 }
0560
0561 if (last == null) {
0562 throw new Error("nodes should be null");
0563 }
0564
0565 return ((DefaultMutableTreeNode) last).getLevel() - getLevel();
0566 }
0567
0568 /**
0569 * Returns the number of levels above this node -- the distance from
0570 * the root to this node. If this node is the root, returns 0.
0571 *
0572 * @see #getDepth
0573 * @return the number of levels above this node
0574 */
0575 public int getLevel() {
0576 TreeNode ancestor;
0577 int levels = 0;
0578
0579 ancestor = this ;
0580 while ((ancestor = ancestor.getParent()) != null) {
0581 levels++;
0582 }
0583
0584 return levels;
0585 }
0586
0587 /**
0588 * Returns the path from the root, to get to this node. The last
0589 * element in the path is this node.
0590 *
0591 * @return an array of TreeNode objects giving the path, where the
0592 * first element in the path is the root and the last
0593 * element is this node.
0594 */
0595 public TreeNode[] getPath() {
0596 return getPathToRoot(this , 0);
0597 }
0598
0599 /**
0600 * Builds the parents of node up to and including the root node,
0601 * where the original node is the last element in the returned array.
0602 * The length of the returned array gives the node's depth in the
0603 * tree.
0604 *
0605 * @param aNode the TreeNode to get the path for
0606 * @param depth an int giving the number of steps already taken towards
0607 * the root (on recursive calls), used to size the returned array
0608 * @return an array of TreeNodes giving the path from the root to the
0609 * specified node
0610 */
0611 protected TreeNode[] getPathToRoot(TreeNode aNode, int depth) {
0612 TreeNode[] retNodes;
0613
0614 /* Check for null, in case someone passed in a null node, or
0615 they passed in an element that isn't rooted at root. */
0616 if (aNode == null) {
0617 if (depth == 0)
0618 return null;
0619 else
0620 retNodes = new TreeNode[depth];
0621 } else {
0622 depth++;
0623 retNodes = getPathToRoot(aNode.getParent(), depth);
0624 retNodes[retNodes.length - depth] = aNode;
0625 }
0626 return retNodes;
0627 }
0628
0629 /**
0630 * Returns the user object path, from the root, to get to this node.
0631 * If some of the TreeNodes in the path have null user objects, the
0632 * returned path will contain nulls.
0633 */
0634 public Object[] getUserObjectPath() {
0635 TreeNode[] realPath = getPath();
0636 Object[] retPath = new Object[realPath.length];
0637
0638 for (int counter = 0; counter < realPath.length; counter++)
0639 retPath[counter] = ((DefaultMutableTreeNode) realPath[counter])
0640 .getUserObject();
0641 return retPath;
0642 }
0643
0644 /**
0645 * Returns the root of the tree that contains this node. The root is
0646 * the ancestor with a null parent.
0647 *
0648 * @see #isNodeAncestor
0649 * @return the root of the tree that contains this node
0650 */
0651 public TreeNode getRoot() {
0652 TreeNode ancestor = this ;
0653 TreeNode previous;
0654
0655 do {
0656 previous = ancestor;
0657 ancestor = ancestor.getParent();
0658 } while (ancestor != null);
0659
0660 return previous;
0661 }
0662
0663 /**
0664 * Returns true if this node is the root of the tree. The root is
0665 * the only node in the tree with a null parent; every tree has exactly
0666 * one root.
0667 *
0668 * @return true if this node is the root of its tree
0669 */
0670 public boolean isRoot() {
0671 return getParent() == null;
0672 }
0673
0674 /**
0675 * Returns the node that follows this node in a preorder traversal of this
0676 * node's tree. Returns null if this node is the last node of the
0677 * traversal. This is an inefficient way to traverse the entire tree; use
0678 * an enumeration, instead.
0679 *
0680 * @see #preorderEnumeration
0681 * @return the node that follows this node in a preorder traversal, or
0682 * null if this node is last
0683 */
0684 public DefaultMutableTreeNode getNextNode() {
0685 if (getChildCount() == 0) {
0686 // No children, so look for nextSibling
0687 DefaultMutableTreeNode nextSibling = getNextSibling();
0688
0689 if (nextSibling == null) {
0690 DefaultMutableTreeNode aNode = (DefaultMutableTreeNode) getParent();
0691
0692 do {
0693 if (aNode == null) {
0694 return null;
0695 }
0696
0697 nextSibling = aNode.getNextSibling();
0698 if (nextSibling != null) {
0699 return nextSibling;
0700 }
0701
0702 aNode = (DefaultMutableTreeNode) aNode.getParent();
0703 } while (true);
0704 } else {
0705 return nextSibling;
0706 }
0707 } else {
0708 return (DefaultMutableTreeNode) getChildAt(0);
0709 }
0710 }
0711
0712 /**
0713 * Returns the node that precedes this node in a preorder traversal of
0714 * this node's tree. Returns <code>null</code> if this node is the
0715 * first node of the traversal -- the root of the tree.
0716 * This is an inefficient way to
0717 * traverse the entire tree; use an enumeration, instead.
0718 *
0719 * @see #preorderEnumeration
0720 * @return the node that precedes this node in a preorder traversal, or
0721 * null if this node is the first
0722 */
0723 public DefaultMutableTreeNode getPreviousNode() {
0724 DefaultMutableTreeNode previousSibling;
0725 DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();
0726
0727 if (myParent == null) {
0728 return null;
0729 }
0730
0731 previousSibling = getPreviousSibling();
0732
0733 if (previousSibling != null) {
0734 if (previousSibling.getChildCount() == 0)
0735 return previousSibling;
0736 else
0737 return previousSibling.getLastLeaf();
0738 } else {
0739 return myParent;
0740 }
0741 }
0742
0743 /**
0744 * Creates and returns an enumeration that traverses the subtree rooted at
0745 * this node in preorder. The first node returned by the enumeration's
0746 * <code>nextElement()</code> method is this node.<P>
0747 *
0748 * Modifying the tree by inserting, removing, or moving a node invalidates
0749 * any enumerations created before the modification.
0750 *
0751 * @see #postorderEnumeration
0752 * @return an enumeration for traversing the tree in preorder
0753 */
0754 public Enumeration preorderEnumeration() {
0755 return new PreorderEnumeration(this );
0756 }
0757
0758 /**
0759 * Creates and returns an enumeration that traverses the subtree rooted at
0760 * this node in postorder. The first node returned by the enumeration's
0761 * <code>nextElement()</code> method is the leftmost leaf. This is the
0762 * same as a depth-first traversal.<P>
0763 *
0764 * Modifying the tree by inserting, removing, or moving a node invalidates
0765 * any enumerations created before the modification.
0766 *
0767 * @see #depthFirstEnumeration
0768 * @see #preorderEnumeration
0769 * @return an enumeration for traversing the tree in postorder
0770 */
0771 public Enumeration postorderEnumeration() {
0772 return new PostorderEnumeration(this );
0773 }
0774
0775 /**
0776 * Creates and returns an enumeration that traverses the subtree rooted at
0777 * this node in breadth-first order. The first node returned by the
0778 * enumeration's <code>nextElement()</code> method is this node.<P>
0779 *
0780 * Modifying the tree by inserting, removing, or moving a node invalidates
0781 * any enumerations created before the modification.
0782 *
0783 * @see #depthFirstEnumeration
0784 * @return an enumeration for traversing the tree in breadth-first order
0785 */
0786 public Enumeration breadthFirstEnumeration() {
0787 return new BreadthFirstEnumeration(this );
0788 }
0789
0790 /**
0791 * Creates and returns an enumeration that traverses the subtree rooted at
0792 * this node in depth-first order. The first node returned by the
0793 * enumeration's <code>nextElement()</code> method is the leftmost leaf.
0794 * This is the same as a postorder traversal.<P>
0795 *
0796 * Modifying the tree by inserting, removing, or moving a node invalidates
0797 * any enumerations created before the modification.
0798 *
0799 * @see #breadthFirstEnumeration
0800 * @see #postorderEnumeration
0801 * @return an enumeration for traversing the tree in depth-first order
0802 */
0803 public Enumeration depthFirstEnumeration() {
0804 return postorderEnumeration();
0805 }
0806
0807 /**
0808 * Creates and returns an enumeration that follows the path from
0809 * <code>ancestor</code> to this node. The enumeration's
0810 * <code>nextElement()</code> method first returns <code>ancestor</code>,
0811 * then the child of <code>ancestor</code> that is an ancestor of this
0812 * node, and so on, and finally returns this node. Creation of the
0813 * enumeration is O(m) where m is the number of nodes between this node
0814 * and <code>ancestor</code>, inclusive. Each <code>nextElement()</code>
0815 * message is O(1).<P>
0816 *
0817 * Modifying the tree by inserting, removing, or moving a node invalidates
0818 * any enumerations created before the modification.
0819 *
0820 * @see #isNodeAncestor
0821 * @see #isNodeDescendant
0822 * @exception IllegalArgumentException if <code>ancestor</code> is
0823 * not an ancestor of this node
0824 * @return an enumeration for following the path from an ancestor of
0825 * this node to this one
0826 */
0827 public Enumeration pathFromAncestorEnumeration(TreeNode ancestor) {
0828 return new PathBetweenNodesEnumeration(ancestor, this );
0829 }
0830
0831 //
0832 // Child Queries
0833 //
0834
0835 /**
0836 * Returns true if <code>aNode</code> is a child of this node. If
0837 * <code>aNode</code> is null, this method returns false.
0838 *
0839 * @return true if <code>aNode</code> is a child of this node; false if
0840 * <code>aNode</code> is null
0841 */
0842 public boolean isNodeChild(TreeNode aNode) {
0843 boolean retval;
0844
0845 if (aNode == null) {
0846 retval = false;
0847 } else {
0848 if (getChildCount() == 0) {
0849 retval = false;
0850 } else {
0851 retval = (aNode.getParent() == this );
0852 }
0853 }
0854
0855 return retval;
0856 }
0857
0858 /**
0859 * Returns this node's first child. If this node has no children,
0860 * throws NoSuchElementException.
0861 *
0862 * @return the first child of this node
0863 * @exception NoSuchElementException if this node has no children
0864 */
0865 public TreeNode getFirstChild() {
0866 if (getChildCount() == 0) {
0867 throw new NoSuchElementException("node has no children");
0868 }
0869 return getChildAt(0);
0870 }
0871
0872 /**
0873 * Returns this node's last child. If this node has no children,
0874 * throws NoSuchElementException.
0875 *
0876 * @return the last child of this node
0877 * @exception NoSuchElementException if this node has no children
0878 */
0879 public TreeNode getLastChild() {
0880 if (getChildCount() == 0) {
0881 throw new NoSuchElementException("node has no children");
0882 }
0883 return getChildAt(getChildCount() - 1);
0884 }
0885
0886 /**
0887 * Returns the child in this node's child array that immediately
0888 * follows <code>aChild</code>, which must be a child of this node. If
0889 * <code>aChild</code> is the last child, returns null. This method
0890 * performs a linear search of this node's children for
0891 * <code>aChild</code> and is O(n) where n is the number of children; to
0892 * traverse the entire array of children, use an enumeration instead.
0893 *
0894 * @see #children
0895 * @exception IllegalArgumentException if <code>aChild</code> is
0896 * null or is not a child of this node
0897 * @return the child of this node that immediately follows
0898 * <code>aChild</code>
0899 */
0900 public TreeNode getChildAfter(TreeNode aChild) {
0901 if (aChild == null) {
0902 throw new IllegalArgumentException("argument is null");
0903 }
0904
0905 int index = getIndex(aChild); // linear search
0906
0907 if (index == -1) {
0908 throw new IllegalArgumentException("node is not a child");
0909 }
0910
0911 if (index < getChildCount() - 1) {
0912 return getChildAt(index + 1);
0913 } else {
0914 return null;
0915 }
0916 }
0917
0918 /**
0919 * Returns the child in this node's child array that immediately
0920 * precedes <code>aChild</code>, which must be a child of this node. If
0921 * <code>aChild</code> is the first child, returns null. This method
0922 * performs a linear search of this node's children for <code>aChild</code>
0923 * and is O(n) where n is the number of children.
0924 *
0925 * @exception IllegalArgumentException if <code>aChild</code> is null
0926 * or is not a child of this node
0927 * @return the child of this node that immediately precedes
0928 * <code>aChild</code>
0929 */
0930 public TreeNode getChildBefore(TreeNode aChild) {
0931 if (aChild == null) {
0932 throw new IllegalArgumentException("argument is null");
0933 }
0934
0935 int index = getIndex(aChild); // linear search
0936
0937 if (index == -1) {
0938 throw new IllegalArgumentException(
0939 "argument is not a child");
0940 }
0941
0942 if (index > 0) {
0943 return getChildAt(index - 1);
0944 } else {
0945 return null;
0946 }
0947 }
0948
0949 //
0950 // Sibling Queries
0951 //
0952
0953 /**
0954 * Returns true if <code>anotherNode</code> is a sibling of (has the
0955 * same parent as) this node. A node is its own sibling. If
0956 * <code>anotherNode</code> is null, returns false.
0957 *
0958 * @param anotherNode node to test as sibling of this node
0959 * @return true if <code>anotherNode</code> is a sibling of this node
0960 */
0961 public boolean isNodeSibling(TreeNode anotherNode) {
0962 boolean retval;
0963
0964 if (anotherNode == null) {
0965 retval = false;
0966 } else if (anotherNode == this ) {
0967 retval = true;
0968 } else {
0969 TreeNode myParent = getParent();
0970 retval = (myParent != null && myParent == anotherNode
0971 .getParent());
0972
0973 if (retval
0974 && !((DefaultMutableTreeNode) getParent())
0975 .isNodeChild(anotherNode)) {
0976 throw new Error("sibling has different parent");
0977 }
0978 }
0979
0980 return retval;
0981 }
0982
0983 /**
0984 * Returns the number of siblings of this node. A node is its own sibling
0985 * (if it has no parent or no siblings, this method returns
0986 * <code>1</code>).
0987 *
0988 * @return the number of siblings of this node
0989 */
0990 public int getSiblingCount() {
0991 TreeNode myParent = getParent();
0992
0993 if (myParent == null) {
0994 return 1;
0995 } else {
0996 return myParent.getChildCount();
0997 }
0998 }
0999
1000 /**
1001 * Returns the next sibling of this node in the parent's children array.
1002 * Returns null if this node has no parent or is the parent's last child.
1003 * This method performs a linear search that is O(n) where n is the number
1004 * of children; to traverse the entire array, use the parent's child
1005 * enumeration instead.
1006 *
1007 * @see #children
1008 * @return the sibling of this node that immediately follows this node
1009 */
1010 public DefaultMutableTreeNode getNextSibling() {
1011 DefaultMutableTreeNode retval;
1012
1013 DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();
1014
1015 if (myParent == null) {
1016 retval = null;
1017 } else {
1018 retval = (DefaultMutableTreeNode) myParent
1019 .getChildAfter(this ); // linear search
1020 }
1021
1022 if (retval != null && !isNodeSibling(retval)) {
1023 throw new Error("child of parent is not a sibling");
1024 }
1025
1026 return retval;
1027 }
1028
1029 /**
1030 * Returns the previous sibling of this node in the parent's children
1031 * array. Returns null if this node has no parent or is the parent's
1032 * first child. This method performs a linear search that is O(n) where n
1033 * is the number of children.
1034 *
1035 * @return the sibling of this node that immediately precedes this node
1036 */
1037 public DefaultMutableTreeNode getPreviousSibling() {
1038 DefaultMutableTreeNode retval;
1039
1040 DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();
1041
1042 if (myParent == null) {
1043 retval = null;
1044 } else {
1045 retval = (DefaultMutableTreeNode) myParent
1046 .getChildBefore(this ); // linear search
1047 }
1048
1049 if (retval != null && !isNodeSibling(retval)) {
1050 throw new Error("child of parent is not a sibling");
1051 }
1052
1053 return retval;
1054 }
1055
1056 //
1057 // Leaf Queries
1058 //
1059
1060 /**
1061 * Returns true if this node has no children. To distinguish between
1062 * nodes that have no children and nodes that <i>cannot</i> have
1063 * children (e.g. to distinguish files from empty directories), use this
1064 * method in conjunction with <code>getAllowsChildren</code>
1065 *
1066 * @see #getAllowsChildren
1067 * @return true if this node has no children
1068 */
1069 public boolean isLeaf() {
1070 return (getChildCount() == 0);
1071 }
1072
1073 /**
1074 * Finds and returns the first leaf that is a descendant of this node --
1075 * either this node or its first child's first leaf.
1076 * Returns this node if it is a leaf.
1077 *
1078 * @see #isLeaf
1079 * @see #isNodeDescendant
1080 * @return the first leaf in the subtree rooted at this node
1081 */
1082 public DefaultMutableTreeNode getFirstLeaf() {
1083 DefaultMutableTreeNode node = this ;
1084
1085 while (!node.isLeaf()) {
1086 node = (DefaultMutableTreeNode) node.getFirstChild();
1087 }
1088
1089 return node;
1090 }
1091
1092 /**
1093 * Finds and returns the last leaf that is a descendant of this node --
1094 * either this node or its last child's last leaf.
1095 * Returns this node if it is a leaf.
1096 *
1097 * @see #isLeaf
1098 * @see #isNodeDescendant
1099 * @return the last leaf in the subtree rooted at this node
1100 */
1101 public DefaultMutableTreeNode getLastLeaf() {
1102 DefaultMutableTreeNode node = this ;
1103
1104 while (!node.isLeaf()) {
1105 node = (DefaultMutableTreeNode) node.getLastChild();
1106 }
1107
1108 return node;
1109 }
1110
1111 /**
1112 * Returns the leaf after this node or null if this node is the
1113 * last leaf in the tree.
1114 * <p>
1115 * In this implementation of the <code>MutableNode</code> interface,
1116 * this operation is very inefficient. In order to determine the
1117 * next node, this method first performs a linear search in the
1118 * parent's child-list in order to find the current node.
1119 * <p>
1120 * That implementation makes the operation suitable for short
1121 * traversals from a known position. But to traverse all of the
1122 * leaves in the tree, you should use <code>depthFirstEnumeration</code>
1123 * to enumerate the nodes in the tree and use <code>isLeaf</code>
1124 * on each node to determine which are leaves.
1125 *
1126 * @see #depthFirstEnumeration
1127 * @see #isLeaf
1128 * @return returns the next leaf past this node
1129 */
1130 public DefaultMutableTreeNode getNextLeaf() {
1131 DefaultMutableTreeNode nextSibling;
1132 DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();
1133
1134 if (myParent == null)
1135 return null;
1136
1137 nextSibling = getNextSibling(); // linear search
1138
1139 if (nextSibling != null)
1140 return nextSibling.getFirstLeaf();
1141
1142 return myParent.getNextLeaf(); // tail recursion
1143 }
1144
1145 /**
1146 * Returns the leaf before this node or null if this node is the
1147 * first leaf in the tree.
1148 * <p>
1149 * In this implementation of the <code>MutableNode</code> interface,
1150 * this operation is very inefficient. In order to determine the
1151 * previous node, this method first performs a linear search in the
1152 * parent's child-list in order to find the current node.
1153 * <p>
1154 * That implementation makes the operation suitable for short
1155 * traversals from a known position. But to traverse all of the
1156 * leaves in the tree, you should use <code>depthFirstEnumeration</code>
1157 * to enumerate the nodes in the tree and use <code>isLeaf</code>
1158 * on each node to determine which are leaves.
1159 *
1160 * @see #depthFirstEnumeration
1161 * @see #isLeaf
1162 * @return returns the leaf before this node
1163 */
1164 public DefaultMutableTreeNode getPreviousLeaf() {
1165 DefaultMutableTreeNode previousSibling;
1166 DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();
1167
1168 if (myParent == null)
1169 return null;
1170
1171 previousSibling = getPreviousSibling(); // linear search
1172
1173 if (previousSibling != null)
1174 return previousSibling.getLastLeaf();
1175
1176 return myParent.getPreviousLeaf(); // tail recursion
1177 }
1178
1179 /**
1180 * Returns the total number of leaves that are descendants of this node.
1181 * If this node is a leaf, returns <code>1</code>. This method is O(n)
1182 * where n is the number of descendants of this node.
1183 *
1184 * @see #isNodeAncestor
1185 * @return the number of leaves beneath this node
1186 */
1187 public int getLeafCount() {
1188 int count = 0;
1189
1190 TreeNode node;
1191 Enumeration enum_ = breadthFirstEnumeration(); // order matters not
1192
1193 while (enum_.hasMoreElements()) {
1194 node = (TreeNode) enum_.nextElement();
1195 if (node.isLeaf()) {
1196 count++;
1197 }
1198 }
1199
1200 if (count < 1) {
1201 throw new Error("tree has zero leaves");
1202 }
1203
1204 return count;
1205 }
1206
1207 //
1208 // Overrides
1209 //
1210
1211 /**
1212 * Returns the result of sending <code>toString()</code> to this node's
1213 * user object, or the empty string if the node has no user object.
1214 *
1215 * @see #getUserObject
1216 */
1217 public String toString() {
1218 if (userObject == null) {
1219 return "";
1220 } else {
1221 return userObject.toString();
1222 }
1223 }
1224
1225 /**
1226 * Overridden to make clone public. Returns a shallow copy of this node;
1227 * the new node has no parent or children and has a reference to the same
1228 * user object, if any.
1229 *
1230 * @return a copy of this node
1231 */
1232 public Object clone() {
1233 DefaultMutableTreeNode newNode = null;
1234
1235 try {
1236 newNode = (DefaultMutableTreeNode) super .clone();
1237
1238 // shallow copy -- the new node has no parent or children
1239 newNode.children = null;
1240 newNode.parent = null;
1241
1242 } catch (CloneNotSupportedException e) {
1243 // Won't happen because we implement Cloneable
1244 throw new Error(e.toString());
1245 }
1246
1247 return newNode;
1248 }
1249
1250 // Serialization support.
1251 private void writeObject(ObjectOutputStream s) throws IOException {
1252 Object[] tValues;
1253
1254 s.defaultWriteObject();
1255 // Save the userObject, if its Serializable.
1256 if (userObject != null && userObject instanceof Serializable) {
1257 tValues = new Object[2];
1258 tValues[0] = "userObject";
1259 tValues[1] = userObject;
1260 } else
1261 tValues = new Object[0];
1262 s.writeObject(tValues);
1263 }
1264
1265 private void readObject(ObjectInputStream s) throws IOException,
1266 ClassNotFoundException {
1267 Object[] tValues;
1268
1269 s.defaultReadObject();
1270
1271 tValues = (Object[]) s.readObject();
1272
1273 if (tValues.length > 0 && tValues[0].equals("userObject"))
1274 userObject = tValues[1];
1275 }
1276
1277 final class PreorderEnumeration implements Enumeration<TreeNode> {
1278 protected Stack stack;
1279
1280 public PreorderEnumeration(TreeNode rootNode) {
1281 super ();
1282 Vector v = new Vector(1);
1283 v.addElement(rootNode); // PENDING: don't really need a vector
1284 stack = new Stack();
1285 stack.push(v.elements());
1286 }
1287
1288 public boolean hasMoreElements() {
1289 return (!stack.empty() && ((Enumeration) stack.peek())
1290 .hasMoreElements());
1291 }
1292
1293 public TreeNode nextElement() {
1294 Enumeration enumer = (Enumeration) stack.peek();
1295 TreeNode node = (TreeNode) enumer.nextElement();
1296 Enumeration children = node.children();
1297
1298 if (!enumer.hasMoreElements()) {
1299 stack.pop();
1300 }
1301 if (children.hasMoreElements()) {
1302 stack.push(children);
1303 }
1304 return node;
1305 }
1306
1307 } // End of class PreorderEnumeration
1308
1309 final class PostorderEnumeration implements Enumeration<TreeNode> {
1310 protected TreeNode root;
1311 protected Enumeration<TreeNode> children;
1312 protected Enumeration<TreeNode> subtree;
1313
1314 public PostorderEnumeration(TreeNode rootNode) {
1315 super ();
1316 root = rootNode;
1317 children = root.children();
1318 subtree = EMPTY_ENUMERATION;
1319 }
1320
1321 public boolean hasMoreElements() {
1322 return root != null;
1323 }
1324
1325 public TreeNode nextElement() {
1326 TreeNode retval;
1327
1328 if (subtree.hasMoreElements()) {
1329 retval = subtree.nextElement();
1330 } else if (children.hasMoreElements()) {
1331 subtree = new PostorderEnumeration((TreeNode) children
1332 .nextElement());
1333 retval = subtree.nextElement();
1334 } else {
1335 retval = root;
1336 root = null;
1337 }
1338
1339 return retval;
1340 }
1341
1342 } // End of class PostorderEnumeration
1343
1344 final class BreadthFirstEnumeration implements
1345 Enumeration<TreeNode> {
1346 protected Queue queue;
1347
1348 public BreadthFirstEnumeration(TreeNode rootNode) {
1349 super ();
1350 Vector v = new Vector(1);
1351 v.addElement(rootNode); // PENDING: don't really need a vector
1352 queue = new Queue();
1353 queue.enqueue(v.elements());
1354 }
1355
1356 public boolean hasMoreElements() {
1357 return (!queue.isEmpty() && ((Enumeration) queue
1358 .firstObject()).hasMoreElements());
1359 }
1360
1361 public TreeNode nextElement() {
1362 Enumeration enumer = (Enumeration) queue.firstObject();
1363 TreeNode node = (TreeNode) enumer.nextElement();
1364 Enumeration children = node.children();
1365
1366 if (!enumer.hasMoreElements()) {
1367 queue.dequeue();
1368 }
1369 if (children.hasMoreElements()) {
1370 queue.enqueue(children);
1371 }
1372 return node;
1373 }
1374
1375 // A simple queue with a linked list data structure.
1376 final class Queue {
1377 QNode head; // null if empty
1378 QNode tail;
1379
1380 final class QNode {
1381 public Object object;
1382 public QNode next; // null if end
1383
1384 public QNode(Object object, QNode next) {
1385 this .object = object;
1386 this .next = next;
1387 }
1388 }
1389
1390 public void enqueue(Object anObject) {
1391 if (head == null) {
1392 head = tail = new QNode(anObject, null);
1393 } else {
1394 tail.next = new QNode(anObject, null);
1395 tail = tail.next;
1396 }
1397 }
1398
1399 public Object dequeue() {
1400 if (head == null) {
1401 throw new NoSuchElementException("No more elements");
1402 }
1403
1404 Object retval = head.object;
1405 QNode oldHead = head;
1406 head = head.next;
1407 if (head == null) {
1408 tail = null;
1409 } else {
1410 oldHead.next = null;
1411 }
1412 return retval;
1413 }
1414
1415 public Object firstObject() {
1416 if (head == null) {
1417 throw new NoSuchElementException("No more elements");
1418 }
1419
1420 return head.object;
1421 }
1422
1423 public boolean isEmpty() {
1424 return head == null;
1425 }
1426
1427 } // End of class Queue
1428
1429 } // End of class BreadthFirstEnumeration
1430
1431 final class PathBetweenNodesEnumeration implements
1432 Enumeration<TreeNode> {
1433 protected Stack<TreeNode> stack;
1434
1435 public PathBetweenNodesEnumeration(TreeNode ancestor,
1436 TreeNode descendant) {
1437 super ();
1438
1439 if (ancestor == null || descendant == null) {
1440 throw new IllegalArgumentException("argument is null");
1441 }
1442
1443 TreeNode current;
1444
1445 stack = new Stack<TreeNode>();
1446 stack.push(descendant);
1447
1448 current = descendant;
1449 while (current != ancestor) {
1450 current = current.getParent();
1451 if (current == null && descendant != ancestor) {
1452 throw new IllegalArgumentException("node "
1453 + ancestor + " is not an ancestor of "
1454 + descendant);
1455 }
1456 stack.push(current);
1457 }
1458 }
1459
1460 public boolean hasMoreElements() {
1461 return stack.size() > 0;
1462 }
1463
1464 public TreeNode nextElement() {
1465 try {
1466 return stack.pop();
1467 } catch (EmptyStackException e) {
1468 throw new NoSuchElementException("No more elements");
1469 }
1470 }
1471
1472 } // End of class PathBetweenNodesEnumeration
1473
1474 } // End of class DefaultMutableTreeNode
|