icltermtraverser.java

SRI international 发布的OAA框架软件

package com.sri.oaa2.icl;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * An abstract class for doing depth first traversal of an IclTerm.  This
 * is an alternative to the Visitor pattern that exists in the IclTerm class.
 * To use it, just create a subclass and provide the discover(IclTerm) and
 * finish(IclTerm) methods.  The discover method is called when an IclTerm
 * is first encountered, and the finish method is called when all the children
 * of an IclTerm have been finished.  Given an IclTerm t, if t.isAtomic() is
 * true, then finish() will be called immediately after discover() has been
 * called.
 * <p>
 * Implementation wise, this is faster than a standard recursive traversal, since
 * existing implementations of Java don't handle recursion well.
 * <p>
 * For an example of using this class, look at the source for
 * GenerateManualConstruction.  ToString does something similar,
 * but much more specialized.
 *
 * @author agno
 */
public abstract class IclTermTraverser 
{
  /**
   * Called when an IclTerm is first visited.
   *
   * @param t The IclTerm that was discovered.
   * @return boolean false to stop the traversal and true otherwise
   */
  public abstract boolean discover(IclTerm t);

  /**
   * Called when an IclTerm's children have all been visited.
   *
   * @param t The IclTerm that was finished.
   * @return boolean false to stop the traversal and true otherwise
   */
  public abstract boolean finish(IclTerm t);

  /**
   * Perform a traversal on the given IclTerm.
   *
   * @param t The IclTerm to traverse.
   */
  public final void traverse(IclTerm t) 
  {
    // list of IteratorInfo objects
    ArrayList iterators = new ArrayList();

    IteratorInfo itInfo = new IteratorInfo();
    itInfo.t = t;
    iterators.add(itInfo);

    IteratorInfo newItInfo;

    while(!iterators.isEmpty()) {
      itInfo = (IteratorInfo)iterators.get(iterators.size() - 1);

      // if we've never visited the node before, we have to run
      // the pre traversal hooks
      if(!itInfo.visited) {
        itInfo.visited = true;
        if(!this.discover(itInfo.t)) {
          return;
        }
        itInfo.it = itInfo.t.iterator();

        // either we have children, in which case we recurse
        // or we are done, in which case we run the post
        // traversal hooks
        if(itInfo.it.hasNext()) {
          newItInfo = new IteratorInfo();
          newItInfo.t = (IclTerm)itInfo.it.next();
          iterators.add(newItInfo);

          continue;
        }
        else {
          if(!this.finish(itInfo.t)) {
            return;
          }
          iterators.remove(iterators.size() - 1);

          continue;
        }
      }
      else {
        // we've seen this node before--keep going through its
        // children if it has any, or we're finished with this
        // node
        if(itInfo.it.hasNext()) {
          newItInfo = new IteratorInfo();
          newItInfo.t = (IclTerm)itInfo.it.next();
          iterators.add(newItInfo);

          continue;
        }
        else {
          if(!this.finish(itInfo.t)) {
            return;
          }
          iterators.remove(iterators.size() - 1);

          continue;
        }
      }
    }
  }
  
  /**
   * Keeps track of a single subtree in the traversal.
   * 
   * @author agno
   */
  private class IteratorInfo
  {
    /** The root of the subtree */
    IclTerm t;

    /** Iterator over the children of the subtree */
    Iterator it;

    /** Have we ever visited this node before? */
    boolean visited = false;
  }
}