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 @SuppressWarnings("unchecked") // Required for API compatibility 288 public Enumeration children() 289 { 290 if (children.size() == 0) 291 return EMPTY_ENUMERATION; 292 293 return children.elements(); 294 } 295 296 /** 297 * Set the parent node for this node. 298 * 299 * @param node the parent node 300 */ 301 public void setParent(MutableTreeNode node) 302 { 303 parent = node; 304 } 305 306 /** 307 * Returns the child node at a given index. 308 * 309 * @param index the index 310 * 311 * @return the child node 312 */ 313 public TreeNode getChildAt(int index) 314 { 315 return children.elementAt(index); 316 } 317 318 /** 319 * Returns the number of children of this node. 320 * 321 * @return the number of children 322 */ 323 public int getChildCount() 324 { 325 return children.size(); 326 } 327 328 /** 329 * Returns the index of the specified child node, or -1 if the node is not 330 * in fact a child of this node. 331 * 332 * @param node the node (<code>null</code> not permitted). 333 * 334 * @return The index of the specified child node, or -1. 335 * 336 * @throws IllegalArgumentException if <code>node</code> is <code>null</code>. 337 */ 338 public int getIndex(TreeNode node) 339 { 340 if (node == null) 341 throw new IllegalArgumentException("Null 'node' argument."); 342 return children.indexOf(node); 343 } 344 345 /** 346 * Sets the flag that controls whether or not this node allows the addition / 347 * insertion of child nodes. If the flag is set to <code>false</code>, any 348 * existing children are removed. 349 * 350 * @param allowsChildren the flag. 351 */ 352 public void setAllowsChildren(boolean allowsChildren) 353 { 354 if (!allowsChildren) 355 removeAllChildren(); 356 this.allowsChildren = allowsChildren; 357 } 358 359 /** 360 * getAllowsChildren 361 * 362 * @return boolean 363 */ 364 public boolean getAllowsChildren() 365 { 366 return allowsChildren; 367 } 368 369 /** 370 * Sets the user object for this node 371 * 372 * @param userObject the user object 373 */ 374 public void setUserObject(Object userObject) 375 { 376 this.userObject = userObject; 377 } 378 379 /** 380 * Returns the user object attached to this node. <code>null</code> is 381 * returned when no user object is set. 382 * 383 * @return the user object 384 */ 385 public Object getUserObject() 386 { 387 return userObject; 388 } 389 390 /** 391 * Removes this node from its parent. 392 */ 393 public void removeFromParent() 394 { 395 parent.remove(this); 396 parent = null; 397 } 398 399 /** 400 * Removes all child nodes from this node. 401 */ 402 public void removeAllChildren() 403 { 404 for (int i = getChildCount() - 1; i >= 0; i--) 405 remove(i); 406 } 407 408 /** 409 * Returns <code>true</code> if <code>node</code> is an ancestor of this 410 * tree node, and <code>false</code> otherwise. An ancestor node is any of: 411 * <ul> 412 * <li>this tree node;</li> 413 * <li>the parent node (if there is one);</li> 414 * <li>any ancestor of the parent node;</li> 415 * </ul> 416 * If <code>node</code> is <code>null</code>, this method returns 417 * <code>false</code>. 418 * 419 * @param node the node (<code>null</code> permitted). 420 * 421 * @return A boolean. 422 */ 423 public boolean isNodeAncestor(TreeNode node) 424 { 425 if (node == null) 426 return false; 427 428 TreeNode current = this; 429 430 while (current != null && current != node) 431 current = current.getParent(); 432 433 return current == node; 434 } 435 436 /** 437 * Returns <code>true</code> if <code>node</code> is a descendant of this 438 * tree node, and <code>false</code> otherwise. A descendant node is any of: 439 * <ul> 440 * <li>this tree node;</li> 441 * <li>the child nodes belonging to this tree node, if there are any;</li> 442 * <li>any descendants of the child nodes;</li> 443 * </ul> 444 * If <code>node</code> is <code>null</code>, this method returns 445 * <code>false</code>. 446 * 447 * @param node the node (<code>null</code> permitted). 448 * 449 * @return A boolean. 450 */ 451 public boolean isNodeDescendant(DefaultMutableTreeNode node) 452 { 453 if (node == null) 454 return false; 455 456 TreeNode current = node; 457 458 while (current != null 459 && current != this) 460 current = current.getParent(); 461 462 return current == this; 463 } 464 465 /** 466 * getSharedAncestor 467 * 468 * @param node TODO 469 * 470 * @return TreeNode 471 */ 472 public TreeNode getSharedAncestor(DefaultMutableTreeNode node) 473 { 474 TreeNode current = this; 475 ArrayList<TreeNode> list = new ArrayList<TreeNode>(); 476 477 while (current != null) 478 { 479 list.add(current); 480 current = current.getParent(); 481 } 482 483 current = node; 484 485 while (current != null) 486 { 487 if (list.contains(current)) 488 return current; 489 490 current = current.getParent(); 491 } 492 493 return null; 494 } 495 496 /** 497 * isNodeRelated 498 * 499 * @param node TODO 500 * 501 * @return boolean 502 */ 503 public boolean isNodeRelated(DefaultMutableTreeNode node) 504 { 505 if (node == null) 506 return false; 507 508 return node.getRoot() == getRoot(); 509 } 510 511 /** 512 * getDepth 513 * 514 * @return int 515 */ 516 public int getDepth() 517 { 518 if ((! allowsChildren) 519 || children.size() == 0) 520 return 0; 521 522 Stack<Integer> stack = new Stack<Integer>(); 523 stack.push(new Integer(0)); 524 TreeNode node = getChildAt(0); 525 int depth = 0; 526 int current = 1; 527 528 while (! stack.empty()) 529 { 530 if (node.getChildCount() != 0) 531 { 532 node = node.getChildAt(0); 533 stack.push(new Integer(0)); 534 current++; 535 } 536 else 537 { 538 if (current > depth) 539 depth = current; 540 541 int size; 542 int index; 543 544 do 545 { 546 node = node.getParent(); 547 size = node.getChildCount(); 548 index = stack.pop().intValue() + 1; 549 current--; 550 } 551 while (index >= size 552 && node != this); 553 554 if (index < size) 555 { 556 node = node.getChildAt(index); 557 stack.push(new Integer(index)); 558 current++; 559 } 560 } 561 } 562 563 return depth; 564 } 565 566 /** 567 * getLevel 568 * 569 * @return int 570 */ 571 public int getLevel() 572 { 573 int count = -1; 574 TreeNode current = this; 575 576 do 577 { 578 current = current.getParent(); 579 count++; 580 } 581 while (current != null); 582 583 return count; 584 } 585 586 /** 587 * getPathToRoot 588 * 589 * @param node TODO 590 * @param depth TODO 591 * 592 * @return TreeNode[] 593 */ 594 protected TreeNode[] getPathToRoot(TreeNode node, int depth) 595 { 596 if (node == null) 597 { 598 if (depth == 0) 599 return null; 600 601 return new TreeNode[depth]; 602 } 603 604 TreeNode[] path = getPathToRoot(node.getParent(), depth + 1); 605 path[path.length - depth - 1] = node; 606 return path; 607 } 608 609 /** 610 * getUserObjectPath 611 * 612 * @return Object[] 613 */ 614 public Object[] getUserObjectPath() 615 { 616 TreeNode[] path = getPathToRoot(this, 0); 617 Object[] object = new Object[path.length]; 618 619 for (int index = 0; index < path.length; ++index) 620 object[index] = ((DefaultMutableTreeNode) path[index]).getUserObject(); 621 622 return object; 623 } 624 625 /** 626 * Returns the root node by iterating the parents of this node. 627 * 628 * @return the root node 629 */ 630 public TreeNode getRoot() 631 { 632 TreeNode current = this; 633 TreeNode check = current.getParent(); 634 635 while (check != null) 636 { 637 current = check; 638 check = current.getParent(); 639 } 640 641 return current; 642 } 643 644 /** 645 * Tells whether this node is the root node or not. 646 * 647 * @return <code>true</code> if this is the root node, 648 * <code>false</code>otherwise 649 */ 650 public boolean isRoot() 651 { 652 return parent == null; 653 } 654 655 /** 656 * getNextNode 657 * 658 * @return DefaultMutableTreeNode 659 */ 660 public DefaultMutableTreeNode getNextNode() 661 { 662 // Return first child. 663 if (getChildCount() != 0) 664 return (DefaultMutableTreeNode) getChildAt(0); 665 666 // Return next sibling (if needed the sibling of some parent). 667 DefaultMutableTreeNode node = this; 668 DefaultMutableTreeNode sibling; 669 670 do 671 { 672 sibling = node.getNextSibling(); 673 node = (DefaultMutableTreeNode) node.getParent(); 674 } 675 while (sibling == null && 676 node != null); 677 678 // Return sibling. 679 return sibling; 680 } 681 682 /** 683 * getPreviousNode 684 * 685 * @return DefaultMutableTreeNode 686 */ 687 public DefaultMutableTreeNode getPreviousNode() 688 { 689 // Return null if no parent. 690 if (parent == null) 691 return null; 692 693 DefaultMutableTreeNode sibling = getPreviousSibling(); 694 695 // Return parent if no sibling. 696 if (sibling == null) 697 return (DefaultMutableTreeNode) parent; 698 699 // Return last leaf of sibling. 700 if (sibling.getChildCount() != 0) 701 return sibling.getLastLeaf(); 702 703 // Return sibling. 704 return sibling; 705 } 706 707 /** 708 * preorderEnumeration 709 * 710 * @return Enumeration 711 */ 712 @SuppressWarnings("unchecked") // Required for API compatibility 713 public Enumeration preorderEnumeration() 714 { 715 return new PreorderEnumeration(this); 716 } 717 718 /** 719 * postorderEnumeration 720 * 721 * @return Enumeration 722 */ 723 @SuppressWarnings("unchecked") // Required for API compatibility 724 public Enumeration postorderEnumeration() 725 { 726 return new PostorderEnumeration(this); 727 } 728 729 /** 730 * breadthFirstEnumeration 731 * 732 * @return Enumeration 733 */ 734 @SuppressWarnings("unchecked") // Required for API compatibility 735 public Enumeration breadthFirstEnumeration() 736 { 737 return new BreadthFirstEnumeration(this); 738 } 739 740 /** 741 * depthFirstEnumeration 742 * 743 * @return Enumeration 744 */ 745 @SuppressWarnings("unchecked") // Required for API compatibility 746 public Enumeration depthFirstEnumeration() 747 { 748 return postorderEnumeration(); 749 } 750 751 /** 752 * pathFromAncestorEnumeration 753 * 754 * @param node TODO 755 * 756 * @return Enumeration 757 */ 758 @SuppressWarnings("unchecked") // Required for API compatibility 759 public Enumeration pathFromAncestorEnumeration(TreeNode node) 760 { 761 if (node == null) 762 throw new IllegalArgumentException(); 763 764 TreeNode parent = this; 765 Vector<TreeNode> nodes = new Vector<TreeNode>(); 766 nodes.add(this); 767 768 while (parent != node && parent != null) 769 { 770 parent = parent.getParent(); 771 nodes.add(0, parent); 772 } 773 774 if (parent != node) 775 throw new IllegalArgumentException(); 776 777 return nodes.elements(); 778 } 779 780 /** 781 * Returns <code>true</code> if <code>node</code> is a child of this tree 782 * node, and <code>false</code> otherwise. If <code>node</code> is 783 * <code>null</code>, this method returns <code>false</code>. 784 * 785 * @param node the node (<code>null</code> permitted). 786 * 787 * @return A boolean. 788 */ 789 public boolean isNodeChild(TreeNode node) 790 { 791 if (node == null) 792 return false; 793 794 return node.getParent() == this; 795 } 796 797 /** 798 * Returns the first child node belonging to this tree node. 799 * 800 * @return The first child node. 801 * 802 * @throws NoSuchElementException if this tree node has no children. 803 */ 804 public TreeNode getFirstChild() 805 { 806 return children.firstElement(); 807 } 808 809 /** 810 * Returns the last child node belonging to this tree node. 811 * 812 * @return The last child node. 813 * 814 * @throws NoSuchElementException if this tree node has no children. 815 */ 816 public TreeNode getLastChild() 817 { 818 return children.lastElement(); 819 } 820 821 /** 822 * Returns the next child after the specified <code>node</code>, or 823 * <code>null</code> if there is no child after the specified 824 * <code>node</code>. 825 * 826 * @param node a child of this node (<code>null</code> not permitted). 827 * 828 * @return The next child, or <code>null</code>. 829 * 830 * @throws IllegalArgumentException if <code>node</code> is not a child of 831 * this node, or is <code>null</code>. 832 */ 833 public TreeNode getChildAfter(TreeNode node) 834 { 835 if (node == null || node.getParent() != this) 836 throw new IllegalArgumentException(); 837 838 int index = getIndex(node) + 1; 839 840 if (index == getChildCount()) 841 return null; 842 843 return getChildAt(index); 844 } 845 846 /** 847 * Returns the previous child before the specified <code>node</code>, or 848 * <code>null</code> if there is no child before the specified 849 * <code>node</code>. 850 * 851 * @param node a child of this node (<code>null</code> not permitted). 852 * 853 * @return The previous child, or <code>null</code>. 854 * 855 * @throws IllegalArgumentException if <code>node</code> is not a child of 856 * this node, or is <code>null</code>. 857 */ 858 public TreeNode getChildBefore(TreeNode node) 859 { 860 if (node == null || node.getParent() != this) 861 throw new IllegalArgumentException(); 862 863 int index = getIndex(node) - 1; 864 865 if (index < 0) 866 return null; 867 868 return getChildAt(index); 869 } 870 871 /** 872 * Returns <code>true</code> if this tree node and <code>node</code> share 873 * the same parent. If <code>node</code> is this tree node, the method 874 * returns <code>true</code> and if <code>node</code> is <code>null</code> 875 * this method returns <code>false</code>. 876 * 877 * @param node the node (<code>null</code> permitted). 878 * 879 * @return A boolean. 880 */ 881 public boolean isNodeSibling(TreeNode node) 882 { 883 if (node == null) 884 return false; 885 if (node == this) 886 return true; 887 return node.getParent() == getParent() && getParent() != null; 888 } 889 890 /** 891 * Returns the number of siblings for this tree node. If the tree node has 892 * a parent, this method returns the child count for the parent, otherwise 893 * it returns <code>1</code>. 894 * 895 * @return The sibling count. 896 */ 897 public int getSiblingCount() 898 { 899 if (parent == null) 900 return 1; 901 902 return parent.getChildCount(); 903 } 904 905 /** 906 * Returns the next sibling for this tree node. If this node has no parent, 907 * or this node is the last child of its parent, this method returns 908 * <code>null</code>. 909 * 910 * @return The next sibling, or <code>null</code>. 911 */ 912 public DefaultMutableTreeNode getNextSibling() 913 { 914 if (parent == null) 915 return null; 916 917 int index = parent.getIndex(this) + 1; 918 919 if (index == parent.getChildCount()) 920 return null; 921 922 return (DefaultMutableTreeNode) parent.getChildAt(index); 923 } 924 925 /** 926 * Returns the previous sibling for this tree node. If this node has no 927 * parent, or this node is the first child of its parent, this method returns 928 * <code>null</code>. 929 * 930 * @return The previous sibling, or <code>null</code>. 931 */ 932 public DefaultMutableTreeNode getPreviousSibling() 933 { 934 if (parent == null) 935 return null; 936 937 int index = parent.getIndex(this) - 1; 938 939 if (index < 0) 940 return null; 941 942 return (DefaultMutableTreeNode) parent.getChildAt(index); 943 } 944 945 /** 946 * Returns <code>true</code> if this tree node is a lead node (that is, it 947 * has no children), and <code>false</otherwise>. 948 * 949 * @return A boolean. 950 */ 951 public boolean isLeaf() 952 { 953 return children.size() == 0; 954 } 955 956 /** 957 * Returns the first leaf node that is a descendant of this node. Recall 958 * that a node is its own descendant, so if this node has no children then 959 * it is returned as the first leaf. 960 * 961 * @return The first leaf node. 962 */ 963 public DefaultMutableTreeNode getFirstLeaf() 964 { 965 TreeNode current = this; 966 967 while (current.getChildCount() > 0) 968 current = current.getChildAt(0); 969 970 return (DefaultMutableTreeNode) current; 971 } 972 973 /** 974 * Returns the last leaf node that is a descendant of this node. Recall 975 * that a node is its own descendant, so if this node has no children then 976 * it is returned as the last leaf. 977 * 978 * @return The first leaf node. 979 */ 980 public DefaultMutableTreeNode getLastLeaf() 981 { 982 TreeNode current = this; 983 int size = current.getChildCount(); 984 985 while (size > 0) 986 { 987 current = current.getChildAt(size - 1); 988 size = current.getChildCount(); 989 } 990 991 return (DefaultMutableTreeNode) current; 992 } 993 994 /** 995 * Returns the next leaf node after this tree node. 996 * 997 * @return The next leaf node, or <code>null</code>. 998 */ 999 public DefaultMutableTreeNode getNextLeaf() 1000 { 1001 // if there is a next sibling, return its first leaf 1002 DefaultMutableTreeNode sibling = getNextSibling(); 1003 if (sibling != null) 1004 return sibling.getFirstLeaf(); 1005 // otherwise move up one level and try again... 1006 if (parent != null) 1007 return ((DefaultMutableTreeNode) parent).getNextLeaf(); 1008 return null; 1009 } 1010 1011 /** 1012 * Returns the previous leaf node before this tree node. 1013 * 1014 * @return The previous leaf node, or <code>null</code>. 1015 */ 1016 public DefaultMutableTreeNode getPreviousLeaf() 1017 { 1018 // if there is a previous sibling, return its last leaf 1019 DefaultMutableTreeNode sibling = getPreviousSibling(); 1020 if (sibling != null) 1021 return sibling.getLastLeaf(); 1022 // otherwise move up one level and try again... 1023 if (parent != null) 1024 return ((DefaultMutableTreeNode) parent).getPreviousLeaf(); 1025 return null; 1026 } 1027 1028 /** 1029 * getLeafCount 1030 * 1031 * @return int 1032 */ 1033 public int getLeafCount() 1034 { 1035 int count = 0; 1036 Enumeration<?> e = depthFirstEnumeration(); 1037 1038 while (e.hasMoreElements()) 1039 { 1040 TreeNode current = (TreeNode) e.nextElement(); 1041 1042 if (current.isLeaf()) 1043 count++; 1044 } 1045 1046 return count; 1047 } 1048 1049 /** Provides an enumeration of a tree in breadth-first traversal 1050 * order. 1051 */ 1052 static class BreadthFirstEnumeration implements Enumeration<TreeNode> 1053 { 1054 1055 LinkedList<TreeNode> queue = new LinkedList<TreeNode>(); 1056 1057 BreadthFirstEnumeration(TreeNode node) 1058 { 1059 queue.add(node); 1060 } 1061 1062 public boolean hasMoreElements() 1063 { 1064 return !queue.isEmpty(); 1065 } 1066 1067 @SuppressWarnings("unchecked") 1068 public TreeNode nextElement() 1069 { 1070 if (queue.isEmpty()) 1071 throw new NoSuchElementException("No more elements left."); 1072 1073 TreeNode node = queue.removeFirst(); 1074 1075 Enumeration<TreeNode> children = 1076 (Enumeration<TreeNode>) node.children(); 1077 while (children.hasMoreElements()) 1078 queue.add(children.nextElement()); 1079 1080 return node; 1081 } 1082 } 1083 1084 /** Provides an enumeration of a tree traversing it 1085 * preordered. 1086 */ 1087 static class PreorderEnumeration implements Enumeration<TreeNode> 1088 { 1089 TreeNode next; 1090 1091 Stack<Enumeration<TreeNode>> childrenEnums = 1092 new Stack<Enumeration<TreeNode>>(); 1093 1094 @SuppressWarnings("unchecked") 1095 PreorderEnumeration(TreeNode node) 1096 { 1097 next = node; 1098 childrenEnums.push((Enumeration<TreeNode>) node.children()); 1099 } 1100 1101 public boolean hasMoreElements() 1102 { 1103 return next != null; 1104 } 1105 1106 public TreeNode nextElement() 1107 { 1108 if (next == null) 1109 throw new NoSuchElementException("No more elements left."); 1110 1111 TreeNode current = next; 1112 1113 Enumeration<TreeNode> children = childrenEnums.peek(); 1114 1115 // Retrieves the next element. 1116 next = traverse(children); 1117 1118 return current; 1119 } 1120 1121 @SuppressWarnings("unchecked") 1122 private TreeNode traverse(Enumeration<TreeNode> children) 1123 { 1124 // If more children are available step down. 1125 if (children.hasMoreElements()) 1126 { 1127 TreeNode child = children.nextElement(); 1128 childrenEnums.push((Enumeration<TreeNode>) child.children()); 1129 1130 return child; 1131 } 1132 1133 // If no children are left, we return to a higher level. 1134 childrenEnums.pop(); 1135 1136 // If there are no more levels left, there is no next 1137 // element to return. 1138 if (childrenEnums.isEmpty()) 1139 return null; 1140 else 1141 { 1142 return traverse(childrenEnums.peek()); 1143 } 1144 } 1145 } 1146 1147 /** Provides an enumeration of a tree traversing it 1148 * postordered (= depth-first). 1149 */ 1150 static class PostorderEnumeration implements Enumeration<TreeNode> 1151 { 1152 1153 Stack<TreeNode> nodes = new Stack<TreeNode>(); 1154 Stack<Enumeration<TreeNode>> childrenEnums = 1155 new Stack<Enumeration<TreeNode>>(); 1156 1157 @SuppressWarnings("unchecked") 1158 PostorderEnumeration(TreeNode node) 1159 { 1160 nodes.push(node); 1161 childrenEnums.push((Enumeration<TreeNode>) node.children()); 1162 } 1163 1164 public boolean hasMoreElements() 1165 { 1166 return !nodes.isEmpty(); 1167 } 1168 1169 public TreeNode nextElement() 1170 { 1171 if (nodes.isEmpty()) 1172 throw new NoSuchElementException("No more elements left!"); 1173 1174 Enumeration<TreeNode> children = childrenEnums.peek(); 1175 1176 return traverse(children); 1177 } 1178 1179 @SuppressWarnings("unchecked") 1180 private TreeNode traverse(Enumeration<TreeNode> children) 1181 { 1182 if (children.hasMoreElements()) 1183 { 1184 TreeNode node = children.nextElement(); 1185 nodes.push(node); 1186 1187 Enumeration<TreeNode> newChildren = 1188 (Enumeration<TreeNode>) node.children(); 1189 childrenEnums.push(newChildren); 1190 1191 return traverse(newChildren); 1192 } 1193 else 1194 { 1195 childrenEnums.pop(); 1196 1197 // Returns the node whose children 1198 // have all been visited. (= postorder) 1199 TreeNode next = nodes.peek(); 1200 nodes.pop(); 1201 1202 return next; 1203 } 1204 } 1205 1206 } 1207 1208}