// Go up the tree until the nodes are at the same level while (diff > 0) { node1 = node1.getParent(); diff--; } // Move up the tree until we find a common ancestor. Since we know // that both nodes are at the same level, we won't cross paths // unknowingly (if there is a common ancestor, both nodes hit it in // the same iteration). do { if (node1 == node2) { return node1; } node1 = node1.getParent(); node2 = node2.getParent(); } while (node1 != null);// only need to check one -- they're at the // same level so if one is null, the other is if (node1 != null || node2 != null) { throw new Error ("nodes should be null"); } return null; } /** * Returns true if and only if <code>aNode</code> is in the same tree * as this node. Returns false if <code>aNode</code> is null. * * @see #getSharedAncestor * @see #getRoot * @return true if <code>aNode</code> is in the same tree as this node; * false if <code>aNode</code> is null */ public boolean isNodeRelated(DefaultMutableTreeNode aNode) { return (aNode != null) && (getRoot() == aNode.getRoot()); } /** * Returns the depth of the tree rooted at this node -- the longest * distance from this node to a leaf. If this node has no children, * returns 0. This operation is much more expensive than * <code>getLevel()</code> because it must effectively traverse the entire * tree rooted at this node. * * @see #getLevel * @return the depth of the tree whose root is this node */ public int getDepth() { Object last = null; Enumeration enum_ = breadthFirstEnumeration(); while (enum_.hasMoreElements()) { last = enum_.nextElement(); } if (last == null) { throw new Error ("nodes should be null"); } return ((DefaultMutableTreeNode)last).getLevel() - getLevel(); } /** * Returns the number of levels above this node -- the distance from * the root to this node. If this node is the root, returns 0. * * @see #getDepth * @return the number of levels above this node */ public int getLevel() { TreeNode ancestor; int levels = 0; ancestor = this; while((ancestor = ancestor.getParent()) != null){ levels++; } return levels; } /** * Returns the path from the root, to get to this node. The last * element in the path is this node. * * @return an array of TreeNode objects giving the path, where the * first element in the path is the root and the last * element is this node. */ public TreeNode[] getPath() { return getPathToRoot(this, 0); } /** * Builds the parents of node up to and including the root node, * where the original node is the last element in the returned array. * The length of the returned array gives the node's depth in the * tree. * * @param aNode the TreeNode to get the path for * @param depth an int giving the number of steps already taken towards * the root (on recursive calls), used to size the returned array * @return an array of TreeNodes giving the path from the root to the * specified node */ protected TreeNode[] getPathToRoot(TreeNode aNode, int depth) { TreeNode[] retNodes; /* Check for null, in case someone passed in a null node, or they passed in an element that isn't rooted at root. */ if(aNode == null) { if(depth == 0) return null; else retNodes = new TreeNode[depth]; } else { depth++; retNodes = getPathToRoot(aNode.getParent(), depth); retNodes[retNodes.length - depth] = aNode; } return retNodes; } /** * Returns the user object path, from the root, to get to this node. * If some of the TreeNodes in the path have null user objects, the * returned path will contain nulls. */ public Object[] getUserObjectPath() { TreeNode[] realPath = getPath(); Object[] retPath = new Object[realPath.length]; for(int counter = 0; counter < realPath.length; counter++) retPath[counter] = ((DefaultMutableTreeNode)realPath[counter]) .getUserObject(); return retPath; } /** * Returns the root of the tree that contains this node. The root is * the ancestor with a null parent. * * @see #isNodeAncestor * @return the root of the tree that contains this node */ public TreeNode getRoot() { TreeNode ancestor = this; TreeNode previous; do { previous = ancestor; ancestor = ancestor.getParent(); } while (ancestor != null); return previous; } /** * Returns true if this node is the root of the tree. The root is * the only node in the tree with a null parent; every tree has exactly * one root. * * @return true if this node is the root of its tree */ public boolean isRoot() { return getParent() == null; } /** * Returns the node that follows this node in a preorder traversal of this * node's tree. Returns null if this node is the last node of the * traversal. This is an inefficient way to traverse the entire tree; use * an enumeration, instead. * * @see #preorderEnumeration * @return the node that follows this node in a preorder traversal, or * null if this node is last */ public DefaultMutableTreeNode getNextNode() { if (getChildCount() == 0) { // No children, so look for nextSibling DefaultMutableTreeNode nextSibling = getNextSibling(); if (nextSibling == null) { DefaultMutableTreeNode aNode = (DefaultMutableTreeNode)getParent(); do { if (aNode == null) { return null; } nextSibling = aNode.getNextSibling(); if (nextSibling != null) { return nextSibling; } aNode = (DefaultMutableTreeNode)aNode.getParent(); } while(true); } else { return nextSibling; } } else { return (DefaultMutableTreeNode)getChildAt(0); } } /** * Returns the node that precedes this node in a preorder traversal of * this node's tree. Returns <code>null</code> if this node is the * first node of the traversal -- the root of the tree. * This is an inefficient way to * traverse the entire tree; use an enumeration, instead. * * @see #preorderEnumeration * @return the node that precedes this node in a preorder traversal, or * null if this node is the first */ public DefaultMutableTreeNode getPreviousNode() { DefaultMutableTreeNode previousSibling; DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent(); if (myParent == null) { return null; } previousSibling = getPreviousSibling(); if (previousSibling != null) { if (previousSibling.getChildCount() == 0) return previousSibling; else return previousSibling.getLastLeaf(); } else { return myParent; } } /** * Creates and returns an enumeration that traverses the subtree rooted at * this node in preorder. The first node returned by the enumeration's * <code>nextElement()</code> method is this node.<P> * * Modifying the tree by inserting, removing, or moving a node invalidates * any enumerations created before the modification. * * @see #postorderEnumeration * @return an enumeration for traversing the tree in preorder */ public Enumeration preorderEnumeration() { return new PreorderEnumeration(this); } /** * Creates and returns an enumeration that traverses the subtree rooted at * this node in postorder. The first node returned by the enumeration's * <code>nextElement()</code> method is the leftmost leaf. This is the * same as a depth-first traversal.<P> * * Modifying the tree by inserting, removing, or moving a node invalidates * any enumerations created before the modification. * * @see #depthFirstEnumeration * @see #preorderEnumeration * @return an enumeration for traversing the tree in postorder */ public Enumeration postorderEnumeration() { return new PostorderEnumeration(this); } /** * Creates and returns an enumeration that traverses the subtree rooted at * this node in breadth-first order. The first node returned by the * enumeration's <code>nextElement()</code> method is this node.<P> * * Modifying the tree by inserting, removing, or moving a node invalidates * any enumerations created before the modification. * * @see #depthFirstEnumeration * @return an enumeration for traversing the tree in breadth-first order */ public Enumeration breadthFirstEnumeration() { return new BreadthFirstEnumeration(this); } /** * Creates and returns an enumeration that traverses the subtree rooted at * this node in depth-first order. The first node returned by the * enumeration's <code>nextElement()</code> method is the leftmost leaf. * This is the same as a postorder traversal.<P> * * Modifying the tree by inserting, removing, or moving a node invalidates * any enumerations created before the modification. * * @see #breadthFirstEnumeration * @see #postorderEnumeration * @return an enumeration for traversing the tree in depth-first order */ public Enumeration depthFirstEnumeration() { return postorderEnumeration(); } /** * Creates and returns an enumeration that follows the path from * <code>ancestor</code> to this node. The enumeration's * <code>nextElement()</code> method first returns <code>ancestor</code>, * then the child of <code>ancestor</code> that is an ancestor of this * node, and so on, and finally returns this node. Creation of the * enumeration is O(m) where m is the number of nodes between this node * and <code>ancestor</code>, inclusive. Each <code>nextElement()</code> * message is O(1).<P> * * Modifying the tree by inserting, removing, or moving a node invalidates * any enumerations created before the modification. * * @see #isNodeAncestor * @see #isNodeDescendant * @exception IllegalArgumentException if <code>ancestor</code> is * not an ancestor of this node * @return an enumeration for following the path from an ancestor of * this node to this one */ public Enumeration pathFromAncestorEnumeration(TreeNode ancestor) { return new PathBetweenNodesEnumeration(ancestor, this); } // // Child Queries // /** * Returns true if <code>aNode</code> is a child of this node. If * <code>aNode</code> is null, this method returns false. * * @return true if <code>aNode</code> is a child of this node; false if * <code>aNode</code> is null */ public boolean isNodeChild(TreeNode aNode) { boolean retval; if (aNode == null) { retval = false; } else { if (getChildCount() == 0) { retval = false; } else { retval = (aNode.getParent() == this); } } return retval; } /** * Returns this node's first child. If this node has no children, * throws NoSuchElementException. * * @return the first child of this node * @exception NoSuchElementException if this node has no children */ public TreeNode getFirstChild() { if (getChildCount() == 0) { throw new NoSuchElementException("node has no children"); } return getChildAt(0); } /** * Returns this node's last child. If this node has no children, * throws NoSuchElementException. * * @return the last child of this node * @exception NoSuchElementException if this node has no children */ public TreeNode getLastChild() { if (getChildCount() == 0) { throw new NoSuchElementException("node has no children"); } return getChildAt(getChildCount()-1); } /** * Returns the child in this node's child array that immediately * follows <code>aChild</code>, which must be a child of this node. If * <code>aChild</code> is the last child, returns null. This method * performs a linear search of this node's children for * <code>aChild</code> and is O(n) where n is the number of children; to * traverse the entire array of children, use an enumeration instead. * * @see #children * @exception IllegalArgumentException if <code>aChild</code> is * null or is not a child of this node * @return the child of this node that immediately follows * <code>aChild</code> */ public TreeNode getChildAfter(TreeNode aChild) { if (aChild == null) { throw new IllegalArgumentException("argument is null"); } int index = getIndex(aChild); // linear search if (index == -1) { throw new IllegalArgumentException("node is not a child"); } if (index < getChildCount() - 1) { return getChildAt(index + 1); } else { return null; } } /** * Returns the child in this node's child array that immediately * precedes <code>aChild</code>, which must be a child of this node. If * <code>aChild</code> is the first child, returns null. This method * performs a linear search of this node's children for <code>aChild</code> * and is O(n) where n is the number of children. * * @exception IllegalArgumentException if <code>aChild</code> is null * or is not a child of this node * @return the child of this node that immediately precedes * <code>aChild</code> */ public TreeNode getChildBefore(TreeNode aChild) { if (aChild == null) { throw new IllegalArgumentException("argument is null"); } int index = getIndex(aChild); // linear search if (index == -1) { throw new IllegalArgumentException("argument is not a child"); } if (index > 0) { return getChildAt(index - 1); } else { return null; } } // // Sibling Queries // /** * Returns true if <code>anotherNode</code> is a sibling of (has the * same parent as) this node. A node is its own sibling. If * <code>anotherNode</code> is null, returns false. * * @param anotherNode node to test as sibling of this node * @return true if <code>anotherNode</code> is a sibling of this node */ public boolean isNodeSibling(TreeNode anotherNode) { boolean retval; if (anotherNode == null) { retval = false; } else if (anotherNode == this) { retval = true; } else { TreeNode myParent = getParent(); retval = (myParent != null && myParent == anotherNode.getParent()); if (retval && !((DefaultMutableTreeNode)getParent()) .isNodeChild(anotherNode)) { throw new Error("sibling has different parent"); } } return retval; } /** * Returns the number of siblings of this node. A node is its own sibling * (if it has no parent or no siblings, this method returns * <code>1</code>). *Lines 501–1000 of 1500. Previous lines Load more
// Go up the tree until the nodes are at the same level while (diff > 0) { node1 = node1.getParent(); diff--; } // Move up the tree until we find a common ancestor. Since we know // that both nodes are at the same level, we won't cross paths // unknowingly (if there is a common ancestor, both nodes hit it in // the same iteration). do { if (node1 == node2) { return node1; } node1 = node1.getParent(); node2 = node2.getParent(); } while (node1 != null);// only need to check one -- they're at the // same level so if one is null, the other is if (node1 != null || node2 != null) { throw new Error ("nodes should be null"); } return null; } /** * Returns true if and only if <code>aNode</code> is in the same tree * as this node. Returns false if <code>aNode</code> is null. * * @see #getSharedAncestor * @see #getRoot * @return true if <code>aNode</code> is in the same tree as this node; * false if <code>aNode</code> is null */ public boolean isNodeRelated(DefaultMutableTreeNode aNode) { return (aNode != null) && (getRoot() == aNode.getRoot()); } /** * Returns the depth of the tree rooted at this node -- the longest * distance from this node to a leaf. If this node has no children, * returns 0. This operation is much more expensive than * <code>getLevel()</code> because it must effectively traverse the entire * tree rooted at this node. * * @see #getLevel * @return the depth of the tree whose root is this node */ public int getDepth() { Object last = null; Enumeration enum_ = breadthFirstEnumeration(); while (enum_.hasMoreElements()) { last = enum_.nextElement(); } if (last == null) { throw new Error ("nodes should be null"); } return ((DefaultMutableTreeNode)last).getLevel() - getLevel(); } /** * Returns the number of levels above this node -- the distance from * the root to this node. If this node is the root, returns 0. * * @see #getDepth * @return the number of levels above this node */ public int getLevel() { TreeNode ancestor; int levels = 0; ancestor = this; while((ancestor = ancestor.getParent()) != null){ levels++; } return levels; } /** * Returns the path from the root, to get to this node. The last * element in the path is this node. * * @return an array of TreeNode objects giving the path, where the * first element in the path is the root and the last * element is this node. */ public TreeNode[] getPath() { return getPathToRoot(this, 0); } /** * Builds the parents of node up to and including the root node, * where the original node is the last element in the returned array. * The length of the returned array gives the node's depth in the * tree. * * @param aNode the TreeNode to get the path for * @param depth an int giving the number of steps already taken towards * the root (on recursive calls), used to size the returned array * @return an array of TreeNodes giving the path from the root to the * specified node */ protected TreeNode[] getPathToRoot(TreeNode aNode, int depth) { TreeNode[] retNodes; /* Check for null, in case someone passed in a null node, or they passed in an element that isn't rooted at root. */ if(aNode == null) { if(depth == 0) return null; else retNodes = new TreeNode[depth]; } else { depth++; retNodes = getPathToRoot(aNode.getParent(), depth); retNodes[retNodes.length - depth] = aNode; } return retNodes; } /** * Returns the user object path, from the root, to get to this node. * If some of the TreeNodes in the path have null user objects, the * returned path will contain nulls. */ public Object[] getUserObjectPath() { TreeNode[] realPath = getPath(); Object[] retPath = new Object[realPath.length]; for(int counter = 0; counter < realPath.length; counter++) retPath[counter] = ((DefaultMutableTreeNode)realPath[counter]) .getUserObject(); return retPath; } /** * Returns the root of the tree that contains this node. The root is * the ancestor with a null parent. * * @see #isNodeAncestor * @return the root of the tree that contains this node */ public TreeNode getRoot() { TreeNode ancestor = this; TreeNode previous; do { previous = ancestor; ancestor = ancestor.getParent(); } while (ancestor != null); return previous; } /** * Returns true if this node is the root of the tree. The root is * the only node in the tree with a null parent; every tree has exactly * one root. * * @return true if this node is the root of its tree */ public boolean isRoot() { return getParent() == null; } /** * Returns the node that follows this node in a preorder traversal of this * node's tree. Returns null if this node is the last node of the * traversal. This is an inefficient way to traverse the entire tree; use * an enumeration, instead. * * @see #preorderEnumeration * @return the node that follows this node in a preorder traversal, or * null if this node is last */ public DefaultMutableTreeNode getNextNode() { if (getChildCount() == 0) { // No children, so look for nextSibling DefaultMutableTreeNode nextSibling = getNextSibling(); if (nextSibling == null) { DefaultMutableTreeNode aNode = (DefaultMutableTreeNode)getParent(); do { if (aNode == null) { return null; } nextSibling = aNode.getNextSibling(); if (nextSibling != null) { return nextSibling; } aNode = (DefaultMutableTreeNode)aNode.getParent(); } while(true); } else { return nextSibling; } } else { return (DefaultMutableTreeNode)getChildAt(0); } } /** * Returns the node that precedes this node in a preorder traversal of * this node's tree. Returns <code>null</code> if this node is the * first node of the traversal -- the root of the tree. * This is an inefficient way to * traverse the entire tree; use an enumeration, instead. * * @see #preorderEnumeration * @return the node that precedes this node in a preorder traversal, or * null if this node is the first */ public DefaultMutableTreeNode getPreviousNode() { DefaultMutableTreeNode previousSibling; DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent(); if (myParent == null) { return null; } previousSibling = getPreviousSibling(); if (previousSibling != null) { if (previousSibling.getChildCount() == 0) return previousSibling; else return previousSibling.getLastLeaf(); } else { return myParent; } } /** * Creates and returns an enumeration that traverses the subtree rooted at * this node in preorder. The first node returned by the enumeration's * <code>nextElement()</code> method is this node.<P> * * Modifying the tree by inserting, removing, or moving a node invalidates * any enumerations created before the modification. * * @see #postorderEnumeration * @return an enumeration for traversing the tree in preorder */ public Enumeration preorderEnumeration() { return new PreorderEnumeration(this); } /** * Creates and returns an enumeration that traverses the subtree rooted at * this node in postorder. The first node returned by the enumeration's * <code>nextElement()</code> method is the leftmost leaf. This is the * same as a depth-first traversal.<P> * * Modifying the tree by inserting, removing, or moving a node invalidates * any enumerations created before the modification. * * @see #depthFirstEnumeration * @see #preorderEnumeration * @return an enumeration for traversing the tree in postorder */ public Enumeration postorderEnumeration() { return new PostorderEnumeration(this); } /** * Creates and returns an enumeration that traverses the subtree rooted at * this node in breadth-first order. The first node returned by the * enumeration's <code>nextElement()</code> method is this node.<P> * * Modifying the tree by inserting, removing, or moving a node invalidates * any enumerations created before the modification. * * @see #depthFirstEnumeration * @return an enumeration for traversing the tree in breadth-first order */ public Enumeration breadthFirstEnumeration() { return new BreadthFirstEnumeration(this); } /** * Creates and returns an enumeration that traverses the subtree rooted at * this node in depth-first order. The first node returned by the * enumeration's <code>nextElement()</code> method is the leftmost leaf. * This is the same as a postorder traversal.<P> * * Modifying the tree by inserting, removing, or moving a node invalidates * any enumerations created before the modification. * * @see #breadthFirstEnumeration * @see #postorderEnumeration * @return an enumeration for traversing the tree in depth-first order */ public Enumeration depthFirstEnumeration() { return postorderEnumeration(); } /** * Creates and returns an enumeration that follows the path from * <code>ancestor</code> to this node. The enumeration's * <code>nextElement()</code> method first returns <code>ancestor</code>, * then the child of <code>ancestor</code> that is an ancestor of this * node, and so on, and finally returns this node. Creation of the * enumeration is O(m) where m is the number of nodes between this node * and <code>ancestor</code>, inclusive. Each <code>nextElement()</code> * message is O(1).<P> * * Modifying the tree by inserting, removing, or moving a node invalidates * any enumerations created before the modification. * * @see #isNodeAncestor * @see #isNodeDescendant * @exception IllegalArgumentException if <code>ancestor</code> is * not an ancestor of this node * @return an enumeration for following the path from an ancestor of * this node to this one */ public Enumeration pathFromAncestorEnumeration(TreeNode ancestor) { return new PathBetweenNodesEnumeration(ancestor, this); } // // Child Queries // /** * Returns true if <code>aNode</code> is a child of this node. If * <code>aNode</code> is null, this method returns false. * * @return true if <code>aNode</code> is a child of this node; false if * <code>aNode</code> is null */ public boolean isNodeChild(TreeNode aNode) { boolean retval; if (aNode == null) { retval = false; } else { if (getChildCount() == 0) { retval = false; } else { retval = (aNode.getParent() == this); } } return retval; } /** * Returns this node's first child. If this node has no children, * throws NoSuchElementException. * * @return the first child of this node * @exception NoSuchElementException if this node has no children */ public TreeNode getFirstChild() { if (getChildCount() == 0) { throw new NoSuchElementException("node has no children"); } return getChildAt(0); } /** * Returns this node's last child. If this node has no children, * throws NoSuchElementException. * * @return the last child of this node * @exception NoSuchElementException if this node has no children */ public TreeNode getLastChild() { if (getChildCount() == 0) { throw new NoSuchElementException("node has no children"); } return getChildAt(getChildCount()-1); } /** * Returns the child in this node's child array that immediately * follows <code>aChild</code>, which must be a child of this node. If * <code>aChild</code> is the last child, returns null. This method * performs a linear search of this node's children for * <code>aChild</code> and is O(n) where n is the number of children; to * traverse the entire array of children, use an enumeration instead. * * @see #children * @exception IllegalArgumentException if <code>aChild</code> is * null or is not a child of this node * @return the child of this node that immediately follows * <code>aChild</code> */ public TreeNode getChildAfter(TreeNode aChild) { if (aChild == null) { throw new IllegalArgumentException("argument is null"); } int index = getIndex(aChild); // linear search if (index == -1) { throw new IllegalArgumentException("node is not a child"); } if (index < getChildCount() - 1) { return getChildAt(index + 1); } else { return null; } } /** * Returns the child in this node's child array that immediately * precedes <code>aChild</code>, which must be a child of this node. If * <code>aChild</code> is the first child, returns null. This method * performs a linear search of this node's children for <code>aChild</code> * and is O(n) where n is the number of children. * * @exception IllegalArgumentException if <code>aChild</code> is null * or is not a child of this node * @return the child of this node that immediately precedes * <code>aChild</code> */ public TreeNode getChildBefore(TreeNode aChild) { if (aChild == null) { throw new IllegalArgumentException("argument is null"); } int index = getIndex(aChild); // linear search if (index == -1) { throw new IllegalArgumentException("argument is not a child"); } if (index > 0) { return getChildAt(index - 1); } else { return null; } } // // Sibling Queries // /** * Returns true if <code>anotherNode</code> is a sibling of (has the * same parent as) this node. A node is its own sibling. If * <code>anotherNode</code> is null, returns false. * * @param anotherNode node to test as sibling of this node * @return true if <code>anotherNode</code> is a sibling of this node */ public boolean isNodeSibling(TreeNode anotherNode) { boolean retval; if (anotherNode == null) { retval = false; } else if (anotherNode == this) { retval = true; } else { TreeNode myParent = getParent(); retval = (myParent != null && myParent == anotherNode.getParent()); if (retval && !((DefaultMutableTreeNode)getParent()) .isNodeChild(anotherNode)) { throw new Error("sibling has different parent"); } } return retval; } /** * Returns the number of siblings of this node. A node is its own sibling * (if it has no parent or no siblings, this method returns * <code>1</code>). *