/*---------------------------------------------------------------------------
File:         			FSAToRegExp.java
Package:                        JFLAP Version 3.1
Author:			        Ted Hung
                                
Description of Contents:	Contains class FSAToRegExp.
				
--------------------------------------------------------------------------*/

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

//
//
// FSAToRegExp
//
//
public class FSAToRegExp
{
   /**
    * public function that returns a simplified regular expression
    * representing the NFA
    */
   public static String toRegExp(Desktop d) throws BadInputException
   {
      //make sure all of the intermediate states exist
      d.relabel();

      String answer = "";

      Vector ans = createTree(d);
      RegExpNode temp;
      for(Enumeration e = ans.elements(); e.hasMoreElements(); )
      {
	 temp = (RegExpNode) e.nextElement();
	 answer = answer + "+" + temp.getSimplifiedExp();
      }

      return answer;
   }

   /**
    * returns a Vector of RegExpNodes for each
    * final state. The RegExpNodes point to the
    * top of a tree which tells the forms of each expression 
    */
   public static Vector createTree(Desktop d)
   {
      //make sure all of the intermediate states exist
      d.relabel();

      Vector answer =  new Vector();

      //find the final states and make regular expressions
      //out of them
      State aState = null;
      int maxstate = d.theStates.size();
      RegExpNode temp;
      for(Enumeration e = d.theStates.elements(); e.hasMoreElements(); )
      {
	 aState = (State) e.nextElement();
	 if(aState.isFinal)
	 {
	    temp = Rtree(d.initialState.id, aState.id,
	       d.currentId, d, 0, null);
	    answer.addElement(temp);
	 }
      }
    
      if(answer.isEmpty())
	return null;
      return answer;
   }

   /**
    * recursive call that creates a tree of RegExpNodes
    */
   private static RegExpNode Rtree(int start, int end, 
      int max, Desktop d, int exppart, RegExpNode prev)
   {
      RegExpNode node = new RegExpNode(start, end, max, exppart);
      node.prevnode = prev;

      // if the max has been reduced to 1 apply
      // non recursive rules 
      if(max <= 0)
      {
	 node.R1 = null;
	 node.R2 = null;
	 node.R3 = null;
	 node.R4 = null;

	 Vector aTrans = findTransition(start, end, d);
	 String temp;
	 if(aTrans.isEmpty())
	 {
	    temp = new String("{}");
	 }
	 else
	 {
	    temp = "";
	    Transition trans;
	    for(Enumeration e = aTrans.elements(); e.hasMoreElements(); )
	    {
	       trans = (Transition) e.nextElement();
               if(trans.label.trim().equals(""))
                  temp += "!+";
               else
	          temp += trans.label.trim() + "+";
	    }
	    temp = temp.substring(0, temp.length() - 1);
	    int foundcomma = temp.indexOf(',');
	    temp = temp.replace(',', '+');
	 }

	 //remove white spaces
	 int pos = 0;
	 while(pos < temp.length())
	 {
	    if(temp.charAt(pos) == ' ')
	    {
	       temp = temp.substring(0, pos) + temp.substring(pos + 1, temp.length());
	    }
	    ++pos;
	 }

	 if(start != end && temp.length() > 0)
	 {
	    node.expression = temp;
	 }
	 else
	 {
	    if(temp.equals("") || temp.equals("{}"))
	    {
	       node.expression = "!";
	    }
	    else
	    {
               node.expression = temp + "+!";
	    }
	 }

	 return node;
      }

      node.expression = "R(" + Integer.toString(start) + " " + 
	              Integer.toString(end)   + " " + 
		      Integer.toString(max) + ")";

      //call recursive rules
      node.R1 = Rtree(start,   end,     max - 1, d, 1, node);
      node.R2 = Rtree(start,   max - 1, max - 1, d, 2, node);
      node.R3 = Rtree(max - 1, max - 1, max - 1, d, 3, node);
      node.R4 = Rtree(max - 1, end,     max - 1, d, 4, node);

      return node;
   }


   /**
    * finds the transition(s) that go from idfrom to idto
    * and returns them in a vector of transitions
    */
   private static Vector findTransition(int idfrom, int idto, Desktop d)
   {
      Vector retVect = new Vector();
      Transition aTrans;
      for(Enumeration e = d.theTransitions.elements(); e.hasMoreElements(); )
      {
	 aTrans = (Transition) e.nextElement();
	 if(aTrans.from != null && aTrans.from.id == idfrom &&
	    aTrans.to != null && aTrans.to.id == idto)
	 {
	    retVect.addElement(aTrans);
	 }
      }
      return retVect;
   }
}

