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