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();
}
}