001/* DefaultMutableTreeNode.java --
002   Copyright (C) 2002, 2004, 2005, 2006,  Free Software Foundation, Inc.
003
004This file is part of GNU Classpath.
005
006GNU Classpath is free software; you can redistribute it and/or modify
007it under the terms of the GNU General Public License as published by
008the Free Software Foundation; either version 2, or (at your option)
009any later version.
010
011GNU Classpath is distributed in the hope that it will be useful, but
012WITHOUT ANY WARRANTY; without even the implied warranty of
013MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014General Public License for more details.
015
016You should have received a copy of the GNU General Public License
017along with GNU Classpath; see the file COPYING.  If not, write to the
018Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
01902110-1301 USA.
020
021Linking this library statically or dynamically with other modules is
022making a combined work based on this library.  Thus, the terms and
023conditions of the GNU General Public License cover the whole
024combination.
025
026As a special exception, the copyright holders of this library give you
027permission to link this library with independent modules to produce an
028executable, regardless of the license terms of these independent
029modules, and to copy and distribute the resulting executable under
030terms of your choice, provided that you also meet, for each linked
031independent module, the terms and conditions of the license of that
032module.  An independent module is a module which is not derived from
033or based on this library.  If you modify this library, you may extend
034this exception to your version of the library, but you are not
035obligated to do so.  If you do not wish to do so, delete this
036exception statement from your version. */
037
038
039package javax.swing.tree;
040
041import java.io.IOException;
042import java.io.ObjectInputStream;
043import java.io.ObjectOutputStream;
044import java.io.Serializable;
045import java.util.ArrayList;
046import java.util.Enumeration;
047import java.util.LinkedList;
048import java.util.NoSuchElementException;
049import java.util.Stack;
050import 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 */
059public 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}