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