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

/* 
 * 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.awt.event.*;

/**
  * This is the class that handles converting an PDA to a grammar.
  */ 
public class PDAToGrammar extends ToGrammar
{
  private int curTransIndex;
  private Grammar answer;
  private boolean processed;
  private boolean firststate;
  private State finalState;
  private ToGrammarDialog dg;

  public PDAToGrammar(Desktop desk, ToGrammarDialog dial) throws BadInputException
  {
     super(desk);

     dg = dial;
     checkCorrect(desk);

     finalState = null;
     State aState;
     for(Enumeration e = d.theStates.elements(); e.hasMoreElements(); )
     {
       aState = (State) e.nextElement();
       if(aState.isFinal)
         finalState = aState;
     }
     answer = new Grammar();
     answer.setStart(new Variable("S"));
     Rule r = new Rule();
     r.setLeft(new Variable("S"));
     r.addRight(new Variable("q"+d.initialState.id+"Zq"+ finalState.id));
     answer.addRule(r); 

     d.selectedState = null;
     d.selectedTransition = null;

     curTransIndex = 0;
     processed = false;
     firststate = true;
  }

  /**
   * checks if the PDA can be turned into a grammar. (i.e. only 1 final
   * state and transitions in proper format
   */
  public void checkCorrect(Desktop desk) throws BadInputException
  {
    State aState;
    Transition aTransition;
    int i = 0;
    for(Enumeration e = d.theStates.elements(); e.hasMoreElements();)
    {
      aState = (State) e.nextElement();
      if(aState.isFinal)
        i++;
    }
    if(i != 1)
      throw new BadInputException(
         "\nThere must be exactly one" +
         "\nfinal state to convert this PDA" +
         "\ninto a grammar.");

    for(Enumeration e = d.theTransitions.elements(); e.hasMoreElements();)
    {
      aTransition = (Transition) e.nextElement();
      aTransition.tokenizeLabel();
      if(aTransition.sublabel[1].trim().length() == 1 &&
         aTransition.sublabel[2].trim().length() == 0)
        continue;
      if(aTransition.sublabel[1].trim().length() == 1 &&
         aTransition.sublabel[2].trim().length() == 2)
        continue;

      aTransition.st = Transition.HIGHLIGHTED;
      d.selectedState = null;
      d.selectedTransition = null;
      throw new BadInputException(
         "\nThe highlighted transition must be" + 
         "\nin the format: \"a;A; \" or \"a,A;BC\"" +
         "\n to convert this PDA into a grammar." +
         "\nSee HELP under \"Grammar Conversion.\"");
    }
  }

  /**
   * does msot of the work. if something goes wrong, Badinputexception 
   * will be thrown
   */
  public Grammar toGramm() throws BadInputException
  {
    if(processed)
       return answer;
    else
       processed = true;

    Enumeration e, e2, e3;

    Rule r;
    Variable leftHand;

    Transition aTransition;
    String nameFrom, nameTo, label1, label2, label3;
    State aState2, aState3;
    boolean first;

    for(e = d.theTransitions.elements(); e.hasMoreElements(); )
    {
      aTransition = (Transition) e.nextElement();
      aTransition.tokenizeLabel();
      nameFrom = "q" + aTransition.from.id;
      nameTo = "q" + aTransition.to.id ;
      label1 = aTransition.sublabel[0].trim();
      label2 = aTransition.sublabel[1].trim();
      label3 = aTransition.sublabel[2].trim();

      if(aTransition.sublabel[2].trim().length() == 0)
      {
        r = new Rule();
        r.setLeft(new Variable(nameFrom+label2+nameTo));
        if(label1.trim().length() > 0)
          r.addRight(new Terminal(label1));
        else
          r.addRight(new Lambda(""));
        answer.addRule(r);
      }
      else
      {
        first = true;
        for(e2 = d.theStates.elements(); e2.hasMoreElements(); )
	{
          aState2 = (State) e2.nextElement();

          for(e3 = d.theStates.elements(); e3.hasMoreElements(); )
	  {
            aState3 = (State) e3.nextElement();
           
            r = new Rule();
            r.setLeft( new Variable(nameFrom + label2 + "q" + aState3.id));
            if(!label1.equals(""))
	       r.addRight(new Terminal(label1));
            r.addRight(new Variable(nameTo+label3.charAt(0) + "q" + aState2.id));
            r.addRight(new Variable("q" + aState2.id + label3.charAt(1) + "q" + aState3.id));
            answer.addRule(r);
            if(first)
	    {
              first = false;
            }
          }
        }
      }
    }

    return answer;
  }

  public Vector stepNext()
  {
      Rule r;
      Vector vect = new Vector();
      if(firststate)
      {	 
	 dg.setMessage(ToGrammarDialog.STATE);
	 firststate = false;
	 r = new Rule();
	 r.setLeft(new Variable("S"));
         r.addRight(new Variable("q"+d.initialState.id+"Zq"+ finalState.id));
	 d.initialState.ss = State.FOCUSED;
         vect.addElement(r);
	 return vect;
      }
      dg.setMessage(ToGrammarDialog.TRANSITION);
      if(curTransIndex >= d.theTransitions.size())
	return null;

      Enumeration e, e2, e3;
      
      Variable leftHand;

      String nameFrom, nameTo, label1, label2, label3;
      State aState2, aState3;
      Transition aTransition = (Transition)(d.theTransitions.elementAt(curTransIndex));
      boolean first;
      aTransition.tokenizeLabel();
      nameFrom = "q" + aTransition.from.id;
      nameTo = "q" + aTransition.to.id ;
      label1 = aTransition.sublabel[0].trim();
      label2 = aTransition.sublabel[1].trim();
      label3 = aTransition.sublabel[2].trim();

      if(aTransition.sublabel[2].trim().length() == 0)
      {
        r = new Rule();
        r.setLeft(new Variable(nameFrom+label2+nameTo));
        if(label1.trim().length() > 0)
          r.addRight(new Terminal(label1));
        else
          r.addRight(new Lambda(""));
        vect.addElement(r);
      }
      else
      {
        first = true;
        for(e2 = d.theStates.elements(); e2.hasMoreElements(); )
	{
          aState2 = (State) e2.nextElement();

          for(e3 = d.theStates.elements(); e3.hasMoreElements(); )
	  {
            aState3 = (State) e3.nextElement();
           
            r = new Rule();
            r.setLeft( new Variable(nameFrom + label2 + "q" + aState3.id));
            r.addRight(new Terminal(label1));
            r.addRight(new Variable(nameTo+label3.charAt(0) + "q" + aState2.id));
            r.addRight(new Variable("q" + aState2.id + label3.charAt(1) + "q" + aState3.id));
	    vect.addElement(r);
            if(first)
	    {
              first = false;
            }
          }
        }
     }
     aTransition.st = Transition.HIGHLIGHTED;
     ++curTransIndex;
     
     //sort the results
     Sorting.sort(vect, new RuleSorter());
     return vect;
  }


}
