| /* DefaultMutableTreeNode.java -- |
| Copyright (C) 2002, 2004, 2005, 2006, Free Software Foundation, Inc. |
| |
| This file is part of GNU Classpath. |
| |
| GNU Classpath is free software; you can redistribute it and/or modify |
| it under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 2, or (at your option) |
| any later version. |
| |
| GNU Classpath is distributed in the hope that it will be useful, but |
| WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with GNU Classpath; see the file COPYING. If not, write to the |
| Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA |
| 02110-1301 USA. |
| |
| Linking this library statically or dynamically with other modules is |
| making a combined work based on this library. Thus, the terms and |
| conditions of the GNU General Public License cover the whole |
| combination. |
| |
| As a special exception, the copyright holders of this library give you |
| permission to link this library with independent modules to produce an |
| executable, regardless of the license terms of these independent |
| modules, and to copy and distribute the resulting executable under |
| terms of your choice, provided that you also meet, for each linked |
| independent module, the terms and conditions of the license of that |
| module. An independent module is a module which is not derived from |
| or based on this library. If you modify this library, you may extend |
| this exception to your version of the library, but you are not |
| obligated to do so. If you do not wish to do so, delete this |
| exception statement from your version. */ |
| |
| |
| package javax.swing.tree; |
| |
| import gnu.java.util.EmptyEnumeration; |
| |
| import java.io.IOException; |
| import java.io.ObjectInputStream; |
| import java.io.ObjectOutputStream; |
| import java.io.Serializable; |
| import java.util.ArrayList; |
| import java.util.Enumeration; |
| import java.util.LinkedList; |
| import java.util.NoSuchElementException; |
| import java.util.Stack; |
| import java.util.Vector; |
| |
| |
| /** |
| * A default implementation of the {@link MutableTreeNode} interface. |
| * |
| * @author Andrew Selkirk |
| * @author Robert Schuster (robertschuster@fsfe.org) |
| */ |
| public class DefaultMutableTreeNode |
| implements Cloneable, MutableTreeNode, Serializable |
| { |
| private static final long serialVersionUID = -4298474751201349152L; |
| |
| /** |
| * An empty enumeration, returned by {@link #children()} if a node has no |
| * children. |
| */ |
| public static final Enumeration EMPTY_ENUMERATION = |
| EmptyEnumeration.getInstance(); |
| |
| /** |
| * The parent of this node (possibly <code>null</code>). |
| */ |
| protected MutableTreeNode parent; |
| |
| /** |
| * The child nodes for this node (may be empty). |
| */ |
| protected Vector children = new Vector(); |
| |
| /** |
| * userObject |
| */ |
| protected transient Object userObject; |
| |
| /** |
| * allowsChildren |
| */ |
| protected boolean allowsChildren; |
| |
| /** |
| * Creates a <code>DefaultMutableTreeNode</code> object. |
| * This is equivalent to <code>DefaultMutableTreeNode(null, true)</code>. |
| */ |
| public DefaultMutableTreeNode() |
| { |
| this(null, true); |
| } |
| |
| /** |
| * Creates a <code>DefaultMutableTreeNode</code> object with the given |
| * user object attached to it. This is equivalent to |
| * <code>DefaultMutableTreeNode(userObject, true)</code>. |
| * |
| * @param userObject the user object (<code>null</code> permitted). |
| */ |
| public DefaultMutableTreeNode(Object userObject) |
| { |
| this(userObject, true); |
| } |
| |
| /** |
| * Creates a <code>DefaultMutableTreeNode</code> object with the given |
| * user object attached to it. |
| * |
| * @param userObject the user object (<code>null</code> permitted). |
| * @param allowsChildren <code>true</code> if the code allows to add child |
| * nodes, <code>false</code> otherwise |
| */ |
| public DefaultMutableTreeNode(Object userObject, boolean allowsChildren) |
| { |
| this.userObject = userObject; |
| this.allowsChildren = allowsChildren; |
| } |
| |
| /** |
| * Returns a clone of the node. The clone contains a shallow copy of the |
| * user object, and does not copy the parent node or the child nodes. |
| * |
| * @return A clone of the node. |
| */ |
| public Object clone() |
| { |
| return new DefaultMutableTreeNode(this.userObject, this.allowsChildren); |
| } |
| |
| /** |
| * Returns a string representation of the node. This implementation returns |
| * <code>getUserObject().toString()</code>, or <code>null</code> if there |
| * is no user object. |
| * |
| * @return A string representation of the node (possibly <code>null</code>). |
| */ |
| public String toString() |
| { |
| if (userObject == null) |
| return null; |
| |
| return userObject.toString(); |
| } |
| |
| /** |
| * Adds a new child node to this node and sets this node as the parent of |
| * the child node. The child node must not be an ancestor of this node. |
| * If the tree uses the {@link DefaultTreeModel}, you must subsequently |
| * call {@link DefaultTreeModel#reload(TreeNode)}. |
| * |
| * @param child the child node (<code>null</code> not permitted). |
| * |
| * @throws IllegalStateException if {@link #getAllowsChildren()} returns |
| * <code>false</code>. |
| * @throws IllegalArgumentException if {@link #isNodeAncestor} returns |
| * <code>true</code>. |
| * @throws IllegalArgumentException if <code>child</code> is |
| * <code>null</code>. |
| */ |
| public void add(MutableTreeNode child) |
| { |
| if (! allowsChildren) |
| throw new IllegalStateException(); |
| |
| if (child == null) |
| throw new IllegalArgumentException(); |
| |
| if (isNodeAncestor(child)) |
| throw new IllegalArgumentException("Cannot add ancestor node."); |
| |
| children.add(child); |
| child.setParent(this); |
| } |
| |
| /** |
| * Returns the parent node of this node. |
| * |
| * @return The parent node (possibly <code>null</code>). |
| */ |
| public TreeNode getParent() |
| { |
| return parent; |
| } |
| |
| /** |
| * Removes the child with the given index from this node. |
| * |
| * @param index the index (in the range <code>0</code> to |
| * <code>getChildCount() - 1</code>). |
| * |
| * @throws ArrayIndexOutOfBoundsException if <code>index</code> is outside |
| * the valid range. |
| */ |
| public void remove(int index) |
| { |
| MutableTreeNode child = (MutableTreeNode) children.remove(index); |
| child.setParent(null); |
| } |
| |
| /** |
| * Removes the given child from this node and sets its parent to |
| * <code>null</code>. |
| * |
| * @param node the child node (<code>null</code> not permitted). |
| * |
| * @throws IllegalArgumentException if <code>node</code> is not a child of |
| * this node. |
| * @throws IllegalArgumentException if <code>node</code> is null. |
| */ |
| public void remove(MutableTreeNode node) |
| { |
| if (node == null) |
| throw new IllegalArgumentException("Null 'node' argument."); |
| if (node.getParent() != this) |
| throw new IllegalArgumentException( |
| "The given 'node' is not a child of this node."); |
| children.remove(node); |
| node.setParent(null); |
| } |
| |
| /** |
| * writeObject |
| * |
| * @param stream the output stream |
| * |
| * @exception IOException If an error occurs |
| */ |
| private void writeObject(ObjectOutputStream stream) |
| throws IOException |
| { |
| // TODO: Implement me. |
| } |
| |
| /** |
| * readObject |
| * |
| * @param stream the input stream |
| * |
| * @exception IOException If an error occurs |
| * @exception ClassNotFoundException TODO |
| */ |
| private void readObject(ObjectInputStream stream) |
| throws IOException, ClassNotFoundException |
| { |
| // TODO: Implement me. |
| } |
| |
| /** |
| * Inserts given child node at the given index. |
| * |
| * @param node the child node (<code>null</code> not permitted). |
| * @param index the index. |
| * |
| * @throws IllegalArgumentException if <code>node</code> is |
| * </code>null</code>. |
| */ |
| public void insert(MutableTreeNode node, int index) |
| { |
| if (! allowsChildren) |
| throw new IllegalStateException(); |
| |
| if (node == null) |
| throw new IllegalArgumentException("Null 'node' argument."); |
| |
| if (isNodeAncestor(node)) |
| throw new IllegalArgumentException("Cannot insert ancestor node."); |
| |
| children.insertElementAt(node, index); |
| } |
| |
| /** |
| * Returns a path to this node from the root. |
| * |
| * @return an array of tree nodes |
| */ |
| public TreeNode[] getPath() |
| { |
| return getPathToRoot(this, 0); |
| } |
| |
| /** |
| * Returns an enumeration containing all children of this node. |
| * <code>EMPTY_ENUMERATION</code> is returned if this node has no children. |
| * |
| * @return an enumeration of tree nodes |
| */ |
| public Enumeration children() |
| { |
| if (children.size() == 0) |
| return EMPTY_ENUMERATION; |
| |
| return children.elements(); |
| } |
| |
| /** |
| * Set the parent node for this node. |
| * |
| * @param node the parent node |
| */ |
| public void setParent(MutableTreeNode node) |
| { |
| parent = node; |
| } |
| |
| /** |
| * Returns the child node at a given index. |
| * |
| * @param index the index |
| * |
| * @return the child node |
| */ |
| public TreeNode getChildAt(int index) |
| { |
| return (TreeNode) children.elementAt(index); |
| } |
| |
| /** |
| * Returns the number of children of this node. |
| * |
| * @return the number of children |
| */ |
| public int getChildCount() |
| { |
| return children.size(); |
| } |
| |
| /** |
| * Returns the index of the specified child node, or -1 if the node is not |
| * in fact a child of this node. |
| * |
| * @param node the node (<code>null</code> not permitted). |
| * |
| * @return The index of the specified child node, or -1. |
| * |
| * @throws IllegalArgumentException if <code>node</code> is <code>null</code>. |
| */ |
| public int getIndex(TreeNode node) |
| { |
| if (node == null) |
| throw new IllegalArgumentException("Null 'node' argument."); |
| return children.indexOf(node); |
| } |
| |
| /** |
| * Sets the flag that controls whether or not this node allows the addition / |
| * insertion of child nodes. If the flag is set to <code>false</code>, any |
| * existing children are removed. |
| * |
| * @param allowsChildren the flag. |
| */ |
| public void setAllowsChildren(boolean allowsChildren) |
| { |
| if (!allowsChildren) |
| removeAllChildren(); |
| this.allowsChildren = allowsChildren; |
| } |
| |
| /** |
| * getAllowsChildren |
| * |
| * @return boolean |
| */ |
| public boolean getAllowsChildren() |
| { |
| return allowsChildren; |
| } |
| |
| /** |
| * Sets the user object for this node |
| * |
| * @param userObject the user object |
| */ |
| public void setUserObject(Object userObject) |
| { |
| this.userObject = userObject; |
| } |
| |
| /** |
| * Returns the user object attached to this node. <code>null</code> is |
| * returned when no user object is set. |
| * |
| * @return the user object |
| */ |
| public Object getUserObject() |
| { |
| return userObject; |
| } |
| |
| /** |
| * Removes this node from its parent. |
| */ |
| public void removeFromParent() |
| { |
| parent.remove(this); |
| parent = null; |
| } |
| |
| /** |
| * Removes all child nodes from this node. |
| */ |
| public void removeAllChildren() |
| { |
| for (int i = getChildCount() - 1; i >= 0; i--) |
| remove(i); |
| } |
| |
| /** |
| * Returns <code>true</code> if <code>node</code> is an ancestor of this |
| * tree node, and <code>false</code> otherwise. An ancestor node is any of: |
| * <ul> |
| * <li>this tree node;</li> |
| * <li>the parent node (if there is one);</li> |
| * <li>any ancestor of the parent node;</li> |
| * </ul> |
| * If <code>node</code> is <code>null</code>, this method returns |
| * <code>false</code>. |
| * |
| * @param node the node (<code>null</code> permitted). |
| * |
| * @return A boolean. |
| */ |
| public boolean isNodeAncestor(TreeNode node) |
| { |
| if (node == null) |
| return false; |
| |
| TreeNode current = this; |
| |
| while (current != null && current != node) |
| current = current.getParent(); |
| |
| return current == node; |
| } |
| |
| /** |
| * Returns <code>true</code> if <code>node</code> is a descendant of this |
| * tree node, and <code>false</code> otherwise. A descendant node is any of: |
| * <ul> |
| * <li>this tree node;</li> |
| * <li>the child nodes belonging to this tree node, if there are any;</li> |
| * <li>any descendants of the child nodes;</li> |
| * </ul> |
| * If <code>node</code> is <code>null</code>, this method returns |
| * <code>false</code>. |
| * |
| * @param node the node (<code>null</code> permitted). |
| * |
| * @return A boolean. |
| */ |
| public boolean isNodeDescendant(DefaultMutableTreeNode node) |
| { |
| if (node == null) |
| return false; |
| |
| TreeNode current = node; |
| |
| while (current != null |
| && current != this) |
| current = current.getParent(); |
| |
| return current == this; |
| } |
| |
| /** |
| * getSharedAncestor |
| * |
| * @param node TODO |
| * |
| * @return TreeNode |
| */ |
| public TreeNode getSharedAncestor(DefaultMutableTreeNode node) |
| { |
| TreeNode current = this; |
| ArrayList list = new ArrayList(); |
| |
| while (current != null) |
| { |
| list.add(current); |
| current = current.getParent(); |
| } |
| |
| current = node; |
| |
| while (current != null) |
| { |
| if (list.contains(current)) |
| return current; |
| |
| current = current.getParent(); |
| } |
| |
| return null; |
| } |
| |
| /** |
| * isNodeRelated |
| * |
| * @param node TODO |
| * |
| * @return boolean |
| */ |
| public boolean isNodeRelated(DefaultMutableTreeNode node) |
| { |
| if (node == null) |
| return false; |
| |
| return node.getRoot() == getRoot(); |
| } |
| |
| /** |
| * getDepth |
| * |
| * @return int |
| */ |
| public int getDepth() |
| { |
| if ((! allowsChildren) |
| || children.size() == 0) |
| return 0; |
| |
| Stack stack = new Stack(); |
| stack.push(new Integer(0)); |
| TreeNode node = getChildAt(0); |
| int depth = 0; |
| int current = 1; |
| |
| while (! stack.empty()) |
| { |
| if (node.getChildCount() != 0) |
| { |
| node = node.getChildAt(0); |
| stack.push(new Integer(0)); |
| current++; |
| } |
| else |
| { |
| if (current > depth) |
| depth = current; |
| |
| int size; |
| int index; |
| |
| do |
| { |
| node = node.getParent(); |
| size = node.getChildCount(); |
| index = ((Integer) stack.pop()).intValue() + 1; |
| current--; |
| } |
| while (index >= size |
| && node != this); |
| |
| if (index < size) |
| { |
| node = node.getChildAt(index); |
| stack.push(new Integer(index)); |
| current++; |
| } |
| } |
| } |
| |
| return depth; |
| } |
| |
| /** |
| * getLevel |
| * |
| * @return int |
| */ |
| public int getLevel() |
| { |
| int count = -1; |
| TreeNode current = this; |
| |
| do |
| { |
| current = current.getParent(); |
| count++; |
| } |
| while (current != null); |
| |
| return count; |
| } |
| |
| /** |
| * getPathToRoot |
| * |
| * @param node TODO |
| * @param depth TODO |
| * |
| * @return TreeNode[] |
| */ |
| protected TreeNode[] getPathToRoot(TreeNode node, int depth) |
| { |
| if (node == null) |
| { |
| if (depth == 0) |
| return null; |
| |
| return new TreeNode[depth]; |
| } |
| |
| TreeNode[] path = getPathToRoot(node.getParent(), depth + 1); |
| path[path.length - depth - 1] = node; |
| return path; |
| } |
| |
| /** |
| * getUserObjectPath |
| * |
| * @return Object[] |
| */ |
| public Object[] getUserObjectPath() |
| { |
| TreeNode[] path = getPathToRoot(this, 0); |
| Object[] object = new Object[path.length]; |
| |
| for (int index = 0; index < path.length; ++index) |
| object[index] = ((DefaultMutableTreeNode) path[index]).getUserObject(); |
| |
| return object; |
| } |
| |
| /** |
| * Returns the root node by iterating the parents of this node. |
| * |
| * @return the root node |
| */ |
| public TreeNode getRoot() |
| { |
| TreeNode current = this; |
| TreeNode check = current.getParent(); |
| |
| while (check != null) |
| { |
| current = check; |
| check = current.getParent(); |
| } |
| |
| return current; |
| } |
| |
| /** |
| * Tells whether this node is the root node or not. |
| * |
| * @return <code>true</code> if this is the root node, |
| * <code>false</code>otherwise |
| */ |
| public boolean isRoot() |
| { |
| return parent == null; |
| } |
| |
| /** |
| * getNextNode |
| * |
| * @return DefaultMutableTreeNode |
| */ |
| public DefaultMutableTreeNode getNextNode() |
| { |
| // Return first child. |
| if (getChildCount() != 0) |
| return (DefaultMutableTreeNode) getChildAt(0); |
| |
| // Return next sibling (if needed the sibling of some parent). |
| DefaultMutableTreeNode node = this; |
| DefaultMutableTreeNode sibling; |
| |
| do |
| { |
| sibling = node.getNextSibling(); |
| node = (DefaultMutableTreeNode) node.getParent(); |
| } |
| while (sibling == null && |
| node != null); |
| |
| // Return sibling. |
| return sibling; |
| } |
| |
| /** |
| * getPreviousNode |
| * |
| * @return DefaultMutableTreeNode |
| */ |
| public DefaultMutableTreeNode getPreviousNode() |
| { |
| // Return null if no parent. |
| if (parent == null) |
| return null; |
| |
| DefaultMutableTreeNode sibling = getPreviousSibling(); |
| |
| // Return parent if no sibling. |
| if (sibling == null) |
| return (DefaultMutableTreeNode) parent; |
| |
| // Return last leaf of sibling. |
| if (sibling.getChildCount() != 0) |
| return sibling.getLastLeaf(); |
| |
| // Return sibling. |
| return sibling; |
| } |
| |
| /** |
| * preorderEnumeration |
| * |
| * @return Enumeration |
| */ |
| public Enumeration preorderEnumeration() |
| { |
| return new PreorderEnumeration(this); |
| } |
| |
| /** |
| * postorderEnumeration |
| * |
| * @return Enumeration |
| */ |
| public Enumeration postorderEnumeration() |
| { |
| return new PostorderEnumeration(this); |
| } |
| |
| /** |
| * breadthFirstEnumeration |
| * |
| * @return Enumeration |
| */ |
| public Enumeration breadthFirstEnumeration() |
| { |
| return new BreadthFirstEnumeration(this); |
| } |
| |
| /** |
| * depthFirstEnumeration |
| * |
| * @return Enumeration |
| */ |
| public Enumeration depthFirstEnumeration() |
| { |
| return postorderEnumeration(); |
| } |
| |
| /** |
| * pathFromAncestorEnumeration |
| * |
| * @param node TODO |
| * |
| * @return Enumeration |
| */ |
| public Enumeration pathFromAncestorEnumeration(TreeNode node) |
| { |
| if (node == null) |
| throw new IllegalArgumentException(); |
| |
| TreeNode parent = this; |
| Vector nodes = new Vector(); |
| nodes.add(this); |
| |
| while (parent != node && parent != null) |
| { |
| parent = parent.getParent(); |
| nodes.add(0, parent); |
| } |
| |
| if (parent != node) |
| throw new IllegalArgumentException(); |
| |
| return nodes.elements(); |
| } |
| |
| /** |
| * Returns <code>true</code> if <code>node</code> is a child of this tree |
| * node, and <code>false</code> otherwise. If <code>node</code> is |
| * <code>null</code>, this method returns <code>false</code>. |
| * |
| * @param node the node (<code>null</code> permitted). |
| * |
| * @return A boolean. |
| */ |
| public boolean isNodeChild(TreeNode node) |
| { |
| if (node == null) |
| return false; |
| |
| return node.getParent() == this; |
| } |
| |
| /** |
| * Returns the first child node belonging to this tree node. |
| * |
| * @return The first child node. |
| * |
| * @throws NoSuchElementException if this tree node has no children. |
| */ |
| public TreeNode getFirstChild() |
| { |
| return (TreeNode) children.firstElement(); |
| } |
| |
| /** |
| * Returns the last child node belonging to this tree node. |
| * |
| * @return The last child node. |
| * |
| * @throws NoSuchElementException if this tree node has no children. |
| */ |
| public TreeNode getLastChild() |
| { |
| return (TreeNode) children.lastElement(); |
| } |
| |
| /** |
| * Returns the next child after the specified <code>node</code>, or |
| * <code>null</code> if there is no child after the specified |
| * <code>node</code>. |
| * |
| * @param node a child of this node (<code>null</code> not permitted). |
| * |
| * @return The next child, or <code>null</code>. |
| * |
| * @throws IllegalArgumentException if <code>node</code> is not a child of |
| * this node, or is <code>null</code>. |
| */ |
| public TreeNode getChildAfter(TreeNode node) |
| { |
| if (node == null || node.getParent() != this) |
| throw new IllegalArgumentException(); |
| |
| int index = getIndex(node) + 1; |
| |
| if (index == getChildCount()) |
| return null; |
| |
| return getChildAt(index); |
| } |
| |
| /** |
| * Returns the previous child before the specified <code>node</code>, or |
| * <code>null</code> if there is no child before the specified |
| * <code>node</code>. |
| * |
| * @param node a child of this node (<code>null</code> not permitted). |
| * |
| * @return The previous child, or <code>null</code>. |
| * |
| * @throws IllegalArgumentException if <code>node</code> is not a child of |
| * this node, or is <code>null</code>. |
| */ |
| public TreeNode getChildBefore(TreeNode node) |
| { |
| if (node == null || node.getParent() != this) |
| throw new IllegalArgumentException(); |
| |
| int index = getIndex(node) - 1; |
| |
| if (index < 0) |
| return null; |
| |
| return getChildAt(index); |
| } |
| |
| /** |
| * Returns <code>true</code> if this tree node and <code>node</code> share |
| * the same parent. If <code>node</code> is this tree node, the method |
| * returns <code>true</code> and if <code>node</code> is <code>null</code> |
| * this method returns <code>false</code>. |
| * |
| * @param node the node (<code>null</code> permitted). |
| * |
| * @return A boolean. |
| */ |
| public boolean isNodeSibling(TreeNode node) |
| { |
| if (node == null) |
| return false; |
| if (node == this) |
| return true; |
| return node.getParent() == getParent() && getParent() != null; |
| } |
| |
| /** |
| * Returns the number of siblings for this tree node. If the tree node has |
| * a parent, this method returns the child count for the parent, otherwise |
| * it returns <code>1</code>. |
| * |
| * @return The sibling count. |
| */ |
| public int getSiblingCount() |
| { |
| if (parent == null) |
| return 1; |
| |
| return parent.getChildCount(); |
| } |
| |
| /** |
| * Returns the next sibling for this tree node. If this node has no parent, |
| * or this node is the last child of its parent, this method returns |
| * <code>null</code>. |
| * |
| * @return The next sibling, or <code>null</code>. |
| */ |
| public DefaultMutableTreeNode getNextSibling() |
| { |
| if (parent == null) |
| return null; |
| |
| int index = parent.getIndex(this) + 1; |
| |
| if (index == parent.getChildCount()) |
| return null; |
| |
| return (DefaultMutableTreeNode) parent.getChildAt(index); |
| } |
| |
| /** |
| * Returns the previous sibling for this tree node. If this node has no |
| * parent, or this node is the first child of its parent, this method returns |
| * <code>null</code>. |
| * |
| * @return The previous sibling, or <code>null</code>. |
| */ |
| public DefaultMutableTreeNode getPreviousSibling() |
| { |
| if (parent == null) |
| return null; |
| |
| int index = parent.getIndex(this) - 1; |
| |
| if (index < 0) |
| return null; |
| |
| return (DefaultMutableTreeNode) parent.getChildAt(index); |
| } |
| |
| /** |
| * Returns <code>true</code> if this tree node is a lead node (that is, it |
| * has no children), and <code>false</otherwise>. |
| * |
| * @return A boolean. |
| */ |
| public boolean isLeaf() |
| { |
| return children.size() == 0; |
| } |
| |
| /** |
| * Returns the first leaf node that is a descendant of this node. Recall |
| * that a node is its own descendant, so if this node has no children then |
| * it is returned as the first leaf. |
| * |
| * @return The first leaf node. |
| */ |
| public DefaultMutableTreeNode getFirstLeaf() |
| { |
| TreeNode current = this; |
| |
| while (current.getChildCount() > 0) |
| current = current.getChildAt(0); |
| |
| return (DefaultMutableTreeNode) current; |
| } |
| |
| /** |
| * Returns the last leaf node that is a descendant of this node. Recall |
| * that a node is its own descendant, so if this node has no children then |
| * it is returned as the last leaf. |
| * |
| * @return The first leaf node. |
| */ |
| public DefaultMutableTreeNode getLastLeaf() |
| { |
| TreeNode current = this; |
| int size = current.getChildCount(); |
| |
| while (size > 0) |
| { |
| current = current.getChildAt(size - 1); |
| size = current.getChildCount(); |
| } |
| |
| return (DefaultMutableTreeNode) current; |
| } |
| |
| /** |
| * Returns the next leaf node after this tree node. |
| * |
| * @return The next leaf node, or <code>null</code>. |
| */ |
| public DefaultMutableTreeNode getNextLeaf() |
| { |
| // if there is a next sibling, return its first leaf |
| DefaultMutableTreeNode sibling = getNextSibling(); |
| if (sibling != null) |
| return sibling.getFirstLeaf(); |
| // otherwise move up one level and try again... |
| if (parent != null) |
| return ((DefaultMutableTreeNode) parent).getNextLeaf(); |
| return null; |
| } |
| |
| /** |
| * Returns the previous leaf node before this tree node. |
| * |
| * @return The previous leaf node, or <code>null</code>. |
| */ |
| public DefaultMutableTreeNode getPreviousLeaf() |
| { |
| // if there is a previous sibling, return its last leaf |
| DefaultMutableTreeNode sibling = getPreviousSibling(); |
| if (sibling != null) |
| return sibling.getLastLeaf(); |
| // otherwise move up one level and try again... |
| if (parent != null) |
| return ((DefaultMutableTreeNode) parent).getPreviousLeaf(); |
| return null; |
| } |
| |
| /** |
| * getLeafCount |
| * |
| * @return int |
| */ |
| public int getLeafCount() |
| { |
| int count = 0; |
| Enumeration e = depthFirstEnumeration(); |
| |
| while (e.hasMoreElements()) |
| { |
| TreeNode current = (TreeNode) e.nextElement(); |
| |
| if (current.isLeaf()) |
| count++; |
| } |
| |
| return count; |
| } |
| |
| /** Provides an enumeration of a tree in breadth-first traversal |
| * order. |
| */ |
| static class BreadthFirstEnumeration implements Enumeration |
| { |
| |
| LinkedList queue = new LinkedList(); |
| |
| BreadthFirstEnumeration(TreeNode node) |
| { |
| queue.add(node); |
| } |
| |
| public boolean hasMoreElements() |
| { |
| return !queue.isEmpty(); |
| } |
| |
| public Object nextElement() |
| { |
| if (queue.isEmpty()) |
| throw new NoSuchElementException("No more elements left."); |
| |
| TreeNode node = (TreeNode) queue.removeFirst(); |
| |
| Enumeration children = node.children(); |
| while (children.hasMoreElements()) |
| queue.add(children.nextElement()); |
| |
| return node; |
| } |
| } |
| |
| /** Provides an enumeration of a tree traversing it |
| * preordered. |
| */ |
| static class PreorderEnumeration implements Enumeration |
| { |
| TreeNode next; |
| |
| Stack childrenEnums = new Stack(); |
| |
| PreorderEnumeration(TreeNode node) |
| { |
| next = node; |
| childrenEnums.push(node.children()); |
| } |
| |
| public boolean hasMoreElements() |
| { |
| return next != null; |
| } |
| |
| public Object nextElement() |
| { |
| if (next == null) |
| throw new NoSuchElementException("No more elements left."); |
| |
| Object current = next; |
| |
| Enumeration children = (Enumeration) childrenEnums.peek(); |
| |
| // Retrieves the next element. |
| next = traverse(children); |
| |
| return current; |
| } |
| |
| private TreeNode traverse(Enumeration children) |
| { |
| // If more children are available step down. |
| if (children.hasMoreElements()) |
| { |
| TreeNode child = (TreeNode) children.nextElement(); |
| childrenEnums.push(child.children()); |
| |
| return child; |
| } |
| |
| // If no children are left, we return to a higher level. |
| childrenEnums.pop(); |
| |
| // If there are no more levels left, there is no next |
| // element to return. |
| if (childrenEnums.isEmpty()) |
| return null; |
| else |
| { |
| return traverse((Enumeration) childrenEnums.peek()); |
| } |
| } |
| } |
| |
| /** Provides an enumeration of a tree traversing it |
| * postordered (= depth-first). |
| */ |
| static class PostorderEnumeration implements Enumeration |
| { |
| |
| Stack nodes = new Stack(); |
| Stack childrenEnums = new Stack(); |
| |
| PostorderEnumeration(TreeNode node) |
| { |
| nodes.push(node); |
| childrenEnums.push(node.children()); |
| } |
| |
| public boolean hasMoreElements() |
| { |
| return !nodes.isEmpty(); |
| } |
| |
| public Object nextElement() |
| { |
| if (nodes.isEmpty()) |
| throw new NoSuchElementException("No more elements left!"); |
| |
| Enumeration children = (Enumeration) childrenEnums.peek(); |
| |
| return traverse(children); |
| } |
| |
| private Object traverse(Enumeration children) |
| { |
| if (children.hasMoreElements()) |
| { |
| TreeNode node = (TreeNode) children.nextElement(); |
| nodes.push(node); |
| |
| Enumeration newChildren = node.children(); |
| childrenEnums.push(newChildren); |
| |
| return traverse(newChildren); |
| } |
| else |
| { |
| childrenEnums.pop(); |
| |
| // Returns the node whose children |
| // have all been visited. (= postorder) |
| Object next = nodes.peek(); |
| nodes.pop(); |
| |
| return next; |
| } |
| } |
| |
| } |
| |
| } |