001/* DefaultMutableTreeNode.java -- 002 Copyright (C) 2002, 2004, 2005, 2006, Free Software Foundation, Inc. 003 004This file is part of GNU Classpath. 005 006GNU Classpath is free software; you can redistribute it and/or modify 007it under the terms of the GNU General Public License as published by 008the Free Software Foundation; either version 2, or (at your option) 009any later version. 010 011GNU Classpath is distributed in the hope that it will be useful, but 012WITHOUT ANY WARRANTY; without even the implied warranty of 013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 014General Public License for more details. 015 016You should have received a copy of the GNU General Public License 017along with GNU Classpath; see the file COPYING. If not, write to the 018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 01902110-1301 USA. 020 021Linking this library statically or dynamically with other modules is 022making a combined work based on this library. Thus, the terms and 023conditions of the GNU General Public License cover the whole 024combination. 025 026As a special exception, the copyright holders of this library give you 027permission to link this library with independent modules to produce an 028executable, regardless of the license terms of these independent 029modules, and to copy and distribute the resulting executable under 030terms of your choice, provided that you also meet, for each linked 031independent module, the terms and conditions of the license of that 032module. An independent module is a module which is not derived from 033or based on this library. If you modify this library, you may extend 034this exception to your version of the library, but you are not 035obligated to do so. If you do not wish to do so, delete this 036exception statement from your version. */ 037 038 039package javax.swing.tree; 040 041import java.io.IOException; 042import java.io.ObjectInputStream; 043import java.io.ObjectOutputStream; 044import java.io.Serializable; 045import java.util.ArrayList; 046import java.util.Enumeration; 047import java.util.LinkedList; 048import java.util.NoSuchElementException; 049import java.util.Stack; 050import java.util.Vector; 051 052 053/** 054 * A default implementation of the {@link MutableTreeNode} interface. 055 * 056 * @author Andrew Selkirk 057 * @author Robert Schuster (robertschuster@fsfe.org) 058 */ 059public class DefaultMutableTreeNode 060 implements Cloneable, MutableTreeNode, Serializable 061{ 062 private static final long serialVersionUID = -4298474751201349152L; 063 064 /** 065 * The parent of this node (possibly <code>null</code>). 066 */ 067 protected MutableTreeNode parent; 068 069 /** 070 * The child nodes for this node (may be empty). 071 */ 072 protected Vector<MutableTreeNode> children = new Vector<MutableTreeNode>(); 073 074 /** 075 * userObject 076 */ 077 protected transient Object userObject; 078 079 /** 080 * allowsChildren 081 */ 082 protected boolean allowsChildren; 083 084 /** 085 * Creates a <code>DefaultMutableTreeNode</code> object. 086 * This is equivalent to <code>DefaultMutableTreeNode(null, true)</code>. 087 */ 088 public DefaultMutableTreeNode() 089 { 090 this(null, true); 091 } 092 093 /** 094 * Creates a <code>DefaultMutableTreeNode</code> object with the given 095 * user object attached to it. This is equivalent to 096 * <code>DefaultMutableTreeNode(userObject, true)</code>. 097 * 098 * @param userObject the user object (<code>null</code> permitted). 099 */ 100 public DefaultMutableTreeNode(Object userObject) 101 { 102 this(userObject, true); 103 } 104 105 /** 106 * Creates a <code>DefaultMutableTreeNode</code> object with the given 107 * user object attached to it. 108 * 109 * @param userObject the user object (<code>null</code> permitted). 110 * @param allowsChildren <code>true</code> if the code allows to add child 111 * nodes, <code>false</code> otherwise 112 */ 113 public DefaultMutableTreeNode(Object userObject, boolean allowsChildren) 114 { 115 this.userObject = userObject; 116 this.allowsChildren = allowsChildren; 117 } 118 119 /** 120 * Returns a clone of the node. The clone contains a shallow copy of the 121 * user object, and does not copy the parent node or the child nodes. 122 * 123 * @return A clone of the node. 124 */ 125 public Object clone() 126 { 127 return new DefaultMutableTreeNode(this.userObject, this.allowsChildren); 128 } 129 130 /** 131 * Returns a string representation of the node. This implementation returns 132 * <code>getUserObject().toString()</code>, or <code>null</code> if there 133 * is no user object. 134 * 135 * @return A string representation of the node (possibly <code>null</code>). 136 */ 137 public String toString() 138 { 139 if (userObject == null) 140 return null; 141 142 return userObject.toString(); 143 } 144 145 /** 146 * Adds a new child node to this node and sets this node as the parent of 147 * the child node. The child node must not be an ancestor of this node. 148 * If the tree uses the {@link DefaultTreeModel}, you must subsequently 149 * call {@link DefaultTreeModel#reload(TreeNode)}. 150 * 151 * @param child the child node (<code>null</code> not permitted). 152 * 153 * @throws IllegalStateException if {@link #getAllowsChildren()} returns 154 * <code>false</code>. 155 * @throws IllegalArgumentException if {@link #isNodeAncestor} returns 156 * <code>true</code>. 157 * @throws IllegalArgumentException if <code>child</code> is 158 * <code>null</code>. 159 */ 160 public void add(MutableTreeNode child) 161 { 162 if (! allowsChildren) 163 throw new IllegalStateException(); 164 165 if (child == null) 166 throw new IllegalArgumentException(); 167 168 if (isNodeAncestor(child)) 169 throw new IllegalArgumentException("Cannot add ancestor node."); 170 171 children.add(child); 172 child.setParent(this); 173 } 174 175 /** 176 * Returns the parent node of this node. 177 * 178 * @return The parent node (possibly <code>null</code>). 179 */ 180 public TreeNode getParent() 181 { 182 return parent; 183 } 184 185 /** 186 * Removes the child with the given index from this node. 187 * 188 * @param index the index (in the range <code>0</code> to 189 * <code>getChildCount() - 1</code>). 190 * 191 * @throws ArrayIndexOutOfBoundsException if <code>index</code> is outside 192 * the valid range. 193 */ 194 public void remove(int index) 195 { 196 MutableTreeNode child = children.remove(index); 197 child.setParent(null); 198 } 199 200 /** 201 * Removes the given child from this node and sets its parent to 202 * <code>null</code>. 203 * 204 * @param node the child node (<code>null</code> not permitted). 205 * 206 * @throws IllegalArgumentException if <code>node</code> is not a child of 207 * this node. 208 * @throws IllegalArgumentException if <code>node</code> is null. 209 */ 210 public void remove(MutableTreeNode node) 211 { 212 if (node == null) 213 throw new IllegalArgumentException("Null 'node' argument."); 214 if (node.getParent() != this) 215 throw new IllegalArgumentException( 216 "The given 'node' is not a child of this node."); 217 children.remove(node); 218 node.setParent(null); 219 } 220 221 /** 222 * writeObject 223 * 224 * @param stream the output stream 225 * 226 * @exception IOException If an error occurs 227 */ 228 private void writeObject(ObjectOutputStream stream) 229 throws IOException 230 { 231 // TODO: Implement me. 232 } 233 234 /** 235 * readObject 236 * 237 * @param stream the input stream 238 * 239 * @exception IOException If an error occurs 240 * @exception ClassNotFoundException TODO 241 */ 242 private void readObject(ObjectInputStream stream) 243 throws IOException, ClassNotFoundException 244 { 245 // TODO: Implement me. 246 } 247 248 /** 249 * Inserts given child node at the given index. 250 * 251 * @param node the child node (<code>null</code> not permitted). 252 * @param index the index. 253 * 254 * @throws IllegalArgumentException if <code>node</code> is 255 * </code>null</code>. 256 */ 257 public void insert(MutableTreeNode node, int index) 258 { 259 if (! allowsChildren) 260 throw new IllegalStateException(); 261 262 if (node == null) 263 throw new IllegalArgumentException("Null 'node' argument."); 264 265 if (isNodeAncestor(node)) 266 throw new IllegalArgumentException("Cannot insert ancestor node."); 267 268 children.insertElementAt(node, index); 269 } 270 271 /** 272 * Returns a path to this node from the root. 273 * 274 * @return an array of tree nodes 275 */ 276 public TreeNode[] getPath() 277 { 278 return getPathToRoot(this, 0); 279 } 280 281 /** 282 * Returns an enumeration containing all children of this node. 283 * <code>EMPTY_ENUMERATION</code> is returned if this node has no children. 284 * 285 * @return an enumeration of tree nodes 286 */ 287 public Enumeration children() 288 { 289 if (children.size() == 0) 290 return EMPTY_ENUMERATION; 291 292 return children.elements(); 293 } 294 295 /** 296 * Set the parent node for this node. 297 * 298 * @param node the parent node 299 */ 300 public void setParent(MutableTreeNode node) 301 { 302 parent = node; 303 } 304 305 /** 306 * Returns the child node at a given index. 307 * 308 * @param index the index 309 * 310 * @return the child node 311 */ 312 public TreeNode getChildAt(int index) 313 { 314 return (TreeNode) children.elementAt(index); 315 } 316 317 /** 318 * Returns the number of children of this node. 319 * 320 * @return the number of children 321 */ 322 public int getChildCount() 323 { 324 return children.size(); 325 } 326 327 /** 328 * Returns the index of the specified child node, or -1 if the node is not 329 * in fact a child of this node. 330 * 331 * @param node the node (<code>null</code> not permitted). 332 * 333 * @return The index of the specified child node, or -1. 334 * 335 * @throws IllegalArgumentException if <code>node</code> is <code>null</code>. 336 */ 337 public int getIndex(TreeNode node) 338 { 339 if (node == null) 340 throw new IllegalArgumentException("Null 'node' argument."); 341 return children.indexOf(node); 342 } 343 344 /** 345 * Sets the flag that controls whether or not this node allows the addition / 346 * insertion of child nodes. If the flag is set to <code>false</code>, any 347 * existing children are removed. 348 * 349 * @param allowsChildren the flag. 350 */ 351 public void setAllowsChildren(boolean allowsChildren) 352 { 353 if (!allowsChildren) 354 removeAllChildren(); 355 this.allowsChildren = allowsChildren; 356 } 357 358 /** 359 * getAllowsChildren 360 * 361 * @return boolean 362 */ 363 public boolean getAllowsChildren() 364 { 365 return allowsChildren; 366 } 367 368 /** 369 * Sets the user object for this node 370 * 371 * @param userObject the user object 372 */ 373 public void setUserObject(Object userObject) 374 { 375 this.userObject = userObject; 376 } 377 378 /** 379 * Returns the user object attached to this node. <code>null</code> is 380 * returned when no user object is set. 381 * 382 * @return the user object 383 */ 384 public Object getUserObject() 385 { 386 return userObject; 387 } 388 389 /** 390 * Removes this node from its parent. 391 */ 392 public void removeFromParent() 393 { 394 parent.remove(this); 395 parent = null; 396 } 397 398 /** 399 * Removes all child nodes from this node. 400 */ 401 public void removeAllChildren() 402 { 403 for (int i = getChildCount() - 1; i >= 0; i--) 404 remove(i); 405 } 406 407 /** 408 * Returns <code>true</code> if <code>node</code> is an ancestor of this 409 * tree node, and <code>false</code> otherwise. An ancestor node is any of: 410 * <ul> 411 * <li>this tree node;</li> 412 * <li>the parent node (if there is one);</li> 413 * <li>any ancestor of the parent node;</li> 414 * </ul> 415 * If <code>node</code> is <code>null</code>, this method returns 416 * <code>false</code>. 417 * 418 * @param node the node (<code>null</code> permitted). 419 * 420 * @return A boolean. 421 */ 422 public boolean isNodeAncestor(TreeNode node) 423 { 424 if (node == null) 425 return false; 426 427 TreeNode current = this; 428 429 while (current != null && current != node) 430 current = current.getParent(); 431 432 return current == node; 433 } 434 435 /** 436 * Returns <code>true</code> if <code>node</code> is a descendant of this 437 * tree node, and <code>false</code> otherwise. A descendant node is any of: 438 * <ul> 439 * <li>this tree node;</li> 440 * <li>the child nodes belonging to this tree node, if there are any;</li> 441 * <li>any descendants of the child nodes;</li> 442 * </ul> 443 * If <code>node</code> is <code>null</code>, this method returns 444 * <code>false</code>. 445 * 446 * @param node the node (<code>null</code> permitted). 447 * 448 * @return A boolean. 449 */ 450 public boolean isNodeDescendant(DefaultMutableTreeNode node) 451 { 452 if (node == null) 453 return false; 454 455 TreeNode current = node; 456 457 while (current != null 458 && current != this) 459 current = current.getParent(); 460 461 return current == this; 462 } 463 464 /** 465 * getSharedAncestor 466 * 467 * @param node TODO 468 * 469 * @return TreeNode 470 */ 471 public TreeNode getSharedAncestor(DefaultMutableTreeNode node) 472 { 473 TreeNode current = this; 474 ArrayList<TreeNode> list = new ArrayList<TreeNode>(); 475 476 while (current != null) 477 { 478 list.add(current); 479 current = current.getParent(); 480 } 481 482 current = node; 483 484 while (current != null) 485 { 486 if (list.contains(current)) 487 return current; 488 489 current = current.getParent(); 490 } 491 492 return null; 493 } 494 495 /** 496 * isNodeRelated 497 * 498 * @param node TODO 499 * 500 * @return boolean 501 */ 502 public boolean isNodeRelated(DefaultMutableTreeNode node) 503 { 504 if (node == null) 505 return false; 506 507 return node.getRoot() == getRoot(); 508 } 509 510 /** 511 * getDepth 512 * 513 * @return int 514 */ 515 public int getDepth() 516 { 517 if ((! allowsChildren) 518 || children.size() == 0) 519 return 0; 520 521 Stack<Integer> stack = new Stack<Integer>(); 522 stack.push(new Integer(0)); 523 TreeNode node = getChildAt(0); 524 int depth = 0; 525 int current = 1; 526 527 while (! stack.empty()) 528 { 529 if (node.getChildCount() != 0) 530 { 531 node = node.getChildAt(0); 532 stack.push(new Integer(0)); 533 current++; 534 } 535 else 536 { 537 if (current > depth) 538 depth = current; 539 540 int size; 541 int index; 542 543 do 544 { 545 node = node.getParent(); 546 size = node.getChildCount(); 547 index = stack.pop().intValue() + 1; 548 current--; 549 } 550 while (index >= size 551 && node != this); 552 553 if (index < size) 554 { 555 node = node.getChildAt(index); 556 stack.push(new Integer(index)); 557 current++; 558 } 559 } 560 } 561 562 return depth; 563 } 564 565 /** 566 * getLevel 567 * 568 * @return int 569 */ 570 public int getLevel() 571 { 572 int count = -1; 573 TreeNode current = this; 574 575 do 576 { 577 current = current.getParent(); 578 count++; 579 } 580 while (current != null); 581 582 return count; 583 } 584 585 /** 586 * getPathToRoot 587 * 588 * @param node TODO 589 * @param depth TODO 590 * 591 * @return TreeNode[] 592 */ 593 protected TreeNode[] getPathToRoot(TreeNode node, int depth) 594 { 595 if (node == null) 596 { 597 if (depth == 0) 598 return null; 599 600 return new TreeNode[depth]; 601 } 602 603 TreeNode[] path = getPathToRoot(node.getParent(), depth + 1); 604 path[path.length - depth - 1] = node; 605 return path; 606 } 607 608 /** 609 * getUserObjectPath 610 * 611 * @return Object[] 612 */ 613 public Object[] getUserObjectPath() 614 { 615 TreeNode[] path = getPathToRoot(this, 0); 616 Object[] object = new Object[path.length]; 617 618 for (int index = 0; index < path.length; ++index) 619 object[index] = ((DefaultMutableTreeNode) path[index]).getUserObject(); 620 621 return object; 622 } 623 624 /** 625 * Returns the root node by iterating the parents of this node. 626 * 627 * @return the root node 628 */ 629 public TreeNode getRoot() 630 { 631 TreeNode current = this; 632 TreeNode check = current.getParent(); 633 634 while (check != null) 635 { 636 current = check; 637 check = current.getParent(); 638 } 639 640 return current; 641 } 642 643 /** 644 * Tells whether this node is the root node or not. 645 * 646 * @return <code>true</code> if this is the root node, 647 * <code>false</code>otherwise 648 */ 649 public boolean isRoot() 650 { 651 return parent == null; 652 } 653 654 /** 655 * getNextNode 656 * 657 * @return DefaultMutableTreeNode 658 */ 659 public DefaultMutableTreeNode getNextNode() 660 { 661 // Return first child. 662 if (getChildCount() != 0) 663 return (DefaultMutableTreeNode) getChildAt(0); 664 665 // Return next sibling (if needed the sibling of some parent). 666 DefaultMutableTreeNode node = this; 667 DefaultMutableTreeNode sibling; 668 669 do 670 { 671 sibling = node.getNextSibling(); 672 node = (DefaultMutableTreeNode) node.getParent(); 673 } 674 while (sibling == null && 675 node != null); 676 677 // Return sibling. 678 return sibling; 679 } 680 681 /** 682 * getPreviousNode 683 * 684 * @return DefaultMutableTreeNode 685 */ 686 public DefaultMutableTreeNode getPreviousNode() 687 { 688 // Return null if no parent. 689 if (parent == null) 690 return null; 691 692 DefaultMutableTreeNode sibling = getPreviousSibling(); 693 694 // Return parent if no sibling. 695 if (sibling == null) 696 return (DefaultMutableTreeNode) parent; 697 698 // Return last leaf of sibling. 699 if (sibling.getChildCount() != 0) 700 return sibling.getLastLeaf(); 701 702 // Return sibling. 703 return sibling; 704 } 705 706 /** 707 * preorderEnumeration 708 * 709 * @return Enumeration 710 */ 711 public Enumeration preorderEnumeration() 712 { 713 return new PreorderEnumeration(this); 714 } 715 716 /** 717 * postorderEnumeration 718 * 719 * @return Enumeration 720 */ 721 public Enumeration postorderEnumeration() 722 { 723 return new PostorderEnumeration(this); 724 } 725 726 /** 727 * breadthFirstEnumeration 728 * 729 * @return Enumeration 730 */ 731 public Enumeration breadthFirstEnumeration() 732 { 733 return new BreadthFirstEnumeration(this); 734 } 735 736 /** 737 * depthFirstEnumeration 738 * 739 * @return Enumeration 740 */ 741 public Enumeration depthFirstEnumeration() 742 { 743 return postorderEnumeration(); 744 } 745 746 /** 747 * pathFromAncestorEnumeration 748 * 749 * @param node TODO 750 * 751 * @return Enumeration 752 */ 753 public Enumeration pathFromAncestorEnumeration(TreeNode node) 754 { 755 if (node == null) 756 throw new IllegalArgumentException(); 757 758 TreeNode parent = this; 759 Vector<TreeNode> nodes = new Vector<TreeNode>(); 760 nodes.add(this); 761 762 while (parent != node && parent != null) 763 { 764 parent = parent.getParent(); 765 nodes.add(0, parent); 766 } 767 768 if (parent != node) 769 throw new IllegalArgumentException(); 770 771 return nodes.elements(); 772 } 773 774 /** 775 * Returns <code>true</code> if <code>node</code> is a child of this tree 776 * node, and <code>false</code> otherwise. If <code>node</code> is 777 * <code>null</code>, this method returns <code>false</code>. 778 * 779 * @param node the node (<code>null</code> permitted). 780 * 781 * @return A boolean. 782 */ 783 public boolean isNodeChild(TreeNode node) 784 { 785 if (node == null) 786 return false; 787 788 return node.getParent() == this; 789 } 790 791 /** 792 * Returns the first child node belonging to this tree node. 793 * 794 * @return The first child node. 795 * 796 * @throws NoSuchElementException if this tree node has no children. 797 */ 798 public TreeNode getFirstChild() 799 { 800 return (TreeNode) children.firstElement(); 801 } 802 803 /** 804 * Returns the last child node belonging to this tree node. 805 * 806 * @return The last child node. 807 * 808 * @throws NoSuchElementException if this tree node has no children. 809 */ 810 public TreeNode getLastChild() 811 { 812 return (TreeNode) children.lastElement(); 813 } 814 815 /** 816 * Returns the next child after the specified <code>node</code>, or 817 * <code>null</code> if there is no child after the specified 818 * <code>node</code>. 819 * 820 * @param node a child of this node (<code>null</code> not permitted). 821 * 822 * @return The next child, or <code>null</code>. 823 * 824 * @throws IllegalArgumentException if <code>node</code> is not a child of 825 * this node, or is <code>null</code>. 826 */ 827 public TreeNode getChildAfter(TreeNode node) 828 { 829 if (node == null || node.getParent() != this) 830 throw new IllegalArgumentException(); 831 832 int index = getIndex(node) + 1; 833 834 if (index == getChildCount()) 835 return null; 836 837 return getChildAt(index); 838 } 839 840 /** 841 * Returns the previous child before the specified <code>node</code>, or 842 * <code>null</code> if there is no child before the specified 843 * <code>node</code>. 844 * 845 * @param node a child of this node (<code>null</code> not permitted). 846 * 847 * @return The previous child, or <code>null</code>. 848 * 849 * @throws IllegalArgumentException if <code>node</code> is not a child of 850 * this node, or is <code>null</code>. 851 */ 852 public TreeNode getChildBefore(TreeNode node) 853 { 854 if (node == null || node.getParent() != this) 855 throw new IllegalArgumentException(); 856 857 int index = getIndex(node) - 1; 858 859 if (index < 0) 860 return null; 861 862 return getChildAt(index); 863 } 864 865 /** 866 * Returns <code>true</code> if this tree node and <code>node</code> share 867 * the same parent. If <code>node</code> is this tree node, the method 868 * returns <code>true</code> and if <code>node</code> is <code>null</code> 869 * this method returns <code>false</code>. 870 * 871 * @param node the node (<code>null</code> permitted). 872 * 873 * @return A boolean. 874 */ 875 public boolean isNodeSibling(TreeNode node) 876 { 877 if (node == null) 878 return false; 879 if (node == this) 880 return true; 881 return node.getParent() == getParent() && getParent() != null; 882 } 883 884 /** 885 * Returns the number of siblings for this tree node. If the tree node has 886 * a parent, this method returns the child count for the parent, otherwise 887 * it returns <code>1</code>. 888 * 889 * @return The sibling count. 890 */ 891 public int getSiblingCount() 892 { 893 if (parent == null) 894 return 1; 895 896 return parent.getChildCount(); 897 } 898 899 /** 900 * Returns the next sibling for this tree node. If this node has no parent, 901 * or this node is the last child of its parent, this method returns 902 * <code>null</code>. 903 * 904 * @return The next sibling, or <code>null</code>. 905 */ 906 public DefaultMutableTreeNode getNextSibling() 907 { 908 if (parent == null) 909 return null; 910 911 int index = parent.getIndex(this) + 1; 912 913 if (index == parent.getChildCount()) 914 return null; 915 916 return (DefaultMutableTreeNode) parent.getChildAt(index); 917 } 918 919 /** 920 * Returns the previous sibling for this tree node. If this node has no 921 * parent, or this node is the first child of its parent, this method returns 922 * <code>null</code>. 923 * 924 * @return The previous sibling, or <code>null</code>. 925 */ 926 public DefaultMutableTreeNode getPreviousSibling() 927 { 928 if (parent == null) 929 return null; 930 931 int index = parent.getIndex(this) - 1; 932 933 if (index < 0) 934 return null; 935 936 return (DefaultMutableTreeNode) parent.getChildAt(index); 937 } 938 939 /** 940 * Returns <code>true</code> if this tree node is a lead node (that is, it 941 * has no children), and <code>false</otherwise>. 942 * 943 * @return A boolean. 944 */ 945 public boolean isLeaf() 946 { 947 return children.size() == 0; 948 } 949 950 /** 951 * Returns the first leaf node that is a descendant of this node. Recall 952 * that a node is its own descendant, so if this node has no children then 953 * it is returned as the first leaf. 954 * 955 * @return The first leaf node. 956 */ 957 public DefaultMutableTreeNode getFirstLeaf() 958 { 959 TreeNode current = this; 960 961 while (current.getChildCount() > 0) 962 current = current.getChildAt(0); 963 964 return (DefaultMutableTreeNode) current; 965 } 966 967 /** 968 * Returns the last leaf node that is a descendant of this node. Recall 969 * that a node is its own descendant, so if this node has no children then 970 * it is returned as the last leaf. 971 * 972 * @return The first leaf node. 973 */ 974 public DefaultMutableTreeNode getLastLeaf() 975 { 976 TreeNode current = this; 977 int size = current.getChildCount(); 978 979 while (size > 0) 980 { 981 current = current.getChildAt(size - 1); 982 size = current.getChildCount(); 983 } 984 985 return (DefaultMutableTreeNode) current; 986 } 987 988 /** 989 * Returns the next leaf node after this tree node. 990 * 991 * @return The next leaf node, or <code>null</code>. 992 */ 993 public DefaultMutableTreeNode getNextLeaf() 994 { 995 // if there is a next sibling, return its first leaf 996 DefaultMutableTreeNode sibling = getNextSibling(); 997 if (sibling != null) 998 return sibling.getFirstLeaf(); 999 // otherwise move up one level and try again... 1000 if (parent != null) 1001 return ((DefaultMutableTreeNode) parent).getNextLeaf(); 1002 return null; 1003 } 1004 1005 /** 1006 * Returns the previous leaf node before this tree node. 1007 * 1008 * @return The previous leaf node, or <code>null</code>. 1009 */ 1010 public DefaultMutableTreeNode getPreviousLeaf() 1011 { 1012 // if there is a previous sibling, return its last leaf 1013 DefaultMutableTreeNode sibling = getPreviousSibling(); 1014 if (sibling != null) 1015 return sibling.getLastLeaf(); 1016 // otherwise move up one level and try again... 1017 if (parent != null) 1018 return ((DefaultMutableTreeNode) parent).getPreviousLeaf(); 1019 return null; 1020 } 1021 1022 /** 1023 * getLeafCount 1024 * 1025 * @return int 1026 */ 1027 public int getLeafCount() 1028 { 1029 int count = 0; 1030 Enumeration e = depthFirstEnumeration(); 1031 1032 while (e.hasMoreElements()) 1033 { 1034 TreeNode current = (TreeNode) e.nextElement(); 1035 1036 if (current.isLeaf()) 1037 count++; 1038 } 1039 1040 return count; 1041 } 1042 1043 /** Provides an enumeration of a tree in breadth-first traversal 1044 * order. 1045 */ 1046 static class BreadthFirstEnumeration implements Enumeration<TreeNode> 1047 { 1048 1049 LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); 1050 1051 BreadthFirstEnumeration(TreeNode node) 1052 { 1053 queue.add(node); 1054 } 1055 1056 public boolean hasMoreElements() 1057 { 1058 return !queue.isEmpty(); 1059 } 1060 1061 @SuppressWarnings("unchecked") 1062 public TreeNode nextElement() 1063 { 1064 if (queue.isEmpty()) 1065 throw new NoSuchElementException("No more elements left."); 1066 1067 TreeNode node = queue.removeFirst(); 1068 1069 Enumeration<TreeNode> children = 1070 (Enumeration<TreeNode>) node.children(); 1071 while (children.hasMoreElements()) 1072 queue.add(children.nextElement()); 1073 1074 return node; 1075 } 1076 } 1077 1078 /** Provides an enumeration of a tree traversing it 1079 * preordered. 1080 */ 1081 static class PreorderEnumeration implements Enumeration<TreeNode> 1082 { 1083 TreeNode next; 1084 1085 Stack<Enumeration<TreeNode>> childrenEnums = 1086 new Stack<Enumeration<TreeNode>>(); 1087 1088 @SuppressWarnings("unchecked") 1089 PreorderEnumeration(TreeNode node) 1090 { 1091 next = node; 1092 childrenEnums.push((Enumeration<TreeNode>) node.children()); 1093 } 1094 1095 public boolean hasMoreElements() 1096 { 1097 return next != null; 1098 } 1099 1100 public TreeNode nextElement() 1101 { 1102 if (next == null) 1103 throw new NoSuchElementException("No more elements left."); 1104 1105 TreeNode current = next; 1106 1107 Enumeration<TreeNode> children = childrenEnums.peek(); 1108 1109 // Retrieves the next element. 1110 next = traverse(children); 1111 1112 return current; 1113 } 1114 1115 @SuppressWarnings("unchecked") 1116 private TreeNode traverse(Enumeration<TreeNode> children) 1117 { 1118 // If more children are available step down. 1119 if (children.hasMoreElements()) 1120 { 1121 TreeNode child = children.nextElement(); 1122 childrenEnums.push((Enumeration<TreeNode>) child.children()); 1123 1124 return child; 1125 } 1126 1127 // If no children are left, we return to a higher level. 1128 childrenEnums.pop(); 1129 1130 // If there are no more levels left, there is no next 1131 // element to return. 1132 if (childrenEnums.isEmpty()) 1133 return null; 1134 else 1135 { 1136 return traverse(childrenEnums.peek()); 1137 } 1138 } 1139 } 1140 1141 /** Provides an enumeration of a tree traversing it 1142 * postordered (= depth-first). 1143 */ 1144 static class PostorderEnumeration implements Enumeration<TreeNode> 1145 { 1146 1147 Stack<TreeNode> nodes = new Stack<TreeNode>(); 1148 Stack<Enumeration<TreeNode>> childrenEnums = 1149 new Stack<Enumeration<TreeNode>>(); 1150 1151 @SuppressWarnings("unchecked") 1152 PostorderEnumeration(TreeNode node) 1153 { 1154 nodes.push(node); 1155 childrenEnums.push((Enumeration<TreeNode>) node.children()); 1156 } 1157 1158 public boolean hasMoreElements() 1159 { 1160 return !nodes.isEmpty(); 1161 } 1162 1163 public TreeNode nextElement() 1164 { 1165 if (nodes.isEmpty()) 1166 throw new NoSuchElementException("No more elements left!"); 1167 1168 Enumeration<TreeNode> children = childrenEnums.peek(); 1169 1170 return traverse(children); 1171 } 1172 1173 @SuppressWarnings("unchecked") 1174 private TreeNode traverse(Enumeration<TreeNode> children) 1175 { 1176 if (children.hasMoreElements()) 1177 { 1178 TreeNode node = children.nextElement(); 1179 nodes.push(node); 1180 1181 Enumeration<TreeNode> newChildren = 1182 (Enumeration<TreeNode>) node.children(); 1183 childrenEnums.push(newChildren); 1184 1185 return traverse(newChildren); 1186 } 1187 else 1188 { 1189 childrenEnums.pop(); 1190 1191 // Returns the node whose children 1192 // have all been visited. (= postorder) 1193 TreeNode next = nodes.peek(); 1194 nodes.pop(); 1195 1196 return next; 1197 } 1198 } 1199 1200 } 1201 1202}