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

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

/**
 * RegExpUtilities is a set of functions used on regular expressions
 * in general
 */

public class RegExpUtilities 
{
   /**
    * sorts all of the expressions recursively based on
    * ORed expressions so that lambdas are at the ends and
    * the rest are alphabetical and removes repeated values
    */
   public static String sortExpressions(String exp)
   {
      Vector vect = sortExpressionsVect(exp);
      String result = "";
      for(Enumeration e = vect.elements(); e.hasMoreElements(); )
      {
         result += (String) e.nextElement() + "+";
      }
      if(result.charAt(result.length() - 1) == '+')
         result = result.substring(0, result.length() - 1);
      return result;
   }

   /**
    * sorts all of the expressions recursively based on
    * ORed expressions so that lambdas are at the ends and
    * then returns the vector and removes repeated values
    */
   public static Vector sortExpressionsVect(String exp)
   {
      String newexp = new String(exp);
      String temp;
      int lastpos = 0;
      int parenthlevel = 0;
      Vector vect = new Vector();

      //recursively call until no parenthesis are found
      for(int x = 0; x < newexp.length(); ++x)
      {
         switch(newexp.charAt(x))
         {
         case '(':
            ++parenthlevel;
            if(parenthlevel == 1)
               lastpos = x;
            break;
         case ')':
            if(parenthlevel == 1)
            {
               temp = sortExpressions(newexp.substring(lastpos + 1, x));
               newexp = newexp.substring(0, lastpos + 1) +
                        temp +
                        newexp.substring(x, newexp.length());
            }
            --parenthlevel;
            break;
         }
      }

      parenthlevel = 0;
      vect.removeAllElements();
      lastpos = 0;
      for(int x = 0; x < newexp.length(); ++x)
      {
         switch(newexp.charAt(x))
         {
         case '(':
            ++parenthlevel;
            break;
         case ')':
            --parenthlevel;
            break;
         case '+':
            if(parenthlevel == 0)
            {
               if(lastpos != 0)
                  vect.addElement(newexp.substring(lastpos + 1, x));
               else
                  vect.addElement(newexp.substring(0, x));
               
               lastpos = x;
            }
         }
      }

      if(lastpos != 0)
         vect.addElement(newexp.substring(lastpos + 1, newexp.length()));
      else
         vect.addElement(newexp);

      Sorting.sort(vect, new RegExpSorter());

      //remove repetitions
      String lastexp = "";
      for(int x = 0; x < vect.size(); ++x)
      {
         temp = (String) vect.elementAt(x);
         if(temp.equals(lastexp))
         {
            vect.removeElementAt(x);
            --x;
         }
         lastexp = temp;
      }

      return vect;
   }

   /**
    * Minimizes the number of parenthesis in a given expression
    */
   public static String minimizeParenthesis(String str)
   {
      String exp = new String(str);
      Stack beginIndices = new Stack();
      int curpos = 0;

      if(str.length() <= 2)
         return new String(str);

      while(curpos < exp.length())
      {
	 //find all the beginning parenthesis and push them onto the stack
	 while(curpos < exp.length() && exp.charAt(curpos) != ')')
	 {
	    if(exp.charAt(curpos) == '(')
	    {
	       beginIndices.push(new Integer(curpos));
	    }
	    ++curpos;
	 }

	 //pop the index of the begin parenthesis and figure out
	 //whether to remove them or not
	 if(!beginIndices.isEmpty())
	 {
	    int index = ((Integer) beginIndices.pop()).intValue();
	    String temp = exp.substring(index + 1, curpos);
	    	    
	    if(temp.length() > 0 && temp.charAt(0) == '(' && 
	       temp.charAt(temp.length() - 1) == ')')
	    {
	       if(!findUnionOp(temp))
               {  // (( )( )) or (( ))
		  if(curpos + 1 < exp.length())
		  {
		     exp = exp.substring(0, index) + temp + 
			exp.substring(curpos + 1, exp.length());
		  }
		  else
		  {
		     exp = exp.substring(0, index) + temp;
		  }
		  curpos -= 2;
	       }
	       else if(findUnionOp(temp) &&
		  (index == 0 || temp.charAt(index - 1) == '+') &&
		  (curpos + 1 > exp.length() - 1 || exp.charAt(curpos + 1) == '+'))
	       {// (( )+( )) or ( )+( )
		  if(curpos + 1 < exp.length())
		  {
		     exp = exp.substring(0, index) + temp + 
			exp.substring(curpos + 1, exp.length());
		  }
		  else
		  {
		     exp = exp.substring(0, index) + temp;
		  }
		  curpos -= 2;
	       }
	    }
	    // ( + ) or ( )
	    else if(index == 0 && curpos == exp.length() - 1)
	    {
	       if(curpos + 1 < exp.length())
	       {
		  exp = exp.substring(0, index) + temp + 
		     exp.substring(curpos + 1, exp.length());
	       }
	       else
	       {
		  exp = exp.substring(0, index) + temp;
	       }
	       curpos -= 2;
	    }
	    // +( + )+
	    else if((index == 0 ||
	       exp.charAt(index - 1) == '+' || 
	       exp.charAt(index - 1) == '(') &&
	       (curpos + 1 > exp.length() - 1 ||
	       exp.charAt(curpos + 1) == '+' ||
	       exp.charAt(curpos + 1) == ')'))
	    {
	       if(curpos + 1 < exp.length())
	       {
		  exp = exp.substring(0, index) + temp + 
		     exp.substring(curpos + 1, exp.length());
	       }
	       else
	       {
		  exp = exp.substring(0, index) + temp;
	       }
	       curpos -= 2;
	    }
	    else if(!findUnionOp(temp) &&
	       (curpos + 1 > exp.length() - 1 ||
	       exp.charAt(curpos + 1) != '*'))
	    {
	       if(curpos + 1 < exp.length())
	       {
		  exp = exp.substring(0, index) + temp + 
		     exp.substring(curpos + 1, exp.length());
	       }
	       else
	       {
		  exp = exp.substring(0, index) + temp;
	       }
	       curpos -= 2;
	    }
	    else if(temp.length() == 1)
	    {
	       if(curpos + 1 < exp.length())
	       {
		  exp = exp.substring(0, index) + temp + 
		     exp.substring(curpos + 1, exp.length());
	       }
	       else
	       {
		  exp = exp.substring(0, index) + temp;
	       }
	       curpos -= 2;
	    }
	 }

	 ++curpos;
      }

      return exp;
   }

   /**
    * finds out whether the Union '+' is found in the
    * expression without parenthesis around it.
    */
   private static boolean findUnionOp(String str)
   {
      int numParenth = 0;
      int low = 10;

      //find all the beginning parenthesis and push them onto the stack
      for(int x = 0; x < str.length(); ++x)
      {
	 switch(str.charAt(x))
	 {
	 case '(': 
	    ++numParenth;
	    break;
	 case ')':
	    --numParenth;
	    break;
	 case '+':
	    if(numParenth == 0)
	       return true;
	    break;
	 }
      }

      return false;
   }

   /**
    * removes the '!' epsilons in a string from the
    * current parenthesis level. For example a+!+b(a+!) -> a+b(a+!)
    */
   public static String removeEpsilons(String str)
   {
       String retstr = new String(str);
       int parenthlevel = 0;
       int begin;
       int end;
       for(int pos = 0; pos < retstr.length(); ++pos)
       {
          switch(retstr.charAt(pos))
          {
          case '(':
             ++parenthlevel;
             break;
          case ')':
             --parenthlevel;
             break;
          case '!':
             if(parenthlevel == 0)
             {
                begin = pos;
                end = pos + 1;
                if((pos - 1) >= 0 && retstr.charAt(pos - 1) == '+')
                   --begin;
                if((pos + 1) < retstr.length() && retstr.charAt(pos + 1) == '+')
                   ++end;

                if(begin != pos && end != pos + 1)
                {
                  retstr = retstr.substring(0, begin) + "+" +
                     retstr.substring(end, retstr.length());
                }
                else
                {
                  retstr = retstr.substring(0, begin) +
                     retstr.substring(end, retstr.length());
                }

                //rescan the whole string
                pos = 0;
             }
             break;
          }
       }

       return retstr;
   }
}

