001 /*
002 * This file is part of the Echo Point Project. This project is a
003 * collection of Components that have extended the Echo Web Application
004 * Framework Version 3.
005 *
006 * Version: MPL 1.1
007 *
008 * The contents of this file are subject to the Mozilla Public License Version
009 * 1.1 (the "License"); you may not use this file except in compliance with
010 * the License. You may obtain a copy of the License at
011 * http://www.mozilla.org/MPL/
012 *
013 * Software distributed under the License is distributed on an "AS IS" basis,
014 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
015 * for the specific language governing rights and limitations under the
016 * License.
017 */
018
019 package echopoint.tree;
020
021 import java.util.Enumeration;
022 import java.util.Vector;
023 import java.util.NoSuchElementException;
024
025 /**
026 * A {@code DefaultMutableTreeNode} is a general-purpose node in a tree
027 * data structure. A tree node may have at most one parent and 0 or more
028 * children. {@code DefaultMutableTreeNode} provides operations for
029 * examining and modifying a node's parent and children and also operations
030 * for examining the tree that the node is a part of. A node's tree is the set
031 * of all nodes that can be reached by starting at the node and following all
032 * the possible links to parents and children. A node with no parent is the
033 * root of its tree; a node with no children is a leaf. A tree may consist of
034 * many subtrees, each node acting as the root for its own subtree.
035 * <p/>
036 * This class provides enumerations for efficiently traversing a tree or
037 * subtree in various orders or for following the path between two nodes.
038 * <p/>
039 * A {@code DefaultMutableTreeNode} may also hold a reference to a user
040 * object, the use of which is left to the user. Asking a
041 * {@code DefaultMutableTreeNode} for its string representation with
042 * {@code toString()} returns the string representation of its user
043 * object.
044 * <p/>
045 * <b>This is not a thread safe class.</b>If you intend to use a
046 * DefaultMutableTreeNode (or a tree of TreeNodes) in more than one thread,
047 * you need to do your own synchronizing. A good convention to adopt is
048 * synchronizing on the root node of a tree.
049 * <p/>
050 * While DefaultMutableTreeNode implements the MutableTreeNode interface and
051 * will allow you to add in any implementation of MutableTreeNode not all of
052 * the methods in DefaultMutableTreeNode will be applicable to all
053 * MutableTreeNodes implementations. Especially with some of the enumerations
054 * that are provided, using some of these methods assumes the
055 * DefaultMutableTreeNode contains only DefaultMutableNode instances. All of
056 * the TreeNode/MutableTreeNode methods will behave as defined no matter what
057 * implementations are added.
058 * <p/>
059 *
060 * @author Brad Baker, Rakesh Vidyadharan 2009-05-29
061 * @version $Id: DefaultMutableTreeNode.java 213 2009-06-03 16:34:13Z sptrakesh $
062 * @since 3.0.0b3
063 */
064 @SuppressWarnings( { "OverlyComplexClass", "ClassWithTooManyMethods" } )
065 public class DefaultMutableTreeNode<M> implements MutableTreeNode<M>
066 {
067 private static final long serialVersionUID = 1L;
068
069 /** this node's action command */
070 protected String actionCommand;
071
072 /** this node's parent, or null if this node has no parent */
073 protected MutableTreeNode parent;
074
075 /** Array of children, may be null if this node has no children */
076 protected Vector<TreeNode> children;
077
078 /** optional user object */
079 transient protected M userObject;
080
081 /** true if the node is able to have children */
082 protected boolean allowsChildren;
083
084 /**
085 * An enumeration that is always empty. This is used when an enumeration of
086 * a leaf node's children is requested.
087 */
088 public static final Enumeration<TreeNode> EMPTY_ENUMERATION = new EmptyEnumeration();
089
090 /**
091 * Creates a tree node that has no parent and no children, but which allows
092 * children.
093 */
094 public DefaultMutableTreeNode() {}
095
096 /**
097 * Creates a tree node with no parent, no children, but which allows
098 * children, and initializes it with the specified user object.
099 *
100 * @param userObject an Object provided by the user that constitutes the
101 * node's data
102 */
103 public DefaultMutableTreeNode( final M userObject )
104 {
105 this( userObject, true );
106 }
107
108 /**
109 * Creates a tree node with no parent, no children, initialized with the
110 * specified user object, and that allows children only if specified.
111 *
112 * @param userObject an Object provided by the user that constitutes the
113 * node's data
114 * @param allowsChildren if true, the node is allowed to have child nodes --
115 * otherwise, it is always a leaf node
116 */
117 public DefaultMutableTreeNode( final M userObject,
118 final boolean allowsChildren )
119 {
120 super();
121 parent = null;
122 this.allowsChildren = allowsChildren;
123 this.userObject = userObject;
124 }
125
126 /**
127 * Removes {@code newChild} from its parent and makes it a child of
128 * this node by adding it to the end of this node's child array.
129 *
130 * @param newChild The child node to add.
131 * @throws IllegalArgumentException if {@code newChild} is null
132 * @throws IllegalStateException if this node does not allow children
133 */
134 public void add( final MutableTreeNode newChild )
135 {
136 if ( newChild != null && newChild.getParent() == this )
137 {
138 insert( newChild, getChildCount() - 1 );
139 }
140 else
141 {
142 insert( newChild, getChildCount() );
143 }
144 }
145
146 /**
147 * Creates and returns an enumeration that traverses the subtree rooted at
148 * this node in breadth-first order. The first node returned by the
149 * enumeration's {@code nextElement()} method is this node.
150 * <p/>
151 * Modifying the tree by inserting, removing, or moving a node invalidates
152 * any enumerations created before the modification.
153 *
154 * @return an enumeration for traversing the tree in breadth-first order
155 */
156 public Enumeration<TreeNode> breadthFirstEnumeration()
157 {
158 return new BreadthFirstEnumeration( this );
159 }
160
161 /**
162 * Creates and returns a forward-order enumeration of this node's children.
163 * Modifying this node's child array invalidates any child enumerations
164 * created before the modification.
165 *
166 * @return an Enumeration of this node's children
167 */
168 public Enumeration<TreeNode> children()
169 {
170 if ( children == null )
171 {
172 return EMPTY_ENUMERATION;
173 }
174 else
175 {
176 return children.elements();
177 }
178 }
179
180 /**
181 * Creates and returns an enumeration that traverses the subtree rooted at
182 * this node in depth-first order. The first node returned by the
183 * enumeration's {@code nextElement()} method is the leftmost leaf.
184 * This is the same as a postorder traversal.
185 * <p/>
186 * Modifying the tree by inserting, removing, or moving a node invalidates
187 * any enumerations created before the modification.
188 *
189 * @return an enumeration for traversing the tree in depth-first order
190 */
191 public Enumeration<TreeNode> depthFirstEnumeration()
192 {
193 return postorderEnumeration();
194 }
195
196 /** Returns the Action command string associated with this node */
197 public String getActionCommand()
198 {
199 return actionCommand;
200 }
201
202 /**
203 * Returns true if this node is allowed to have children.
204 *
205 * @return true if this node allows children, else false
206 */
207 public boolean getAllowsChildren()
208 {
209 return allowsChildren;
210 }
211
212 /**
213 * Returns the child in this node's child array that immediately follows
214 * {@code aChild}, which must be a child of this node. If
215 * {@code aChild} is the last child, returns null. This method performs
216 * a linear search of this node's children for {@code aChild} and is
217 * O(n) where n is the number of children; to traverse the entire array of
218 * children, use an enumeration instead.
219 *
220 * @param aChild The child node from which the next node is to be retrieved.
221 * @return the child of this node that immediately follows
222 * {@code aChild}
223 * @throws IllegalArgumentException if {@code aChild} is null or is not
224 * a child of this node
225 */
226 public TreeNode getChildAfter( final TreeNode aChild )
227 {
228 if ( aChild == null )
229 {
230 throw new IllegalArgumentException( "argument is null" );
231 }
232
233 final int index = getIndex( aChild ); // linear search
234
235 if ( index == -1 )
236 {
237 throw new IllegalArgumentException( "node is not a child" );
238 }
239
240 if ( index < getChildCount() - 1 )
241 {
242 return getChildAt( index + 1 );
243 }
244 else
245 {
246 return null;
247 }
248 }
249
250 /**
251 * Returns the child at the specified index in this node's child array.
252 *
253 * @param index an index into this node's child array
254 * @return the TreeNode in this node's child array at the specified index
255 * @throws ArrayIndexOutOfBoundsException if {@code index} is out of
256 * bounds
257 */
258 public TreeNode getChildAt( final int index )
259 {
260 if ( children == null )
261 {
262 throw new ArrayIndexOutOfBoundsException( "node has no children" );
263 }
264 return children.elementAt( index );
265 }
266
267 /**
268 * Returns the child in this node's child array that immediately precedes
269 * {@code aChild}, which must be a child of this node. If
270 * {@code aChild} is the first child, returns null. This method
271 * performs a linear search of this node's children for {@code aChild}
272 * and is O(n) where n is the number of children.
273 *
274 * @param aChild The node from which the node before is to be retrieved.
275 * @return the child of this node that immediately precedes
276 * {@code aChild}
277 * @throws IllegalArgumentException if {@code aChild} is null or is not
278 * a child of this node
279 */
280 public TreeNode getChildBefore( final TreeNode aChild )
281 {
282 if ( aChild == null )
283 {
284 throw new IllegalArgumentException( "argument is null" );
285 }
286
287 final int index = getIndex( aChild ); // linear search
288
289 if ( index == -1 )
290 {
291 throw new IllegalArgumentException( "argument is not a child" );
292 }
293
294 if ( index > 0 )
295 {
296 return getChildAt( index - 1 );
297 }
298 else
299 {
300 return null;
301 }
302 }
303
304 /**
305 * Returns the number of children of this node.
306 *
307 * @return an int giving the number of children of this node
308 */
309 public int getChildCount()
310 {
311 if ( children == null )
312 {
313 return 0;
314 }
315 else
316 {
317 return children.size();
318 }
319 }
320
321 /**
322 * Returns the depth of the tree rooted at this node -- the longest distance
323 * from this node to a leaf. If this node has no children, returns 0. This
324 * operation is much more expensive than {@code getLevel()} because it
325 * must effectively traverse the entire tree rooted at this node.
326 *
327 * @return the depth of the tree whose root is this node
328 */
329 public int getDepth()
330 {
331 Object last = null;
332 final Enumeration enumeration = breadthFirstEnumeration();
333
334 while ( enumeration.hasMoreElements() )
335 {
336 last = enumeration.nextElement();
337 }
338
339 if ( last == null )
340 {
341 throw new InternalError( "nodes should be null" );
342 }
343
344 return ( (DefaultMutableTreeNode) last ).getLevel() - getLevel();
345 }
346
347 /**
348 * Returns this node's first child. If this node has no children, throws
349 * NoSuchElementException.
350 *
351 * @return the first child of this node
352 * @throws NoSuchElementException if this node has no children
353 */
354 public TreeNode getFirstChild()
355 {
356 if ( getChildCount() == 0 )
357 {
358 throw new NoSuchElementException( "node has no children" );
359 }
360 return getChildAt( 0 );
361 }
362
363 /**
364 * Finds and returns the first leaf that is a descendant of this node --
365 * either this node or its first child's first leaf. Returns this node if it
366 * is a leaf.
367 *
368 * @return the first leaf in the subtree rooted at this node
369 */
370 public DefaultMutableTreeNode getFirstLeaf()
371 {
372 DefaultMutableTreeNode node = this;
373
374 while ( !node.isLeaf() )
375 {
376 node = (DefaultMutableTreeNode) node.getFirstChild();
377 }
378
379 return node;
380 }
381
382 /**
383 * Returns the index of the specified child in this node's child array. If
384 * the specified node is not a child of this node, returns {@code -1}.
385 * This method performs a linear search and is O(n) where n is the number of
386 * children.
387 *
388 * @param aChild the TreeNode to search for among this node's children
389 * @return an int giving the index of the node in this node's child array,
390 * or {@code -1} if the specified node is a not a child of this
391 * node
392 * @throws IllegalArgumentException if {@code aChild} is null
393 */
394 public int getIndex( final TreeNode aChild )
395 {
396 if ( aChild == null )
397 {
398 throw new IllegalArgumentException( "argument is null" );
399 }
400
401 if ( !isNodeChild( aChild ) )
402 {
403 return -1;
404 }
405 return children.indexOf( aChild ); // linear search
406 }
407
408 /**
409 * Returns this node's last child. If this node has no children, throws
410 * NoSuchElementException.
411 *
412 * @return the last child of this node
413 * @throws NoSuchElementException if this node has no children
414 */
415 public TreeNode getLastChild()
416 {
417 if ( getChildCount() == 0 )
418 {
419 throw new NoSuchElementException( "node has no children" );
420 }
421 return getChildAt( getChildCount() - 1 );
422 }
423
424 /**
425 * Finds and returns the last leaf that is a descendant of this node --
426 * either this node or its last child's last leaf. Returns this node if it
427 * is a leaf.
428 *
429 * @return the last leaf in the subtree rooted at this node
430 */
431 public DefaultMutableTreeNode getLastLeaf()
432 {
433 DefaultMutableTreeNode node = this;
434
435 while ( !node.isLeaf() )
436 {
437 node = (DefaultMutableTreeNode) node.getLastChild();
438 }
439
440 return node;
441 }
442
443 /**
444 * Returns the total number of leaves that are descendants of this node. If
445 * this node is a leaf, returns {@code 1}. This method is O(n) where n
446 * is the number of descendants of this node.
447 *
448 * @return the number of leaves beneath this node
449 */
450 public int getLeafCount()
451 {
452 int count = 0;
453
454 TreeNode node;
455 final Enumeration enumeration = breadthFirstEnumeration(); // order matters
456 // not
457
458 while ( enumeration.hasMoreElements() )
459 {
460 node = (TreeNode) enumeration.nextElement();
461 if ( node.isLeaf() )
462 {
463 count++;
464 }
465 }
466
467 if ( count < 1 )
468 {
469 throw new InternalError( "tree has zero leaves" );
470 }
471
472 return count;
473 }
474
475 /**
476 * Returns the number of levels above this node -- the distance from the
477 * root to this node. If this node is the root, returns 0.
478 *
479 * @return the number of levels above this node
480 */
481 public int getLevel()
482 {
483 TreeNode ancestor;
484 int levels = 0;
485
486 ancestor = this;
487 while ( ( ancestor = ancestor.getParent() ) != null )
488 {
489 levels++;
490 }
491
492 return levels;
493 }
494
495 /**
496 * Returns the leaf after this node or null if this node is the last leaf in
497 * the tree.
498 * <p/>
499 * In this implementation of the {@code MutableNode} interface, this
500 * operation is very inefficient. In order to determine the next node, this
501 * method first performs a linear search in the parent's child-list in order
502 * to find the current node.
503 * <p/>
504 * That implementation makes the operation suitable for short traversals
505 * from a known position. But to traverse all of the leaves in the tree, you
506 * should use {@code depthFirstEnumeration} to enumerate the nodes in
507 * the tree and use {@code isLeaf} on each node to determine which are
508 * leaves.
509 *
510 * @return The leaf after this node or {@code null}.
511 */
512 public DefaultMutableTreeNode getNextLeaf()
513 {
514 DefaultMutableTreeNode nextSibling;
515 final DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();
516
517 if ( myParent == null )
518 {
519 return null;
520 }
521
522 nextSibling = getNextSibling(); // linear search
523
524 if ( nextSibling != null )
525 {
526 return nextSibling.getFirstLeaf();
527 }
528
529 return myParent.getNextLeaf(); // tail recursion
530 }
531
532 /**
533 * Returns the node that follows this node in a preorder traversal of this
534 * node's tree. Returns null if this node is the last node of the traversal.
535 * This is an inefficient way to traverse the entire tree; use an
536 * enumeration, instead.
537 *
538 * @return Return the node that follows this node.
539 */
540 public DefaultMutableTreeNode getNextNode()
541 {
542 if ( getChildCount() == 0 )
543 {
544 // No children, so look for nextSibling
545 DefaultMutableTreeNode nextSibling = getNextSibling();
546
547 if ( nextSibling == null )
548 {
549 DefaultMutableTreeNode aNode = (DefaultMutableTreeNode) getParent();
550
551 do
552 {
553 if ( aNode == null )
554 {
555 return null;
556 }
557
558 nextSibling = aNode.getNextSibling();
559 if ( nextSibling != null )
560 {
561 return nextSibling;
562 }
563
564 aNode = (DefaultMutableTreeNode) aNode.getParent();
565 } while ( true );
566 }
567 else
568 {
569 return nextSibling;
570 }
571 }
572 else
573 {
574 return (DefaultMutableTreeNode) getChildAt( 0 );
575 }
576 }
577
578 /**
579 * Returns the next sibling of this node in the parent's children array.
580 * Returns null if this node has no parent or is the parent's last child.
581 * This method performs a linear search that is O(n) where n is the number
582 * of children; to traverse the entire array, use the parent's child
583 * enumeration instead.
584 *
585 * @return Return the next sibling from the parent node.
586 */
587 public DefaultMutableTreeNode getNextSibling()
588 {
589 DefaultMutableTreeNode retval;
590
591 final DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();
592
593 if ( myParent == null )
594 {
595 retval = null;
596 }
597 else
598 {
599 retval = (DefaultMutableTreeNode) myParent.getChildAfter( this );
600 // linear search
601 }
602
603 if ( retval != null && !isNodeSibling( retval ) )
604 {
605 throw new InternalError( "child of parent is not a sibling" );
606 }
607
608 return retval;
609 }
610
611 /**
612 * Returns this node's parent or null if this node has no parent.
613 *
614 * @return this node's parent TreeNode, or null if this node has no parent
615 */
616 public TreeNode getParent()
617 {
618 return parent;
619 }
620
621 /**
622 * Returns the path from the root, to get to this node. The last element in
623 * the path is this node.
624 *
625 * @return an array of TreeNode objects giving the path, where the first
626 * element in the path is the root and the last element is this
627 * node.
628 */
629 public TreeNode[] getPath()
630 {
631 return getPathToRoot( this, 0 );
632 }
633
634 /**
635 * Builds the parents of node up to and including the root node, where the
636 * original node is the last element in the returned array. The length of
637 * the returned array gives the node's depth in the tree.
638 *
639 * @param aNode the TreeNode to get the path for
640 * @param depth an int giving the number of steps already taken towards the
641 * root (on recursive calls), used to size the returned array
642 * @return an array of TreeNodes giving the path from the root to the
643 * specified node
644 */
645 protected TreeNode[] getPathToRoot( final TreeNode aNode, int depth )
646 {
647 TreeNode[] retNodes;
648
649 /*
650 * Check for null, in case someone passed in a null node, or they passed in
651 * an element that isn't rooted at root.
652 */
653 if ( aNode == null )
654 {
655 if ( depth == 0 )
656 {
657 return null;
658 }
659 else
660 {
661 retNodes = new TreeNode[depth];
662 }
663 }
664 else
665 {
666 depth++;
667 retNodes = getPathToRoot( aNode.getParent(), depth );
668 retNodes[retNodes.length - depth] = aNode;
669 }
670 return retNodes;
671 }
672
673 /**
674 * Returns the leaf before this node or null if this node is the first leaf
675 * in the tree.
676 * <p/>
677 * In this implementation of the {@code MutableNode} interface, this
678 * operation is very inefficient. In order to determine the previous node,
679 * this method first performs a linear search in the parent's child-list in
680 * order to find the current node.
681 * <p/>
682 * That implementation makes the operation suitable for short traversals
683 * from a known position. But to traverse all of the leaves in the tree, you
684 * should use {@code depthFirstEnumeration} to enumerate the nodes in
685 * the tree and use {@code isLeaf} on each node to determine which are
686 * leaves.
687 *
688 * @return The previous leaf node based on the position of this node.
689 */
690 public DefaultMutableTreeNode getPreviousLeaf()
691 {
692 DefaultMutableTreeNode previousSibling;
693 final DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();
694
695 if ( myParent == null )
696 {
697 return null;
698 }
699
700 previousSibling = getPreviousSibling(); // linear search
701
702 if ( previousSibling != null )
703 {
704 return previousSibling.getLastLeaf();
705 }
706
707 return myParent.getPreviousLeaf(); // tail recursion
708 }
709
710 /**
711 * Returns the node that precedes this node in a preorder traversal of this
712 * node's tree. Returns null if this node is the first node of the traveral
713 * -- the root of the tree. This is an inefficient way to traverse the
714 * entire tree; use an enumeration, instead.
715 *
716 * @return The preivous node based on the position of this node.
717 */
718 public DefaultMutableTreeNode getPreviousNode()
719 {
720 DefaultMutableTreeNode previousSibling;
721 final DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();
722
723 if ( myParent == null )
724 {
725 return null;
726 }
727
728 previousSibling = getPreviousSibling();
729
730 if ( previousSibling != null )
731 {
732 if ( previousSibling.getChildCount() == 0 )
733 {
734 return previousSibling;
735 }
736 else
737 {
738 return previousSibling.getLastLeaf();
739 }
740 }
741 else
742 {
743 return myParent;
744 }
745 }
746
747 /**
748 * Returns the previous sibling of this node in the parent's children array.
749 * Returns null if this node has no parent or is the parent's first child.
750 * This method performs a linear search that is O(n) where n is the number
751 * of children.
752 *
753 * @return the sibling of this node that immediately precedes this node
754 */
755 public DefaultMutableTreeNode getPreviousSibling()
756 {
757 DefaultMutableTreeNode retval;
758
759 final DefaultMutableTreeNode myParent = (DefaultMutableTreeNode) getParent();
760
761 if ( myParent == null )
762 {
763 retval = null;
764 }
765 else
766 {
767 retval = (DefaultMutableTreeNode) myParent.getChildBefore( this );
768 // linear search
769 }
770
771 if ( retval != null && !isNodeSibling( retval ) )
772 {
773 throw new InternalError( "child of parent is not a sibling" );
774 }
775
776 return retval;
777 }
778
779 /**
780 * Returns the root of the tree that contains this node. The root is the
781 * ancestor with a null parent.
782 *
783 * @return The root of the tree.
784 */
785 public TreeNode getRoot()
786 {
787 TreeNode ancestor = this;
788 TreeNode previous;
789
790 do
791 {
792 previous = ancestor;
793 ancestor = ancestor.getParent();
794 } while ( ancestor != null );
795
796 return previous;
797 }
798
799 /**
800 * Returns the nearest common ancestor to this node and {@code aNode}.
801 * Returns null, if no such ancestor exists -- if this node and
802 * {@code aNode} are in different trees or if {@code aNode} is
803 * null. A node is considered an ancestor of itself.
804 *
805 * @param aNode The node for which the common ancestor is to be retrieved.
806 * @return The common ancestor of this node and the specified node.
807 */
808 public TreeNode getSharedAncestor( final DefaultMutableTreeNode aNode )
809 {
810 if ( aNode == this )
811 {
812 return this;
813 }
814 else if ( aNode == null )
815 {
816 return null;
817 }
818
819 int level1, level2, diff;
820 TreeNode node1, node2;
821
822 level1 = getLevel();
823 level2 = aNode.getLevel();
824
825 if ( level2 > level1 )
826 {
827 diff = level2 - level1;
828 node1 = aNode;
829 node2 = this;
830 }
831 else
832 {
833 diff = level1 - level2;
834 node1 = this;
835 node2 = aNode;
836 }
837
838 // Go up the tree until the nodes are at the same level
839 while ( diff > 0 )
840 {
841 node1 = node1.getParent();
842 diff--;
843 }
844
845 // Move up the tree until we find a common ancestor. Since we know
846 // that both nodes are at the same level, we won't cross paths
847 // unknowingly (if there is a common ancestor, both nodes hit it in
848 // the same iteration).
849
850 do
851 {
852 if ( node1 == node2 )
853 {
854 return node1;
855 }
856 node1 = node1.getParent();
857 node2 = node2.getParent();
858 } while ( node1 != null ); // only need to check one -- they're at the
859 // same level so if one is null, the other is
860
861 if ( node2 != null ) throw new InternalError( "nodes should be null" );
862
863 return null;
864 }
865
866 /**
867 * Returns the number of siblings of this node. A node is its own sibling
868 * (if it has no parent or no siblings, this method returns
869 * {@code 1}).
870 *
871 * @return the number of siblings of this node
872 */
873 public int getSiblingCount()
874 {
875 final TreeNode myParent = getParent();
876
877 if ( myParent == null )
878 {
879 return 1;
880 }
881 else
882 {
883 return myParent.getChildCount();
884 }
885 }
886
887 /** @return Returns this node's user object. */
888 public M getUserObject()
889 {
890 return userObject;
891 }
892
893 /**
894 * Returns the user object path, from the root, to get to this node. If some
895 * of the TreeNodes in the path have null user objects, the returned path
896 * will contain nulls.
897 *
898 * @return The array of user objects.
899 */
900 public Object[] getUserObjectPath()
901 {
902 final TreeNode[] realPath = getPath();
903 final Object[] retPath = new Object[realPath.length];
904
905 for ( int counter = 0; counter < realPath.length; counter++ )
906 {
907 retPath[counter] = ( (DefaultMutableTreeNode) realPath[counter] )
908 .getUserObject();
909 }
910 return retPath;
911 }
912
913 /**
914 * Removes {@code newChild} from its present parent (if it has a
915 * parent), sets the child's parent to this node, and then adds the child to
916 * this node's child array at index {@code childIndex}.
917 * {@code newChild} must not be null and must not be an ancestor of
918 * this node.
919 */
920 public void insert( final MutableTreeNode newChild, final int childIndex )
921 {
922 if ( !getAllowsChildren() )
923 {
924 throw new IllegalStateException( "node does not allow children" );
925 }
926 else if ( newChild == null )
927 {
928 throw new IllegalArgumentException( "new child is null" );
929 }
930 else if ( isNodeAncestor( newChild ) )
931 {
932 throw new IllegalArgumentException( "new child is an ancestor" );
933 }
934
935 final MutableTreeNode oldParent = (MutableTreeNode) newChild.getParent();
936
937 if ( oldParent != null )
938 {
939 oldParent.remove( newChild );
940 }
941 newChild.setParent( this );
942 if ( children == null )
943 {
944 children = new Vector<TreeNode>();
945 }
946 children.insertElementAt( newChild, childIndex );
947 }
948
949 /**
950 * Returns true if this node has no children. To distinguish between nodes
951 * that have no children and nodes that <i>cannot</i> have children (e.g. to
952 * distinguish files from empty directories), use this method in conjunction
953 * with {@code getAllowsChildren}
954 */
955 public boolean isLeaf()
956 {
957 return getChildCount() == 0;
958 }
959
960 /**
961 * Returns true if {@code anotherNode} is an ancestor of this node --
962 * if it is this node, this node's parent, or an ancestor of this node's
963 * parent. (Note that a node is considered an ancestor of itself.) If
964 * {@code anotherNode} is null, this method returns false. This
965 * operation is at worst O(h) where h is the distance from the root to this
966 * node.
967 *
968 * @param anotherNode The node to check.
969 * @return {@code true} if the specified node is an ancestor.
970 */
971 public boolean isNodeAncestor( final TreeNode anotherNode )
972 {
973 if ( anotherNode == null )
974 {
975 return false;
976 }
977
978 TreeNode ancestor = this;
979
980 do
981 {
982 if ( ancestor == anotherNode )
983 {
984 return true;
985 }
986 } while ( ( ancestor = ancestor.getParent() ) != null );
987
988 return false;
989 }
990
991 /**
992 * Returns true if {@code aNode} is a child of this node. If
993 * {@code aNode} is null, this method returns false.
994 *
995 * @param aNode The node to check.
996 * @return {@code true} if {@code aNode} is a child of this node;
997 * {@code false} if {@code aNode} is {@code null}
998 */
999 public boolean isNodeChild( final TreeNode aNode )
1000 {
1001 boolean retval;
1002 retval = aNode != null && getChildCount() != 0 && aNode.getParent() == this;
1003 return retval;
1004 }
1005
1006 /**
1007 * Returns true if {@code anotherNode} is a descendant of this node --
1008 * if it is this node, one of this node's children, or a descendant of one
1009 * of this node's children. Note that a node is considered a descendant of
1010 * itself. If {@code anotherNode} is null, returns false. This
1011 * operation is at worst O(h) where h is the distance from the root to
1012 * {@code anotherNode}.
1013 *
1014 * @param anotherNode The node to check.
1015 * @return {@code true} is the node is a descendent of this node.
1016 */
1017 public boolean isNodeDescendant( final DefaultMutableTreeNode anotherNode )
1018 {
1019 return anotherNode != null && anotherNode.isNodeAncestor( this );
1020 }
1021
1022 /**
1023 * Returns true if and only if {@code aNode} is in the same tree as
1024 * this node. Returns false if {@code aNode} is null.
1025 *
1026 * @param aNode The node to check.
1027 * @return {@code true} if the node is in the same tree.
1028 */
1029 public boolean isNodeRelated( final DefaultMutableTreeNode aNode )
1030 {
1031 return aNode != null && getRoot() == aNode.getRoot();
1032 }
1033
1034 /**
1035 * Returns true if {@code anotherNode} is a sibling of (has the same
1036 * parent as) this node. A node is its own sibling. If
1037 * {@code anotherNode} is null, returns false.
1038 *
1039 * @param anotherNode node to test as sibling of this node
1040 * @return true if {@code anotherNode} is a sibling of this node
1041 */
1042 public boolean isNodeSibling( final TreeNode anotherNode )
1043 {
1044 boolean retval;
1045
1046 if ( anotherNode == null )
1047 {
1048 retval = false;
1049 }
1050 else if ( anotherNode == this )
1051 {
1052 retval = true;
1053 }
1054 else
1055 {
1056 final TreeNode myParent = getParent();
1057 retval = myParent != null && myParent == anotherNode.getParent();
1058
1059 if ( retval
1060 && !( (DefaultMutableTreeNode) getParent() ).isNodeChild( anotherNode ) )
1061 {
1062 throw new InternalError( "sibling has different parent" );
1063 }
1064 }
1065
1066 return retval;
1067 }
1068
1069 /**
1070 * Returns true if this node is the root of the tree. The root is the only
1071 * node in the tree with a null parent; every tree has exactly one root.
1072 *
1073 * @return true if this node is the root of its tree
1074 */
1075 public boolean isRoot()
1076 {
1077 return getParent() == null;
1078 }
1079
1080 /**
1081 * Creates and returns an enumeration that follows the path from
1082 * {@code ancestor} to this node. The enumeration's
1083 * {@code nextElement()} method first returns {@code ancestor},
1084 * then the child of {@code ancestor} that is an ancestor of this node,
1085 * and so on, and finally returns this node. Creation of the enumeration is
1086 * O(m) where m is the number of nodes between this node and
1087 * {@code ancestor}, inclusive. Each {@code nextElement()} message
1088 * is O(1).
1089 * <p/>
1090 * Modifying the tree by inserting, removing, or moving a node invalidates
1091 * any enumerations created before the modification.
1092 *
1093 * @param ancestor The ancestor node from which the path is to be generated.
1094 * @return The enumeration of nodes.
1095 */
1096 public Enumeration<TreeNode> pathFromAncestorEnumeration(
1097 final TreeNode ancestor )
1098 {
1099 return new PathBetweenNodesEnumeration( ancestor, this );
1100 }
1101
1102 /**
1103 * Creates and returns an enumeration that traverses the subtree rooted at
1104 * this node in postorder. The first node returned by the enumeration's
1105 * {@code nextElement()} method is the leftmost leaf. This is the same
1106 * as a depth-first traversal.
1107 * <p/>
1108 * Modifying the tree by inserting, removing, or moving a node invalidates
1109 * any enumerations created before the modification.
1110 *
1111 * @return The post order enumeration for this node.
1112 */
1113 public Enumeration<TreeNode> postorderEnumeration()
1114 {
1115 return new PostorderEnumeration( this );
1116 }
1117
1118 /**
1119 * Creates and returns an enumeration that traverses the subtree rooted at
1120 * this node in preorder. The first node returned by the enumeration's
1121 * {@code nextElement()} method is this node.
1122 * <p/>
1123 * Modifying the tree by inserting, removing, or moving a node invalidates
1124 * any enumerations created before the modification.
1125 *
1126 * @return The enumeration of nodes.
1127 */
1128 public Enumeration<TreeNode> preorderEnumeration()
1129 {
1130 return new PreorderEnumeration( this );
1131 }
1132
1133 /**
1134 * Removes the child at the specified index from this node's children and
1135 * sets that node's parent to null. The child node to remove must be a
1136 * {@code MutableTreeNode}.
1137 *
1138 * @param childIndex the index in this node's child array of the child to
1139 * remove
1140 * @throws ArrayIndexOutOfBoundsException if {@code childIndex} is out
1141 * of bounds
1142 */
1143 public void remove( final int childIndex )
1144 {
1145 final MutableTreeNode child = (MutableTreeNode) getChildAt( childIndex );
1146 children.removeElementAt( childIndex );
1147 child.setParent( null );
1148 }
1149
1150 /**
1151 * Removes {@code aChild} from this node's child array, giving it a
1152 * null parent.
1153 *
1154 * @param aChild a child of this node to remove
1155 * @throws IllegalArgumentException if {@code aChild} is null or is not
1156 * a child of this node
1157 */
1158 public void remove( final MutableTreeNode aChild )
1159 {
1160 if ( aChild == null )
1161 {
1162 throw new IllegalArgumentException( "argument is null" );
1163 }
1164
1165 if ( !isNodeChild( aChild ) )
1166 {
1167 throw new IllegalArgumentException( "argument is not a child" );
1168 }
1169 remove( getIndex( aChild ) ); // linear search
1170 }
1171
1172 /**
1173 * Removes all of this node's children, setting their parents to null. If
1174 * this node has no children, this method does nothing.
1175 */
1176 public void removeAllChildren()
1177 {
1178 for ( int i = getChildCount() - 1; i >= 0; i-- )
1179 {
1180 remove( i );
1181 }
1182 }
1183
1184 /**
1185 * Removes the subtree rooted at this node from the tree, giving this node a
1186 * null parent. Does nothing if this node is the root of its tree.
1187 */
1188 public void removeFromParent()
1189 {
1190 final MutableTreeNode parent = (MutableTreeNode) getParent();
1191 if ( parent != null )
1192 {
1193 parent.remove( this );
1194 }
1195 }
1196
1197 /**
1198 * Sets this node's action command to {@code newActionCommand}
1199 *
1200 * @param newActionCommand this node's new action command
1201 */
1202 public void setActionCommand( final String newActionCommand )
1203 {
1204 actionCommand = newActionCommand;
1205 }
1206
1207 /**
1208 * Determines whether or not this node is allowed to have children. If
1209 * {@code allows} is false, all of this node's children are removed.
1210 * <p/>
1211 * Note: By default, a node allows children.
1212 *
1213 * @param allows true if this node is allowed to have children
1214 */
1215 public void setAllowsChildren( final boolean allows )
1216 {
1217 if ( allows != allowsChildren )
1218 {
1219 allowsChildren = allows;
1220 if ( !allowsChildren )
1221 {
1222 removeAllChildren();
1223 }
1224 }
1225 }
1226
1227 /**
1228 * Sets this node's parent to {@code newParent} but does not change the
1229 * parent's child array. This method is called from {@code insert()}
1230 * and {@code remove()} to reassign a child's parent, it should not be
1231 * messaged from anywhere else.
1232 *
1233 * @param newParent this node's new parent
1234 */
1235 public void setParent( final MutableTreeNode newParent )
1236 {
1237 parent = newParent;
1238 }
1239
1240 /** Sets the user object for this node to {@code userObject}. */
1241 public void setUserObject( final M userObject )
1242 {
1243 this.userObject = userObject;
1244 }
1245
1246 /**
1247 * Returns the result of sending {@code toString()} to this node's user
1248 * object, or {@code null} if this node has no user object.
1249 */
1250 @Override
1251 public String toString()
1252 {
1253 if ( userObject == null )
1254 {
1255 return null;
1256 }
1257 else
1258 {
1259 return userObject.toString();
1260 }
1261 }
1262
1263 /** An empty enumeration for nodes that are leaves. */
1264 static class EmptyEnumeration implements Enumeration<TreeNode>
1265 {
1266 public boolean hasMoreElements()
1267 {
1268 return false;
1269 }
1270
1271 public TreeNode nextElement()
1272 {
1273 throw new NoSuchElementException( "No more elements" );
1274 }
1275 }
1276 }