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

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

//
//
// RegExpExpression
//
//

import java.util.*;

/**
 * Acts as a node in a tree that holds all of the
 * expressions in the regular 
 */
public class RegExpNode
{
   public RegExpNode R1 = null;
   public RegExpNode R2 = null;
   public RegExpNode R3 = null;
   public RegExpNode R4 = null;
   public RegExpNode prevnode = null;
   public int i;
   public int j;
   public int k;

   /**
    *  tells which part this expression represents
    *  inside of the expression one level up.
    *  It should equal 0,1,2,3,4
    *  0 is the top node
    */
   public int exppart;

   public String expression = null;
   public String simplified = null;

   public RegExpNode(int start, int end, int max, int part)
   {
      i = start;
      j = end;
      k = max;
      exppart = part;
   }

   /**
    * returns the value of the expression in unexpanded form
    * or its value if it is a leaf node
    */
   public String getUnexpandedExp()
   {
      if(R1 == null ||
	 R2 == null ||
	 R3 == null ||
	 R4 == null)
	 return new String(expression);

      return new String(R1 + " + " + R2 + " " + R3 + "* " + R4);
   }

   /**
    * returns the expanded expression for this node
    */
   public String getExpandedExp()
   {
      if(R1 == null ||
	 R2 == null ||
	 R3 == null ||
	 R4 == null)
	 return new String(expression);

      String strR1 = R1.getSimplifiedExpRec();
      String strR2 = R2.getSimplifiedExpRec();
      String strR3 = R3.getSimplifiedExpRec();
      String strR4 = R4.getSimplifiedExpRec();

      return RegExpUtilities.minimizeParenthesis("(" + strR1 + ")+(" +
	        strR2 + ")(" +
	        strR3 + ")*(" +
	        strR4 + ")");
   }

   /**
    *  returns the simplified expression for this node
    */
   public String getSimplifiedExp()
   {
      if(simplified == null)
      {
	 simplified = getSimplifiedExpRec();
      }

      return new String(simplified);
   }

   /**
    * recursive function to produce the simplified expression
    * for this node
    */
   public String getSimplifiedExpRec()
   {
      if(simplified != null)
	  return new String(simplified);

      if(R1 == null ||
	 R2 == null ||
	 R3 == null ||
	 R4 == null)
      {
	 return RegExpUtilities.sortExpressions(expression);
      }

      //Use local variables so nodes below
      //tree are not disturbed
      String strR1 = R1.getSimplifiedExpRec();
      String strR2 = R2.getSimplifiedExpRec();
      String strR3 = R3.getSimplifiedExpRec();
      String strR4 = R4.getSimplifiedExpRec();

      //remove the empty set in the special case
      if(strR1.equals("!+{}"))
      {
	 strR1 = "!";
      }
      if(strR2.equals("!+{}") || strR2.equals("!"))
      {
	 //!bc = bc
	 strR2 = "";
      }
      if(strR3.equals("!+{}") || strR3.equals("!"))
      {
	 //a!*b = ab
	 //allow the simplification down the line to
	 //remove the R3 term for you
	 strR3 = "{}";
      }
      if(strR4.equals("!+{}") || strR4.equals("!"))
      {
	 //ab! = ab
	 strR4 = "";
      }
      if(strR2.equals("") && strR3.equals("{}") && strR4.equals(""))
      {
	 //a+!!*! = a+!
	 return "!+" + strR1;
      }

      //remove lambdas from Kleene starred expression
      Vector vect = RegExpUtilities.sortExpressionsVect(strR3);
      if(vect.size() > 0 && ((String) vect.elementAt(0)).equals("!"))
         vect.removeElementAt(0);
      if(vect.size() > 0)
      {
         strR3 = "";
         for(Enumeration e = vect.elements(); e.hasMoreElements(); )
         {
            strR3 += (String) e.nextElement() + "+";
         }
         if(strR3.charAt(strR3.length() - 1) == '+')
            strR3 = strR3.substring(0, strR3.length() - 1);
      }
      else
      {
         strR3 = "{}";
      }

      if(strR2.equals("!+" + strR3))
      {  // (!+x)x* = x*
         strR2 = "";
      }
      if(strR4.equals("!+" + strR3))
      {  // x*(!+x) = x*
         strR4 = "";
      }

      //if the second term falls out
      //a+bc*{} = a
      //a+{}b*c = a
      if(strR2.equals("{}") || strR4.equals("{}"))
      {
	 return strR1;
      }
      else if(strR1.equals("{}"))
      {
	 //{}+a{}*c
	 if(strR3.equals("{}"))
	 {
	    return RegExpUtilities.sortExpressions(
               RegExpUtilities.minimizeParenthesis("(" + strR2 + ")(" + strR4 + ")"));
	 }
	 else
	 {
	    //{}+ab*c
	    return RegExpUtilities.sortExpressions(
               RegExpUtilities.minimizeParenthesis("(" + strR2 + ")(" + strR3 + ")*(" + strR4 + ")"));
	 }
      }
      else if(strR3.equals("{}"))
      {
	 //if the third term (Kleene Star) falls out
	 if(strR1.equals(strR2 + strR4))
	    return strR1;
	 return RegExpUtilities.sortExpressions(
            RegExpUtilities.minimizeParenthesis("(" + strR1 + ")+(" + strR2 + ")(" + strR4 + ")"));
      }

      //b+a*b = a*b
      if(strR1.equals(strR4) && strR2.equals(""))
      {
         return RegExpUtilities.sortExpressions(
               RegExpUtilities.minimizeParenthesis("(" + strR3 + ")*(" + strR1 + ")"));
      }

      //a+ab* = ab*
      if(strR1.equals(strR2) && strR4.equals(""))
      {
         return RegExpUtilities.sortExpressions(
               RegExpUtilities.minimizeParenthesis("(" + strR1 + ")(" + strR3 + ")*"));
      }

      if(strR1.equals(strR2 + strR3 + "*" + strR4))
         return strR1;

      return RegExpUtilities.sortExpressions(RegExpUtilities.minimizeParenthesis("(" + strR1 + ")+(" +
         strR2 + ")(" +
         strR3 + ")*(" +
         strR4 + ")"));
   }

   /**
    * used to determine equality
    */
   public boolean equals(Object obj)
   {
      if(((RegExpNode)obj).i == i &&
	 ((RegExpNode)obj).j == j &&
	 ((RegExpNode)obj).k == k)
      {
	 return true;
      }

      return false;
   }

   /**
    * used to return a string identifying this node
    */
   public String toString()
   {
      return new String("R(" + i + ", " + j + ", " + k + ")");
   }
}

