001 /* DefaultMutableTreeNode.java --
002 Copyright (C) 2002, 2004, 2005, 2006, Free Software Foundation, Inc.
003
004 This file is part of GNU Classpath.
005
006 GNU Classpath is free software; you can redistribute it and/or modify
007 it under the terms of the GNU General Public License as published by
008 the Free Software Foundation; either version 2, or (at your option)
009 any later version.
010
011 GNU Classpath is distributed in the hope that it will be useful, but
012 WITHOUT ANY WARRANTY; without even the implied warranty of
013 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
014 General Public License for more details.
015
016 You should have received a copy of the GNU General Public License
017 along with GNU Classpath; see the file COPYING. If not, write to the
018 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019 02110-1301 USA.
020
021 Linking this library statically or dynamically with other modules is
022 making a combined work based on this library. Thus, the terms and
023 conditions of the GNU General Public License cover the whole
024 combination.
025
026 As a special exception, the copyright holders of this library give you
027 permission to link this library with independent modules to produce an
028 executable, regardless of the license terms of these independent
029 modules, and to copy and distribute the resulting executable under
030 terms of your choice, provided that you also meet, for each linked
031 independent module, the terms and conditions of the license of that
032 module. An independent module is a module which is not derived from
033 or based on this library. If you modify this library, you may extend
034 this exception to your version of the library, but you are not
035 obligated to do so. If you do not wish to do so, delete this
036 exception statement from your version. */
037
038
039 package javax.swing.tree;
040
041 import java.io.IOException;
042 import java.io.ObjectInputStream;
043 import java.io.ObjectOutputStream;
044 import java.io.Serializable;
045 import java.util.ArrayList;
046 import java.util.Enumeration;
047 import java.util.LinkedList;
048 import java.util.NoSuchElementException;
049 import java.util.Stack;
050 import java.util.Vector;
051
052
053 /**
054 * A default implementation of the {@link MutableTreeNode} interface.
055 *
056 * @author Andrew Selkirk
057 * @author Robert Schuster (robertschuster@fsfe.org)
058 */
059 public class DefaultMutableTreeNode
060 implements Cloneable, MutableTreeNode, Serializable
061 {
062 private static final long serialVersionUID = -4298474751201349152L;
063
064 /**
065 * The parent of this node (possibly <code>null</code>).
066 */
067 protected MutableTreeNode parent;
068
069 /**
070 * The child nodes for this node (may be empty).
071 */
072 protected Vector<MutableTreeNode> children = new Vector<MutableTreeNode>();
073
074 /**
075 * userObject
076 */
077 protected transient Object userObject;
078
079 /**
080 * allowsChildren
081 */
082 protected boolean allowsChildren;
083
084 /**
085 * Creates a <code>DefaultMutableTreeNode</code> object.
086 * This is equivalent to <code>DefaultMutableTreeNode(null, true)</code>.
087 */
088 public DefaultMutableTreeNode()
089 {
090 this(null, true);
091 }
092
093 /**
094 * Creates a <code>DefaultMutableTreeNode</code> object with the given
095 * user object attached to it. This is equivalent to
096 * <code>DefaultMutableTreeNode(userObject, true)</code>.
097 *
098 * @param userObject the user object (<code>null</code> permitted).
099 */
100 public DefaultMutableTreeNode(Object userObject)
101 {
102 this(userObject, true);
103 }
104
105 /**
106 * Creates a <code>DefaultMutableTreeNode</code> object with the given
107 * user object attached to it.
108 *
109 * @param userObject the user object (<code>null</code> permitted).
110 * @param allowsChildren <code>true</code> if the code allows to add child
111 * nodes, <code>false</code> otherwise
112 */
113 public DefaultMutableTreeNode(Object userObject, boolean allowsChildren)
114 {
115 this.userObject = userObject;
116 this.allowsChildren = allowsChildren;
117 }
118
119 /**
120 * Returns a clone of the node. The clone contains a shallow copy of the
121 * user object, and does not copy the parent node or the child nodes.
122 *
123 * @return A clone of the node.
124 */
125 public Object clone()
126 {
127 return new DefaultMutableTreeNode(this.userObject, this.allowsChildren);
128 }
129
130 /**
131 * Returns a string representation of the node. This implementation returns
132 * <code>getUserObject().toString()</code>, or <code>null</code> if there
133 * is no user object.
134 *
135 * @return A string representation of the node (possibly <code>null</code>).
136 */
137 public String toString()
138 {
139 if (userObject == null)
140 return null;
141
142 return userObject.toString();
143 }
144
145 /**
146 * Adds a new child node to this node and sets this node as the parent of
147 * the child node. The child node must not be an ancestor of this node.
148 * If the tree uses the {@link DefaultTreeModel}, you must subsequently
149 * call {@link DefaultTreeModel#reload(TreeNode)}.
150 *
151 * @param child the child node (<code>null</code> not permitted).
152 *
153 * @throws IllegalStateException if {@link #getAllowsChildren()} returns
154 * <code>false</code>.
155 * @throws IllegalArgumentException if {@link #isNodeAncestor} returns
156 * <code>true</code>.
157 * @throws IllegalArgumentException if <code>child</code> is
158 * <code>null</code>.
159 */
160 public void add(MutableTreeNode child)
161 {
162 if (! allowsChildren)
163 throw new IllegalStateException();
164
165 if (child == null)
166 throw new IllegalArgumentException();
167
168 if (isNodeAncestor(child))
169 throw new IllegalArgumentException("Cannot add ancestor node.");
170
171 children.add(child);
172 child.setParent(this);
173 }
174
175 /**
176 * Returns the parent node of this node.
177 *
178 * @return The parent node (possibly <code>null</code>).
179 */
180 public TreeNode getParent()
181 {
182 return parent;
183 }
184
185 /**
186 * Removes the child with the given index from this node.
187 *
188 * @param index the index (in the range <code>0</code> to
189 * <code>getChildCount() - 1</code>).
190 *
191 * @throws ArrayIndexOutOfBoundsException if <code>index</code> is outside
192 * the valid range.
193 */
194 public void remove(int index)
195 {
196 MutableTreeNode child = children.remove(index);
197 child.setParent(null);
198 }
199
200 /**
201 * Removes the given child from this node and sets its parent to
202 * <code>null</code>.
203 *
204 * @param node the child node (<code>null</code> not permitted).
205 *
206 * @throws IllegalArgumentException if <code>node</code> is not a child of
207 * this node.
208 * @throws IllegalArgumentException if <code>node</code> is null.
209 */
210 public void remove(MutableTreeNode node)
211 {
212 if (node == null)
213 throw new IllegalArgumentException("Null 'node' argument.");
214 if (node.getParent() != this)
215 throw new IllegalArgumentException(
216 "The given 'node' is not a child of this node.");
217 children.remove(node);
218 node.setParent(null);
219 }
220
221 /**
222 * writeObject
223 *
224 * @param stream the output stream
225 *
226 * @exception IOException If an error occurs
227 */
228 private void writeObject(ObjectOutputStream stream)
229 throws IOException
230 {
231 // TODO: Implement me.
232 }
233
234 /**
235 * readObject
236 *
237 * @param stream the input stream
238 *
239 * @exception IOException If an error occurs
240 * @exception ClassNotFoundException TODO
241 */
242 private void readObject(ObjectInputStream stream)
243 throws IOException, ClassNotFoundException
244 {
245 // TODO: Implement me.
246 }
247
248 /**
249 * Inserts given child node at the given index.
250 *
251 * @param node the child node (<code>null</code> not permitted).
252 * @param index the index.
253 *
254 * @throws IllegalArgumentException if <code>node</code> is
255 * </code>null</code>.
256 */
257 public void insert(MutableTreeNode node, int index)
258 {
259 if (! allowsChildren)
260 throw new IllegalStateException();
261
262 if (node == null)
263 throw new IllegalArgumentException("Null 'node' argument.");
264
265 if (isNodeAncestor(node))
266 throw new IllegalArgumentException("Cannot insert ancestor node.");
267
268 children.insertElementAt(node, index);
269 }
270
271 /**
272 * Returns a path to this node from the root.
273 *
274 * @return an array of tree nodes
275 */
276 public TreeNode[] getPath()
277 {
278 return getPathToRoot(this, 0);
279 }
280
281 /**
282 * Returns an enumeration containing all children of this node.
283 * <code>EMPTY_ENUMERATION</code> is returned if this node has no children.
284 *
285 * @return an enumeration of tree nodes
286 */
287 @SuppressWarnings("unchecked") // Required for API compatibility
288 public Enumeration children()
289 {
290 if (children.size() == 0)
291 return EMPTY_ENUMERATION;
292
293 return children.elements();
294 }
295
296 /**
297 * Set the parent node for this node.
298 *
299 * @param node the parent node
300 */
301 public void setParent(MutableTreeNode node)
302 {
303 parent = node;
304 }
305
306 /**
307 * Returns the child node at a given index.
308 *
309 * @param index the index
310 *
311 * @return the child node
312 */
313 public TreeNode getChildAt(int index)
314 {
315 return children.elementAt(index);
316 }
317
318 /**
319 * Returns the number of children of this node.
320 *
321 * @return the number of children
322 */
323 public int getChildCount()
324 {
325 return children.size();
326 }
327
328 /**
329 * Returns the index of the specified child node, or -1 if the node is not
330 * in fact a child of this node.
331 *
332 * @param node the node (<code>null</code> not permitted).
333 *
334 * @return The index of the specified child node, or -1.
335 *
336 * @throws IllegalArgumentException if <code>node</code> is <code>null</code>.
337 */
338 public int getIndex(TreeNode node)
339 {
340 if (node == null)
341 throw new IllegalArgumentException("Null 'node' argument.");
342 return children.indexOf(node);
343 }
344
345 /**
346 * Sets the flag that controls whether or not this node allows the addition /
347 * insertion of child nodes. If the flag is set to <code>false</code>, any
348 * existing children are removed.
349 *
350 * @param allowsChildren the flag.
351 */
352 public void setAllowsChildren(boolean allowsChildren)
353 {
354 if (!allowsChildren)
355 removeAllChildren();
356 this.allowsChildren = allowsChildren;
357 }
358
359 /**
360 * getAllowsChildren
361 *
362 * @return boolean
363 */
364 public boolean getAllowsChildren()
365 {
366 return allowsChildren;
367 }
368
369 /**
370 * Sets the user object for this node
371 *
372 * @param userObject the user object
373 */
374 public void setUserObject(Object userObject)
375 {
376 this.userObject = userObject;
377 }
378
379 /**
380 * Returns the user object attached to this node. <code>null</code> is
381 * returned when no user object is set.
382 *
383 * @return the user object
384 */
385 public Object getUserObject()
386 {
387 return userObject;
388 }
389
390 /**
391 * Removes this node from its parent.
392 */
393 public void removeFromParent()
394 {
395 parent.remove(this);
396 parent = null;
397 }
398
399 /**
400 * Removes all child nodes from this node.
401 */
402 public void removeAllChildren()
403 {
404 for (int i = getChildCount() - 1; i >= 0; i--)
405 remove(i);
406 }
407
408 /**
409 * Returns <code>true</code> if <code>node</code> is an ancestor of this
410 * tree node, and <code>false</code> otherwise. An ancestor node is any of:
411 * <ul>
412 * <li>this tree node;</li>
413 * <li>the parent node (if there is one);</li>
414 * <li>any ancestor of the parent node;</li>
415 * </ul>
416 * If <code>node</code> is <code>null</code>, this method returns
417 * <code>false</code>.
418 *
419 * @param node the node (<code>null</code> permitted).
420 *
421 * @return A boolean.
422 */
423 public boolean isNodeAncestor(TreeNode node)
424 {
425 if (node == null)
426 return false;
427
428 TreeNode current = this;
429
430 while (current != null && current != node)
431 current = current.getParent();
432
433 return current == node;
434 }
435
436 /**
437 * Returns <code>true</code> if <code>node</code> is a descendant of this
438 * tree node, and <code>false</code> otherwise. A descendant node is any of:
439 * <ul>
440 * <li>this tree node;</li>
441 * <li>the child nodes belonging to this tree node, if there are any;</li>
442 * <li>any descendants of the child nodes;</li>
443 * </ul>
444 * If <code>node</code> is <code>null</code>, this method returns
445 * <code>false</code>.
446 *
447 * @param node the node (<code>null</code> permitted).
448 *
449 * @return A boolean.
450 */
451 public boolean isNodeDescendant(DefaultMutableTreeNode node)
452 {
453 if (node == null)
454 return false;
455
456 TreeNode current = node;
457
458 while (current != null
459 && current != this)
460 current = current.getParent();
461
462 return current == this;
463 }
464
465 /**
466 * getSharedAncestor
467 *
468 * @param node TODO
469 *
470 * @return TreeNode
471 */
472 public TreeNode getSharedAncestor(DefaultMutableTreeNode node)
473 {
474 TreeNode current = this;
475 ArrayList<TreeNode> list = new ArrayList<TreeNode>();
476
477 while (current != null)
478 {
479 list.add(current);
480 current = current.getParent();
481 }
482
483 current = node;
484
485 while (current != null)
486 {
487 if (list.contains(current))
488 return current;
489
490 current = current.getParent();
491 }
492
493 return null;
494 }
495
496 /**
497 * isNodeRelated
498 *
499 * @param node TODO
500 *
501 * @return boolean
502 */
503 public boolean isNodeRelated(DefaultMutableTreeNode node)
504 {
505 if (node == null)
506 return false;
507
508 return node.getRoot() == getRoot();
509 }
510
511 /**
512 * getDepth
513 *
514 * @return int
515 */
516 public int getDepth()
517 {
518 if ((! allowsChildren)
519 || children.size() == 0)
520 return 0;
521
522 Stack<Integer> stack = new Stack<Integer>();
523 stack.push(new Integer(0));
524 TreeNode node = getChildAt(0);
525 int depth = 0;
526 int current = 1;
527
528 while (! stack.empty())
529 {
530 if (node.getChildCount() != 0)
531 {
532 node = node.getChildAt(0);
533 stack.push(new Integer(0));
534 current++;
535 }
536 else
537 {
538 if (current > depth)
539 depth = current;
540
541 int size;
542 int index;
543
544 do
545 {
546 node = node.getParent();
547 size = node.getChildCount();
548 index = stack.pop().intValue() + 1;
549 current--;
550 }
551 while (index >= size
552 && node != this);
553
554 if (index < size)
555 {
556 node = node.getChildAt(index);
557 stack.push(new Integer(index));
558 current++;
559 }
560 }
561 }
562
563 return depth;
564 }
565
566 /**
567 * getLevel
568 *
569 * @return int
570 */
571 public int getLevel()
572 {
573 int count = -1;
574 TreeNode current = this;
575
576 do
577 {
578 current = current.getParent();
579 count++;
580 }
581 while (current != null);
582
583 return count;
584 }
585
586 /**
587 * getPathToRoot
588 *
589 * @param node TODO
590 * @param depth TODO
591 *
592 * @return TreeNode[]
593 */
594 protected TreeNode[] getPathToRoot(TreeNode node, int depth)
595 {
596 if (node == null)
597 {
598 if (depth == 0)
599 return null;
600
601 return new TreeNode[depth];
602 }
603
604 TreeNode[] path = getPathToRoot(node.getParent(), depth + 1);
605 path[path.length - depth - 1] = node;
606 return path;
607 }
608
609 /**
610 * getUserObjectPath
611 *
612 * @return Object[]
613 */
614 public Object[] getUserObjectPath()
615 {
616 TreeNode[] path = getPathToRoot(this, 0);
617 Object[] object = new Object[path.length];
618
619 for (int index = 0; index < path.length; ++index)
620 object[index] = ((DefaultMutableTreeNode) path[index]).getUserObject();
621
622 return object;
623 }
624
625 /**
626 * Returns the root node by iterating the parents of this node.
627 *
628 * @return the root node
629 */
630 public TreeNode getRoot()
631 {
632 TreeNode current = this;
633 TreeNode check = current.getParent();
634
635 while (check != null)
636 {
637 current = check;
638 check = current.getParent();
639 }
640
641 return current;
642 }
643
644 /**
645 * Tells whether this node is the root node or not.
646 *
647 * @return <code>true</code> if this is the root node,
648 * <code>false</code>otherwise
649 */
650 public boolean isRoot()
651 {
652 return parent == null;
653 }
654
655 /**
656 * getNextNode
657 *
658 * @return DefaultMutableTreeNode
659 */
660 public DefaultMutableTreeNode getNextNode()
661 {
662 // Return first child.
663 if (getChildCount() != 0)
664 return (DefaultMutableTreeNode) getChildAt(0);
665
666 // Return next sibling (if needed the sibling of some parent).
667 DefaultMutableTreeNode node = this;
668 DefaultMutableTreeNode sibling;
669
670 do
671 {
672 sibling = node.getNextSibling();
673 node = (DefaultMutableTreeNode) node.getParent();
674 }
675 while (sibling == null &&
676 node != null);
677
678 // Return sibling.
679 return sibling;
680 }
681
682 /**
683 * getPreviousNode
684 *
685 * @return DefaultMutableTreeNode
686 */
687 public DefaultMutableTreeNode getPreviousNode()
688 {
689 // Return null if no parent.
690 if (parent == null)
691 return null;
692
693 DefaultMutableTreeNode sibling = getPreviousSibling();
694
695 // Return parent if no sibling.
696 if (sibling == null)
697 return (DefaultMutableTreeNode) parent;
698
699 // Return last leaf of sibling.
700 if (sibling.getChildCount() != 0)
701 return sibling.getLastLeaf();
702
703 // Return sibling.
704 return sibling;
705 }
706
707 /**
708 * preorderEnumeration
709 *
710 * @return Enumeration
711 */
712 @SuppressWarnings("unchecked") // Required for API compatibility
713 public Enumeration preorderEnumeration()
714 {
715 return new PreorderEnumeration(this);
716 }
717
718 /**
719 * postorderEnumeration
720 *
721 * @return Enumeration
722 */
723 @SuppressWarnings("unchecked") // Required for API compatibility
724 public Enumeration postorderEnumeration()
725 {
726 return new PostorderEnumeration(this);
727 }
728
729 /**
730 * breadthFirstEnumeration
731 *
732 * @return Enumeration
733 */
734 @SuppressWarnings("unchecked") // Required for API compatibility
735 public Enumeration breadthFirstEnumeration()
736 {
737 return new BreadthFirstEnumeration(this);
738 }
739
740 /**
741 * depthFirstEnumeration
742 *
743 * @return Enumeration
744 */
745 @SuppressWarnings("unchecked") // Required for API compatibility
746 public Enumeration depthFirstEnumeration()
747 {
748 return postorderEnumeration();
749 }
750
751 /**
752 * pathFromAncestorEnumeration
753 *
754 * @param node TODO
755 *
756 * @return Enumeration
757 */
758 @SuppressWarnings("unchecked") // Required for API compatibility
759 public Enumeration pathFromAncestorEnumeration(TreeNode node)
760 {
761 if (node == null)
762 throw new IllegalArgumentException();
763
764 TreeNode parent = this;
765 Vector<TreeNode> nodes = new Vector<TreeNode>();
766 nodes.add(this);
767
768 while (parent != node && parent != null)
769 {
770 parent = parent.getParent();
771 nodes.add(0, parent);
772 }
773
774 if (parent != node)
775 throw new IllegalArgumentException();
776
777 return nodes.elements();
778 }
779
780 /**
781 * Returns <code>true</code> if <code>node</code> is a child of this tree
782 * node, and <code>false</code> otherwise. If <code>node</code> is
783 * <code>null</code>, this method returns <code>false</code>.
784 *
785 * @param node the node (<code>null</code> permitted).
786 *
787 * @return A boolean.
788 */
789 public boolean isNodeChild(TreeNode node)
790 {
791 if (node == null)
792 return false;
793
794 return node.getParent() == this;
795 }
796
797 /**
798 * Returns the first child node belonging to this tree node.
799 *
800 * @return The first child node.
801 *
802 * @throws NoSuchElementException if this tree node has no children.
803 */
804 public TreeNode getFirstChild()
805 {
806 return children.firstElement();
807 }
808
809 /**
810 * Returns the last child node belonging to this tree node.
811 *
812 * @return The last child node.
813 *
814 * @throws NoSuchElementException if this tree node has no children.
815 */
816 public TreeNode getLastChild()
817 {
818 return children.lastElement();
819 }
820
821 /**
822 * Returns the next child after the specified <code>node</code>, or
823 * <code>null</code> if there is no child after the specified
824 * <code>node</code>.
825 *
826 * @param node a child of this node (<code>null</code> not permitted).
827 *
828 * @return The next child, or <code>null</code>.
829 *
830 * @throws IllegalArgumentException if <code>node</code> is not a child of
831 * this node, or is <code>null</code>.
832 */
833 public TreeNode getChildAfter(TreeNode node)
834 {
835 if (node == null || node.getParent() != this)
836 throw new IllegalArgumentException();
837
838 int index = getIndex(node) + 1;
839
840 if (index == getChildCount())
841 return null;
842
843 return getChildAt(index);
844 }
845
846 /**
847 * Returns the previous child before the specified <code>node</code>, or
848 * <code>null</code> if there is no child before the specified
849 * <code>node</code>.
850 *
851 * @param node a child of this node (<code>null</code> not permitted).
852 *
853 * @return The previous child, or <code>null</code>.
854 *
855 * @throws IllegalArgumentException if <code>node</code> is not a child of
856 * this node, or is <code>null</code>.
857 */
858 public TreeNode getChildBefore(TreeNode node)
859 {
860 if (node == null || node.getParent() != this)
861 throw new IllegalArgumentException();
862
863 int index = getIndex(node) - 1;
864
865 if (index < 0)
866 return null;
867
868 return getChildAt(index);
869 }
870
871 /**
872 * Returns <code>true</code> if this tree node and <code>node</code> share
873 * the same parent. If <code>node</code> is this tree node, the method
874 * returns <code>true</code> and if <code>node</code> is <code>null</code>
875 * this method returns <code>false</code>.
876 *
877 * @param node the node (<code>null</code> permitted).
878 *
879 * @return A boolean.
880 */
881 public boolean isNodeSibling(TreeNode node)
882 {
883 if (node == null)
884 return false;
885 if (node == this)
886 return true;
887 return node.getParent() == getParent() && getParent() != null;
888 }
889
890 /**
891 * Returns the number of siblings for this tree node. If the tree node has
892 * a parent, this method returns the child count for the parent, otherwise
893 * it returns <code>1</code>.
894 *
895 * @return The sibling count.
896 */
897 public int getSiblingCount()
898 {
899 if (parent == null)
900 return 1;
901
902 return parent.getChildCount();
903 }
904
905 /**
906 * Returns the next sibling for this tree node. If this node has no parent,
907 * or this node is the last child of its parent, this method returns
908 * <code>null</code>.
909 *
910 * @return The next sibling, or <code>null</code>.
911 */
912 public DefaultMutableTreeNode getNextSibling()
913 {
914 if (parent == null)
915 return null;
916
917 int index = parent.getIndex(this) + 1;
918
919 if (index == parent.getChildCount())
920 return null;
921
922 return (DefaultMutableTreeNode) parent.getChildAt(index);
923 }
924
925 /**
926 * Returns the previous sibling for this tree node. If this node has no
927 * parent, or this node is the first child of its parent, this method returns
928 * <code>null</code>.
929 *
930 * @return The previous sibling, or <code>null</code>.
931 */
932 public DefaultMutableTreeNode getPreviousSibling()
933 {
934 if (parent == null)
935 return null;
936
937 int index = parent.getIndex(this) - 1;
938
939 if (index < 0)
940 return null;
941
942 return (DefaultMutableTreeNode) parent.getChildAt(index);
943 }
944
945 /**
946 * Returns <code>true</code> if this tree node is a lead node (that is, it
947 * has no children), and <code>false</otherwise>.
948 *
949 * @return A boolean.
950 */
951 public boolean isLeaf()
952 {
953 return children.size() == 0;
954 }
955
956 /**
957 * Returns the first leaf node that is a descendant of this node. Recall
958 * that a node is its own descendant, so if this node has no children then
959 * it is returned as the first leaf.
960 *
961 * @return The first leaf node.
962 */
963 public DefaultMutableTreeNode getFirstLeaf()
964 {
965 TreeNode current = this;
966
967 while (current.getChildCount() > 0)
968 current = current.getChildAt(0);
969
970 return (DefaultMutableTreeNode) current;
971 }
972
973 /**
974 * Returns the last leaf node that is a descendant of this node. Recall
975 * that a node is its own descendant, so if this node has no children then
976 * it is returned as the last leaf.
977 *
978 * @return The first leaf node.
979 */
980 public DefaultMutableTreeNode getLastLeaf()
981 {
982 TreeNode current = this;
983 int size = current.getChildCount();
984
985 while (size > 0)
986 {
987 current = current.getChildAt(size - 1);
988 size = current.getChildCount();
989 }
990
991 return (DefaultMutableTreeNode) current;
992 }
993
994 /**
995 * Returns the next leaf node after this tree node.
996 *
997 * @return The next leaf node, or <code>null</code>.
998 */
999 public DefaultMutableTreeNode getNextLeaf()
1000 {
1001 // if there is a next sibling, return its first leaf
1002 DefaultMutableTreeNode sibling = getNextSibling();
1003 if (sibling != null)
1004 return sibling.getFirstLeaf();
1005 // otherwise move up one level and try again...
1006 if (parent != null)
1007 return ((DefaultMutableTreeNode) parent).getNextLeaf();
1008 return null;
1009 }
1010
1011 /**
1012 * Returns the previous leaf node before this tree node.
1013 *
1014 * @return The previous leaf node, or <code>null</code>.
1015 */
1016 public DefaultMutableTreeNode getPreviousLeaf()
1017 {
1018 // if there is a previous sibling, return its last leaf
1019 DefaultMutableTreeNode sibling = getPreviousSibling();
1020 if (sibling != null)
1021 return sibling.getLastLeaf();
1022 // otherwise move up one level and try again...
1023 if (parent != null)
1024 return ((DefaultMutableTreeNode) parent).getPreviousLeaf();
1025 return null;
1026 }
1027
1028 /**
1029 * getLeafCount
1030 *
1031 * @return int
1032 */
1033 public int getLeafCount()
1034 {
1035 int count = 0;
1036 Enumeration<?> e = depthFirstEnumeration();
1037
1038 while (e.hasMoreElements())
1039 {
1040 TreeNode current = (TreeNode) e.nextElement();
1041
1042 if (current.isLeaf())
1043 count++;
1044 }
1045
1046 return count;
1047 }
1048
1049 /** Provides an enumeration of a tree in breadth-first traversal
1050 * order.
1051 */
1052 static class BreadthFirstEnumeration implements Enumeration<TreeNode>
1053 {
1054
1055 LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
1056
1057 BreadthFirstEnumeration(TreeNode node)
1058 {
1059 queue.add(node);
1060 }
1061
1062 public boolean hasMoreElements()
1063 {
1064 return !queue.isEmpty();
1065 }
1066
1067 @SuppressWarnings("unchecked")
1068 public TreeNode nextElement()
1069 {
1070 if (queue.isEmpty())
1071 throw new NoSuchElementException("No more elements left.");
1072
1073 TreeNode node = queue.removeFirst();
1074
1075 Enumeration<TreeNode> children =
1076 (Enumeration<TreeNode>) node.children();
1077 while (children.hasMoreElements())
1078 queue.add(children.nextElement());
1079
1080 return node;
1081 }
1082 }
1083
1084 /** Provides an enumeration of a tree traversing it
1085 * preordered.
1086 */
1087 static class PreorderEnumeration implements Enumeration<TreeNode>
1088 {
1089 TreeNode next;
1090
1091 Stack<Enumeration<TreeNode>> childrenEnums =
1092 new Stack<Enumeration<TreeNode>>();
1093
1094 @SuppressWarnings("unchecked")
1095 PreorderEnumeration(TreeNode node)
1096 {
1097 next = node;
1098 childrenEnums.push((Enumeration<TreeNode>) node.children());
1099 }
1100
1101 public boolean hasMoreElements()
1102 {
1103 return next != null;
1104 }
1105
1106 public TreeNode nextElement()
1107 {
1108 if (next == null)
1109 throw new NoSuchElementException("No more elements left.");
1110
1111 TreeNode current = next;
1112
1113 Enumeration<TreeNode> children = childrenEnums.peek();
1114
1115 // Retrieves the next element.
1116 next = traverse(children);
1117
1118 return current;
1119 }
1120
1121 @SuppressWarnings("unchecked")
1122 private TreeNode traverse(Enumeration<TreeNode> children)
1123 {
1124 // If more children are available step down.
1125 if (children.hasMoreElements())
1126 {
1127 TreeNode child = children.nextElement();
1128 childrenEnums.push((Enumeration<TreeNode>) child.children());
1129
1130 return child;
1131 }
1132
1133 // If no children are left, we return to a higher level.
1134 childrenEnums.pop();
1135
1136 // If there are no more levels left, there is no next
1137 // element to return.
1138 if (childrenEnums.isEmpty())
1139 return null;
1140 else
1141 {
1142 return traverse(childrenEnums.peek());
1143 }
1144 }
1145 }
1146
1147 /** Provides an enumeration of a tree traversing it
1148 * postordered (= depth-first).
1149 */
1150 static class PostorderEnumeration implements Enumeration<TreeNode>
1151 {
1152
1153 Stack<TreeNode> nodes = new Stack<TreeNode>();
1154 Stack<Enumeration<TreeNode>> childrenEnums =
1155 new Stack<Enumeration<TreeNode>>();
1156
1157 @SuppressWarnings("unchecked")
1158 PostorderEnumeration(TreeNode node)
1159 {
1160 nodes.push(node);
1161 childrenEnums.push((Enumeration<TreeNode>) node.children());
1162 }
1163
1164 public boolean hasMoreElements()
1165 {
1166 return !nodes.isEmpty();
1167 }
1168
1169 public TreeNode nextElement()
1170 {
1171 if (nodes.isEmpty())
1172 throw new NoSuchElementException("No more elements left!");
1173
1174 Enumeration<TreeNode> children = childrenEnums.peek();
1175
1176 return traverse(children);
1177 }
1178
1179 @SuppressWarnings("unchecked")
1180 private TreeNode traverse(Enumeration<TreeNode> children)
1181 {
1182 if (children.hasMoreElements())
1183 {
1184 TreeNode node = children.nextElement();
1185 nodes.push(node);
1186
1187 Enumeration<TreeNode> newChildren =
1188 (Enumeration<TreeNode>) node.children();
1189 childrenEnums.push(newChildren);
1190
1191 return traverse(newChildren);
1192 }
1193 else
1194 {
1195 childrenEnums.pop();
1196
1197 // Returns the node whose children
1198 // have all been visited. (= postorder)
1199 TreeNode next = nodes.peek();
1200 nodes.pop();
1201
1202 return next;
1203 }
1204 }
1205
1206 }
1207
1208 }