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 public static final Enumeration<TreeNode> EMPTY_ENUMERATION
99 = Collections.emptyEnumeration();
100
101 /** this node's parent, or null if this node has no parent */
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 {
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
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,
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.
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;
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() {
|
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} 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} 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} may also hold a reference to a user object, the
56 * use of which is left to the user. Asking a {@code DefaultMutableTreeNode} for its
57 * string representation with {@code toString()} 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} 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 public static final Enumeration<TreeNode> EMPTY_ENUMERATION
99 = Collections.emptyEnumeration();
100
101 /** this node's parent, or null if this node has no parent */
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} 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}.
159 * {@code newChild} 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} is out of bounds
167 * @exception IllegalArgumentException if
168 * {@code newChild} 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}.
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} 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} but does not
213 * change the parent's child array. This method is called from
214 * {@code insert()} and {@code remove()} 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}
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}. 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}
270 * is null
271 * @return an int giving the index of the node in this node's child
272 * array, or {@code -1} 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} 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}.
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} 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}
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} 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}
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} 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} 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}
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} 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} is null, returns
455 * false. This operation is at worst O(h) where h is the distance from the
456 * root to {@code anotherNode}.
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}
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}.
472 * Returns null, if no such ancestor exists -- if this node and
473 * {@code aNode} are in different trees or if {@code aNode} 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},
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 {
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} is in the same tree
535 * as this node. Returns false if {@code aNode} is null.
536 *
537 * @param aNode node to find common ancestor with
538 * @see #getSharedAncestor
539 * @see #getRoot
540 * @return true if {@code aNode} is in the same tree as this node;
541 * false if {@code aNode} 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()} 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
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} 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()} 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()} 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()} 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()} 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} to this node. The enumeration's
824 * {@code nextElement()} method first returns {@code ancestor},
825 * then the child of {@code ancestor} 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}, inclusive. Each {@code nextElement()}
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} 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} is a child of this node. If
853 * {@code aNode} 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} is a child of this node; false if
857 * {@code aNode} 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,
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}, which must be a child of this node. If
909 * {@code aChild} is the last child, returns null. This method
910 * performs a linear search of this node's children for
911 * {@code aChild} 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} is
917 * null or is not a child of this node
918 * @return the child of this node that immediately follows
919 * {@code aChild}
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}, which must be a child of this node. If
943 * {@code aChild} is the first child, returns null. This method
944 * performs a linear search of this node's children for {@code aChild}
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} is null
949 * or is not a child of this node
950 * @return the child of this node that immediately precedes
951 * {@code aChild}
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} is a sibling of (has the
979 * same parent as) this node. A node is its own sibling. If
980 * {@code anotherNode} is null, returns false.
981 *
982 * @param anotherNode node to test as sibling of this node
983 * @return true if {@code anotherNode} 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}).
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.
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}
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;
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} 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}
1151 * to enumerate the nodes in the tree and use {@code isLeaf}
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} 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}
1186 * to enumerate the nodes in the tree and use {@code isLeaf}
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}. 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()} 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() {
|