package finiteAutomata;
import java.util.Random;
import java.util.Vector;
/**
 * A non-empty string of variables and terminals such as occur in grammar 
 * derivations (supports the CNF class).
 * 
 * <BR><BR>Data Fields: Each StringVarTerm has a Vector (code) of Integer  
 * codes to represent the string, a counter (vars) telling how many  
 * variables are in the string, a Vector (derivation) of String objects  
 * showing the sequence of strings used in deriving this string, and an  
 * Alphabet (alpha) of allowable terminal symbols.
 * 
 * <BR><BR>Example (encoding/decoding):
 * Suppose the Alphabet is {a,b,c}.  The integers 1, 2, 3 are used to 
 * represent, respectively, the terminal symbols a, b, and c.  0
 * represents the start variable v0, -1 represents v1, -2 represents v2, 
 * and so on.  Thus, the string "c a v1 v2 b a v2" would be encoded by 
 * the integer sequence "3, 1, -1, -2, 2, 1, -2".  Note that 
 * terminals are represented by positive codes and variables are
 * represented by non-positive codes.
 *  
 * @author Barbara Wahl
 * @version Fall 2007 
 */
public class StringVarTerm {
	
	// ** DATA FIELDS **
	/**
	 * sequence of Integer codes for this StringVarTerm
	 */
	protected Vector code;       
	/**
	 * number of variables in this StringVarTerm (vars == 0 
	 * if this represents a string of terminal symbols)
	 */
	protected int vars;          
	/**
	 * alphabet of terminal symbols
	 */
	protected Alphabet alpha;   
	/**
	 * sequence of Strings showing how this StringVarTerm is derived
	 * from start (v0)
	 */
	protected Vector derivation;
	
	/**
	 * 1-parameter constructor, creates the StringVarTerm representing the start
	 * string, "v0"
	 * @param S Alphabet of terminal symbols
	 * @post creates the "start" string consisting of only the start variable, "v0" 
	 * (alpha = S, vars = 1, derivation is empty)
	 */
	public StringVarTerm(Alphabet S)
	{
		alpha = S;
		vars = 1;
		code = new Vector();       // allocate Vector for code
		code.add(new Integer(0));  // 0 = encoding for v0
		derivation = new Vector(); // empty derivation 
	}
	/**
	 * Returns number of steps to derive this StringVarTerm.
	 * @return number of steps to derive this StringVarTerm from
	 * "v0" (where 0 steps are needed to derive "v0")
	 */
	public int numSteps()
	// post: returns number of steps to derive this StringVarTerm,
	//       (0 steps are needed to derive the start string "v0")
	{
		return this.derivation.size();
	}
	/**
	 * Returns number of variables.
	 * @return this.vars
	 */
	public int vars()
	{
		return this.vars;
	}
	/**
	 * Returns a deep copy of this StringVarTerm.
	 * @return a new StringVarTerm with all the same data fields as this
	 * @post the new object is completely independent of the original 
	 * (the derivation and code Vectors are deep-copied)
	 */
	public StringVarTerm copy()
	{
		StringVarTerm newString = new StringVarTerm(alpha);
		newString.vars = vars;
		newString.code = code();
		newString.derivation = derivation();
		return newString;		
	}
	/**
	 * Returns a deep copy of this.derivation.
	 * @return a new derivation Vector filled with new String objects
	 */
	public Vector derivation()
	{
		Vector v = new Vector();
		for(int i=0; i<derivation.size(); i++)
		{
			// create a new String object with same information...
			String curr = new String((String)derivation.elementAt(i));
			v.add(curr);
		}
		return v;
	}
	/**
	 * Returns a deep copy of this.code.
	 * @return a new code Vector filled with new Integer objects
	 */
	public Vector code()
	{
		Vector v = new Vector();
		for(int i=0; i<code.size(); i++)
		{
			// create a new Integer object with same information...
			int val = ((Integer)code.elementAt(i)).intValue();
			Integer curr = new Integer(val);
			v.add(curr);
		}
		return v;
	}	
	/**
	 * Pretty-prints a report on this StringVarTerm.
	 * @post reports alphabet, string of variables and terminals, number of 
	 * variables in string, number of terminals in string, length of 
	 * derivation for this StringVarTerm, steps in derivation for this 
	 * StringVarTerm
	 */
	public void printStringVarTerm()
	{
		System.out.println("=======================");
		System.out.println("alphabet = " + alpha.toPrettyString());
		System.out.println("string = " + this.toPrettyString());
		System.out.println("# variables in string = " + this.vars);
		System.out.println("# terminals in string = " + (code.size() - vars));		
		System.out.println("length of derivation = " + derivation.size());
		System.out.print("derivation: ");
		this.printDerivation();
		System.out.println("=======================");
	}
	/**
	 * Pretty-prints the derivation.
	 * @post prints each string in the derivation, separated by arrows ("->"),
	 * with "this" string appended at the end
	 */
	public void printDerivation()
	{
		for(int i=0; i<derivation.size(); i++)
		{
			String s = (String)derivation.elementAt(i);
			System.out.print(s + " -> ");
		}
		System.out.println(this.toPrettyString());
	}	
	/**
	 * Returns a "pretty" representation of the string represented
	 * by this StringVarTerm.
	 * @return a "pretty" String representation of this StringVarTerm 
	 * (decodes the "code" Vector, inserts 'v's and spaces)
	 */
	public String toPrettyString()
	{
		StringBuffer s = new StringBuffer();
		int num;
		char c;
		// iterate through this.code and append appropriate chars
		// to s (separated by spaces)
		for(int i=0; i<code.size(); i++)
		{
			num = ((Integer)code.elementAt(i)).intValue();
			if(num<=0) // num is a coded variable
			{
				s.append('v');
				// decode num to get variable number	
				num = 0 - num; 
				// convert variable number to a char & append
				c = (new Integer(num)).toString().charAt(0);
				s.append(c);
				// append a space
				s.append(' ');
			}
			else // num is a coded terminal
			{
				// decode num to get a terminal symbol & append;
				// don't forget "-1"!  for example, num = 3 stands
				// for T.charAt(2)
				s.append(alpha.charAt(num-1));
				// append a space
				s.append(' ');
			}
		}		
		return s.toString();
	}
	/**
	 * Decodes this StringVarTerm (which has no variables); returns a String
	 * with no spaces.
	 * @return the decoded String version of this.code, with no spaces
	 * inserted between characters (useful for strings of terminals only)
	 * @pre vars == 0
	 */
	public String toTermString()
	{
		Assert.pre(vars == 0, "this StringVarTerm has no variables");
		StringBuffer s = new StringBuffer();
		int num;
		// iterate through this.code and append appropriate chars
		// to s (no spaces)
		for(int i=0; i<code.size(); i++)
		{
			num = ((Integer)code.elementAt(i)).intValue();

			// decode num to get a terminal symbol & append;
			// don't forget "-1"!  for example, num = 3 stands
			// for T.charAt(2)
			s.append(alpha.charAt(num-1));			
		}		
		return s.toString();
	}
	/**
	 * Returns the result of applying the given CNFRule to the LEFT-MOST variable 
	 * in this StringVarTerm.
	 * @param r the rule to be applied
	 * @return the StringVarTerm which results from applying rule r to the 
	 * LEFT-MOST variable in this StringVarTerm, if possible (otherwise, 
	 * returns a copy of this StringVarTerm and prints a warning message).  
	 * @pre if r is a "type 1" rule (var -> term) then r.term() must be a 
	 * symbol in this.alpha
	 * @post this StringVarTerm is left unchanged
	 */
	public StringVarTerm applyRule(CNFRule r)
	{
		StringVarTerm temp = this.copy(); // to insure non-destruction of this		
		if(!temp.matches(r)) // nothing to do -- rule does not apply
		{
			System.out.println("rule does not apply! (variable mis-match)");
			return temp;
		}				
		// otherwise, locate position of left-most variable
		int pos = temp.leftMostVarIndex();
		if(r.type() == 0)
		{   // type 0 rule, vn -> vi vj
			// 0 - r.var2() encodes r.var2(); 0 - r.var3() encodes r.var3()
			temp.code.insertElementAt(new Integer(0 - r.var2()),pos+1);
			temp.code.insertElementAt(new Integer(0 - r.var3()),pos+2);
			temp.code.remove(pos);
			temp.vars = vars + 1;
		}		
		if(r.type() == 1)
		{   // type 1 rule, vn -> terminal
			// first, make sure r.term() is in alphabet
			int index = temp.alpha.indexOf(r.term());
			if(index < 0)
				return temp; // r.term() not in alphabet
			
			// T.charAt(index) is encoded by index+1
			temp.code.insertElementAt(new Integer(index+1),pos+1);
			temp.code.remove(pos);
			temp.vars = vars - 1;
		}
		temp.derivation.add(this.toPrettyString());
		return temp;
	}
	/**
	 * Returns the decoded value of the given position in this.code, assuming
	 * that position is a coded variable.
	 * @param i position of interest in this code
	 * @pre 0 <= i < code.length()
	 * @return assuming code.elementAt(i) has a non-positive value,
	 * returns the corresponding variable number 
	 */
	protected int decodeVar(int i)
	{
		return (0 - ((Integer)code.elementAt(i)).intValue());
	}
	/**
	 * Returns the index (position) of the left-most variable in this
	 * StringVarTerm.
	 * @return the index of the left-most variable in this StringVarTerm, 
	 * or -1 (if no variables are present)
	 */
	public int leftMostVarIndex()
	{
		if(vars == 0)          // no variables
			return -1;
		int i=0;
		while(((Integer)code.elementAt(i)).intValue() > 0) // not var
			i++;
		return i;
	}
	/**
	 * Tests whether a given rule applies to the left-most variable in this
	 * StringVarTerm.
	 * @param r the rule to be tested
	 * @return true iff the left-most variable in this StringVarTerm is
	 * the same as r.var1, the LHS of rule r
	 * @pre r is not null
	 */
	public boolean matches(CNFRule r)
	{
		int i = leftMostVarIndex(); // position of left-most variable
		if(i<0) 
			return false;           // no variable exists
		
		// convert from Integer to int
		int leftMostVar = ((Integer)code.elementAt(i)).intValue();
		
		// 0 - r.var1() is the int code for r.var1()
		if(leftMostVar == 0 - r.var1())
			return true;   // int codes match -- success!
		else return false; // no match		
	}	
	/**
	 * Tests whether a given String is a non-empty string of terminals and 
	 * this StringVarTerm represents the same string of terminals.
	 * @param s the String to be tested
	 * @return true iff "this" and s represent exactly the same non-empty 
	 * string of terminal symbols
	 * @pre s is not null
	 */	
	public boolean equalTermString(String s)
	{
		// false if s is empty or if "this" contains any variables
		if(s.length() == 0 && this.vars > 0)
			return false;

		if(alpha.indexArray(s,new int[s.length()])) 
		// if s is a string of terminals from this.alpha...
		{
			// convert this to a string of terminals & compare with s
			String termString = this.toTermString(); 
			return termString.equals(s);
		}
		else 
			return false;
	}
	/**
	 * Tests whether "this" and another StringVarTerm represent the
	 * same string.
	 * @param other the StringVarTerm with which to compare this
	 * @return true iff "this" and other represent the same string
	 * of variables and terminals (perhaps with different derivations)
	 * @pre other is not null
	 */
	public boolean equalString(StringVarTerm other)
	{
		String s1 = this.toPrettyString();
		String s2 = other.toPrettyString();
		return s1.equals(s2);
	}
	
	// ** TEST METHOD **
	public static void main(String[] args) {
		// create Alphabet = {a,b,c}
		Alphabet alpha = new Alphabet("abc");
		// create "start" string using alphabet {a,b,c}
		StringVarTerm str = new StringVarTerm(alpha);
		str.printStringVarTerm();
		// create some rules
		CNFRule[] rule = new CNFRule[4];
		rule[0] = new CNFRule(0,1,2); // create the rule "v0 -> v1 v2"
		rule[1] = new CNFRule(1,'a'); // create the rule "v1 -> a"
		rule[2] = new CNFRule(2,'b'); // create the rule "v2 -> b"
		rule[3] = new CNFRule(1,1,1); // // create the rule "v1 -> v1 v1"
		
		// apply rule v0 -> v1 v2
		str = str.applyRule(rule[0]);
		System.out.println("After calling str.applyRule, we have:");
		str.printStringVarTerm();
		
		// randomly try to apply a rule 40 times
		Random rand = new Random(35); // new random number generator
		int randInt;
		for(int i=0; i<40; i++)
		{
			randInt = rand.nextInt(3);
			str = str.applyRule(rule[randInt+1]); // apply rule 1, 2, or 3
			// print str
			System.out.println("After calling str.applyRule, we have:");
			str.printStringVarTerm();
		}
		
		// print the final result
		str.printStringVarTerm();
	}

}