1 /*
   2  * Copyright (c) 1997, 2006, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package javax.swing.tree;
  27    // ISSUE: this class depends on nothing in AWT -- move to java.util?
  28 
  29 import java.io.*;
  30 import java.util.*;
  31 
  32 
  33 /**
  34  * A <code>DefaultMutableTreeNode</code> is a general-purpose node in a tree data
  35  * structure.
  36  * For examples of using default mutable tree nodes, see
  37  * <a
  38  href="http://docs.oracle.com/javase/tutorial/uiswing/components/tree.html">How to Use Trees</a>
  39  * in <em>The Java Tutorial.</em>
  40  *
  41  * <p>
  42  *
  43  * A tree node may have at most one parent and 0 or more children.
  44  * <code>DefaultMutableTreeNode</code> provides operations for examining and modifying a
  45  * node's parent and children and also operations for examining the tree that
  46  * the node is a part of.  A node's tree is the set of all nodes that can be
  47  * reached by starting at the node and following all the possible links to
  48  * parents and children.  A node with no parent is the root of its tree; a
  49  * node with no children is a leaf.  A tree may consist of many subtrees,
  50  * each node acting as the root for its own subtree.
  51  * <p>
  52  * This class provides enumerations for efficiently traversing a tree or
  53  * subtree in various orders or for following the path between two nodes.
  54  * A <code>DefaultMutableTreeNode</code> may also hold a reference to a user object, the
  55  * use of which is left to the user.  Asking a <code>DefaultMutableTreeNode</code> for its
  56  * string representation with <code>toString()</code> returns the string
  57  * representation of its user object.
  58  * <p>
  59  * <b>This is not a thread safe class.</b>If you intend to use
  60  * a DefaultMutableTreeNode (or a tree of TreeNodes) in more than one thread, you
  61  * need to do your own synchronizing. A good convention to adopt is
  62  * synchronizing on the root node of a tree.
  63  * <p>
  64  * While DefaultMutableTreeNode implements the MutableTreeNode interface and
  65  * will allow you to add in any implementation of MutableTreeNode not all
  66  * of the methods in DefaultMutableTreeNode will be applicable to all
  67  * MutableTreeNodes implementations. Especially with some of the enumerations
  68  * that are provided, using some of these methods assumes the
  69  * DefaultMutableTreeNode contains only DefaultMutableNode instances. All
  70  * of the TreeNode/MutableTreeNode methods will behave as defined no
  71  * matter what implementations are added.
  72  *
  73  * <p>
  74  * <strong>Warning:</strong>
  75  * Serialized objects of this class will not be compatible with
  76  * future Swing releases. The current serialization support is
  77  * appropriate for short term storage or RMI between applications running
  78  * the same version of Swing.  As of 1.4, support for long term storage
  79  * of all JavaBeans<sup><font size="-2">TM</font></sup>
  80  * has been added to the <code>java.beans</code> package.
  81  * Please see {@link java.beans.XMLEncoder}.
  82  *
  83  * @see MutableTreeNode
  84  *
  85  * @author Rob Davis
  86  */
  87 public class DefaultMutableTreeNode implements Cloneable,
  88        MutableTreeNode, Serializable
  89 {
  90     private static final long serialVersionUID = -4298474751201349152L;
  91 
  92     /**
  93      * An enumeration that is always empty. This is used when an enumeration
  94      * of a leaf node's children is requested.
  95      */
  96     static public final Enumeration<TreeNode> EMPTY_ENUMERATION
  97         = Collections.emptyEnumeration();
  98 
  99     /** this node's parent, or null if this node has no parent */
 100     protected MutableTreeNode   parent;
 101 
 102     /** array of children, may be null if this node has no children */
 103     protected Vector children;
 104 
 105     /** optional user object */
 106     transient protected Object  userObject;
 107 
 108     /** true if the node is able to have children */
 109     protected boolean           allowsChildren;
 110 
 111 
 112     /**
 113      * Creates a tree node that has no parent and no children, but which
 114      * allows children.
 115      */
 116     public DefaultMutableTreeNode() {
 117         this(null);
 118     }
 119 
 120     /**
 121      * Creates a tree node with no parent, no children, but which allows
 122      * children, and initializes it with the specified user object.
 123      *
 124      * @param userObject an Object provided by the user that constitutes
 125      *                   the node's data
 126      */
 127     public DefaultMutableTreeNode(Object userObject) {
 128         this(userObject, true);
 129     }
 130 
 131     /**
 132      * Creates a tree node with no parent, no children, initialized with
 133      * the specified user object, and that allows children only if
 134      * specified.
 135      *
 136      * @param userObject an Object provided by the user that constitutes
 137      *        the node's data
 138      * @param allowsChildren if true, the node is allowed to have child
 139      *        nodes -- otherwise, it is always a leaf node
 140      */
 141     public DefaultMutableTreeNode(Object userObject, boolean allowsChildren) {
 142         super();
 143         parent = null;
 144         this.allowsChildren = allowsChildren;
 145         this.userObject = userObject;
 146     }
 147 
 148 
 149     //
 150     //  Primitives
 151     //
 152 
 153     /**
 154      * Removes <code>newChild</code> from its present parent (if it has a
 155      * parent), sets the child's parent to this node, and then adds the child
 156      * to this node's child array at index <code>childIndex</code>.
 157      * <code>newChild</code> must not be null and must not be an ancestor of
 158      * this node.
 159      *
 160      * @param   newChild        the MutableTreeNode to insert under this node
 161      * @param   childIndex      the index in this node's child array
 162      *                          where this node is to be inserted
 163      * @exception       ArrayIndexOutOfBoundsException  if
 164      *                          <code>childIndex</code> is out of bounds
 165      * @exception       IllegalArgumentException        if
 166      *                          <code>newChild</code> is null or is an
 167      *                          ancestor of this node
 168      * @exception       IllegalStateException   if this node does not allow
 169      *                                          children
 170      * @see     #isNodeDescendant
 171      */
 172     public void insert(MutableTreeNode newChild, int childIndex) {
 173         if (!allowsChildren) {
 174             throw new IllegalStateException("node does not allow children");
 175         } else if (newChild == null) {
 176             throw new IllegalArgumentException("new child is null");
 177         } else if (isNodeAncestor(newChild)) {
 178             throw new IllegalArgumentException("new child is an ancestor");
 179         }
 180 
 181             MutableTreeNode oldParent = (MutableTreeNode)newChild.getParent();
 182 
 183             if (oldParent != null) {
 184                 oldParent.remove(newChild);
 185             }
 186             newChild.setParent(this);
 187             if (children == null) {
 188                 children = new Vector();
 189             }
 190             children.insertElementAt(newChild, childIndex);
 191     }
 192 
 193     /**
 194      * Removes the child at the specified index from this node's children
 195      * and sets that node's parent to null. The child node to remove
 196      * must be a <code>MutableTreeNode</code>.
 197      *
 198      * @param   childIndex      the index in this node's child array
 199      *                          of the child to remove
 200      * @exception       ArrayIndexOutOfBoundsException  if
 201      *                          <code>childIndex</code> is out of bounds
 202      */
 203     public void remove(int childIndex) {
 204         MutableTreeNode child = (MutableTreeNode)getChildAt(childIndex);
 205         children.removeElementAt(childIndex);
 206         child.setParent(null);
 207     }
 208 
 209     /**
 210      * Sets this node's parent to <code>newParent</code> but does not
 211      * change the parent's child array.  This method is called from
 212      * <code>insert()</code> and <code>remove()</code> to
 213      * reassign a child's parent, it should not be messaged from anywhere
 214      * else.
 215      *
 216      * @param   newParent       this node's new parent
 217      */
 218     public void setParent(MutableTreeNode newParent) {
 219         parent = newParent;
 220     }
 221 
 222     /**
 223      * Returns this node's parent or null if this node has no parent.
 224      *
 225      * @return  this node's parent TreeNode, or null if this node has no parent
 226      */
 227     public TreeNode getParent() {
 228         return parent;
 229     }
 230 
 231     /**
 232      * Returns the child at the specified index in this node's child array.
 233      *
 234      * @param   index   an index into this node's child array
 235      * @exception       ArrayIndexOutOfBoundsException  if <code>index</code>
 236      *                                          is out of bounds
 237      * @return  the TreeNode in this node's child array at  the specified index
 238      */
 239     public TreeNode getChildAt(int index) {
 240         if (children == null) {
 241             throw new ArrayIndexOutOfBoundsException("node has no children");
 242         }
 243         return (TreeNode)children.elementAt(index);
 244     }
 245 
 246     /**
 247      * Returns the number of children of this node.
 248      *
 249      * @return  an int giving the number of children of this node
 250      */
 251     public int getChildCount() {
 252         if (children == null) {
 253             return 0;
 254         } else {
 255             return children.size();
 256         }
 257     }
 258 
 259     /**
 260      * Returns the index of the specified child in this node's child array.
 261      * If the specified node is not a child of this node, returns
 262      * <code>-1</code>.  This method performs a linear search and is O(n)
 263      * where n is the number of children.
 264      *
 265      * @param   aChild  the TreeNode to search for among this node's children
 266      * @exception       IllegalArgumentException        if <code>aChild</code>
 267      *                                                  is null
 268      * @return  an int giving the index of the node in this node's child
 269      *          array, or <code>-1</code> if the specified node is a not
 270      *          a child of this node
 271      */
 272     public int getIndex(TreeNode aChild) {
 273         if (aChild == null) {
 274             throw new IllegalArgumentException("argument is null");
 275         }
 276 
 277         if (!isNodeChild(aChild)) {
 278             return -1;
 279         }
 280         return children.indexOf(aChild);        // linear search
 281     }
 282 
 283     /**
 284      * Creates and returns a forward-order enumeration of this node's
 285      * children.  Modifying this node's child array invalidates any child
 286      * enumerations created before the modification.
 287      *
 288      * @return  an Enumeration of this node's children
 289      */
 290     public Enumeration children() {
 291         if (children == null) {
 292             return EMPTY_ENUMERATION;
 293         } else {
 294             return children.elements();
 295         }
 296     }
 297 
 298     /**
 299      * Determines whether or not this node is allowed to have children.
 300      * If <code>allows</code> is false, all of this node's children are
 301      * removed.
 302      * <p>
 303      * Note: By default, a node allows children.
 304      *
 305      * @param   allows  true if this node is allowed to have children
 306      */
 307     public void setAllowsChildren(boolean allows) {
 308         if (allows != allowsChildren) {
 309             allowsChildren = allows;
 310             if (!allowsChildren) {
 311                 removeAllChildren();
 312             }
 313         }
 314     }
 315 
 316     /**
 317      * Returns true if this node is allowed to have children.
 318      *
 319      * @return  true if this node allows children, else false
 320      */
 321     public boolean getAllowsChildren() {
 322         return allowsChildren;
 323     }
 324 
 325     /**
 326      * Sets the user object for this node to <code>userObject</code>.
 327      *
 328      * @param   userObject      the Object that constitutes this node's
 329      *                          user-specified data
 330      * @see     #getUserObject
 331      * @see     #toString
 332      */
 333     public void setUserObject(Object userObject) {
 334         this.userObject = userObject;
 335     }
 336 
 337     /**
 338      * Returns this node's user object.
 339      *
 340      * @return  the Object stored at this node by the user
 341      * @see     #setUserObject
 342      * @see     #toString
 343      */
 344     public Object getUserObject() {
 345         return userObject;
 346     }
 347 
 348 
 349     //
 350     //  Derived methods
 351     //
 352 
 353     /**
 354      * Removes the subtree rooted at this node from the tree, giving this
 355      * node a null parent.  Does nothing if this node is the root of its
 356      * tree.
 357      */
 358     public void removeFromParent() {
 359         MutableTreeNode parent = (MutableTreeNode)getParent();
 360         if (parent != null) {
 361             parent.remove(this);
 362         }
 363     }
 364 
 365     /**
 366      * Removes <code>aChild</code> from this node's child array, giving it a
 367      * null parent.
 368      *
 369      * @param   aChild  a child of this node to remove
 370      * @exception       IllegalArgumentException        if <code>aChild</code>
 371      *                                  is null or is not a child of this node
 372      */
 373     public void remove(MutableTreeNode aChild) {
 374         if (aChild == null) {
 375             throw new IllegalArgumentException("argument is null");
 376         }
 377 
 378         if (!isNodeChild(aChild)) {
 379             throw new IllegalArgumentException("argument is not a child");
 380         }
 381         remove(getIndex(aChild));       // linear search
 382     }
 383 
 384     /**
 385      * Removes all of this node's children, setting their parents to null.
 386      * If this node has no children, this method does nothing.
 387      */
 388     public void removeAllChildren() {
 389         for (int i = getChildCount()-1; i >= 0; i--) {
 390             remove(i);
 391         }
 392     }
 393 
 394     /**
 395      * Removes <code>newChild</code> from its parent and makes it a child of
 396      * this node by adding it to the end of this node's child array.
 397      *
 398      * @see             #insert
 399      * @param   newChild        node to add as a child of this node
 400      * @exception       IllegalArgumentException    if <code>newChild</code>
 401      *                                          is null
 402      * @exception       IllegalStateException   if this node does not allow
 403      *                                          children
 404      */
 405     public void add(MutableTreeNode newChild) {
 406         if(newChild != null && newChild.getParent() == this)
 407             insert(newChild, getChildCount() - 1);
 408         else
 409             insert(newChild, getChildCount());
 410     }
 411 
 412 
 413 
 414     //
 415     //  Tree Queries
 416     //
 417 
 418     /**
 419      * Returns true if <code>anotherNode</code> is an ancestor of this node
 420      * -- if it is this node, this node's parent, or an ancestor of this
 421      * node's parent.  (Note that a node is considered an ancestor of itself.)
 422      * If <code>anotherNode</code> is null, this method returns false.  This
 423      * operation is at worst O(h) where h is the distance from the root to
 424      * this node.
 425      *
 426      * @see             #isNodeDescendant
 427      * @see             #getSharedAncestor
 428      * @param   anotherNode     node to test as an ancestor of this node
 429      * @return  true if this node is a descendant of <code>anotherNode</code>
 430      */
 431     public boolean isNodeAncestor(TreeNode anotherNode) {
 432         if (anotherNode == null) {
 433             return false;
 434         }
 435 
 436         TreeNode ancestor = this;
 437 
 438         do {
 439             if (ancestor == anotherNode) {
 440                 return true;
 441             }
 442         } while((ancestor = ancestor.getParent()) != null);
 443 
 444         return false;
 445     }
 446 
 447     /**
 448      * Returns true if <code>anotherNode</code> is a descendant of this node
 449      * -- if it is this node, one of this node's children, or a descendant of
 450      * one of this node's children.  Note that a node is considered a
 451      * descendant of itself.  If <code>anotherNode</code> is null, returns
 452      * false.  This operation is at worst O(h) where h is the distance from the
 453      * root to <code>anotherNode</code>.
 454      *
 455      * @see     #isNodeAncestor
 456      * @see     #getSharedAncestor
 457      * @param   anotherNode     node to test as descendant of this node
 458      * @return  true if this node is an ancestor of <code>anotherNode</code>
 459      */
 460     public boolean isNodeDescendant(DefaultMutableTreeNode anotherNode) {
 461         if (anotherNode == null)
 462             return false;
 463 
 464         return anotherNode.isNodeAncestor(this);
 465     }
 466 
 467     /**
 468      * Returns the nearest common ancestor to this node and <code>aNode</code>.
 469      * Returns null, if no such ancestor exists -- if this node and
 470      * <code>aNode</code> are in different trees or if <code>aNode</code> is
 471      * null.  A node is considered an ancestor of itself.
 472      *
 473      * @see     #isNodeAncestor
 474      * @see     #isNodeDescendant
 475      * @param   aNode   node to find common ancestor with
 476      * @return  nearest ancestor common to this node and <code>aNode</code>,
 477      *          or null if none
 478      */
 479     public TreeNode getSharedAncestor(DefaultMutableTreeNode aNode) {
 480         if (aNode == this) {
 481             return this;
 482         } else if (aNode == null) {
 483             return null;
 484         }
 485 
 486         int             level1, level2, diff;
 487         TreeNode        node1, node2;
 488 
 489         level1 = getLevel();
 490         level2 = aNode.getLevel();
 491 
 492         if (level2 > level1) {
 493             diff = level2 - level1;
 494             node1 = aNode;
 495             node2 = this;
 496         } else {
 497             diff = level1 - level2;
 498             node1 = this;
 499             node2 = aNode;
 500         }
 501 
 502         // Go up the tree until the nodes are at the same level
 503         while (diff > 0) {
 504             node1 = node1.getParent();
 505             diff--;
 506         }
 507 
 508         // Move up the tree until we find a common ancestor.  Since we know
 509         // that both nodes are at the same level, we won't cross paths
 510         // unknowingly (if there is a common ancestor, both nodes hit it in
 511         // the same iteration).
 512 
 513         do {
 514             if (node1 == node2) {
 515                 return node1;
 516             }
 517             node1 = node1.getParent();
 518             node2 = node2.getParent();
 519         } while (node1 != null);// only need to check one -- they're at the
 520         // same level so if one is null, the other is
 521 
 522         if (node1 != null || node2 != null) {
 523             throw new Error ("nodes should be null");
 524         }
 525 
 526         return null;
 527     }
 528 
 529 
 530     /**
 531      * Returns true if and only if <code>aNode</code> is in the same tree
 532      * as this node.  Returns false if <code>aNode</code> is null.
 533      *
 534      * @see     #getSharedAncestor
 535      * @see     #getRoot
 536      * @return  true if <code>aNode</code> is in the same tree as this node;
 537      *          false if <code>aNode</code> is null
 538      */
 539     public boolean isNodeRelated(DefaultMutableTreeNode aNode) {
 540         return (aNode != null) && (getRoot() == aNode.getRoot());
 541     }
 542 
 543 
 544     /**
 545      * Returns the depth of the tree rooted at this node -- the longest
 546      * distance from this node to a leaf.  If this node has no children,
 547      * returns 0.  This operation is much more expensive than
 548      * <code>getLevel()</code> because it must effectively traverse the entire
 549      * tree rooted at this node.
 550      *
 551      * @see     #getLevel
 552      * @return  the depth of the tree whose root is this node
 553      */
 554     public int getDepth() {
 555         Object  last = null;
 556         Enumeration     enum_ = breadthFirstEnumeration();
 557 
 558         while (enum_.hasMoreElements()) {
 559             last = enum_.nextElement();
 560         }
 561 
 562         if (last == null) {
 563             throw new Error ("nodes should be null");
 564         }
 565 
 566         return ((DefaultMutableTreeNode)last).getLevel() - getLevel();
 567     }
 568 
 569 
 570 
 571     /**
 572      * Returns the number of levels above this node -- the distance from
 573      * the root to this node.  If this node is the root, returns 0.
 574      *
 575      * @see     #getDepth
 576      * @return  the number of levels above this node
 577      */
 578     public int getLevel() {
 579         TreeNode ancestor;
 580         int levels = 0;
 581 
 582         ancestor = this;
 583         while((ancestor = ancestor.getParent()) != null){
 584             levels++;
 585         }
 586 
 587         return levels;
 588     }
 589 
 590 
 591     /**
 592       * Returns the path from the root, to get to this node.  The last
 593       * element in the path is this node.
 594       *
 595       * @return an array of TreeNode objects giving the path, where the
 596       *         first element in the path is the root and the last
 597       *         element is this node.
 598       */
 599     public TreeNode[] getPath() {
 600         return getPathToRoot(this, 0);
 601     }
 602 
 603     /**
 604      * Builds the parents of node up to and including the root node,
 605      * where the original node is the last element in the returned array.
 606      * The length of the returned array gives the node's depth in the
 607      * tree.
 608      *
 609      * @param aNode  the TreeNode to get the path for
 610      * @param depth  an int giving the number of steps already taken towards
 611      *        the root (on recursive calls), used to size the returned array
 612      * @return an array of TreeNodes giving the path from the root to the
 613      *         specified node
 614      */
 615     protected TreeNode[] getPathToRoot(TreeNode aNode, int depth) {
 616         TreeNode[]              retNodes;
 617 
 618         /* Check for null, in case someone passed in a null node, or
 619            they passed in an element that isn't rooted at root. */
 620         if(aNode == null) {
 621             if(depth == 0)
 622                 return null;
 623             else
 624                 retNodes = new TreeNode[depth];
 625         }
 626         else {
 627             depth++;
 628             retNodes = getPathToRoot(aNode.getParent(), depth);
 629             retNodes[retNodes.length - depth] = aNode;
 630         }
 631         return retNodes;
 632     }
 633 
 634     /**
 635       * Returns the user object path, from the root, to get to this node.
 636       * If some of the TreeNodes in the path have null user objects, the
 637       * returned path will contain nulls.
 638       */
 639     public Object[] getUserObjectPath() {
 640         TreeNode[]          realPath = getPath();
 641         Object[]            retPath = new Object[realPath.length];
 642 
 643         for(int counter = 0; counter < realPath.length; counter++)
 644             retPath[counter] = ((DefaultMutableTreeNode)realPath[counter])
 645                                .getUserObject();
 646         return retPath;
 647     }
 648 
 649     /**
 650      * Returns the root of the tree that contains this node.  The root is
 651      * the ancestor with a null parent.
 652      *
 653      * @see     #isNodeAncestor
 654      * @return  the root of the tree that contains this node
 655      */
 656     public TreeNode getRoot() {
 657         TreeNode ancestor = this;
 658         TreeNode previous;
 659 
 660         do {
 661             previous = ancestor;
 662             ancestor = ancestor.getParent();
 663         } while (ancestor != null);
 664 
 665         return previous;
 666     }
 667 
 668 
 669     /**
 670      * Returns true if this node is the root of the tree.  The root is
 671      * the only node in the tree with a null parent; every tree has exactly
 672      * one root.
 673      *
 674      * @return  true if this node is the root of its tree
 675      */
 676     public boolean isRoot() {
 677         return getParent() == null;
 678     }
 679 
 680 
 681     /**
 682      * Returns the node that follows this node in a preorder traversal of this
 683      * node's tree.  Returns null if this node is the last node of the
 684      * traversal.  This is an inefficient way to traverse the entire tree; use
 685      * an enumeration, instead.
 686      *
 687      * @see     #preorderEnumeration
 688      * @return  the node that follows this node in a preorder traversal, or
 689      *          null if this node is last
 690      */
 691     public DefaultMutableTreeNode getNextNode() {
 692         if (getChildCount() == 0) {
 693             // No children, so look for nextSibling
 694             DefaultMutableTreeNode nextSibling = getNextSibling();
 695 
 696             if (nextSibling == null) {
 697                 DefaultMutableTreeNode aNode = (DefaultMutableTreeNode)getParent();
 698 
 699                 do {
 700                     if (aNode == null) {
 701                         return null;
 702                     }
 703 
 704                     nextSibling = aNode.getNextSibling();
 705                     if (nextSibling != null) {
 706                         return nextSibling;
 707                     }
 708 
 709                     aNode = (DefaultMutableTreeNode)aNode.getParent();
 710                 } while(true);
 711             } else {
 712                 return nextSibling;
 713             }
 714         } else {
 715             return (DefaultMutableTreeNode)getChildAt(0);
 716         }
 717     }
 718 
 719 
 720     /**
 721      * Returns the node that precedes this node in a preorder traversal of
 722      * this node's tree.  Returns <code>null</code> if this node is the
 723      * first node of the traversal -- the root of the tree.
 724      * This is an inefficient way to
 725      * traverse the entire tree; use an enumeration, instead.
 726      *
 727      * @see     #preorderEnumeration
 728      * @return  the node that precedes this node in a preorder traversal, or
 729      *          null if this node is the first
 730      */
 731     public DefaultMutableTreeNode getPreviousNode() {
 732         DefaultMutableTreeNode previousSibling;
 733         DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent();
 734 
 735         if (myParent == null) {
 736             return null;
 737         }
 738 
 739         previousSibling = getPreviousSibling();
 740 
 741         if (previousSibling != null) {
 742             if (previousSibling.getChildCount() == 0)
 743                 return previousSibling;
 744             else
 745                 return previousSibling.getLastLeaf();
 746         } else {
 747             return myParent;
 748         }
 749     }
 750 
 751     /**
 752      * Creates and returns an enumeration that traverses the subtree rooted at
 753      * this node in preorder.  The first node returned by the enumeration's
 754      * <code>nextElement()</code> method is this node.<P>
 755      *
 756      * Modifying the tree by inserting, removing, or moving a node invalidates
 757      * any enumerations created before the modification.
 758      *
 759      * @see     #postorderEnumeration
 760      * @return  an enumeration for traversing the tree in preorder
 761      */
 762     public Enumeration preorderEnumeration() {
 763         return new PreorderEnumeration(this);
 764     }
 765 
 766     /**
 767      * Creates and returns an enumeration that traverses the subtree rooted at
 768      * this node in postorder.  The first node returned by the enumeration's
 769      * <code>nextElement()</code> method is the leftmost leaf.  This is the
 770      * same as a depth-first traversal.<P>
 771      *
 772      * Modifying the tree by inserting, removing, or moving a node invalidates
 773      * any enumerations created before the modification.
 774      *
 775      * @see     #depthFirstEnumeration
 776      * @see     #preorderEnumeration
 777      * @return  an enumeration for traversing the tree in postorder
 778      */
 779     public Enumeration postorderEnumeration() {
 780         return new PostorderEnumeration(this);
 781     }
 782 
 783     /**
 784      * Creates and returns an enumeration that traverses the subtree rooted at
 785      * this node in breadth-first order.  The first node returned by the
 786      * enumeration's <code>nextElement()</code> method is this node.<P>
 787      *
 788      * Modifying the tree by inserting, removing, or moving a node invalidates
 789      * any enumerations created before the modification.
 790      *
 791      * @see     #depthFirstEnumeration
 792      * @return  an enumeration for traversing the tree in breadth-first order
 793      */
 794     public Enumeration breadthFirstEnumeration() {
 795         return new BreadthFirstEnumeration(this);
 796     }
 797 
 798     /**
 799      * Creates and returns an enumeration that traverses the subtree rooted at
 800      * this node in depth-first order.  The first node returned by the
 801      * enumeration's <code>nextElement()</code> method is the leftmost leaf.
 802      * This is the same as a postorder traversal.<P>
 803      *
 804      * Modifying the tree by inserting, removing, or moving a node invalidates
 805      * any enumerations created before the modification.
 806      *
 807      * @see     #breadthFirstEnumeration
 808      * @see     #postorderEnumeration
 809      * @return  an enumeration for traversing the tree in depth-first order
 810      */
 811     public Enumeration depthFirstEnumeration() {
 812         return postorderEnumeration();
 813     }
 814 
 815     /**
 816      * Creates and returns an enumeration that follows the path from
 817      * <code>ancestor</code> to this node.  The enumeration's
 818      * <code>nextElement()</code> method first returns <code>ancestor</code>,
 819      * then the child of <code>ancestor</code> that is an ancestor of this
 820      * node, and so on, and finally returns this node.  Creation of the
 821      * enumeration is O(m) where m is the number of nodes between this node
 822      * and <code>ancestor</code>, inclusive.  Each <code>nextElement()</code>
 823      * message is O(1).<P>
 824      *
 825      * Modifying the tree by inserting, removing, or moving a node invalidates
 826      * any enumerations created before the modification.
 827      *
 828      * @see             #isNodeAncestor
 829      * @see             #isNodeDescendant
 830      * @exception       IllegalArgumentException if <code>ancestor</code> is
 831      *                                          not an ancestor of this node
 832      * @return  an enumeration for following the path from an ancestor of
 833      *          this node to this one
 834      */
 835     public Enumeration pathFromAncestorEnumeration(TreeNode ancestor) {
 836         return new PathBetweenNodesEnumeration(ancestor, this);
 837     }
 838 
 839 
 840     //
 841     //  Child Queries
 842     //
 843 
 844     /**
 845      * Returns true if <code>aNode</code> is a child of this node.  If
 846      * <code>aNode</code> is null, this method returns false.
 847      *
 848      * @return  true if <code>aNode</code> is a child of this node; false if
 849      *                  <code>aNode</code> is null
 850      */
 851     public boolean isNodeChild(TreeNode aNode) {
 852         boolean retval;
 853 
 854         if (aNode == null) {
 855             retval = false;
 856         } else {
 857             if (getChildCount() == 0) {
 858                 retval = false;
 859             } else {
 860                 retval = (aNode.getParent() == this);
 861             }
 862         }
 863 
 864         return retval;
 865     }
 866 
 867 
 868     /**
 869      * Returns this node's first child.  If this node has no children,
 870      * throws NoSuchElementException.
 871      *
 872      * @return  the first child of this node
 873      * @exception       NoSuchElementException  if this node has no children
 874      */
 875     public TreeNode getFirstChild() {
 876         if (getChildCount() == 0) {
 877             throw new NoSuchElementException("node has no children");
 878         }
 879         return getChildAt(0);
 880     }
 881 
 882 
 883     /**
 884      * Returns this node's last child.  If this node has no children,
 885      * throws NoSuchElementException.
 886      *
 887      * @return  the last child of this node
 888      * @exception       NoSuchElementException  if this node has no children
 889      */
 890     public TreeNode getLastChild() {
 891         if (getChildCount() == 0) {
 892             throw new NoSuchElementException("node has no children");
 893         }
 894         return getChildAt(getChildCount()-1);
 895     }
 896 
 897 
 898     /**
 899      * Returns the child in this node's child array that immediately
 900      * follows <code>aChild</code>, which must be a child of this node.  If
 901      * <code>aChild</code> is the last child, returns null.  This method
 902      * performs a linear search of this node's children for
 903      * <code>aChild</code> and is O(n) where n is the number of children; to
 904      * traverse the entire array of children, use an enumeration instead.
 905      *
 906      * @see             #children
 907      * @exception       IllegalArgumentException if <code>aChild</code> is
 908      *                                  null or is not a child of this node
 909      * @return  the child of this node that immediately follows
 910      *          <code>aChild</code>
 911      */
 912     public TreeNode getChildAfter(TreeNode aChild) {
 913         if (aChild == null) {
 914             throw new IllegalArgumentException("argument is null");
 915         }
 916 
 917         int index = getIndex(aChild);           // linear search
 918 
 919         if (index == -1) {
 920             throw new IllegalArgumentException("node is not a child");
 921         }
 922 
 923         if (index < getChildCount() - 1) {
 924             return getChildAt(index + 1);
 925         } else {
 926             return null;
 927         }
 928     }
 929 
 930 
 931     /**
 932      * Returns the child in this node's child array that immediately
 933      * precedes <code>aChild</code>, which must be a child of this node.  If
 934      * <code>aChild</code> is the first child, returns null.  This method
 935      * performs a linear search of this node's children for <code>aChild</code>
 936      * and is O(n) where n is the number of children.
 937      *
 938      * @exception       IllegalArgumentException if <code>aChild</code> is null
 939      *                                          or is not a child of this node
 940      * @return  the child of this node that immediately precedes
 941      *          <code>aChild</code>
 942      */
 943     public TreeNode getChildBefore(TreeNode aChild) {
 944         if (aChild == null) {
 945             throw new IllegalArgumentException("argument is null");
 946         }
 947 
 948         int index = getIndex(aChild);           // linear search
 949 
 950         if (index == -1) {
 951             throw new IllegalArgumentException("argument is not a child");
 952         }
 953 
 954         if (index > 0) {
 955             return getChildAt(index - 1);
 956         } else {
 957             return null;
 958         }
 959     }
 960 
 961 
 962     //
 963     //  Sibling Queries
 964     //
 965 
 966 
 967     /**
 968      * Returns true if <code>anotherNode</code> is a sibling of (has the
 969      * same parent as) this node.  A node is its own sibling.  If
 970      * <code>anotherNode</code> is null, returns false.
 971      *
 972      * @param   anotherNode     node to test as sibling of this node
 973      * @return  true if <code>anotherNode</code> is a sibling of this node
 974      */
 975     public boolean isNodeSibling(TreeNode anotherNode) {
 976         boolean retval;
 977 
 978         if (anotherNode == null) {
 979             retval = false;
 980         } else if (anotherNode == this) {
 981             retval = true;
 982         } else {
 983             TreeNode  myParent = getParent();
 984             retval = (myParent != null && myParent == anotherNode.getParent());
 985 
 986             if (retval && !((DefaultMutableTreeNode)getParent())
 987                            .isNodeChild(anotherNode)) {
 988                 throw new Error("sibling has different parent");
 989             }
 990         }
 991 
 992         return retval;
 993     }
 994 
 995 
 996     /**
 997      * Returns the number of siblings of this node.  A node is its own sibling
 998      * (if it has no parent or no siblings, this method returns
 999      * <code>1</code>).
1000      *
1001      * @return  the number of siblings of this node
1002      */
1003     public int getSiblingCount() {
1004         TreeNode myParent = getParent();
1005 
1006         if (myParent == null) {
1007             return 1;
1008         } else {
1009             return myParent.getChildCount();
1010         }
1011     }
1012 
1013 
1014     /**
1015      * Returns the next sibling of this node in the parent's children array.
1016      * Returns null if this node has no parent or is the parent's last child.
1017      * This method performs a linear search that is O(n) where n is the number
1018      * of children; to traverse the entire array, use the parent's child
1019      * enumeration instead.
1020      *
1021      * @see     #children
1022      * @return  the sibling of this node that immediately follows this node
1023      */
1024     public DefaultMutableTreeNode getNextSibling() {
1025         DefaultMutableTreeNode retval;
1026 
1027         DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent();
1028 
1029         if (myParent == null) {
1030             retval = null;
1031         } else {
1032             retval = (DefaultMutableTreeNode)myParent.getChildAfter(this);      // linear search
1033         }
1034 
1035         if (retval != null && !isNodeSibling(retval)) {
1036             throw new Error("child of parent is not a sibling");
1037         }
1038 
1039         return retval;
1040     }
1041 
1042 
1043     /**
1044      * Returns the previous sibling of this node in the parent's children
1045      * array.  Returns null if this node has no parent or is the parent's
1046      * first child.  This method performs a linear search that is O(n) where n
1047      * is the number of children.
1048      *
1049      * @return  the sibling of this node that immediately precedes this node
1050      */
1051     public DefaultMutableTreeNode getPreviousSibling() {
1052         DefaultMutableTreeNode retval;
1053 
1054         DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent();
1055 
1056         if (myParent == null) {
1057             retval = null;
1058         } else {
1059             retval = (DefaultMutableTreeNode)myParent.getChildBefore(this);     // linear search
1060         }
1061 
1062         if (retval != null && !isNodeSibling(retval)) {
1063             throw new Error("child of parent is not a sibling");
1064         }
1065 
1066         return retval;
1067     }
1068 
1069 
1070 
1071     //
1072     //  Leaf Queries
1073     //
1074 
1075     /**
1076      * Returns true if this node has no children.  To distinguish between
1077      * nodes that have no children and nodes that <i>cannot</i> have
1078      * children (e.g. to distinguish files from empty directories), use this
1079      * method in conjunction with <code>getAllowsChildren</code>
1080      *
1081      * @see     #getAllowsChildren
1082      * @return  true if this node has no children
1083      */
1084     public boolean isLeaf() {
1085         return (getChildCount() == 0);
1086     }
1087 
1088 
1089     /**
1090      * Finds and returns the first leaf that is a descendant of this node --
1091      * either this node or its first child's first leaf.
1092      * Returns this node if it is a leaf.
1093      *
1094      * @see     #isLeaf
1095      * @see     #isNodeDescendant
1096      * @return  the first leaf in the subtree rooted at this node
1097      */
1098     public DefaultMutableTreeNode getFirstLeaf() {
1099         DefaultMutableTreeNode node = this;
1100 
1101         while (!node.isLeaf()) {
1102             node = (DefaultMutableTreeNode)node.getFirstChild();
1103         }
1104 
1105         return node;
1106     }
1107 
1108 
1109     /**
1110      * Finds and returns the last leaf that is a descendant of this node --
1111      * either this node or its last child's last leaf.
1112      * Returns this node if it is a leaf.
1113      *
1114      * @see     #isLeaf
1115      * @see     #isNodeDescendant
1116      * @return  the last leaf in the subtree rooted at this node
1117      */
1118     public DefaultMutableTreeNode getLastLeaf() {
1119         DefaultMutableTreeNode node = this;
1120 
1121         while (!node.isLeaf()) {
1122             node = (DefaultMutableTreeNode)node.getLastChild();
1123         }
1124 
1125         return node;
1126     }
1127 
1128 
1129     /**
1130      * Returns the leaf after this node or null if this node is the
1131      * last leaf in the tree.
1132      * <p>
1133      * In this implementation of the <code>MutableNode</code> interface,
1134      * this operation is very inefficient. In order to determine the
1135      * next node, this method first performs a linear search in the
1136      * parent's child-list in order to find the current node.
1137      * <p>
1138      * That implementation makes the operation suitable for short
1139      * traversals from a known position. But to traverse all of the
1140      * leaves in the tree, you should use <code>depthFirstEnumeration</code>
1141      * to enumerate the nodes in the tree and use <code>isLeaf</code>
1142      * on each node to determine which are leaves.
1143      *
1144      * @see     #depthFirstEnumeration
1145      * @see     #isLeaf
1146      * @return  returns the next leaf past this node
1147      */
1148     public DefaultMutableTreeNode getNextLeaf() {
1149         DefaultMutableTreeNode nextSibling;
1150         DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent();
1151 
1152         if (myParent == null)
1153             return null;
1154 
1155         nextSibling = getNextSibling(); // linear search
1156 
1157         if (nextSibling != null)
1158             return nextSibling.getFirstLeaf();
1159 
1160         return myParent.getNextLeaf();  // tail recursion
1161     }
1162 
1163 
1164     /**
1165      * Returns the leaf before this node or null if this node is the
1166      * first leaf in the tree.
1167      * <p>
1168      * In this implementation of the <code>MutableNode</code> interface,
1169      * this operation is very inefficient. In order to determine the
1170      * previous node, this method first performs a linear search in the
1171      * parent's child-list in order to find the current node.
1172      * <p>
1173      * That implementation makes the operation suitable for short
1174      * traversals from a known position. But to traverse all of the
1175      * leaves in the tree, you should use <code>depthFirstEnumeration</code>
1176      * to enumerate the nodes in the tree and use <code>isLeaf</code>
1177      * on each node to determine which are leaves.
1178      *
1179      * @see             #depthFirstEnumeration
1180      * @see             #isLeaf
1181      * @return  returns the leaf before this node
1182      */
1183     public DefaultMutableTreeNode getPreviousLeaf() {
1184         DefaultMutableTreeNode previousSibling;
1185         DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent();
1186 
1187         if (myParent == null)
1188             return null;
1189 
1190         previousSibling = getPreviousSibling(); // linear search
1191 
1192         if (previousSibling != null)
1193             return previousSibling.getLastLeaf();
1194 
1195         return myParent.getPreviousLeaf();              // tail recursion
1196     }
1197 
1198 
1199     /**
1200      * Returns the total number of leaves that are descendants of this node.
1201      * If this node is a leaf, returns <code>1</code>.  This method is O(n)
1202      * where n is the number of descendants of this node.
1203      *
1204      * @see     #isNodeAncestor
1205      * @return  the number of leaves beneath this node
1206      */
1207     public int getLeafCount() {
1208         int count = 0;
1209 
1210         TreeNode node;
1211         Enumeration enum_ = breadthFirstEnumeration(); // order matters not
1212 
1213         while (enum_.hasMoreElements()) {
1214             node = (TreeNode)enum_.nextElement();
1215             if (node.isLeaf()) {
1216                 count++;
1217             }
1218         }
1219 
1220         if (count < 1) {
1221             throw new Error("tree has zero leaves");
1222         }
1223 
1224         return count;
1225     }
1226 
1227 
1228     //
1229     //  Overrides
1230     //
1231 
1232     /**
1233      * Returns the result of sending <code>toString()</code> to this node's
1234      * user object, or the empty string if the node has no user object.
1235      *
1236      * @see     #getUserObject
1237      */
1238     public String toString() {
1239         if (userObject == null) {
1240             return "";
1241         } else {
1242             return userObject.toString();
1243         }
1244     }
1245 
1246     /**
1247      * Overridden to make clone public.  Returns a shallow copy of this node;
1248      * the new node has no parent or children and has a reference to the same
1249      * user object, if any.
1250      *
1251      * @return  a copy of this node
1252      */
1253     public Object clone() {
1254         DefaultMutableTreeNode newNode;
1255 
1256         try {
1257             newNode = (DefaultMutableTreeNode)super.clone();
1258 
1259             // shallow copy -- the new node has no parent or children
1260             newNode.children = null;
1261             newNode.parent = null;
1262 
1263         } catch (CloneNotSupportedException e) {
1264             // Won't happen because we implement Cloneable
1265             throw new Error(e.toString());
1266         }
1267 
1268         return newNode;
1269     }
1270 
1271 
1272     // Serialization support.
1273     private void writeObject(ObjectOutputStream s) throws IOException {
1274         Object[]             tValues;
1275 
1276         s.defaultWriteObject();
1277         // Save the userObject, if its Serializable.
1278         if(userObject != null && userObject instanceof Serializable) {
1279             tValues = new Object[2];
1280             tValues[0] = "userObject";
1281             tValues[1] = userObject;
1282         }
1283         else
1284             tValues = new Object[0];
1285         s.writeObject(tValues);
1286     }
1287 
1288     private void readObject(ObjectInputStream s)
1289         throws IOException, ClassNotFoundException {
1290         Object[]      tValues;
1291 
1292         s.defaultReadObject();
1293 
1294         tValues = (Object[])s.readObject();
1295 
1296         if(tValues.length > 0 && tValues[0].equals("userObject"))
1297             userObject = tValues[1];
1298     }
1299 
1300     private final class PreorderEnumeration implements Enumeration<TreeNode> {
1301         private final Stack<Enumeration> stack = new Stack<Enumeration>();
1302 
1303         public PreorderEnumeration(TreeNode rootNode) {
1304             super();
1305             Vector<TreeNode> v = new Vector<TreeNode>(1);
1306             v.addElement(rootNode);     // PENDING: don't really need a vector
1307             stack.push(v.elements());
1308         }
1309 
1310         public boolean hasMoreElements() {
1311             return (!stack.empty() && stack.peek().hasMoreElements());
1312         }
1313 
1314         public TreeNode nextElement() {
1315             Enumeration enumer = stack.peek();
1316             TreeNode    node = (TreeNode)enumer.nextElement();
1317             Enumeration children = node.children();
1318 
1319             if (!enumer.hasMoreElements()) {
1320                 stack.pop();
1321             }
1322             if (children.hasMoreElements()) {
1323                 stack.push(children);
1324             }
1325             return node;
1326         }
1327 
1328     }  // End of class PreorderEnumeration
1329 
1330 
1331 
1332     final class PostorderEnumeration implements Enumeration<TreeNode> {
1333         protected TreeNode root;
1334         protected Enumeration<TreeNode> children;
1335         protected Enumeration<TreeNode> subtree;
1336 
1337         public PostorderEnumeration(TreeNode rootNode) {
1338             super();
1339             root = rootNode;
1340             children = root.children();
1341             subtree = EMPTY_ENUMERATION;
1342         }
1343 
1344         public boolean hasMoreElements() {
1345             return root != null;
1346         }
1347 
1348         public TreeNode nextElement() {
1349             TreeNode retval;
1350 
1351             if (subtree.hasMoreElements()) {
1352                 retval = subtree.nextElement();
1353             } else if (children.hasMoreElements()) {
1354                 subtree = new PostorderEnumeration(children.nextElement());
1355                 retval = subtree.nextElement();
1356             } else {
1357                 retval = root;
1358                 root = null;
1359             }
1360 
1361             return retval;
1362         }
1363 
1364     }  // End of class PostorderEnumeration
1365 
1366 
1367 
1368     final class BreadthFirstEnumeration implements Enumeration<TreeNode> {
1369         protected Queue queue;
1370 
1371         public BreadthFirstEnumeration(TreeNode rootNode) {
1372             super();
1373             Vector<TreeNode> v = new Vector<TreeNode>(1);
1374             v.addElement(rootNode);     // PENDING: don't really need a vector
1375             queue = new Queue();
1376             queue.enqueue(v.elements());
1377         }
1378 
1379         public boolean hasMoreElements() {
1380             return (!queue.isEmpty() &&
1381                     ((Enumeration)queue.firstObject()).hasMoreElements());
1382         }
1383 
1384         public TreeNode nextElement() {
1385             Enumeration enumer = (Enumeration)queue.firstObject();
1386             TreeNode    node = (TreeNode)enumer.nextElement();
1387             Enumeration children = node.children();
1388 
1389             if (!enumer.hasMoreElements()) {
1390                 queue.dequeue();
1391             }
1392             if (children.hasMoreElements()) {
1393                 queue.enqueue(children);
1394             }
1395             return node;
1396         }
1397 
1398 
1399         // A simple queue with a linked list data structure.
1400         final class Queue {
1401             QNode head; // null if empty
1402             QNode tail;
1403 
1404             final class QNode {
1405                 public Object   object;
1406                 public QNode    next;   // null if end
1407                 public QNode(Object object, QNode next) {
1408                     this.object = object;
1409                     this.next = next;
1410                 }
1411             }
1412 
1413             public void enqueue(Object anObject) {
1414                 if (head == null) {
1415                     head = tail = new QNode(anObject, null);
1416                 } else {
1417                     tail.next = new QNode(anObject, null);
1418                     tail = tail.next;
1419                 }
1420             }
1421 
1422             public Object dequeue() {
1423                 if (head == null) {
1424                     throw new NoSuchElementException("No more elements");
1425                 }
1426 
1427                 Object retval = head.object;
1428                 QNode oldHead = head;
1429                 head = head.next;
1430                 if (head == null) {
1431                     tail = null;
1432                 } else {
1433                     oldHead.next = null;
1434                 }
1435                 return retval;
1436             }
1437 
1438             public Object firstObject() {
1439                 if (head == null) {
1440                     throw new NoSuchElementException("No more elements");
1441                 }
1442 
1443                 return head.object;
1444             }
1445 
1446             public boolean isEmpty() {
1447                 return head == null;
1448             }
1449 
1450         } // End of class Queue
1451 
1452     }  // End of class BreadthFirstEnumeration
1453 
1454 
1455 
1456     final class PathBetweenNodesEnumeration implements Enumeration<TreeNode> {
1457         protected Stack<TreeNode> stack;
1458 
1459         public PathBetweenNodesEnumeration(TreeNode ancestor,
1460                                            TreeNode descendant)
1461         {
1462             super();
1463 
1464             if (ancestor == null || descendant == null) {
1465                 throw new IllegalArgumentException("argument is null");
1466             }
1467 
1468             TreeNode current;
1469 
1470             stack = new Stack<TreeNode>();
1471             stack.push(descendant);
1472 
1473             current = descendant;
1474             while (current != ancestor) {
1475                 current = current.getParent();
1476                 if (current == null && descendant != ancestor) {
1477                     throw new IllegalArgumentException("node " + ancestor +
1478                                 " is not an ancestor of " + descendant);
1479                 }
1480                 stack.push(current);
1481             }
1482         }
1483 
1484         public boolean hasMoreElements() {
1485             return stack.size() > 0;
1486         }
1487 
1488         public TreeNode nextElement() {
1489             try {
1490                 return stack.pop();
1491             } catch (EmptyStackException e) {
1492                 throw new NoSuchElementException("No more elements");
1493             }
1494         }
1495 
1496     } // End of class PathBetweenNodesEnumeration
1497 
1498 
1499 
1500 } // End of class DefaultMutableTreeNode