package org.hibernate.hql.ast.util;

import antlr.collections.AST;
import java.util.Map;
import java.util.HashMap;

/**
* A visitor for traversing an AST tree.
*
* @author Steve Ebersole
* @author Philip R. "Pib" Burns.   Replaced recursion in tree traversal
*   with iteration.
*/

public class NodeTraverser {
   public static interface VisitationStrategy {
      public void visit(AST node);
   }

   private final VisitationStrategy strategy;

   public NodeTraverser(VisitationStrategy strategy) {
      this.strategy = strategy;
   }

   /**   Traverse the AST tree depth first.
    *
    *   @param ast Root node of subtree to traverse.
    *
    *   <p>
    *   Note that the AST passed in is not visited itself.  Visitation
    *   starts with its children.
    *   </p>
    *
    *   <p>
    *   This method originally called a recursive method visitDepthFirst
    *   which performed a recursive traversal of the tree rooted at the
    *   node specified by the ast parameter.  The original code looked
    *   like this:
    *   </p>
    *   <code>
    *   <pre>
    *   private void visitDepthFirst(AST ast) {
    *      if ( ast == null ) {
    *         return;
    *      }
    *      strategy.visit( ast );
    *      visitDepthFirst( ast.getFirstChild() );
    *      visitDepthFirst( ast.getNextSibling() );
    *   }
    *   </pre>
    *   </code>
    *   </p>
    *
    *   <p>
    *   The current code for traverseDepthFirst uses iteration to
    *   walk the tree.  This corrects stack overflow problems for
    *   constructs such as "x in (:x)" where ":x" specifies a large number
    *   of items.
    *   </p>
    */

   public void traverseDepthFirst( AST ast )
   {
                        //   Root AST node cannot be null or
                        //   traversal of its subtree is impossible.
      if ( ast == null )
      {
         throw new IllegalArgumentException(
            "node to traverse cannot be null!" );
      }
                        //   Map to hold parents of each
                        //   AST node.  Unfortunately the AST
                        //   interface does not provide a method
                        //   for finding the parent of a node, so
                        //   we use the Map to save them.

      Map parentNodes   = new HashMap();

                        //   Start tree traversal with first child
                        //   of the specified root AST node.

      AST currentNode   = ast.getFirstChild();

                        //   Remember parent of first child.

      parentNodes.put( currentNode , ast );

                        //   Iterate through nodes, simulating
                        //   recursive tree traversal, and add them
                        //   to queue in proper order for later
                        //   linear traversal.  This "flattens" the
                        //   into a linear list of nodes which can
                        //   be visited non-recursively.

      while ( currentNode != null )
      {
                        //   Visit the current node.

         strategy.visit( currentNode );

                        //   Move down to current node's first child
                        //   if it exists.

         AST childNode   = currentNode.getFirstChild();

                        //   If the child is not null, make it
                        //   the current node.

         if ( childNode != null )
         {
                        //   Remember parent of the child.

            parentNodes.put( childNode , currentNode );

                        //   Make child the current node.

            currentNode   = childNode;

            continue;
         }

         while ( currentNode != null )
         {
                        //   Move to next sibling if any.

            AST siblingNode   = currentNode.getNextSibling();

            if ( siblingNode != null )
            {
                        //   Get current node's parent.
                        //   This is also the parent of the
                        //   sibling node.

               AST parentNode   = (AST)parentNodes.get( currentNode );

                        //   Remember parent of sibling.

               parentNodes.put( siblingNode , parentNode );

                        //   Make sibling the current node.

               currentNode      = siblingNode;

               break;
            }
                        //   Move up to parent if no sibling.
                        //   If parent is root node, we're done.

            currentNode   = (AST)parentNodes.get( currentNode );

            if ( currentNode.equals( ast ) )
            {
               currentNode = null;
            }
         }
      }
   }
}