/*
 * Machine.java  
 *
 * Copyright 2001
 * College of Computer Science
 * Northeastern University
 * Boston, MA  02115
 *
 * This software may be used for educational purposes as long as
 * this copyright notice is retained intact at the top of all files.
 *
 * Should this software be modified, the words "Modified from 
 * Original" must be included as a comment below this notice.
 *
 * All publication rights are retained.  This software or its 
 * documentation may not be published in any media either in whole
 * or in part without explicit permission.
 *
 * Contact information:
 *   Richard Rasala    rasala@ccs.neu.edu
 *   Viera Proulx      vkp@ccs.neu.edu
 *   Jeff Raab         jmr@ccs.neu.edu
 *   Jennifer McDonald jenimac@ccs.neu.edu
 * 
 * Telephone:          617-373-2462
 *
 * This software was created with support from Northeastern 
 * University and from NSF grant DUE-9950829.
 */

import java.util.*;
import edu.neu.ccs.*;
import edu.neu.ccs.util.*;


public class Machine{

	// Symbol representing epsilon in the machine
	public static final Symbol EPSILON = Symbol.epsilon();
	

	private Tape tape = null;
	private Automata automata;
	
	private Stack pushdownStack = null;
	private Stack pathStack = null;
	private Stack undoStack = null;
	
	private Vector paths = null;
	
    // Depth maximum -- to prevent infinte loops
	protected int depthMax = 0;
	protected int recursionCount = 0;

	// constructor
	public Machine(Tape t, Automata a, int max) {

		tape = t;
		automata = a;
		depthMax = max;
	}
	
	public void initialize(State s) {
	
		paths = new Vector();
		
		pushdownStack = new Stack();
		pathStack = new Stack();
		undoStack = new Stack();
		
		// push start state onto the path stack
		PathNode n = new PathNode(s);	
		pathStack.push(n);
	}

	// computes all possible paths 
	public Vector findPaths() {
	
		State firstState = automata.getStartState();
		
		initialize(firstState);
		processTape(firstState, 0);

		return paths;
	}
	

	// determines when a full path has been found
	// and adds it to the paths vector
	public void processTape(State state, int tapePtr) {
	
	    recursionCount++;

	    // Make sure the machine does not get stuck in an infinite loop.
	    if(recursionCount >= depthMax) {
	        addPath();
	        return;
	    }

		// if at the end of the tape and the stack
		// is empty it is a terminating path
		if(pushdownStack.empty() && tape.atEnd(tapePtr)) {
			
				// set this to be a terminating path
				((PathNode)pathStack.peek()).setTerminating();
					
				// add this path to the paths found
				addPath();
				
				return;
		}
		
		// otherwise, continue searching for new paths
		continueSearch(state, tape.read(tapePtr), tapePtr);
		
		// when continueSearch returns, there is no where
		// else to go. So add the path and return
		addPath();
	}
	
	
	// finds all possible states reachable 
	// from a given state and test them
	public void continueSearch(State s, Symbol symbol, int tapePtr) {	
		
		Transition t = null;
		
		XHashtable table = automata.getReachableFrom(s);
		
		Enumeration targets = table.keys();
		Enumeration vectors = table.elements();
		
		// for each state reachable from s
		// get the transitions between them
		// and test each transition
		for(int i = 0; i < table.size(); i++) {
			
			State target = 
				automata.getState((XString) targets.nextElement());
			
			XVector vector = 
				(XVector) vectors.nextElement();
			
			testTransitions(s, target, symbol, tapePtr, vector);
			
		}
	}
	
	public void testTransitions(State source, State target, 
								Symbol symbol, int tapePtr,
						  		XVector transitions) {		
		Transition t;
		Symbol searchChar;
		int size = transitions.size();
		
		if (pushdownStack.isEmpty())
			searchChar = Symbol.epsilon();
		else
			searchChar = (Symbol) pushdownStack.peek();
		
		for(int i = 0; i < size; i++) {
			
			t = (Transition) transitions.get(i);
		
			if (t.matches(symbol, searchChar)) {
				
				 // create a new path node 
				 PathNode newNode = new PathNode(source, target, t, i);
				 
				 // march further with this new node
				 visit(newNode, tapePtr);
			}
		}
	}
	
	
	// moves to the next state
	// performs the necessary action
	// recurses to the next path
	public void visit(PathNode node, int tapePtr) {
	
		advance(node, tapePtr);
		rewind();		
	}
	
	// process next path node & perform necessary
	// stack operations
	public void advance(PathNode node, int tapePtr) {
	
		StackClass.Action action = null;
		
		pathStack.push(node);
				
		// get the action for that transition
		action = node.getStackAction();
				
		// save the action so you can undo it later
		undoStack.push(action);
				
		// perform action
		action.doAction(pushdownStack);
		
		if(!(node.movesOnEpsilon())) {
			tapePtr++;
		}

		// recurse to next path
		processTape(node.getTarget(), tapePtr);
	}
	
	// backtrack to the previous node and undo
	// forward actions
	public void rewind() {

		// undo forward progress
		((StackClass.Action) undoStack.pop()).undoAction(pushdownStack);
		pathStack.pop();	
	}
	
	protected void addPath() {
		paths.add((Stack)pathStack.clone());
		
		// reset the recursion count
		recursionCount = 0;
	}
}