home *** CD-ROM | disk | FTP | other *** search
/ Dynamic HTML in Action / Dynamicke-HTML-v-akci-covermount.bin / XML / PARSER / XMLINST.EXE / classes / com / ms / xml / om / TreeEnumeration.java < prev   
Encoding:
Java Source  |  1997-08-27  |  4.4 KB  |  175 lines
  1. /*
  2.  * @(#)TreeEnumeration.java 1.0 7/11/97
  3.  * 
  4.  * Copyright (c) 1997 Microsoft, Corp. All Rights Reserved.
  5.  * 
  6.  */
  7.  
  8. package com.ms.xml.om;
  9.  
  10. import com.ms.xml.util.EnumWrapper;
  11. import com.ms.xml.util.Name;
  12. import com.ms.xml.util.Queue;
  13. import java.util.Enumeration;
  14. import java.util.Stack;
  15.  
  16. /**
  17.  * An Enumeration for iterating over the entire subtree of a given node 
  18.  * in the XML tree, DFS or BFS
  19.  *
  20.  * @version 1.0, 8/27/97
  21.  * @see Element
  22.  * @see Name
  23.  */
  24. public class TreeEnumeration implements Enumeration
  25. {
  26.     /**
  27.      * Creates new iterator for iterating over all of the children
  28.      * of the given root node.
  29.      */
  30.     public TreeEnumeration(Element node)
  31.     {
  32.         Initialize( node, true );
  33.     }
  34.     public TreeEnumeration(Element node, boolean enumDir )
  35.     {
  36.         Initialize( node, enumDir );
  37.     }
  38.  
  39.     private void Initialize( Element node, boolean enumDir )
  40.     {
  41.         this.originalNode   = node;
  42.         this.enumerationDir = enumDir;
  43.         this.next           = null;
  44.  
  45.         this.DFSstack       = null;   
  46.         this.BFSqueue       = null;
  47.  
  48.         this.curr           = node;
  49.         this.children       = new EnumWrapper(node);
  50.  
  51.         if( !enumDir )  // BFS traversal
  52.         {
  53.             this.BFSqueue   = new Queue();
  54.         }
  55.         else  // default to DFS traversal
  56.         {                            
  57.             this.next       = node;
  58.             children.nextElement();
  59.             this.DFSstack   = new Stack();
  60.         }
  61.     }
  62.  
  63.     /**
  64.      * Reset the iterator so you can iterate through the elements again.
  65.      */
  66.     public void reset()
  67.     {
  68.         Initialize( originalNode, enumerationDir );
  69.     }
  70.  
  71.     /**
  72.      * Return whether or not there are any more matching elements.
  73.      * @return true if the next call to nextElement will return
  74.      * non null result.
  75.      */
  76.     public boolean hasMoreElements()
  77.     {       
  78.         if (next == null) 
  79.         {
  80.             next = next();
  81.         }
  82.         return (next != null) ? true : false;
  83.     }
  84.  
  85.     /**
  86.      * Return the next matching element.
  87.      * @return Element or null of there are no more matching elements.
  88.      */
  89.     public Object nextElement()
  90.     {
  91.         if (next != null) 
  92.         {
  93.             Element result = next;
  94.             next = null;
  95.             return result;
  96.         }
  97.         return next();
  98.     }
  99.  
  100.     /**
  101.      * Internal method for getting next element.
  102.      */
  103.     Element next()
  104.     {                
  105.         if( !enumerationDir ) // BFS traversal
  106.             return nextElementTreeBFS();
  107.         else // default to DFS traversal
  108.             return nextElementTreeDFS();
  109.     }
  110.  
  111.     Element nextElementTreeDFS()
  112.     {
  113.         while (curr != null)
  114.         {
  115.             // try to go down a level
  116.             DFSstack.push(children);
  117.             children = curr.getElements();
  118.             // try next at this level
  119.             if (children.hasMoreElements())
  120.             {
  121.                 curr = (Element)children.nextElement();
  122.                 return curr;
  123.             }
  124.             // go back up 
  125.             for (curr = curr.getParent(); curr != null; curr = curr.getParent())
  126.             {
  127.                 if(DFSstack.empty())
  128.                     return null;  // If the original node is not the root of tree...
  129.  
  130.                 children = (Enumeration)DFSstack.pop();
  131.                 if (children.hasMoreElements())
  132.                 {
  133.                     curr = (Element)children.nextElement();
  134.                     return curr;
  135.                 }
  136.             }
  137.         }
  138.         return null;
  139.     }
  140.  
  141.     Element nextElementTreeBFS()
  142.     {
  143.         while (curr != null)
  144.         {
  145.             while( !children.hasMoreElements() )
  146.             {
  147.                 children = (Enumeration)BFSqueue.pull();
  148.                 if( children == null )
  149.                     return null;
  150.             }
  151.  
  152.             // go to the next child
  153.             curr = (Element)children.nextElement();
  154.             BFSqueue.push(curr.getElements());
  155.             return curr;         
  156.         }
  157.         return null;
  158.     }
  159.     
  160.     Element originalNode;
  161.  
  162.     Element next;
  163.  
  164.     Enumeration children;
  165.  
  166.     // DFSTree enumeration
  167.     Stack DFSstack;
  168.     Element curr;
  169.    
  170.     // BFSTree enumeration
  171.     Queue BFSqueue;
  172.  
  173.     boolean enumerationDir;  // true = DFS tree  -  false = BFS tree
  174. }
  175.