/*---------------------------------------------------------------------------
File:         			Grammar.java
Package:                        JFLAP Version 3.1
Author:			        Eric Gramond 
Modified:			Ted Hung V3.1 7/21/99
                                
Description of Contents:	Contains class Grammar.
				
--------------------------------------------------------------------------*/

/* 
 * Susan H. Rodger, Magda Procopiuc, Octavian Procopiuc, Eric Gramond, Ted Hung
 * Computer Science Department
 * Duke University
 * August 1999
 * Supported by National Science Foundation DUE-9596002, DUE-9555084,
 *  and DUE-9752583
 *
 * Copyright (c) 1999
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms are permitted
 * provided that the above copyright notice and this paragraph are
 * duplicated in all such forms and that any documentation,
 * advertising materials, and other materials related to such
 * distribution and use acknowledge that the software was developed
 * by the author.  The name of the author may not be used to
 * endorse or promote products derived from this software without
 * specific prior written permission.
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 */

package flap;

import java.util.*;
import java.awt.*;
import java.io.*;
import java.awt.image.*;
import java.awt.event.*;


/**
 * This a generic grammar. Basically made up of a set of Rules and a start Symbol
 */
public class Grammar {
  
  protected Variable myStartLetter;
  protected Vector myRules;
  protected int maxX, maxY;

    /**
     * creates a new empty grammar
     */
  public Grammar() {
    myRules = new Vector();
  }
  
    /** 
     * copy constructor
     */
  public Grammar(Grammar copy) {
    myStartLetter = new Variable(copy.getStart().getContents());
    myRules = new Vector();
    Rule r;
    for(Enumeration e = copy.getRules().elements(); e.hasMoreElements(); ) {
      r = (Rule) e.nextElement();
      myRules.addElement(new Rule(r));
    }
  }


    /**
     * sets the start symbol
     */
    public void setStart (Variable v){
	myStartLetter = v;
    }

    /**
     * gets the start symbol
     */
    public Variable getStart() {
	return myStartLetter;
    }

    /**
     * adds the given rule to the grammar
     */
    public void addRule(Rule r) {
	myRules.addElement(r);
    }

    /**
     * Turns the grammar into a string
     */
    public String toString() {
	String result = new String();
	Enumeration e;
	
	for(e = myRules.elements(); e.hasMoreElements(); ) 
	    result += ((Rule) e.nextElement()).toString() + "\n";

	return result;
    }

    /**
     * draws the grammar on the graphics (with colors)
     */
    public void draw(Graphics g) {
	
	Enumeration e;
	int x = 3;
	int newX;
	int y;
	Rule r;
	FontMetrics fm = g.getFontMetrics();
	int h = fm.getAscent();
	y = h+5;

	for(e = myRules.elements(); e.hasMoreElements(); ) {
	    r = (Rule) e.nextElement();
	    newX = r.draw(g, x, y);
	    y+=h + 3;
	    maxX = Math.max(newX, maxX);
	}
	maxY = y;
    }
  
    /**
     * transforms a string into a grammar.
     * assuming capitals are Variables for conversion. only letters allowed.
     */
  public void readString(String text) throws BadInputException {
    int lines = 0;
    try {
      StringReader sr = new StringReader(text);
      BufferedReader br = new BufferedReader(sr);
      
      String line = br.readLine();
      while(line != null) {
        lines++;
        addRule(new Rule(line));
        line = br.readLine();
      }    
    }
    catch(IOException h) {
      throw new BadInputException("\n\nOn line " + lines + ":\nInvalid grammar format.");
    }
    catch(BadInputException h) {
      throw new BadInputException("\n\nOn line " + lines + ":\n" + h.getMessage()); }
  }
  
  
  
    /**
     * turns the grammar into a string that can be saved in a file
     * precondition: start symbol on the left of first rule. if this is not
     * met the order of the rules will be changed.
     */
  public String toSaveString() throws BadInputException {
    String result = "";
    Enumeration e;
    Rule r;
    boolean found = false;
    for(e = myRules.elements(); e.hasMoreElements(); ) {
      r = (Rule) e.nextElement();
      if(r.getLeftHand().getContents().trim().equals(myStartLetter.getContents().trim())){
        myRules.removeElement(r);
        myRules.insertElementAt(r,0);
        found = true;
        break;
      }
    }
    
    if(!found)
      throw new BadInputException("The start symbol is not used.");
    
    for(e = myRules.elements(); e.hasMoreElements(); ) {
      r = (Rule) e.nextElement();
      result += r.toString() + "\n";
    }


    return result;
  }
  
  
    /** 
    * Sorts all the rules in lexicographical order (whow, Steve is right, once you 
    * use the word 'lexicographical' once you just can't go back to 'alphabetical'
    * anymore) and then puts all the rules of the start symbol at the beginning.
    */
  public void sortRules()     {    
    Rule aRule;
    VectorArray arr = new VectorArray(myRules);

    Sorting.sort(arr, new RuleSorter());

    while(myRules.size() > 0)
      myRules.removeElementAt(0);

    for(Enumeration e = arr.elements(); e.hasMoreElements(); ) {
      aRule = (Rule) e.nextElement();
      if(aRule.getLeftHand().getContents().equals(myStartLetter.getContents())) 
	myRules.addElement(aRule);
    }
    
    for(Enumeration e = arr.elements(); e.hasMoreElements(); ) {
      aRule = (Rule) e.nextElement();
      if(!aRule.getLeftHand().getContents().equals(myStartLetter.getContents())) 
	myRules.addElement(aRule);
    }
  }

    /**
     * returns the vector of rules
     */
    public Vector getRules() {
	return myRules;
    }


    /**
     * finds a good size for displaying this grammar
     */ 
    public Point bestSize() {
	return new Point(maxX+10, maxY+5);
    }


    /**
     * Finds all terminals in the grammar and returns them in a vector.
     * This basically gives you the terminal alphabet. (but not sorted)
     */
    public Vector findAllTerminals() {
	
      Vector answer = new Vector();
      
      Enumeration e, e2, e3;
      Rule ru;
      GrammarRightHandToken var;
      boolean skip = false;
      
      for(e = myRules.elements(); e.hasMoreElements(); ) {
        ru = (Rule) e.nextElement();
        for(e2 = ru.getRightHand().elements(); e2.hasMoreElements(); ) {
          var = (GrammarRightHandToken) e2.nextElement();
          if(var instanceof Terminal) {
            skip = false;
            for(e3 = answer.elements(); e3.hasMoreElements(); ) {
              if(((Terminal) e3.nextElement()).getContents().equals(var.getContents())) {
                skip = true;  
              }
            }
            if(!skip)
              answer.addElement(var);
          }
        }
      }
      return answer;
    }

    /**
     * Finds all symbols in the grammar and returns them in a Vector
     */
  public Vector findAllSymbols() {

    Vector answer = new Vector();
    
    Enumeration e, e2, e3;
    Rule ru;
    GrammarRightHandToken var, var2;
    boolean skip = false;
    
    for( e = myRules.elements(); e.hasMoreElements(); ) {
      ru = (Rule) e.nextElement();

      var = (GrammarRightHandToken) ru.getLeftHand();
      for(e3 = answer.elements(); e3.hasMoreElements(); ) {        
        var2 = (GrammarRightHandToken) e3.nextElement();
        if(var2.getContents().equals(var.getContents()) && 
           var.getType().equals(var2.getType()))
          skip = true;
      }
      if(!skip)
        answer.addElement(var);
    
      for(e2 = ru.getRightHand().elements(); e2.hasMoreElements(); ) {
        var = (GrammarRightHandToken) e2.nextElement();
        skip = false;
        for(e3 = answer.elements(); e3.hasMoreElements(); ) {
          var2 = (GrammarRightHandToken) e3.nextElement();
          if(var2.getContents().equals(var.getContents()) && 
             var.getType().equals(var2.getType()))
            skip = true;
        }
        if(!skip)
          answer.addElement(var);
      }
    }
    return answer;
  }


    /**
     * Finds all Variables in the grammar and returns them in a Vector
     */
  public Vector findAllVariables() {

    Vector answer = new Vector();
    
    Enumeration e, e2, e3;
    Rule ru;
    GrammarRightHandToken var, var2;
    boolean skip = false;
    
    for( e = myRules.elements(); e.hasMoreElements(); ) {
      ru = (Rule) e.nextElement();

      var = (GrammarRightHandToken) ru.getLeftHand();
      for(e3 = answer.elements(); e3.hasMoreElements(); ) {        
        var2 = (GrammarRightHandToken) e3.nextElement();
        if(var2.getContents().equals(var.getContents()))
          skip = true;
      }
      if(!skip)
        answer.addElement(var);
    
      for(e2 = ru.getRightHand().elements(); e2.hasMoreElements(); ) {
        var = (GrammarRightHandToken) e2.nextElement();
        if(! (var instanceof Variable))
          continue;
        skip = false;
        for(e3 = answer.elements(); e3.hasMoreElements(); ) {
          var2 = (GrammarRightHandToken) e3.nextElement();
          if(var2.getContents().equals(var.getContents()))
            skip = true;
        }
        if(!skip)
          answer.addElement(var);
      }
    }
    return answer;
  }

  
    /**
     * simplifies the grammar. i.e, turns the grammar into a version of it that
     * a grammarinputWindow would accept for example. 
     * terminals are lower case letters. variables are uppercase letters.
     * throws a badinputexception if the grammar has more than 26 variables or
     * terminals.
     *
     * Returns a vector of String[2] arrays containing the remapped terminal
     * symbols and what they were remapped to
     */
     
  public Vector simplify() throws BadInputException {

    Enumeration e, e2;
    Rule r;
    char currentVar = 'A';
    char currentTerm = 'a';
    String aString;
    GrammarRightHandToken right;
    Vector retVect = new Vector();

    if(findAllTerminals().size() > 26) 
      throw new BadInputException("This grammar cannot be converted:\n it has more than 26 terminals.");
    if(findAllVariables().size() > 25) //'I' is not allowed 
      throw new BadInputException("This grammar cannot be converted:\n it has more than 26 variables.");

    //iterate hgrough grammar. everytime one invalid is found, replace all with correct
    for(e = myRules.elements(); e.hasMoreElements();) {
      r = (Rule) e.nextElement();
      aString = r.getLeftHand().getContents();
      if(aString.length() != 1 || !Character.isLetter(aString.charAt(0)) || 
         !Character.isUpperCase(aString.charAt(0)))
      {
        currentVar = nextVar(currentVar);
        doReplace(r.getLeftHand(), currentVar);
      }
      for(e2 = r.getRightHand().elements(); e2.hasMoreElements(); ) {
        right = (GrammarRightHandToken) e2.nextElement();
        aString = right.getContents();
        if(right instanceof Variable) {
          if(aString.length() != 1 || !Character.isLetter(aString.charAt(0)) ||
             !Character.isUpperCase(aString.charAt(0)))
	  {
	    currentVar = nextVar(currentVar);
            doReplace(right, currentVar);
          }         
        }
        else if (right instanceof Terminal) {
          if(aString.length() != 1 || !Character.isLetter(aString.charAt(0)) ||
             !Character.isLowerCase(aString.charAt(0)))
	  {
	     currentTerm = nextTerm(currentTerm);
	     String[] temp = new String[2];
	     temp[0] = new String(right.getContents());
	     temp[1] = currentTerm + "";
	     retVect.addElement(temp);
             doReplace(right, currentTerm);
          }
        }
      }
    }

    return retVect;
  }

  protected char nextVar (char currentVar) {

    Vector v = findAllVariables();
    boolean okay = false;
    String nextVar;

    nextVar = currentVar + "";
    boolean found = false;
    for(Enumeration e = v.elements(); e.hasMoreElements(); )
    {
      if(((Variable) e.nextElement()).getContents().trim().equals(nextVar))
      {
        found = true;
      }
    }
    if(!found)
    {
       return currentVar;
    }

    while(!okay)
    {
      nextVar = (++currentVar) + "";
      okay = true;
      for(Enumeration e = v.elements(); e.hasMoreElements(); )
      {
        if(((Variable) e.nextElement()).getContents().trim().equals(nextVar))
          okay = false;
      }
      if(currentVar == 'I')
	 okay = false;
    }
    return currentVar;
  }

  protected char nextTerm (char currentVar)
  {
    Vector v = findAllTerminals();
    boolean okay = false;
    String nextVar;

    nextVar = currentVar + "";
    boolean found = false;
    for(Enumeration e = v.elements(); e.hasMoreElements(); )
    {
      if(((Terminal) e.nextElement()).getContents().trim().equals(nextVar))
      {
        found = true;
      }
    }
    if(!found)
    {
       return currentVar;
    }

    while(!okay) {
      nextVar = (++currentVar) + "";
      okay = true;
      for(Enumeration e = v.elements(); e.hasMoreElements(); ) {
        if( ((Terminal) e.nextElement()).getContents().trim().equals(nextVar))
          okay = false;
      }
    }
    return currentVar;
  }


    /** 
     * helper function for simplify() 
     */
  protected void doReplace(GrammarRightHandToken grt, char letter)
  {

    String repMe = grt.getContents(); 
    String repBy = letter + "";
    Enumeration e, e2;
    Variable var;
    Rule r;
    GrammarRightHandToken grht;

    if(grt instanceof Variable && myStartLetter.getContents().equals(repMe)) 
      myStartLetter.setContents(repBy);

    for(e = myRules.elements(); e.hasMoreElements(); )
    {
      r = (Rule) e.nextElement(); 
      var = r.getLeftHand();
      if(var.getType().equals(grt.getType()) && var.getContents().equals(repMe)) 
        var.setContents(repBy);
      for(e2 = r.getRightHand().elements(); e2.hasMoreElements(); )
      {
        grht = (GrammarRightHandToken) e2.nextElement();
        if(grht.getType().equals(grt.getType()) && grht.getContents().equals(repMe))
          grht.setContents(repBy);
      }
    }
  }

}
