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    }