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