Source for javax.swing.tree.DefaultMutableTreeNode

   1: /* DefaultMutableTreeNode.java --
   2:    Copyright (C) 2002, 2004, 2005  Free Software Foundation, Inc.
   3: 
   4: This file is part of GNU Classpath.
   5: 
   6: GNU Classpath is free software; you can redistribute it and/or modify
   7: it under the terms of the GNU General Public License as published by
   8: the Free Software Foundation; either version 2, or (at your option)
   9: any later version.
  10: 
  11: GNU Classpath is distributed in the hope that it will be useful, but
  12: WITHOUT ANY WARRANTY; without even the implied warranty of
  13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14: General Public License for more details.
  15: 
  16: You should have received a copy of the GNU General Public License
  17: along with GNU Classpath; see the file COPYING.  If not, write to the
  18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  19: 02110-1301 USA.
  20: 
  21: Linking this library statically or dynamically with other modules is
  22: making a combined work based on this library.  Thus, the terms and
  23: conditions of the GNU General Public License cover the whole
  24: combination.
  25: 
  26: As a special exception, the copyright holders of this library give you
  27: permission to link this library with independent modules to produce an
  28: executable, regardless of the license terms of these independent
  29: modules, and to copy and distribute the resulting executable under
  30: terms of your choice, provided that you also meet, for each linked
  31: independent module, the terms and conditions of the license of that
  32: module.  An independent module is a module which is not derived from
  33: or based on this library.  If you modify this library, you may extend
  34: this exception to your version of the library, but you are not
  35: obligated to do so.  If you do not wish to do so, delete this
  36: exception statement from your version. */
  37: 
  38: 
  39: package javax.swing.tree;
  40: 
  41: import gnu.java.util.EmptyEnumeration;
  42: 
  43: import java.io.IOException;
  44: import java.io.ObjectInputStream;
  45: import java.io.ObjectOutputStream;
  46: import java.io.Serializable;
  47: import java.util.ArrayList;
  48: import java.util.Collections;
  49: import java.util.Enumeration;
  50: import java.util.LinkedList;
  51: import java.util.NoSuchElementException;
  52: import java.util.Stack;
  53: import java.util.Vector;
  54: 
  55: 
  56: /**
  57:  * DefaultMutableTreeNode
  58:  *
  59:  * @author Andrew Selkirk
  60:  * @author Robert Schuster (robertschuster@fsfe.org)
  61:  */
  62: public class DefaultMutableTreeNode
  63:   implements Cloneable, MutableTreeNode, Serializable
  64: {
  65:   private static final long serialVersionUID = -4298474751201349152L;
  66: 
  67:   /**
  68:    * EMPTY_ENUMERATION
  69:    */
  70:   public static final Enumeration EMPTY_ENUMERATION =
  71:     EmptyEnumeration.getInstance();
  72: 
  73:   /**
  74:    * parent
  75:    */
  76:   protected MutableTreeNode parent;
  77: 
  78:   /**
  79:    * children
  80:    */
  81:   protected Vector children = new Vector();
  82: 
  83:   /**
  84:    * userObject
  85:    */
  86:   protected transient Object userObject;
  87: 
  88:   /**
  89:    * allowsChildren
  90:    */
  91:   protected boolean allowsChildren;
  92: 
  93:   /**
  94:    * Creates a <code>DefaultMutableTreeNode</code> object.
  95:    * This node allows to add child nodes.
  96:    */
  97:   public DefaultMutableTreeNode()
  98:   {
  99:     this(null, true);
 100:   }
 101: 
 102:   /**
 103:    * Creates a <code>DefaultMutableTreeNode</code> object with the given
 104:    * user object attached to it. This node allows to add child nodes.
 105:    *
 106:    * @param userObject the user object
 107:    */
 108:   public DefaultMutableTreeNode(Object userObject)
 109:   {
 110:     this(userObject, true);
 111:   }
 112: 
 113:   /**
 114:    * Creates a <code>DefaultMutableTreeNode</code> object with the given
 115:    * user object attached to it.
 116:    *
 117:    * @param userObject the user object
 118:    * @param allowsChildren <code>true</code> if the code allows to add child
 119:    * nodes, <code>false</code> otherwise
 120:    */
 121:   public DefaultMutableTreeNode(Object userObject, boolean allowsChildren)
 122:   {
 123:     this.userObject = userObject;
 124:     this.allowsChildren = allowsChildren;
 125:   }
 126: 
 127:   /**
 128:    * clone
 129:    *
 130:    * @return Object
 131:    */
 132:   public Object clone()
 133:   {
 134:     try
 135:       {
 136:         return super.clone();
 137:         // TODO: Do we need to do more here ?
 138:       }
 139:     catch (CloneNotSupportedException e)
 140:       {
 141:         // This never happens.
 142:         return null;
 143:       }
 144:   }
 145: 
 146:   /**
 147:    * Returns a string representation of this node
 148:    *
 149:    * @return a human-readable String representing this node
 150:    */
 151:   public String toString()
 152:   {
 153:     if (userObject == null)
 154:       return null;
 155: 
 156:     return userObject.toString();
 157:   }
 158: 
 159:   /**
 160:    * Adds a new child node to this node.
 161:    *
 162:    * @param child the child node
 163:    *
 164:    * @throws IllegalArgumentException if <code>child</code> is null
 165:    * @throws IllegalStateException if the node does not allow children
 166:    */
 167:   public void add(MutableTreeNode child)
 168:   {
 169:     if (child == null)
 170:       throw new IllegalArgumentException();
 171: 
 172:     if (! allowsChildren)
 173:       throw new IllegalStateException();
 174:     
 175:     children.add(child);
 176:     child.setParent(this);
 177:   }
 178: 
 179:   /**
 180:    * Returns the parent node of this node.
 181:    *
 182:    * @return the parent node
 183:    */
 184:   public TreeNode getParent()
 185:   {
 186:     return parent;
 187:   }
 188: 
 189:   /**
 190:    * Removes the child with the given index from this node
 191:    *
 192:    * @param index the index
 193:    */
 194:   public void remove(int index)
 195:   {
 196:     children.remove(index);
 197:   }
 198: 
 199:   /**
 200:    * Removes the given child from this node.
 201:    *
 202:    * @param node the child node
 203:    */
 204:   public void remove(MutableTreeNode node)
 205:   {
 206:     children.remove(node);
 207:   }
 208: 
 209:   /**
 210:    * writeObject
 211:    *
 212:    * @param stream the output stream
 213:    *
 214:    * @exception IOException If an error occurs
 215:    */
 216:   private void writeObject(ObjectOutputStream stream)
 217:     throws IOException
 218:   {
 219:     // TODO: Implement me.
 220:   }
 221: 
 222:   /**
 223:    * readObject
 224:    *
 225:    * @param stream the input stream
 226:    *
 227:    * @exception IOException If an error occurs
 228:    * @exception ClassNotFoundException TODO
 229:    */
 230:   private void readObject(ObjectInputStream stream)
 231:     throws IOException, ClassNotFoundException
 232:   {
 233:     // TODO: Implement me.
 234:   }
 235: 
 236:   /**
 237:    * Inserts given child node at the given index.
 238:    *
 239:    * @param node the child node
 240:    * @param index the index.
 241:    */
 242:   public void insert(MutableTreeNode node, int index)
 243:   {
 244:     children.insertElementAt(node, index);
 245:   }
 246: 
 247:   /**
 248:    * Returns a path to this node from the root.
 249:    *
 250:    * @return an array of tree nodes
 251:    */
 252:   public TreeNode[] getPath()
 253:   {
 254:     return getPathToRoot(this, 0);
 255:   }
 256: 
 257:   /**
 258:    * Returns an enumeration containing all children of this node.
 259:    * <code>EMPTY_ENUMERATION</code> is returned if this node has no children.
 260:    *
 261:    * @return an enumeration of tree nodes
 262:    */
 263:   public Enumeration children()
 264:   {
 265:     if (children.size() == 0)
 266:       return EMPTY_ENUMERATION;
 267:     
 268:     return children.elements();
 269:   }
 270: 
 271:   /**
 272:    * Set the parent node for this node.
 273:    *
 274:    * @param node the parent node
 275:    */
 276:   public void setParent(MutableTreeNode node)
 277:   {
 278:     parent = node;
 279:   }
 280: 
 281:   /**
 282:    * Returns the child node at a given index.
 283:    *
 284:    * @param index the index
 285:    *
 286:    * @return the child node
 287:    */
 288:   public TreeNode getChildAt(int index)
 289:   {
 290:     return (TreeNode) children.elementAt(index);
 291:   }
 292: 
 293:   /**
 294:    * Returns the number of children of this node.
 295:    *
 296:    * @return the number of children
 297:    */
 298:   public int getChildCount()
 299:   {
 300:     return children.size();
 301:   }
 302: 
 303:   /**
 304:    * Returns the child index for a given node.
 305:    *
 306:    * @param node this node
 307:    *
 308:    * @return the index
 309:    */
 310:   public int getIndex(TreeNode node)
 311:   {
 312:     return children.indexOf(node);
 313:   }
 314: 
 315:   /**
 316:    * setAllowsChildren
 317:    *
 318:    * @param allowsChildren TODO
 319:    */
 320:   public void setAllowsChildren(boolean allowsChildren)
 321:   {
 322:     this.allowsChildren = allowsChildren;
 323:   }
 324: 
 325:   /**
 326:    * getAllowsChildren
 327:    *
 328:    * @return boolean
 329:    */
 330:   public boolean getAllowsChildren()
 331:   {
 332:     return allowsChildren;
 333:   }
 334: 
 335:   /**
 336:    * Sets the user object for this node
 337:    *
 338:    * @param userObject the user object
 339:    */
 340:   public void setUserObject(Object userObject)
 341:   {
 342:     this.userObject = userObject;
 343:   }
 344: 
 345:   /**
 346:    * Returns the user object attached to this node. <code>null</code> is
 347:    * returned when no user object is set.
 348:    *
 349:    * @return the user object
 350:    */
 351:   public Object getUserObject()
 352:   {
 353:     return userObject;
 354:   }
 355: 
 356:   /**
 357:    * Removes this node from its parent.
 358:    */
 359:   public void removeFromParent()
 360:   {
 361:     parent.remove(this);
 362:     parent = null;
 363:   }
 364: 
 365:   /**
 366:    * Removes all child nodes from this node.
 367:    */
 368:   public void removeAllChildren()
 369:   {
 370:     children.removeAllElements();
 371:   }
 372: 
 373:   /**
 374:    * isNodeAncestor
 375:    *
 376:    * @param node TODO
 377:    *
 378:    * @return boolean
 379:    */
 380:   public boolean isNodeAncestor(TreeNode node)
 381:   {
 382:     if (node == null)
 383:       return false;
 384: 
 385:     TreeNode current = this;
 386: 
 387:     while (current != null
 388:            && current != node)
 389:       current = current.getParent();
 390: 
 391:     return current == node;
 392:   }
 393: 
 394:   /**
 395:    * isNodeDescendant
 396:    *
 397:    * @param node TODO
 398:    *
 399:    * @return boolean
 400:    */
 401:   public boolean isNodeDescendant(DefaultMutableTreeNode node)
 402:   {
 403:     if (node == null)
 404:       return false;
 405: 
 406:     TreeNode current = node;
 407:     
 408:     while (current != null
 409:            && current != this)
 410:       current = current.getParent();
 411: 
 412:     return current == this;
 413:   }
 414: 
 415:   /**
 416:    * getSharedAncestor
 417:    *
 418:    * @param node TODO
 419:    *
 420:    * @return TreeNode
 421:    */
 422:   public TreeNode getSharedAncestor(DefaultMutableTreeNode node)
 423:   {
 424:     TreeNode current = this;
 425:     ArrayList list = new ArrayList();
 426: 
 427:     while (current != null)
 428:       {
 429:         list.add(current);
 430:         current = current.getParent();
 431:       }
 432: 
 433:     current = node;
 434: 
 435:     while (current != null)
 436:       {
 437:         if (list.contains(current))
 438:           return current;
 439: 
 440:         current = current.getParent();
 441:       }
 442: 
 443:     return null;
 444:   }
 445: 
 446:   /**
 447:    * isNodeRelated
 448:    *
 449:    * @param node TODO
 450:    *
 451:    * @return boolean
 452:    */
 453:   public boolean isNodeRelated(DefaultMutableTreeNode node)
 454:   {
 455:     if (node == null)
 456:       return false;
 457: 
 458:     return node.getRoot() == getRoot();
 459:   }
 460: 
 461:   /**
 462:    * getDepth
 463:    *
 464:    * @return int
 465:    */
 466:   public int getDepth()
 467:   {
 468:     if ((! allowsChildren)
 469:         || children.size() == 0)
 470:       return 0;
 471: 
 472:     Stack stack = new Stack();
 473:     stack.push(new Integer(0));
 474:     TreeNode node = getChildAt(0);
 475:     int depth = 0;
 476:     int current = 1;
 477:     
 478:     while (! stack.empty())
 479:       {
 480:         if (node.getChildCount() != 0)
 481:           {
 482:             node = node.getChildAt(0);
 483:             stack.push(new Integer(0));
 484:             current++;
 485:           }
 486:         else
 487:           {
 488:             if (current > depth)
 489:               depth = current;
 490: 
 491:             int size;
 492:             int index;
 493:             
 494:             do
 495:               {
 496:                 node = node.getParent();
 497:                 size = node.getChildCount();
 498:                 index = ((Integer) stack.pop()).intValue() + 1;
 499:                 current--;
 500:               }
 501:             while (index >= size
 502:                    && node != this);
 503: 
 504:             if (index < size)
 505:               {
 506:                 node = node.getChildAt(index);
 507:                 stack.push(new Integer(index));
 508:                 current++;
 509:               }
 510:           }
 511:       }
 512: 
 513:     return depth;
 514:   }
 515: 
 516:   /**
 517:    * getLevel
 518:    *
 519:    * @return int
 520:    */
 521:   public int getLevel()
 522:   {
 523:     int count = -1;
 524:     TreeNode current = this;
 525: 
 526:     do
 527:       {
 528:         current = current.getParent();
 529:         count++;
 530:       }
 531:     while (current != null);
 532: 
 533:     return count;
 534:   }
 535: 
 536:   /**
 537:    * getPathToRoot
 538:    *
 539:    * @param node TODO
 540:    * @param depth TODO
 541:    *
 542:    * @return TreeNode[]
 543:    */
 544:   protected TreeNode[] getPathToRoot(TreeNode node, int depth)
 545:   {
 546:     if (node == null)
 547:       {
 548:         if (depth == 0)
 549:           return null;
 550:         
 551:         return new TreeNode[depth];
 552:       }
 553: 
 554:     TreeNode[] path = getPathToRoot(node.getParent(), depth + 1);
 555:     path[path.length - depth - 1] = node;
 556:     return path;
 557:   }
 558: 
 559:   /**
 560:    * getUserObjectPath
 561:    *
 562:    * @return Object[]
 563:    */
 564:   public Object[] getUserObjectPath()
 565:   {
 566:     TreeNode[] path = getPathToRoot(this, 0);
 567:     Object[] object = new Object[path.length];
 568:     
 569:     for (int index = 0; index < path.length; ++index)
 570:       object[index] = ((DefaultMutableTreeNode) path[index]).getUserObject();
 571: 
 572:     return object;
 573:   }
 574: 
 575:   /**
 576:    * Returns the root node by iterating the parents of this node.
 577:    *
 578:    * @return the root node
 579:    */
 580:   public TreeNode getRoot()
 581:   {
 582:     TreeNode current = this;
 583:     TreeNode check = current.getParent();
 584:     
 585:     while (check != null)
 586:       {
 587:         current = check;
 588:         check = current.getParent();
 589:       }
 590: 
 591:     return current;
 592:   }
 593: 
 594:   /**
 595:    * Tells whether this node is the root node or not.
 596:    *
 597:    * @return <code>true</code> if this is the root node,
 598:    * <code>false</code>otherwise
 599:    */
 600:   public boolean isRoot()
 601:   {
 602:     return parent == null;
 603:   }
 604: 
 605:   /**
 606:    * getNextNode
 607:    *
 608:    * @return DefaultMutableTreeNode
 609:    */
 610:   public DefaultMutableTreeNode getNextNode()
 611:   {
 612:     // Return first child.
 613:     if (getChildCount() != 0)
 614:       return (DefaultMutableTreeNode) getChildAt(0);
 615: 
 616:     // Return next sibling (if needed the sibling of some parent).
 617:     DefaultMutableTreeNode node = this;
 618:     DefaultMutableTreeNode sibling;
 619:     
 620:     do
 621:       {
 622:         sibling = node.getNextSibling();
 623:         node = (DefaultMutableTreeNode) node.getParent();
 624:       }
 625:     while (sibling == null &&
 626:            node != null);
 627:     
 628:     // Return sibling.
 629:     return sibling;
 630:   }
 631: 
 632:   /**
 633:    * getPreviousNode
 634:    *
 635:    * @return DefaultMutableTreeNode
 636:    */
 637:   public DefaultMutableTreeNode getPreviousNode()
 638:   {
 639:     // Return null if no parent.
 640:     if (parent == null)
 641:       return null;
 642:     
 643:     DefaultMutableTreeNode sibling = getPreviousSibling();
 644: 
 645:     // Return parent if no sibling.
 646:     if (sibling == null)
 647:       return (DefaultMutableTreeNode) parent;
 648: 
 649:     // Return last leaf of sibling.
 650:     if (sibling.getChildCount() != 0)
 651:       return sibling.getLastLeaf();
 652: 
 653:     // Return sibling.
 654:     return sibling;
 655:   }
 656: 
 657:   /**
 658:    * preorderEnumeration
 659:    *
 660:    * @return Enumeration
 661:    */
 662:   public Enumeration preorderEnumeration()
 663:   {
 664:     return new PreorderEnumeration(this);
 665:   }
 666: 
 667:   /**
 668:    * postorderEnumeration
 669:    *
 670:    * @return Enumeration
 671:    */
 672:   public Enumeration postorderEnumeration()
 673:   {
 674:     return new PostorderEnumeration(this);
 675:   }
 676: 
 677:   /**
 678:    * breadthFirstEnumeration
 679:    *
 680:    * @return Enumeration
 681:    */
 682:   public Enumeration breadthFirstEnumeration()
 683:   {
 684:     return new BreadthFirstEnumeration(this);
 685:   }
 686: 
 687:   /**
 688:    * depthFirstEnumeration
 689:    *
 690:    * @return Enumeration
 691:    */
 692:   public Enumeration depthFirstEnumeration()
 693:   {
 694:     return postorderEnumeration();
 695:   }
 696: 
 697:   /**
 698:    * pathFromAncestorEnumeration
 699:    *
 700:    * @param node TODO
 701:    *
 702:    * @return Enumeration
 703:    */
 704:   public Enumeration pathFromAncestorEnumeration(TreeNode node)
 705:   {
 706:     if (node == null)
 707:       throw new IllegalArgumentException();
 708:     
 709:     TreeNode parent = this;
 710:     Vector nodes = new Vector();
 711:     nodes.add(this);
 712: 
 713:     while (parent != node && parent != null)
 714:       {
 715:         parent = parent.getParent();
 716:         nodes.add(0, parent);
 717:       }
 718: 
 719:     if (parent != node)
 720:       throw new IllegalArgumentException();
 721:     
 722:     return nodes.elements();
 723:   }
 724: 
 725:   /**
 726:    * isNodeChild
 727:    *
 728:    * @param node TODO
 729:    *
 730:    * @return boolean
 731:    */
 732:   public boolean isNodeChild(TreeNode node)
 733:   {
 734:     if (node == null)
 735:       return false;
 736: 
 737:     return node.getParent() == this;
 738:   }
 739: 
 740:   /**
 741:    * getFirstChild
 742:    *
 743:    * @return TreeNode
 744:    */
 745:   public TreeNode getFirstChild()
 746:   {
 747:     return (TreeNode) children.firstElement();
 748:   }
 749: 
 750:   /**
 751:    * getLastChild
 752:    *
 753:    * @return TreeNode
 754:    */
 755:   public TreeNode getLastChild()
 756:   {
 757:     return (TreeNode) children.lastElement();
 758:   }
 759: 
 760:   /**
 761:    * getChildAfter
 762:    *
 763:    * @param node TODO
 764:    *
 765:    * @return TreeNode
 766:    */
 767:   public TreeNode getChildAfter(TreeNode node)
 768:   {
 769:     if (node == null
 770:         || node.getParent() != this)
 771:       throw new IllegalArgumentException();
 772: 
 773:     int index = getIndex(node) + 1;
 774: 
 775:     if (index == getChildCount())
 776:       return null;
 777: 
 778:     return getChildAt(index);
 779:   }
 780: 
 781:   /**
 782:    * getChildBefore
 783:    *
 784:    * @param node TODO
 785:    *
 786:    * @return TreeNode
 787:    */
 788:   public TreeNode getChildBefore(TreeNode node)
 789:   {
 790:     if (node == null
 791:         || node.getParent() != this)
 792:       throw new IllegalArgumentException();
 793: 
 794:     int index = getIndex(node) - 1;
 795: 
 796:     if (index < 0)
 797:       return null;
 798: 
 799:     return getChildAt(index);
 800:   }
 801: 
 802:   /**
 803:    * isNodeSibling
 804:    *
 805:    * @param node TODO
 806:    *
 807:    * @return boolean
 808:    */
 809:   public boolean isNodeSibling(TreeNode node)
 810:   {
 811:     if (node == null)
 812:       return false;
 813: 
 814:     return (node.getParent() == getParent()
 815:             && getParent() != null);
 816:   }
 817: 
 818:   /**
 819:    * getSiblingCount
 820:    *
 821:    * @return int
 822:    */
 823:   public int getSiblingCount()
 824:   {
 825:     if (parent == null)
 826:       return 1;
 827: 
 828:     return parent.getChildCount();
 829:   }
 830: 
 831:   /**
 832:    * getNextSibling
 833:    *
 834:    * @return DefaultMutableTreeNode
 835:    */
 836:   public DefaultMutableTreeNode getNextSibling()
 837:   {
 838:     if (parent == null)
 839:       return null;
 840: 
 841:     int index = parent.getIndex(this) + 1;
 842:     
 843:     if (index == parent.getChildCount())
 844:       return null;
 845: 
 846:     return (DefaultMutableTreeNode) parent.getChildAt(index);
 847:   }
 848: 
 849:   /**
 850:    * getPreviousSibling
 851:    *
 852:    * @return DefaultMutableTreeNode
 853:    */
 854:   public DefaultMutableTreeNode getPreviousSibling()
 855:   {
 856:     if (parent == null)
 857:       return null;
 858: 
 859:     int index = parent.getIndex(this) - 1;
 860: 
 861:     if (index < 0)
 862:       return null;
 863: 
 864:     return (DefaultMutableTreeNode) parent.getChildAt(index);
 865:   }
 866: 
 867:   /**
 868:    * isLeaf
 869:    *
 870:    * @return boolean
 871:    */
 872:   public boolean isLeaf()
 873:   {
 874:     return children.size() == 0;
 875:   }
 876: 
 877:   /**
 878:    * getFirstLeaf
 879:    *
 880:    * @return DefaultMutableTreeNode
 881:    */
 882:   public DefaultMutableTreeNode getFirstLeaf()
 883:   {
 884:     TreeNode current = this;
 885:     
 886:     while (current.getChildCount() > 0)
 887:       current = current.getChildAt(0);
 888: 
 889:     return (DefaultMutableTreeNode) current;
 890:   }
 891: 
 892:   /**
 893:    * getLastLeaf
 894:    *
 895:    * @return DefaultMutableTreeNode
 896:    */
 897:   public DefaultMutableTreeNode getLastLeaf()
 898:   {
 899:     TreeNode current = this;
 900:     int size = current.getChildCount();
 901:     
 902:     while (size > 0)
 903:       {
 904:         current = current.getChildAt(size - 1);
 905:         size = current.getChildCount();
 906:       }
 907: 
 908:     return (DefaultMutableTreeNode) current;
 909:   }
 910: 
 911:   /**
 912:    * getNextLeaf
 913:    *
 914:    * @return DefaultMutableTreeNode
 915:    */
 916:   public DefaultMutableTreeNode getNextLeaf()
 917:   {
 918:     if (parent == null)
 919:       return null;
 920: 
 921:     // TODO: Fix implementation.
 922:     return null;
 923:     //return parent.getChildAfter(this);
 924:   }
 925: 
 926:   /**
 927:    * getPreviousLeaf
 928:    *
 929:    * @return DefaultMutableTreeNode
 930:    */
 931:   public DefaultMutableTreeNode getPreviousLeaf()
 932:   {
 933:     if (parent == null)
 934:       return null;
 935: 
 936:     // TODO: Fix implementation.
 937:     return null;
 938:     //return parent.getChildBefore(this);
 939:   }
 940: 
 941:   /**
 942:    * getLeafCount
 943:    *
 944:    * @return int
 945:    */
 946:   public int getLeafCount()
 947:   {
 948:     int count = 0;
 949:     Enumeration e = depthFirstEnumeration();
 950: 
 951:     while (e.hasMoreElements())
 952:       {
 953:         TreeNode current = (TreeNode) e.nextElement();
 954:         
 955:         if (current.isLeaf())
 956:           count++;
 957:       }
 958: 
 959:     return count;
 960:   }
 961: 
 962:   /** Provides an enumeration of a tree in breadth-first traversal
 963:    * order.
 964:    */
 965:   static class BreadthFirstEnumeration implements Enumeration
 966:   {
 967: 
 968:       LinkedList queue = new LinkedList();
 969: 
 970:       BreadthFirstEnumeration(TreeNode node)
 971:       {
 972:           queue.add(node);
 973:       }
 974: 
 975:       public boolean hasMoreElements()
 976:       {
 977:           return !queue.isEmpty();
 978:       }
 979: 
 980:       public Object nextElement()
 981:       {
 982:           if(queue.isEmpty())
 983:               throw new NoSuchElementException("No more elements left.");
 984: 
 985:           TreeNode node = (TreeNode) queue.removeFirst();
 986: 
 987:           Enumeration children = node.children();
 988:           while (children.hasMoreElements())
 989:               queue.add(children.nextElement());
 990: 
 991:           return node;
 992:       }
 993:   }
 994: 
 995:   /** Provides an enumeration of a tree traversing it
 996:    * preordered.
 997:    */
 998:   static class PreorderEnumeration implements Enumeration
 999:   {
1000:       TreeNode next;
1001: 
1002:       Stack childrenEnums = new Stack();
1003: 
1004:       PreorderEnumeration(TreeNode node)
1005:       {
1006:           next = node;
1007:           childrenEnums.push(node.children());
1008:       }
1009: 
1010:       public boolean hasMoreElements()
1011:       {
1012:           return next != null;
1013:       }
1014: 
1015:       public Object nextElement()
1016:       {
1017:           if( next == null )
1018:               throw new NoSuchElementException("No more elements left.");
1019: 
1020:           Object current = next;
1021: 
1022:           Enumeration children = (Enumeration) childrenEnums.peek();
1023: 
1024:           // Retrieves the next element.
1025:           next = traverse(children);
1026: 
1027:           return current;
1028:       }
1029: 
1030:       private TreeNode traverse(Enumeration children)
1031:       {
1032:           // If more children are available step down.
1033:           if( children.hasMoreElements() )
1034:           {
1035:               TreeNode child = (TreeNode) children.nextElement();
1036:               childrenEnums.push(child.children());
1037: 
1038:               return child;
1039:           }
1040:           
1041:           // If no children are left, we return to a higher level.
1042:           childrenEnums.pop();
1043: 
1044:           // If there are no more levels left, there is no next
1045:           // element to return.
1046:           if ( childrenEnums.isEmpty() )
1047:               return null;
1048:           else
1049:           {
1050:               return traverse((Enumeration) childrenEnums.peek());
1051:           }
1052:       }
1053:    }
1054: 
1055:   /** Provides an enumeration of a tree traversing it
1056:    * postordered (= depth-first).
1057:    */
1058:    static class PostorderEnumeration implements Enumeration
1059:    {
1060: 
1061:        Stack nodes = new Stack();
1062:        Stack childrenEnums = new Stack();
1063: 
1064:        PostorderEnumeration(TreeNode node)
1065:        {
1066:            nodes.push(node);
1067:            childrenEnums.push(node.children());
1068:        }
1069: 
1070:        public boolean hasMoreElements()
1071:        {
1072:            return !nodes.isEmpty();
1073:        }
1074: 
1075:        public Object nextElement()
1076:        {
1077:            if( nodes.isEmpty() )
1078:                throw new NoSuchElementException("No more elements left!");
1079: 
1080:            Enumeration children = (Enumeration) childrenEnums.peek();
1081: 
1082:            return traverse(children);
1083:        }
1084: 
1085:        private Object traverse(Enumeration children)
1086:        {
1087:            if ( children.hasMoreElements() )
1088:            {
1089:                TreeNode node = (TreeNode) children.nextElement();
1090:                nodes.push(node);
1091: 
1092:                Enumeration newChildren = node.children();
1093:                childrenEnums.push(newChildren);
1094: 
1095:                return traverse(newChildren);
1096:            }
1097:            else
1098:            {
1099:                childrenEnums.pop();
1100: 
1101:                // Returns the node whose children
1102:                // have all been visited. (= postorder)
1103:                Object next = nodes.peek();
1104:                nodes.pop();
1105: 
1106:                return next;
1107:            }
1108:        }
1109: 
1110:     }
1111: 
1112: }