1 /*
2 * Copyright 1997-2006 Sun Microsystems, Inc. All Rights Reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Sun designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Sun in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
22 * CA 95054 USA or visit www.sun.com if you need additional information or
23 * have any questions.
24 */
25
26 package javax.swing.tree;
27 // ISSUE: this class depends on nothing in AWT -- move to java.util?
28
29 import java.io;
30 import java.util;
31
32
33 /**
34 * A <code>DefaultMutableTreeNode</code> is a general-purpose node in a tree data
35 * structure.
36 * For examples of using default mutable tree nodes, see
37 * <a
38 href="http://java.sun.com/docs/books/tutorial/uiswing/components/tree.html">How to Use Trees</a>
39 * in <em>The Java Tutorial.</em>
40 *
41 * <p>
42 *
43 * A tree node may have at most one parent and 0 or more children.
44 * <code>DefaultMutableTreeNode</code> provides operations for examining and modifying a
45 * node's parent and children and also operations for examining the tree that
46 * the node is a part of. A node's tree is the set of all nodes that can be
47 * reached by starting at the node and following all the possible links to
48 * parents and children. A node with no parent is the root of its tree; a
49 * node with no children is a leaf. A tree may consist of many subtrees,
50 * each node acting as the root for its own subtree.
51 * <p>
52 * This class provides enumerations for efficiently traversing a tree or
53 * subtree in various orders or for following the path between two nodes.
54 * A <code>DefaultMutableTreeNode</code> may also hold a reference to a user object, the
55 * use of which is left to the user. Asking a <code>DefaultMutableTreeNode</code> for its
56 * string representation with <code>toString()</code> returns the string
57 * representation of its user object.
58 * <p>
59 * <b>This is not a thread safe class.</b>If you intend to use
60 * a DefaultMutableTreeNode (or a tree of TreeNodes) in more than one thread, you
61 * need to do your own synchronizing. A good convention to adopt is
62 * synchronizing on the root node of a tree.
63 * <p>
64 * While DefaultMutableTreeNode implements the MutableTreeNode interface and
65 * will allow you to add in any implementation of MutableTreeNode not all
66 * of the methods in DefaultMutableTreeNode will be applicable to all
67 * MutableTreeNodes implementations. Especially with some of the enumerations
68 * that are provided, using some of these methods assumes the
69 * DefaultMutableTreeNode contains only DefaultMutableNode instances. All
70 * of the TreeNode/MutableTreeNode methods will behave as defined no
71 * matter what implementations are added.
72 *
73 * <p>
74 * <strong>Warning:</strong>
75 * Serialized objects of this class will not be compatible with
76 * future Swing releases. The current serialization support is
77 * appropriate for short term storage or RMI between applications running
78 * the same version of Swing. As of 1.4, support for long term storage
79 * of all JavaBeans<sup><font size="-2">TM</font></sup>
80 * has been added to the <code>java.beans</code> package.
81 * Please see {@link java.beans.XMLEncoder}.
82 *
83 * @see MutableTreeNode
84 *
85 * @author Rob Davis
86 */
87 public class DefaultMutableTreeNode extends Object implements Cloneable,
88 MutableTreeNode, Serializable
89 {
90 private static final long serialVersionUID = -4298474751201349152L;
91
92 /**
93 * An enumeration that is always empty. This is used when an enumeration
94 * of a leaf node's children is requested.
95 */
96 static public final Enumeration<TreeNode> EMPTY_ENUMERATION
97 = Collections.emptyEnumeration();
98
99 /** this node's parent, or null if this node has no parent */
100 protected MutableTreeNode parent;
101
102 /** array of children, may be null if this node has no children */
103 protected Vector children;
104
105 /** optional user object */
106 transient protected Object userObject;
107
108 /** true if the node is able to have children */
109 protected boolean allowsChildren;
110
111
112 /**
113 * Creates a tree node that has no parent and no children, but which
114 * allows children.
115 */
116 public DefaultMutableTreeNode() {
117 this(null);
118 }
119
120 /**
121 * Creates a tree node with no parent, no children, but which allows
122 * children, and initializes it with the specified user object.
123 *
124 * @param userObject an Object provided by the user that constitutes
125 * the node's data
126 */
127 public DefaultMutableTreeNode(Object userObject) {
128 this(userObject, true);
129 }
130
131 /**
132 * Creates a tree node with no parent, no children, initialized with
133 * the specified user object, and that allows children only if
134 * specified.
135 *
136 * @param userObject an Object provided by the user that constitutes
137 * the node's data
138 * @param allowsChildren if true, the node is allowed to have child
139 * nodes -- otherwise, it is always a leaf node
140 */
141 public DefaultMutableTreeNode(Object userObject, boolean allowsChildren) {
142 super();
143 parent = null;
144 this.allowsChildren = allowsChildren;
145 this.userObject = userObject;
146 }
147
148
149 //
150 // Primitives
151 //
152
153 /**
154 * Removes <code>newChild</code> from its present parent (if it has a
155 * parent), sets the child's parent to this node, and then adds the child
156 * to this node's child array at index <code>childIndex</code>.
157 * <code>newChild</code> must not be null and must not be an ancestor of
158 * this node.
159 *
160 * @param newChild the MutableTreeNode to insert under this node
161 * @param childIndex the index in this node's child array
162 * where this node is to be inserted
163 * @exception ArrayIndexOutOfBoundsException if
164 * <code>childIndex</code> is out of bounds
165 * @exception IllegalArgumentException if
166 * <code>newChild</code> is null or is an
167 * ancestor of this node
168 * @exception IllegalStateException if this node does not allow
169 * children
170 * @see #isNodeDescendant
171 */
172 public void insert(MutableTreeNode newChild, int childIndex) {
173 if (!allowsChildren) {
174 throw new IllegalStateException("node does not allow children");
175 } else if (newChild == null) {
176 throw new IllegalArgumentException("new child is null");
177 } else if (isNodeAncestor(newChild)) {
178 throw new IllegalArgumentException("new child is an ancestor");
179 }
180
181 MutableTreeNode oldParent = (MutableTreeNode)newChild.getParent();
182
183 if (oldParent != null) {
184 oldParent.remove(newChild);
185 }
186 newChild.setParent(this);
187 if (children == null) {
188 children = new Vector();
189 }
190 children.insertElementAt(newChild, childIndex);
191 }
192
193 /**
194 * Removes the child at the specified index from this node's children
195 * and sets that node's parent to null. The child node to remove
196 * must be a <code>MutableTreeNode</code>.
197 *
198 * @param childIndex the index in this node's child array
199 * of the child to remove
200 * @exception ArrayIndexOutOfBoundsException if
201 * <code>childIndex</code> is out of bounds
202 */
203 public void remove(int childIndex) {
204 MutableTreeNode child = (MutableTreeNode)getChildAt(childIndex);
205 children.removeElementAt(childIndex);
206 child.setParent(null);
207 }
208
209 /**
210 * Sets this node's parent to <code>newParent</code> but does not
211 * change the parent's child array. This method is called from
212 * <code>insert()</code> and <code>remove()</code> to
213 * reassign a child's parent, it should not be messaged from anywhere
214 * else.
215 *
216 * @param newParent this node's new parent
217 */
218 public void setParent(MutableTreeNode newParent) {
219 parent = newParent;
220 }
221
222 /**
223 * Returns this node's parent or null if this node has no parent.
224 *
225 * @return this node's parent TreeNode, or null if this node has no parent
226 */
227 public TreeNode getParent() {
228 return parent;
229 }
230
231 /**
232 * Returns the child at the specified index in this node's child array.
233 *
234 * @param index an index into this node's child array
235 * @exception ArrayIndexOutOfBoundsException if <code>index</code>
236 * is out of bounds
237 * @return the TreeNode in this node's child array at the specified index
238 */
239 public TreeNode getChildAt(int index) {
240 if (children == null) {
241 throw new ArrayIndexOutOfBoundsException("node has no children");
242 }
243 return (TreeNode)children.elementAt(index);
244 }
245
246 /**
247 * Returns the number of children of this node.
248 *
249 * @return an int giving the number of children of this node
250 */
251 public int getChildCount() {
252 if (children == null) {
253 return 0;
254 } else {
255 return children.size();
256 }
257 }
258
259 /**
260 * Returns the index of the specified child in this node's child array.
261 * If the specified node is not a child of this node, returns
262 * <code>-1</code>. This method performs a linear search and is O(n)
263 * where n is the number of children.
264 *
265 * @param aChild the TreeNode to search for among this node's children
266 * @exception IllegalArgumentException if <code>aChild</code>
267 * is null
268 * @return an int giving the index of the node in this node's child
269 * array, or <code>-1</code> if the specified node is a not
270 * a child of this node
271 */
272 public int getIndex(TreeNode aChild) {
273 if (aChild == null) {
274 throw new IllegalArgumentException("argument is null");
275 }
276
277 if (!isNodeChild(aChild)) {
278 return -1;
279 }
280 return children.indexOf(aChild); // linear search
281 }
282
283 /**
284 * Creates and returns a forward-order enumeration of this node's
285 * children. Modifying this node's child array invalidates any child
286 * enumerations created before the modification.
287 *
288 * @return an Enumeration of this node's children
289 */
290 public Enumeration children() {
291 if (children == null) {
292 return EMPTY_ENUMERATION;
293 } else {
294 return children.elements();
295 }
296 }
297
298 /**
299 * Determines whether or not this node is allowed to have children.
300 * If <code>allows</code> is false, all of this node's children are
301 * removed.
302 * <p>
303 * Note: By default, a node allows children.
304 *
305 * @param allows true if this node is allowed to have children
306 */
307 public void setAllowsChildren(boolean allows) {
308 if (allows != allowsChildren) {
309 allowsChildren = allows;
310 if (!allowsChildren) {
311 removeAllChildren();
312 }
313 }
314 }
315
316 /**
317 * Returns true if this node is allowed to have children.
318 *
319 * @return true if this node allows children, else false
320 */
321 public boolean getAllowsChildren() {
322 return allowsChildren;
323 }
324
325 /**
326 * Sets the user object for this node to <code>userObject</code>.
327 *
328 * @param userObject the Object that constitutes this node's
329 * user-specified data
330 * @see #getUserObject
331 * @see #toString
332 */
333 public void setUserObject(Object userObject) {
334 this.userObject = userObject;
335 }
336
337 /**
338 * Returns this node's user object.
339 *
340 * @return the Object stored at this node by the user
341 * @see #setUserObject
342 * @see #toString
343 */
344 public Object getUserObject() {
345 return userObject;
346 }
347
348
349 //
350 // Derived methods
351 //
352
353 /**
354 * Removes the subtree rooted at this node from the tree, giving this
355 * node a null parent. Does nothing if this node is the root of its
356 * tree.
357 */
358 public void removeFromParent() {
359 MutableTreeNode parent = (MutableTreeNode)getParent();
360 if (parent != null) {
361 parent.remove(this);
362 }
363 }
364
365 /**
366 * Removes <code>aChild</code> from this node's child array, giving it a
367 * null parent.
368 *
369 * @param aChild a child of this node to remove
370 * @exception IllegalArgumentException if <code>aChild</code>
371 * is null or is not a child of this node
372 */
373 public void remove(MutableTreeNode aChild) {
374 if (aChild == null) {
375 throw new IllegalArgumentException("argument is null");
376 }
377
378 if (!isNodeChild(aChild)) {
379 throw new IllegalArgumentException("argument is not a child");
380 }
381 remove(getIndex(aChild)); // linear search
382 }
383
384 /**
385 * Removes all of this node's children, setting their parents to null.
386 * If this node has no children, this method does nothing.
387 */
388 public void removeAllChildren() {
389 for (int i = getChildCount()-1; i >= 0; i--) {
390 remove(i);
391 }
392 }
393
394 /**
395 * Removes <code>newChild</code> from its parent and makes it a child of
396 * this node by adding it to the end of this node's child array.
397 *
398 * @see #insert
399 * @param newChild node to add as a child of this node
400 * @exception IllegalArgumentException if <code>newChild</code>
401 * is null
402 * @exception IllegalStateException if this node does not allow
403 * children
404 */
405 public void add(MutableTreeNode newChild) {
406 if(newChild != null && newChild.getParent() == this)
407 insert(newChild, getChildCount() - 1);
408 else
409 insert(newChild, getChildCount());
410 }
411
412
413
414 //
415 // Tree Queries
416 //
417
418 /**
419 * Returns true if <code>anotherNode</code> is an ancestor of this node
420 * -- if it is this node, this node's parent, or an ancestor of this
421 * node's parent. (Note that a node is considered an ancestor of itself.)
422 * If <code>anotherNode</code> is null, this method returns false. This
423 * operation is at worst O(h) where h is the distance from the root to
424 * this node.
425 *
426 * @see #isNodeDescendant
427 * @see #getSharedAncestor
428 * @param anotherNode node to test as an ancestor of this node
429 * @return true if this node is a descendant of <code>anotherNode</code>
430 */
431 public boolean isNodeAncestor(TreeNode anotherNode) {
432 if (anotherNode == null) {
433 return false;
434 }
435
436 TreeNode ancestor = this;
437
438 do {
439 if (ancestor == anotherNode) {
440 return true;
441 }
442 } while((ancestor = ancestor.getParent()) != null);
443
444 return false;
445 }
446
447 /**
448 * Returns true if <code>anotherNode</code> is a descendant of this node
449 * -- if it is this node, one of this node's children, or a descendant of
450 * one of this node's children. Note that a node is considered a
451 * descendant of itself. If <code>anotherNode</code> is null, returns
452 * false. This operation is at worst O(h) where h is the distance from the
453 * root to <code>anotherNode</code>.
454 *
455 * @see #isNodeAncestor
456 * @see #getSharedAncestor
457 * @param anotherNode node to test as descendant of this node
458 * @return true if this node is an ancestor of <code>anotherNode</code>
459 */
460 public boolean isNodeDescendant(DefaultMutableTreeNode anotherNode) {
461 if (anotherNode == null)
462 return false;
463
464 return anotherNode.isNodeAncestor(this);
465 }
466
467 /**
468 * Returns the nearest common ancestor to this node and <code>aNode</code>.
469 * Returns null, if no such ancestor exists -- if this node and
470 * <code>aNode</code> are in different trees or if <code>aNode</code> is
471 * null. A node is considered an ancestor of itself.
472 *
473 * @see #isNodeAncestor
474 * @see #isNodeDescendant
475 * @param aNode node to find common ancestor with
476 * @return nearest ancestor common to this node and <code>aNode</code>,
477 * or null if none
478 */
479 public TreeNode getSharedAncestor(DefaultMutableTreeNode aNode) {
480 if (aNode == this) {
481 return this;
482 } else if (aNode == null) {
483 return null;
484 }
485
486 int level1, level2, diff;
487 TreeNode node1, node2;
488
489 level1 = getLevel();
490 level2 = aNode.getLevel();
491
492 if (level2 > level1) {
493 diff = level2 - level1;
494 node1 = aNode;
495 node2 = this;
496 } else {
497 diff = level1 - level2;
498 node1 = this;
499 node2 = aNode;
500 }
501
502 // Go up the tree until the nodes are at the same level
503 while (diff > 0) {
504 node1 = node1.getParent();
505 diff--;
506 }
507
508 // Move up the tree until we find a common ancestor. Since we know
509 // that both nodes are at the same level, we won't cross paths
510 // unknowingly (if there is a common ancestor, both nodes hit it in
511 // the same iteration).
512
513 do {
514 if (node1 == node2) {
515 return node1;
516 }
517 node1 = node1.getParent();
518 node2 = node2.getParent();
519 } while (node1 != null);// only need to check one -- they're at the
520 // same level so if one is null, the other is
521
522 if (node1 != null || node2 != null) {
523 throw new Error ("nodes should be null");
524 }
525
526 return null;
527 }
528
529
530 /**
531 * Returns true if and only if <code>aNode</code> is in the same tree
532 * as this node. Returns false if <code>aNode</code> is null.
533 *
534 * @see #getSharedAncestor
535 * @see #getRoot
536 * @return true if <code>aNode</code> is in the same tree as this node;
537 * false if <code>aNode</code> is null
538 */
539 public boolean isNodeRelated(DefaultMutableTreeNode aNode) {
540 return (aNode != null) && (getRoot() == aNode.getRoot());
541 }
542
543
544 /**
545 * Returns the depth of the tree rooted at this node -- the longest
546 * distance from this node to a leaf. If this node has no children,
547 * returns 0. This operation is much more expensive than
548 * <code>getLevel()</code> because it must effectively traverse the entire
549 * tree rooted at this node.
550 *
551 * @see #getLevel
552 * @return the depth of the tree whose root is this node
553 */
554 public int getDepth() {
555 Object last = null;
556 Enumeration enum_ = breadthFirstEnumeration();
557
558 while (enum_.hasMoreElements()) {
559 last = enum_.nextElement();
560 }
561
562 if (last == null) {
563 throw new Error ("nodes should be null");
564 }
565
566 return ((DefaultMutableTreeNode)last).getLevel() - getLevel();
567 }
568
569
570
571 /**
572 * Returns the number of levels above this node -- the distance from
573 * the root to this node. If this node is the root, returns 0.
574 *
575 * @see #getDepth
576 * @return the number of levels above this node
577 */
578 public int getLevel() {
579 TreeNode ancestor;
580 int levels = 0;
581
582 ancestor = this;
583 while((ancestor = ancestor.getParent()) != null){
584 levels++;
585 }
586
587 return levels;
588 }
589
590
591 /**
592 * Returns the path from the root, to get to this node. The last
593 * element in the path is this node.
594 *
595 * @return an array of TreeNode objects giving the path, where the
596 * first element in the path is the root and the last
597 * element is this node.
598 */
599 public TreeNode[] getPath() {
600 return getPathToRoot(this, 0);
601 }
602
603 /**
604 * Builds the parents of node up to and including the root node,
605 * where the original node is the last element in the returned array.
606 * The length of the returned array gives the node's depth in the
607 * tree.
608 *
609 * @param aNode the TreeNode to get the path for
610 * @param depth an int giving the number of steps already taken towards
611 * the root (on recursive calls), used to size the returned array
612 * @return an array of TreeNodes giving the path from the root to the
613 * specified node
614 */
615 protected TreeNode[] getPathToRoot(TreeNode aNode, int depth) {
616 TreeNode[] retNodes;
617
618 /* Check for null, in case someone passed in a null node, or
619 they passed in an element that isn't rooted at root. */
620 if(aNode == null) {
621 if(depth == 0)
622 return null;
623 else
624 retNodes = new TreeNode[depth];
625 }
626 else {
627 depth++;
628 retNodes = getPathToRoot(aNode.getParent(), depth);
629 retNodes[retNodes.length - depth] = aNode;
630 }
631 return retNodes;
632 }
633
634 /**
635 * Returns the user object path, from the root, to get to this node.
636 * If some of the TreeNodes in the path have null user objects, the
637 * returned path will contain nulls.
638 */
639 public Object[] getUserObjectPath() {
640 TreeNode[] realPath = getPath();
641 Object[] retPath = new Object[realPath.length];
642
643 for(int counter = 0; counter < realPath.length; counter++)
644 retPath[counter] = ((DefaultMutableTreeNode)realPath[counter])
645 .getUserObject();
646 return retPath;
647 }
648
649 /**
650 * Returns the root of the tree that contains this node. The root is
651 * the ancestor with a null parent.
652 *
653 * @see #isNodeAncestor
654 * @return the root of the tree that contains this node
655 */
656 public TreeNode getRoot() {
657 TreeNode ancestor = this;
658 TreeNode previous;
659
660 do {
661 previous = ancestor;
662 ancestor = ancestor.getParent();
663 } while (ancestor != null);
664
665 return previous;
666 }
667
668
669 /**
670 * Returns true if this node is the root of the tree. The root is
671 * the only node in the tree with a null parent; every tree has exactly
672 * one root.
673 *
674 * @return true if this node is the root of its tree
675 */
676 public boolean isRoot() {
677 return getParent() == null;
678 }
679
680
681 /**
682 * Returns the node that follows this node in a preorder traversal of this
683 * node's tree. Returns null if this node is the last node of the
684 * traversal. This is an inefficient way to traverse the entire tree; use
685 * an enumeration, instead.
686 *
687 * @see #preorderEnumeration
688 * @return the node that follows this node in a preorder traversal, or
689 * null if this node is last
690 */
691 public DefaultMutableTreeNode getNextNode() {
692 if (getChildCount() == 0) {
693 // No children, so look for nextSibling
694 DefaultMutableTreeNode nextSibling = getNextSibling();
695
696 if (nextSibling == null) {
697 DefaultMutableTreeNode aNode = (DefaultMutableTreeNode)getParent();
698
699 do {
700 if (aNode == null) {
701 return null;
702 }
703
704 nextSibling = aNode.getNextSibling();
705 if (nextSibling != null) {
706 return nextSibling;
707 }
708
709 aNode = (DefaultMutableTreeNode)aNode.getParent();
710 } while(true);
711 } else {
712 return nextSibling;
713 }
714 } else {
715 return (DefaultMutableTreeNode)getChildAt(0);
716 }
717 }
718
719
720 /**
721 * Returns the node that precedes this node in a preorder traversal of
722 * this node's tree. Returns <code>null</code> if this node is the
723 * first node of the traversal -- the root of the tree.
724 * This is an inefficient way to
725 * traverse the entire tree; use an enumeration, instead.
726 *
727 * @see #preorderEnumeration
728 * @return the node that precedes this node in a preorder traversal, or
729 * null if this node is the first
730 */
731 public DefaultMutableTreeNode getPreviousNode() {
732 DefaultMutableTreeNode previousSibling;
733 DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent();
734
735 if (myParent == null) {
736 return null;
737 }
738
739 previousSibling = getPreviousSibling();
740
741 if (previousSibling != null) {
742 if (previousSibling.getChildCount() == 0)
743 return previousSibling;
744 else
745 return previousSibling.getLastLeaf();
746 } else {
747 return myParent;
748 }
749 }
750
751 /**
752 * Creates and returns an enumeration that traverses the subtree rooted at
753 * this node in preorder. The first node returned by the enumeration's
754 * <code>nextElement()</code> method is this node.<P>
755 *
756 * Modifying the tree by inserting, removing, or moving a node invalidates
757 * any enumerations created before the modification.
758 *
759 * @see #postorderEnumeration
760 * @return an enumeration for traversing the tree in preorder
761 */
762 public Enumeration preorderEnumeration() {
763 return new PreorderEnumeration(this);
764 }
765
766 /**
767 * Creates and returns an enumeration that traverses the subtree rooted at
768 * this node in postorder. The first node returned by the enumeration's
769 * <code>nextElement()</code> method is the leftmost leaf. This is the
770 * same as a depth-first traversal.<P>
771 *
772 * Modifying the tree by inserting, removing, or moving a node invalidates
773 * any enumerations created before the modification.
774 *
775 * @see #depthFirstEnumeration
776 * @see #preorderEnumeration
777 * @return an enumeration for traversing the tree in postorder
778 */
779 public Enumeration postorderEnumeration() {
780 return new PostorderEnumeration(this);
781 }
782
783 /**
784 * Creates and returns an enumeration that traverses the subtree rooted at
785 * this node in breadth-first order. The first node returned by the
786 * enumeration's <code>nextElement()</code> method is this node.<P>
787 *
788 * Modifying the tree by inserting, removing, or moving a node invalidates
789 * any enumerations created before the modification.
790 *
791 * @see #depthFirstEnumeration
792 * @return an enumeration for traversing the tree in breadth-first order
793 */
794 public Enumeration breadthFirstEnumeration() {
795 return new BreadthFirstEnumeration(this);
796 }
797
798 /**
799 * Creates and returns an enumeration that traverses the subtree rooted at
800 * this node in depth-first order. The first node returned by the
801 * enumeration's <code>nextElement()</code> method is the leftmost leaf.
802 * This is the same as a postorder traversal.<P>
803 *
804 * Modifying the tree by inserting, removing, or moving a node invalidates
805 * any enumerations created before the modification.
806 *
807 * @see #breadthFirstEnumeration
808 * @see #postorderEnumeration
809 * @return an enumeration for traversing the tree in depth-first order
810 */
811 public Enumeration depthFirstEnumeration() {
812 return postorderEnumeration();
813 }
814
815 /**
816 * Creates and returns an enumeration that follows the path from
817 * <code>ancestor</code> to this node. The enumeration's
818 * <code>nextElement()</code> method first returns <code>ancestor</code>,
819 * then the child of <code>ancestor</code> that is an ancestor of this
820 * node, and so on, and finally returns this node. Creation of the
821 * enumeration is O(m) where m is the number of nodes between this node
822 * and <code>ancestor</code>, inclusive. Each <code>nextElement()</code>
823 * message is O(1).<P>
824 *
825 * Modifying the tree by inserting, removing, or moving a node invalidates
826 * any enumerations created before the modification.
827 *
828 * @see #isNodeAncestor
829 * @see #isNodeDescendant
830 * @exception IllegalArgumentException if <code>ancestor</code> is
831 * not an ancestor of this node
832 * @return an enumeration for following the path from an ancestor of
833 * this node to this one
834 */
835 public Enumeration pathFromAncestorEnumeration(TreeNode ancestor) {
836 return new PathBetweenNodesEnumeration(ancestor, this);
837 }
838
839
840 //
841 // Child Queries
842 //
843
844 /**
845 * Returns true if <code>aNode</code> is a child of this node. If
846 * <code>aNode</code> is null, this method returns false.
847 *
848 * @return true if <code>aNode</code> is a child of this node; false if
849 * <code>aNode</code> is null
850 */
851 public boolean isNodeChild(TreeNode aNode) {
852 boolean retval;
853
854 if (aNode == null) {
855 retval = false;
856 } else {
857 if (getChildCount() == 0) {
858 retval = false;
859 } else {
860 retval = (aNode.getParent() == this);
861 }
862 }
863
864 return retval;
865 }
866
867
868 /**
869 * Returns this node's first child. If this node has no children,
870 * throws NoSuchElementException.
871 *
872 * @return the first child of this node
873 * @exception NoSuchElementException if this node has no children
874 */
875 public TreeNode getFirstChild() {
876 if (getChildCount() == 0) {
877 throw new NoSuchElementException("node has no children");
878 }
879 return getChildAt(0);
880 }
881
882
883 /**
884 * Returns this node's last child. If this node has no children,
885 * throws NoSuchElementException.
886 *
887 * @return the last child of this node
888 * @exception NoSuchElementException if this node has no children
889 */
890 public TreeNode getLastChild() {
891 if (getChildCount() == 0) {
892 throw new NoSuchElementException("node has no children");
893 }
894 return getChildAt(getChildCount()-1);
895 }
896
897
898 /**
899 * Returns the child in this node's child array that immediately
900 * follows <code>aChild</code>, which must be a child of this node. If
901 * <code>aChild</code> is the last child, returns null. This method
902 * performs a linear search of this node's children for
903 * <code>aChild</code> and is O(n) where n is the number of children; to
904 * traverse the entire array of children, use an enumeration instead.
905 *
906 * @see #children
907 * @exception IllegalArgumentException if <code>aChild</code> is
908 * null or is not a child of this node
909 * @return the child of this node that immediately follows
910 * <code>aChild</code>
911 */
912 public TreeNode getChildAfter(TreeNode aChild) {
913 if (aChild == null) {
914 throw new IllegalArgumentException("argument is null");
915 }
916
917 int index = getIndex(aChild); // linear search
918
919 if (index == -1) {
920 throw new IllegalArgumentException("node is not a child");
921 }
922
923 if (index < getChildCount() - 1) {
924 return getChildAt(index + 1);
925 } else {
926 return null;
927 }
928 }
929
930
931 /**
932 * Returns the child in this node's child array that immediately
933 * precedes <code>aChild</code>, which must be a child of this node. If
934 * <code>aChild</code> is the first child, returns null. This method
935 * performs a linear search of this node's children for <code>aChild</code>
936 * and is O(n) where n is the number of children.
937 *
938 * @exception IllegalArgumentException if <code>aChild</code> is null
939 * or is not a child of this node
940 * @return the child of this node that immediately precedes
941 * <code>aChild</code>
942 */
943 public TreeNode getChildBefore(TreeNode aChild) {
944 if (aChild == null) {
945 throw new IllegalArgumentException("argument is null");
946 }
947
948 int index = getIndex(aChild); // linear search
949
950 if (index == -1) {
951 throw new IllegalArgumentException("argument is not a child");
952 }
953
954 if (index > 0) {
955 return getChildAt(index - 1);
956 } else {
957 return null;
958 }
959 }
960
961
962 //
963 // Sibling Queries
964 //
965
966
967 /**
968 * Returns true if <code>anotherNode</code> is a sibling of (has the
969 * same parent as) this node. A node is its own sibling. If
970 * <code>anotherNode</code> is null, returns false.
971 *
972 * @param anotherNode node to test as sibling of this node
973 * @return true if <code>anotherNode</code> is a sibling of this node
974 */
975 public boolean isNodeSibling(TreeNode anotherNode) {
976 boolean retval;
977
978 if (anotherNode == null) {
979 retval = false;
980 } else if (anotherNode == this) {
981 retval = true;
982 } else {
983 TreeNode myParent = getParent();
984 retval = (myParent != null && myParent == anotherNode.getParent());
985
986 if (retval && !((DefaultMutableTreeNode)getParent())
987 .isNodeChild(anotherNode)) {
988 throw new Error("sibling has different parent");
989 }
990 }
991
992 return retval;
993 }
994
995
996 /**
997 * Returns the number of siblings of this node. A node is its own sibling
998 * (if it has no parent or no siblings, this method returns
999 * <code>1</code>).
1000 *
1001 * @return the number of siblings of this node
1002 */
1003 public int getSiblingCount() {
1004 TreeNode myParent = getParent();
1005
1006 if (myParent == null) {
1007 return 1;
1008 } else {
1009 return myParent.getChildCount();
1010 }
1011 }
1012
1013
1014 /**
1015 * Returns the next sibling of this node in the parent's children array.
1016 * Returns null if this node has no parent or is the parent's last child.
1017 * This method performs a linear search that is O(n) where n is the number
1018 * of children; to traverse the entire array, use the parent's child
1019 * enumeration instead.
1020 *
1021 * @see #children
1022 * @return the sibling of this node that immediately follows this node
1023 */
1024 public DefaultMutableTreeNode getNextSibling() {
1025 DefaultMutableTreeNode retval;
1026
1027 DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent();
1028
1029 if (myParent == null) {
1030 retval = null;
1031 } else {
1032 retval = (DefaultMutableTreeNode)myParent.getChildAfter(this); // linear search
1033 }
1034
1035 if (retval != null && !isNodeSibling(retval)) {
1036 throw new Error("child of parent is not a sibling");
1037 }
1038
1039 return retval;
1040 }
1041
1042
1043 /**
1044 * Returns the previous sibling of this node in the parent's children
1045 * array. Returns null if this node has no parent or is the parent's
1046 * first child. This method performs a linear search that is O(n) where n
1047 * is the number of children.
1048 *
1049 * @return the sibling of this node that immediately precedes this node
1050 */
1051 public DefaultMutableTreeNode getPreviousSibling() {
1052 DefaultMutableTreeNode retval;
1053
1054 DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent();
1055
1056 if (myParent == null) {
1057 retval = null;
1058 } else {
1059 retval = (DefaultMutableTreeNode)myParent.getChildBefore(this); // linear search
1060 }
1061
1062 if (retval != null && !isNodeSibling(retval)) {
1063 throw new Error("child of parent is not a sibling");
1064 }
1065
1066 return retval;
1067 }
1068
1069
1070
1071 //
1072 // Leaf Queries
1073 //
1074
1075 /**
1076 * Returns true if this node has no children. To distinguish between
1077 * nodes that have no children and nodes that <i>cannot</i> have
1078 * children (e.g. to distinguish files from empty directories), use this
1079 * method in conjunction with <code>getAllowsChildren</code>
1080 *
1081 * @see #getAllowsChildren
1082 * @return true if this node has no children
1083 */
1084 public boolean isLeaf() {
1085 return (getChildCount() == 0);
1086 }
1087
1088
1089 /**
1090 * Finds and returns the first leaf that is a descendant of this node --
1091 * either this node or its first child's first leaf.
1092 * Returns this node if it is a leaf.
1093 *
1094 * @see #isLeaf
1095 * @see #isNodeDescendant
1096 * @return the first leaf in the subtree rooted at this node
1097 */
1098 public DefaultMutableTreeNode getFirstLeaf() {
1099 DefaultMutableTreeNode node = this;
1100
1101 while (!node.isLeaf()) {
1102 node = (DefaultMutableTreeNode)node.getFirstChild();
1103 }
1104
1105 return node;
1106 }
1107
1108
1109 /**
1110 * Finds and returns the last leaf that is a descendant of this node --
1111 * either this node or its last child's last leaf.
1112 * Returns this node if it is a leaf.
1113 *
1114 * @see #isLeaf
1115 * @see #isNodeDescendant
1116 * @return the last leaf in the subtree rooted at this node
1117 */
1118 public DefaultMutableTreeNode getLastLeaf() {
1119 DefaultMutableTreeNode node = this;
1120
1121 while (!node.isLeaf()) {
1122 node = (DefaultMutableTreeNode)node.getLastChild();
1123 }
1124
1125 return node;
1126 }
1127
1128
1129 /**
1130 * Returns the leaf after this node or null if this node is the
1131 * last leaf in the tree.
1132 * <p>
1133 * In this implementation of the <code>MutableNode</code> interface,
1134 * this operation is very inefficient. In order to determine the
1135 * next node, this method first performs a linear search in the
1136 * parent's child-list in order to find the current node.
1137 * <p>
1138 * That implementation makes the operation suitable for short
1139 * traversals from a known position. But to traverse all of the
1140 * leaves in the tree, you should use <code>depthFirstEnumeration</code>
1141 * to enumerate the nodes in the tree and use <code>isLeaf</code>
1142 * on each node to determine which are leaves.
1143 *
1144 * @see #depthFirstEnumeration
1145 * @see #isLeaf
1146 * @return returns the next leaf past this node
1147 */
1148 public DefaultMutableTreeNode getNextLeaf() {
1149 DefaultMutableTreeNode nextSibling;
1150 DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent();
1151
1152 if (myParent == null)
1153 return null;
1154
1155 nextSibling = getNextSibling(); // linear search
1156
1157 if (nextSibling != null)
1158 return nextSibling.getFirstLeaf();
1159
1160 return myParent.getNextLeaf(); // tail recursion
1161 }
1162
1163
1164 /**
1165 * Returns the leaf before this node or null if this node is the
1166 * first leaf in the tree.
1167 * <p>
1168 * In this implementation of the <code>MutableNode</code> interface,
1169 * this operation is very inefficient. In order to determine the
1170 * previous node, this method first performs a linear search in the
1171 * parent's child-list in order to find the current node.
1172 * <p>
1173 * That implementation makes the operation suitable for short
1174 * traversals from a known position. But to traverse all of the
1175 * leaves in the tree, you should use <code>depthFirstEnumeration</code>
1176 * to enumerate the nodes in the tree and use <code>isLeaf</code>
1177 * on each node to determine which are leaves.
1178 *
1179 * @see #depthFirstEnumeration
1180 * @see #isLeaf
1181 * @return returns the leaf before this node
1182 */
1183 public DefaultMutableTreeNode getPreviousLeaf() {
1184 DefaultMutableTreeNode previousSibling;
1185 DefaultMutableTreeNode myParent = (DefaultMutableTreeNode)getParent();
1186
1187 if (myParent == null)
1188 return null;
1189
1190 previousSibling = getPreviousSibling(); // linear search
1191
1192 if (previousSibling != null)
1193 return previousSibling.getLastLeaf();
1194
1195 return myParent.getPreviousLeaf(); // tail recursion
1196 }
1197
1198
1199 /**
1200 * Returns the total number of leaves that are descendants of this node.
1201 * If this node is a leaf, returns <code>1</code>. This method is O(n)
1202 * where n is the number of descendants of this node.
1203 *
1204 * @see #isNodeAncestor
1205 * @return the number of leaves beneath this node
1206 */
1207 public int getLeafCount() {
1208 int count = 0;
1209
1210 TreeNode node;
1211 Enumeration enum_ = breadthFirstEnumeration(); // order matters not
1212
1213 while (enum_.hasMoreElements()) {
1214 node = (TreeNode)enum_.nextElement();
1215 if (node.isLeaf()) {
1216 count++;
1217 }
1218 }
1219
1220 if (count < 1) {
1221 throw new Error("tree has zero leaves");
1222 }
1223
1224 return count;
1225 }
1226
1227
1228 //
1229 // Overrides
1230 //
1231
1232 /**
1233 * Returns the result of sending <code>toString()</code> to this node's
1234 * user object, or the empty string if the node has no user object.
1235 *
1236 * @see #getUserObject
1237 */
1238 public String toString() {
1239 if (userObject == null) {
1240 return "";
1241 } else {
1242 return userObject.toString();
1243 }
1244 }
1245
1246 /**
1247 * Overridden to make clone public. Returns a shallow copy of this node;
1248 * the new node has no parent or children and has a reference to the same
1249 * user object, if any.
1250 *
1251 * @return a copy of this node
1252 */
1253 public Object clone() {
1254 DefaultMutableTreeNode newNode = null;
1255
1256 try {
1257 newNode = (DefaultMutableTreeNode)super.clone();
1258
1259 // shallow copy -- the new node has no parent or children
1260 newNode.children = null;
1261 newNode.parent = null;
1262
1263 } catch (CloneNotSupportedException e) {
1264 // Won't happen because we implement Cloneable
1265 throw new Error(e.toString());
1266 }
1267
1268 return newNode;
1269 }
1270
1271
1272 // Serialization support.
1273 private void writeObject(ObjectOutputStream s) throws IOException {
1274 Object[] tValues;
1275
1276 s.defaultWriteObject();
1277 // Save the userObject, if its Serializable.
1278 if(userObject != null && userObject instanceof Serializable) {
1279 tValues = new Object[2];
1280 tValues[0] = "userObject";
1281 tValues[1] = userObject;
1282 }
1283 else
1284 tValues = new Object[0];
1285 s.writeObject(tValues);
1286 }
1287
1288 private void readObject(ObjectInputStream s)
1289 throws IOException, ClassNotFoundException {
1290 Object[] tValues;
1291
1292 s.defaultReadObject();
1293
1294 tValues = (Object[])s.readObject();
1295
1296 if(tValues.length > 0 && tValues[0].equals("userObject"))
1297 userObject = tValues[1];
1298 }
1299
1300 final class PreorderEnumeration implements Enumeration<TreeNode> {
1301 protected Stack stack;
1302
1303 public PreorderEnumeration(TreeNode rootNode) {
1304 super();
1305 Vector v = new Vector(1);
1306 v.addElement(rootNode); // PENDING: don't really need a vector
1307 stack = new Stack();
1308 stack.push(v.elements());
1309 }
1310
1311 public boolean hasMoreElements() {
1312 return (!stack.empty() &&
1313 ((Enumeration)stack.peek()).hasMoreElements());
1314 }
1315
1316 public TreeNode nextElement() {
1317 Enumeration enumer = (Enumeration)stack.peek();
1318 TreeNode node = (TreeNode)enumer.nextElement();
1319 Enumeration children = node.children();
1320
1321 if (!enumer.hasMoreElements()) {
1322 stack.pop();
1323 }
1324 if (children.hasMoreElements()) {
1325 stack.push(children);
1326 }
1327 return node;
1328 }
1329
1330 } // End of class PreorderEnumeration
1331
1332
1333
1334 final class PostorderEnumeration implements Enumeration<TreeNode> {
1335 protected TreeNode root;
1336 protected Enumeration<TreeNode> children;
1337 protected Enumeration<TreeNode> subtree;
1338
1339 public PostorderEnumeration(TreeNode rootNode) {
1340 super();
1341 root = rootNode;
1342 children = root.children();
1343 subtree = EMPTY_ENUMERATION;
1344 }
1345
1346 public boolean hasMoreElements() {
1347 return root != null;
1348 }
1349
1350 public TreeNode nextElement() {
1351 TreeNode retval;
1352
1353 if (subtree.hasMoreElements()) {
1354 retval = subtree.nextElement();
1355 } else if (children.hasMoreElements()) {
1356 subtree = new PostorderEnumeration(
1357 (TreeNode)children.nextElement());
1358 retval = subtree.nextElement();
1359 } else {
1360 retval = root;
1361 root = null;
1362 }
1363
1364 return retval;
1365 }
1366
1367 } // End of class PostorderEnumeration
1368
1369
1370
1371 final class BreadthFirstEnumeration implements Enumeration<TreeNode> {
1372 protected Queue queue;
1373
1374 public BreadthFirstEnumeration(TreeNode rootNode) {
1375 super();
1376 Vector v = new Vector(1);
1377 v.addElement(rootNode); // PENDING: don't really need a vector
1378 queue = new Queue();
1379 queue.enqueue(v.elements());
1380 }
1381
1382 public boolean hasMoreElements() {
1383 return (!queue.isEmpty() &&
1384 ((Enumeration)queue.firstObject()).hasMoreElements());
1385 }
1386
1387 public TreeNode nextElement() {
1388 Enumeration enumer = (Enumeration)queue.firstObject();
1389 TreeNode node = (TreeNode)enumer.nextElement();
1390 Enumeration children = node.children();
1391
1392 if (!enumer.hasMoreElements()) {
1393 queue.dequeue();
1394 }
1395 if (children.hasMoreElements()) {
1396 queue.enqueue(children);
1397 }
1398 return node;
1399 }
1400
1401
1402 // A simple queue with a linked list data structure.
1403 final class Queue {
1404 QNode head; // null if empty
1405 QNode tail;
1406
1407 final class QNode {
1408 public Object object;
1409 public QNode next; // null if end
1410 public QNode(Object object, QNode next) {
1411 this.object = object;
1412 this.next = next;
1413 }
1414 }
1415
1416 public void enqueue(Object anObject) {
1417 if (head == null) {
1418 head = tail = new QNode(anObject, null);
1419 } else {
1420 tail.next = new QNode(anObject, null);
1421 tail = tail.next;
1422 }
1423 }
1424
1425 public Object dequeue() {
1426 if (head == null) {
1427 throw new NoSuchElementException("No more elements");
1428 }
1429
1430 Object retval = head.object;
1431 QNode oldHead = head;
1432 head = head.next;
1433 if (head == null) {
1434 tail = null;
1435 } else {
1436 oldHead.next = null;
1437 }
1438 return retval;
1439 }
1440
1441 public Object firstObject() {
1442 if (head == null) {
1443 throw new NoSuchElementException("No more elements");
1444 }
1445
1446 return head.object;
1447 }
1448
1449 public boolean isEmpty() {
1450 return head == null;
1451 }
1452
1453 } // End of class Queue
1454
1455 } // End of class BreadthFirstEnumeration
1456
1457
1458
1459 final class PathBetweenNodesEnumeration implements Enumeration<TreeNode> {
1460 protected Stack<TreeNode> stack;
1461
1462 public PathBetweenNodesEnumeration(TreeNode ancestor,
1463 TreeNode descendant)
1464 {
1465 super();
1466
1467 if (ancestor == null || descendant == null) {
1468 throw new IllegalArgumentException("argument is null");
1469 }
1470
1471 TreeNode current;
1472
1473 stack = new Stack<TreeNode>();
1474 stack.push(descendant);
1475
1476 current = descendant;
1477 while (current != ancestor) {
1478 current = current.getParent();
1479 if (current == null && descendant != ancestor) {
1480 throw new IllegalArgumentException("node " + ancestor +
1481 " is not an ancestor of " + descendant);
1482 }
1483 stack.push(current);
1484 }
1485 }
1486
1487 public boolean hasMoreElements() {
1488 return stack.size() > 0;
1489 }
1490
1491 public TreeNode nextElement() {
1492 try {
1493 return stack.pop();
1494 } catch (EmptyStackException e) {
1495 throw new NoSuchElementException("No more elements");
1496 }
1497 }
1498
1499 } // End of class PathBetweenNodesEnumeration
1500
1501
1502
1503 } // End of class DefaultMutableTreeNode
Save This Page