Java > Open Source Codes > javax > swing > tree > DefaultMutableTreeNode


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

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags