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