package com.sri.emo.dbobj.model_tree;
   
   import java.util.ArrayList;
   import java.util.Iterator;
   import java.util.List;
   import java.util.Stack;
   
   
   /***
   * Implementation of Iterator that allows depth first iteratation over
   * all the nodes in a model.  This iterator does not allow for removal
   * of individual nodes: <em>it is read only</em>.
   *
   * @author Michael Rimov
   */
  public class ModelDepthFirstIterator implements Iterator {
  
      /***
       * Stack for allowing backtrace of nodes
       */
      private final Stack backtrace;
  
      /***
       * Current index in the stack
       */
      private int currentIndex;
  
  
      /***
       * The children of the node we're iterating through.
       */
      private List currentSiblings;
  
  
      /***
       * Instance of the listener.
       */
      private final TreeTraversalListener listener;
  
      /***
       * Constructor that takes the root of what it is suppsoed to iterate.
       *
       * @param root ModelCompositeNode
       */
      public ModelDepthFirstIterator(final ModelNode root) {
          backtrace = new Stack();
          currentIndex = -1;
          currentSiblings = new ArrayList(1);
          currentSiblings.add(root);
          listener = TreeTraversalListener.NULL_LISTENER;
      }
  
  
      /***
       * Constructor that takes a listener as well as a root of what it is supposed
       * to iterate.
       *
       * @param root     ModelNode the root composite node that we're iterating
       *                 in a depth first fashion.
       * @param listener TreeTraversalListener the notification sink that receives
       *                 notifications of traversal down or up the tree.  This iterator is
       *                 guaranteed to only traverse down one level at a time, although it may
       *                 traverse up several levels.
       */
      public ModelDepthFirstIterator(final ModelNode root, final TreeTraversalListener listener) {
          assert root != null;
          assert listener != null;
  
          backtrace = new Stack();
          currentIndex = -1;
          currentSiblings = new ArrayList(1);
          currentSiblings.add(root);
          this.listener = listener;
      }
  
      /***
       * Returns <tt>true</tt> if the iteration has more elements.
       *
       * @return <tt>true</tt> if the iterator has more elements.
       */
      public boolean hasNext() {
  
          //If there are more children on this level the we're set.
          if ((currentIndex + 1) < currentSiblings.size()) {
              return true;
          }
  
          //Otherwise we have to trace
          boolean foundFurtherNodes = false;
  
          // It doesn't matter what order we search the stack (first in our last in)
          // because all we need to know is 'are there more nodes somewhere to
          // iterate?'
          for (Iterator i = backtrace.iterator(); (i.hasNext() && !foundFurtherNodes);) {
              StackStatus oneStatus = (StackStatus) i.next();
              if ((oneStatus.getChildIndex() + 1) < oneStatus.getNode().size()) {
                  foundFurtherNodes = true;
              }
          }
 
         return foundFurtherNodes;
     }
 
     /***
      * Returns the next element in the iteration.
      *
      * @return the next element in the iteration.
      */
     public Object next() {
         currentIndex++;
 
         //If we are at the end of children array, then we need to pop
         //up the hierarchy and resume where we left off.
         while (currentIndex >= currentSiblings.size()) {
             boolean hasParents = popState();
             if (!hasParents) {
                 throw new ArrayIndexOutOfBoundsException("Iterated past end of model");
             }
         }
 
         //Get the current value to print, and then push down to its children
         //to iterate them.
         Object returnValue = (Object) currentSiblings.get(currentIndex);
 
         //Now, depth first traverse the tree.
         pushState();
 
         return returnValue;
     }
 
     /***
      * Removes from the underlying collection the last element returned by
      * the iterator (optional operation).
      */
     public void remove() {
         throw new java.lang.UnsupportedOperationException("This iterator: " + getClass()
                 + " is read only and does not support removal");
     }
 
     /***
      * Pops the stack and resets state to the previous 'level' in the tree
      * hierarchy.
      *
      * @return boolean if the stack was not empty.  If popStack() returns false,
      *         then hasNext() should return false.
      */
     private boolean popState() {
         if (backtrace.isEmpty()) {
             return false;
         } else {
             StackStatus previousState = (StackStatus) backtrace.pop();
             listener.ascendModelTree((ModelNode) previousState.getNode().get(previousState.getChildIndex()));
             currentIndex = (previousState.getChildIndex() + 1);
             currentSiblings = previousState.getNode();
             return true;
         }
     }
 
     /***
      * Pushes the current state onto the 'call stack' for later
      * return and reiteration.
      */
     private void pushState() {
         backtrace.push(new StackStatus(currentSiblings, currentIndex));
         listener.descendModelTree((ModelNode) currentSiblings.get(currentIndex));
         currentSiblings = ((ModelNode) currentSiblings.get(currentIndex)).getChildren();
         currentIndex = -1;
     }
 
     /***
      * Class for allow state to be saved when traversing the various nodes.  It
      * saves the current node as well as what child we were iterating through
      * before we 'recursively' descended into the children of the tree.
      *
      * @author Michael Rimov
      */
     private static class StackStatus {
         private final List node;
         private final int child;
 
         StackStatus(final List currentList, final int currentChild) {
             node = currentList;
             child = currentChild;
         }
 
         List getNode() {
             return node;
         }
 
         int getChildIndex() {
             return child;
         }
     }
 }