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 public Enumeration children()
288 {
289 if (children.size() == 0)
290 return EMPTY_ENUMERATION;
291
292 return children.elements();
293 }
294
295 /**
296 * Set the parent node for this node.
297 *
298 * @param node the parent node
299 */
300 public void setParent(MutableTreeNode node)
301 {
302 parent = node;
303 }
304
305 /**
306 * Returns the child node at a given index.
307 *
308 * @param index the index
309 *
310 * @return the child node
311 */
312 public TreeNode getChildAt(int index)
313 {
314 return (TreeNode) children.elementAt(index);
315 }
316
317 /**
318 * Returns the number of children of this node.
319 *
320 * @return the number of children
321 */
322 public int getChildCount()
323 {
324 return children.size();
325 }
326
327 /**
328 * Returns the index of the specified child node, or -1 if the node is not
329 * in fact a child of this node.
330 *
331 * @param node the node (<code>null</code> not permitted).
332 *
333 * @return The index of the specified child node, or -1.
334 *
335 * @throws IllegalArgumentException if <code>node</code> is <code>null</code>.
336 */
337 public int getIndex(TreeNode node)
338 {
339 if (node == null)
340 throw new IllegalArgumentException("Null 'node' argument.");
341 return children.indexOf(node);
342 }
343
344 /**
345 * Sets the flag that controls whether or not this node allows the addition /
346 * insertion of child nodes. If the flag is set to <code>false</code>, any
347 * existing children are removed.
348 *
349 * @param allowsChildren the flag.
350 */
351 public void setAllowsChildren(boolean allowsChildren)
352 {
353 if (!allowsChildren)
354 removeAllChildren();
355 this.allowsChildren = allowsChildren;
356 }
357
358 /**
359 * getAllowsChildren
360 *
361 * @return boolean
362 */
363 public boolean getAllowsChildren()
364 {
365 return allowsChildren;
366 }
367
368 /**
369 * Sets the user object for this node
370 *
371 * @param userObject the user object
372 */
373 public void setUserObject(Object userObject)
374 {
375 this.userObject = userObject;
376 }
377
378 /**
379 * Returns the user object attached to this node. <code>null</code> is
380 * returned when no user object is set.
381 *
382 * @return the user object
383 */
384 public Object getUserObject()
385 {
386 return userObject;
387 }
388
389 /**
390 * Removes this node from its parent.
391 */
392 public void removeFromParent()
393 {
394 parent.remove(this);
395 parent = null;
396 }
397
398 /**
399 * Removes all child nodes from this node.
400 */
401 public void removeAllChildren()
402 {
403 for (int i = getChildCount() - 1; i >= 0; i--)
404 remove(i);
405 }
406
407 /**
408 * Returns <code>true</code> if <code>node</code> is an ancestor of this
409 * tree node, and <code>false</code> otherwise. An ancestor node is any of:
410 * <ul>
411 * <li>this tree node;</li>
412 * <li>the parent node (if there is one);</li>
413 * <li>any ancestor of the parent node;</li>
414 * </ul>
415 * If <code>node</code> is <code>null</code>, this method returns
416 * <code>false</code>.
417 *
418 * @param node the node (<code>null</code> permitted).
419 *
420 * @return A boolean.
421 */
422 public boolean isNodeAncestor(TreeNode node)
423 {
424 if (node == null)
425 return false;
426
427 TreeNode current = this;
428
429 while (current != null && current != node)
430 current = current.getParent();
431
432 return current == node;
433 }
434
435 /**
436 * Returns <code>true</code> if <code>node</code> is a descendant of this
437 * tree node, and <code>false</code> otherwise. A descendant node is any of:
438 * <ul>
439 * <li>this tree node;</li>
440 * <li>the child nodes belonging to this tree node, if there are any;</li>
441 * <li>any descendants of the child nodes;</li>
442 * </ul>
443 * If <code>node</code> is <code>null</code>, this method returns
444 * <code>false</code>.
445 *
446 * @param node the node (<code>null</code> permitted).
447 *
448 * @return A boolean.
449 */
450 public boolean isNodeDescendant(DefaultMutableTreeNode node)
451 {
452 if (node == null)
453 return false;
454
455 TreeNode current = node;
456
457 while (current != null
458 && current != this)
459 current = current.getParent();
460
461 return current == this;
462 }
463
464 /**
465 * getSharedAncestor
466 *
467 * @param node TODO
468 *
469 * @return TreeNode
470 */
471 public TreeNode getSharedAncestor(DefaultMutableTreeNode node)
472 {
473 TreeNode current = this;
474 ArrayList<TreeNode> list = new ArrayList<TreeNode>();
475
476 while (current != null)
477 {
478 list.add(current);
479 current = current.getParent();
480 }
481
482 current = node;
483
484 while (current != null)
485 {
486 if (list.contains(current))
487 return current;
488
489 current = current.getParent();
490 }
491
492 return null;
493 }
494
495 /**
496 * isNodeRelated
497 *
498 * @param node TODO
499 *
500 * @return boolean
501 */
502 public boolean isNodeRelated(DefaultMutableTreeNode node)
503 {
504 if (node == null)
505 return false;
506
507 return node.getRoot() == getRoot();
508 }
509
510 /**
511 * getDepth
512 *
513 * @return int
514 */
515 public int getDepth()
516 {
517 if ((! allowsChildren)
518 || children.size() == 0)
519 return 0;
520
521 Stack<Integer> stack = new Stack<Integer>();
522 stack.push(new Integer(0));
523 TreeNode node = getChildAt(0);
524 int depth = 0;
525 int current = 1;
526
527 while (! stack.empty())
528 {
529 if (node.getChildCount() != 0)
530 {
531 node = node.getChildAt(0);
532 stack.push(new Integer(0));
533 current++;
534 }
535 else
536 {
537 if (current > depth)
538 depth = current;
539
540 int size;
541 int index;
542
543 do
544 {
545 node = node.getParent();
546 size = node.getChildCount();
547 index = stack.pop().intValue() + 1;
548 current--;
549 }
550 while (index >= size
551 && node != this);
552
553 if (index < size)
554 {
555 node = node.getChildAt(index);
556 stack.push(new Integer(index));
557 current++;
558 }
559 }
560 }
561
562 return depth;
563 }
564
565 /**
566 * getLevel
567 *
568 * @return int
569 */
570 public int getLevel()
571 {
572 int count = -1;
573 TreeNode current = this;
574
575 do
576 {
577 current = current.getParent();
578 count++;
579 }
580 while (current != null);
581
582 return count;
583 }
584
585 /**
586 * getPathToRoot
587 *
588 * @param node TODO
589 * @param depth TODO
590 *
591 * @return TreeNode[]
592 */
593 protected TreeNode[] getPathToRoot(TreeNode node, int depth)
594 {
595 if (node == null)
596 {
597 if (depth == 0)
598 return null;
599
600 return new TreeNode[depth];
601 }
602
603 TreeNode[] path = getPathToRoot(node.getParent(), depth + 1);
604 path[path.length - depth - 1] = node;
605 return path;
606 }
607
608 /**
609 * getUserObjectPath
610 *
611 * @return Object[]
612 */
613 public Object[] getUserObjectPath()
614 {
615 TreeNode[] path = getPathToRoot(this, 0);
616 Object[] object = new Object[path.length];
617
618 for (int index = 0; index < path.length; ++index)
619 object[index] = ((DefaultMutableTreeNode) path[index]).getUserObject();
620
621 return object;
622 }
623
624 /**
625 * Returns the root node by iterating the parents of this node.
626 *
627 * @return the root node
628 */
629 public TreeNode getRoot()
630 {
631 TreeNode current = this;
632 TreeNode check = current.getParent();
633
634 while (check != null)
635 {
636 current = check;
637 check = current.getParent();
638 }
639
640 return current;
641 }
642
643 /**
644 * Tells whether this node is the root node or not.
645 *
646 * @return <code>true</code> if this is the root node,
647 * <code>false</code>otherwise
648 */
649 public boolean isRoot()
650 {
651 return parent == null;
652 }
653
654 /**
655 * getNextNode
656 *
657 * @return DefaultMutableTreeNode
658 */
659 public DefaultMutableTreeNode getNextNode()
660 {
661 // Return first child.
662 if (getChildCount() != 0)
663 return (DefaultMutableTreeNode) getChildAt(0);
664
665 // Return next sibling (if needed the sibling of some parent).
666 DefaultMutableTreeNode node = this;
667 DefaultMutableTreeNode sibling;
668
669 do
670 {
671 sibling = node.getNextSibling();
672 node = (DefaultMutableTreeNode) node.getParent();
673 }
674 while (sibling == null &&
675 node != null);
676
677 // Return sibling.
678 return sibling;
679 }
680
681 /**
682 * getPreviousNode
683 *
684 * @return DefaultMutableTreeNode
685 */
686 public DefaultMutableTreeNode getPreviousNode()
687 {
688 // Return null if no parent.
689 if (parent == null)
690 return null;
691
692 DefaultMutableTreeNode sibling = getPreviousSibling();
693
694 // Return parent if no sibling.
695 if (sibling == null)
696 return (DefaultMutableTreeNode) parent;
697
698 // Return last leaf of sibling.
699 if (sibling.getChildCount() != 0)
700 return sibling.getLastLeaf();
701
702 // Return sibling.
703 return sibling;
704 }
705
706 /**
707 * preorderEnumeration
708 *
709 * @return Enumeration
710 */
711 public Enumeration preorderEnumeration()
712 {
713 return new PreorderEnumeration(this);
714 }
715
716 /**
717 * postorderEnumeration
718 *
719 * @return Enumeration
720 */
721 public Enumeration postorderEnumeration()
722 {
723 return new PostorderEnumeration(this);
724 }
725
726 /**
727 * breadthFirstEnumeration
728 *
729 * @return Enumeration
730 */
731 public Enumeration breadthFirstEnumeration()
732 {
733 return new BreadthFirstEnumeration(this);
734 }
735
736 /**
737 * depthFirstEnumeration
738 *
739 * @return Enumeration
740 */
741 public Enumeration depthFirstEnumeration()
742 {
743 return postorderEnumeration();
744 }
745
746 /**
747 * pathFromAncestorEnumeration
748 *
749 * @param node TODO
750 *
751 * @return Enumeration
752 */
753 public Enumeration pathFromAncestorEnumeration(TreeNode node)
754 {
755 if (node == null)
756 throw new IllegalArgumentException();
757
758 TreeNode parent = this;
759 Vector<TreeNode> nodes = new Vector<TreeNode>();
760 nodes.add(this);
761
762 while (parent != node && parent != null)
763 {
764 parent = parent.getParent();
765 nodes.add(0, parent);
766 }
767
768 if (parent != node)
769 throw new IllegalArgumentException();
770
771 return nodes.elements();
772 }
773
774 /**
775 * Returns <code>true</code> if <code>node</code> is a child of this tree
776 * node, and <code>false</code> otherwise. If <code>node</code> is
777 * <code>null</code>, this method returns <code>false</code>.
778 *
779 * @param node the node (<code>null</code> permitted).
780 *
781 * @return A boolean.
782 */
783 public boolean isNodeChild(TreeNode node)
784 {
785 if (node == null)
786 return false;
787
788 return node.getParent() == this;
789 }
790
791 /**
792 * Returns the first child node belonging to this tree node.
793 *
794 * @return The first child node.
795 *
796 * @throws NoSuchElementException if this tree node has no children.
797 */
798 public TreeNode getFirstChild()
799 {
800 return (TreeNode) children.firstElement();
801 }
802
803 /**
804 * Returns the last child node belonging to this tree node.
805 *
806 * @return The last child node.
807 *
808 * @throws NoSuchElementException if this tree node has no children.
809 */
810 public TreeNode getLastChild()
811 {
812 return (TreeNode) children.lastElement();
813 }
814
815 /**
816 * Returns the next child after the specified <code>node</code>, or
817 * <code>null</code> if there is no child after the specified
818 * <code>node</code>.
819 *
820 * @param node a child of this node (<code>null</code> not permitted).
821 *
822 * @return The next child, or <code>null</code>.
823 *
824 * @throws IllegalArgumentException if <code>node</code> is not a child of
825 * this node, or is <code>null</code>.
826 */
827 public TreeNode getChildAfter(TreeNode node)
828 {
829 if (node == null || node.getParent() != this)
830 throw new IllegalArgumentException();
831
832 int index = getIndex(node) + 1;
833
834 if (index == getChildCount())
835 return null;
836
837 return getChildAt(index);
838 }
839
840 /**
841 * Returns the previous child before the specified <code>node</code>, or
842 * <code>null</code> if there is no child before the specified
843 * <code>node</code>.
844 *
845 * @param node a child of this node (<code>null</code> not permitted).
846 *
847 * @return The previous child, or <code>null</code>.
848 *
849 * @throws IllegalArgumentException if <code>node</code> is not a child of
850 * this node, or is <code>null</code>.
851 */
852 public TreeNode getChildBefore(TreeNode node)
853 {
854 if (node == null || node.getParent() != this)
855 throw new IllegalArgumentException();
856
857 int index = getIndex(node) - 1;
858
859 if (index < 0)
860 return null;
861
862 return getChildAt(index);
863 }
864
865 /**
866 * Returns <code>true</code> if this tree node and <code>node</code> share
867 * the same parent. If <code>node</code> is this tree node, the method
868 * returns <code>true</code> and if <code>node</code> is <code>null</code>
869 * this method returns <code>false</code>.
870 *
871 * @param node the node (<code>null</code> permitted).
872 *
873 * @return A boolean.
874 */
875 public boolean isNodeSibling(TreeNode node)
876 {
877 if (node == null)
878 return false;
879 if (node == this)
880 return true;
881 return node.getParent() == getParent() && getParent() != null;
882 }
883
884 /**
885 * Returns the number of siblings for this tree node. If the tree node has
886 * a parent, this method returns the child count for the parent, otherwise
887 * it returns <code>1</code>.
888 *
889 * @return The sibling count.
890 */
891 public int getSiblingCount()
892 {
893 if (parent == null)
894 return 1;
895
896 return parent.getChildCount();
897 }
898
899 /**
900 * Returns the next sibling for this tree node. If this node has no parent,
901 * or this node is the last child of its parent, this method returns
902 * <code>null</code>.
903 *
904 * @return The next sibling, or <code>null</code>.
905 */
906 public DefaultMutableTreeNode getNextSibling()
907 {
908 if (parent == null)
909 return null;
910
911 int index = parent.getIndex(this) + 1;
912
913 if (index == parent.getChildCount())
914 return null;
915
916 return (DefaultMutableTreeNode) parent.getChildAt(index);
917 }
918
919 /**
920 * Returns the previous sibling for this tree node. If this node has no
921 * parent, or this node is the first child of its parent, this method returns
922 * <code>null</code>.
923 *
924 * @return The previous sibling, or <code>null</code>.
925 */
926 public DefaultMutableTreeNode getPreviousSibling()
927 {
928 if (parent == null)
929 return null;
930
931 int index = parent.getIndex(this) - 1;
932
933 if (index < 0)
934 return null;
935
936 return (DefaultMutableTreeNode) parent.getChildAt(index);
937 }
938
939 /**
940 * Returns <code>true</code> if this tree node is a lead node (that is, it
941 * has no children), and <code>false</otherwise>.
942 *
943 * @return A boolean.
944 */
945 public boolean isLeaf()
946 {
947 return children.size() == 0;
948 }
949
950 /**
951 * Returns the first leaf node that is a descendant of this node. Recall
952 * that a node is its own descendant, so if this node has no children then
953 * it is returned as the first leaf.
954 *
955 * @return The first leaf node.
956 */
957 public DefaultMutableTreeNode getFirstLeaf()
958 {
959 TreeNode current = this;
960
961 while (current.getChildCount() > 0)
962 current = current.getChildAt(0);
963
964 return (DefaultMutableTreeNode) current;
965 }
966
967 /**
968 * Returns the last leaf node that is a descendant of this node. Recall
969 * that a node is its own descendant, so if this node has no children then
970 * it is returned as the last leaf.
971 *
972 * @return The first leaf node.
973 */
974 public DefaultMutableTreeNode getLastLeaf()
975 {
976 TreeNode current = this;
977 int size = current.getChildCount();
978
979 while (size > 0)
980 {
981 current = current.getChildAt(size - 1);
982 size = current.getChildCount();
983 }
984
985 return (DefaultMutableTreeNode) current;
986 }
987
988 /**
989 * Returns the next leaf node after this tree node.
990 *
991 * @return The next leaf node, or <code>null</code>.
992 */
993 public DefaultMutableTreeNode getNextLeaf()
994 {
995 // if there is a next sibling, return its first leaf
996 DefaultMutableTreeNode sibling = getNextSibling();
997 if (sibling != null)
998 return sibling.getFirstLeaf();
999 // otherwise move up one level and try again...
1000 if (parent != null)
1001 return ((DefaultMutableTreeNode) parent).getNextLeaf();
1002 return null;
1003 }
1004
1005 /**
1006 * Returns the previous leaf node before this tree node.
1007 *
1008 * @return The previous leaf node, or <code>null</code>.
1009 */
1010 public DefaultMutableTreeNode getPreviousLeaf()
1011 {
1012 // if there is a previous sibling, return its last leaf
1013 DefaultMutableTreeNode sibling = getPreviousSibling();
1014 if (sibling != null)
1015 return sibling.getLastLeaf();
1016 // otherwise move up one level and try again...
1017 if (parent != null)
1018 return ((DefaultMutableTreeNode) parent).getPreviousLeaf();
1019 return null;
1020 }
1021
1022 /**
1023 * getLeafCount
1024 *
1025 * @return int
1026 */
1027 public int getLeafCount()
1028 {
1029 int count = 0;
1030 Enumeration e = depthFirstEnumeration();
1031
1032 while (e.hasMoreElements())
1033 {
1034 TreeNode current = (TreeNode) e.nextElement();
1035
1036 if (current.isLeaf())
1037 count++;
1038 }
1039
1040 return count;
1041 }
1042
1043 /** Provides an enumeration of a tree in breadth-first traversal
1044 * order.
1045 */
1046 static class BreadthFirstEnumeration implements Enumeration<TreeNode>
1047 {
1048
1049 LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
1050
1051 BreadthFirstEnumeration(TreeNode node)
1052 {
1053 queue.add(node);
1054 }
1055
1056 public boolean hasMoreElements()
1057 {
1058 return !queue.isEmpty();
1059 }
1060
1061 @SuppressWarnings("unchecked")
1062 public TreeNode nextElement()
1063 {
1064 if (queue.isEmpty())
1065 throw new NoSuchElementException("No more elements left.");
1066
1067 TreeNode node = queue.removeFirst();
1068
1069 Enumeration<TreeNode> children =
1070 (Enumeration<TreeNode>) node.children();
1071 while (children.hasMoreElements())
1072 queue.add(children.nextElement());
1073
1074 return node;
1075 }
1076 }
1077
1078 /** Provides an enumeration of a tree traversing it
1079 * preordered.
1080 */
1081 static class PreorderEnumeration implements Enumeration<TreeNode>
1082 {
1083 TreeNode next;
1084
1085 Stack<Enumeration<TreeNode>> childrenEnums =
1086 new Stack<Enumeration<TreeNode>>();
1087
1088 @SuppressWarnings("unchecked")
1089 PreorderEnumeration(TreeNode node)
1090 {
1091 next = node;
1092 childrenEnums.push((Enumeration<TreeNode>) node.children());
1093 }
1094
1095 public boolean hasMoreElements()
1096 {
1097 return next != null;
1098 }
1099
1100 public TreeNode nextElement()
1101 {
1102 if (next == null)
1103 throw new NoSuchElementException("No more elements left.");
1104
1105 TreeNode current = next;
1106
1107 Enumeration<TreeNode> children = childrenEnums.peek();
1108
1109 // Retrieves the next element.
1110 next = traverse(children);
1111
1112 return current;
1113 }
1114
1115 @SuppressWarnings("unchecked")
1116 private TreeNode traverse(Enumeration<TreeNode> children)
1117 {
1118 // If more children are available step down.
1119 if (children.hasMoreElements())
1120 {
1121 TreeNode child = children.nextElement();
1122 childrenEnums.push((Enumeration<TreeNode>) child.children());
1123
1124 return child;
1125 }
1126
1127 // If no children are left, we return to a higher level.
1128 childrenEnums.pop();
1129
1130 // If there are no more levels left, there is no next
1131 // element to return.
1132 if (childrenEnums.isEmpty())
1133 return null;
1134 else
1135 {
1136 return traverse(childrenEnums.peek());
1137 }
1138 }
1139 }
1140
1141 /** Provides an enumeration of a tree traversing it
1142 * postordered (= depth-first).
1143 */
1144 static class PostorderEnumeration implements Enumeration<TreeNode>
1145 {
1146
1147 Stack<TreeNode> nodes = new Stack<TreeNode>();
1148 Stack<Enumeration<TreeNode>> childrenEnums =
1149 new Stack<Enumeration<TreeNode>>();
1150
1151 @SuppressWarnings("unchecked")
1152 PostorderEnumeration(TreeNode node)
1153 {
1154 nodes.push(node);
1155 childrenEnums.push((Enumeration<TreeNode>) node.children());
1156 }
1157
1158 public boolean hasMoreElements()
1159 {
1160 return !nodes.isEmpty();
1161 }
1162
1163 public TreeNode nextElement()
1164 {
1165 if (nodes.isEmpty())
1166 throw new NoSuchElementException("No more elements left!");
1167
1168 Enumeration<TreeNode> children = childrenEnums.peek();
1169
1170 return traverse(children);
1171 }
1172
1173 @SuppressWarnings("unchecked")
1174 private TreeNode traverse(Enumeration<TreeNode> children)
1175 {
1176 if (children.hasMoreElements())
1177 {
1178 TreeNode node = children.nextElement();
1179 nodes.push(node);
1180
1181 Enumeration<TreeNode> newChildren =
1182 (Enumeration<TreeNode>) node.children();
1183 childrenEnums.push(newChildren);
1184
1185 return traverse(newChildren);
1186 }
1187 else
1188 {
1189 childrenEnums.pop();
1190
1191 // Returns the node whose children
1192 // have all been visited. (= postorder)
1193 TreeNode next = nodes.peek();
1194 nodes.pop();
1195
1196 return next;
1197 }
1198 }
1199
1200 }
1201
1202 }