/*---------------------------------------------------------------------------
File:         			FSA.java
Package:                        JFLAP Version 2.0
Author:				Magda & Octavian Procopiuc V1.0 07/15/96
                                Eric Gramond V2.0 07/22/97 
 
Description of Contents:	Contains class FSA.
				
--------------------------------------------------------------------------*/

/* 
 * Susan H. Rodger, Magda Procopiuc, Octavian Procopiuc, Eric Gramond
 * Computer Science Department
 * Duke University
 * June 1998
 * Supported by National Science Foundation DUE-9596002 and DUE-9555084.
 *
 * Copyright (c) 1998
 * 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.*;

/**
 * This class simulates the behavior of a 
 * (non)deterministic finite state automaton.
 *
 * @author	Magda & Octavian Procopiuc
 * @version	1.0 15 July 1996
 */ 
public class FSA extends Machine {


  public static final String NO_UNREACHABLES_STR = 
   "There are no unreachable states \n in this machine.";

  public static final String FSA_CORRECT_STR = 
   "\n\nThe FSA is correct.";

  /** 
    * used to mark which state is the add3ed trap state in the minimize algorithm
    */
  public State trap;

  /**
    * Creates FSA corresponding to its desktop image.
    */
  public FSA(Desktop d) {
    super(d);
  }

  public FSA(FSA f) {
    super(f);
  }
  
/*
 * Creates a new configuration starting from configuration c, according
 * to the transition rule of a FSA 
 * Overrides Machine.expand()
 */
  boolean expand(Configuration c) {
    boolean willBeValid;
    Transition t;
    Configuration cc;

    String input, pop, push;

    willBeValid = false;
    for (Enumeration et=c.theState.transitions.elements(); et.hasMoreElements(); )   {
      t = (Transition) et.nextElement();
      if (c.theString.startsWith(t.label.trim())) {
        willBeValid = true;
        cc = new Configuration(t.to, c.theString.substring(t.label.trim().length()), c, this);
        if (!isAlreadyIn(temp, cc)) {
          temp.addElement(cc);
          nCurrentConfigs++;
          if (cc.isAccept()) {
            acceptInput = true;
            acceptingConfig = cc;
          }
        }        
      }
    }
    return willBeValid;
  }	// end of method expand.

/*
 * Creates the initial configuration.
 * Overrides Machine.initialConfig().
 */
  Configuration initialConfig() {
    return new Configuration(d.initialState, input, null, this);
  }     // end of method initialConfig

/*
 * Checks if a transition introduces non-determinism.
 * @param t	Transition to be checked.
 *        v	Vector of transitions against which t is checked.
 * @return	true if t does not introduce any non-determinism. 
 * Overrides Machine.isDeterministic().
 */
  boolean isDeterministic(Transition t, Vector v) {
    Enumeration e;
    Transition vt;

    if (v.size() == 0)
      return true;

    for (e = v.elements(); e.hasMoreElements(); ) {
      vt = (Transition) e.nextElement();
      if (t.label.equals(vt.label)) { 
        if (t.to != vt.to) 
           return false;
      } else if (substringRelation(t.label.trim(), vt.label.trim()))
          return false;    
    }

    return true;  
  }  // end of method isDeterministic



  /** 
    * finds all unreachable States, highlights them, and returns a String 
    *corresponding to the message to be printed by the Environment
    * Overrides Machine.showUnreachables()
    */
  public String showUnreachables() {
    Enumeration e;
    State aState;
    boolean found = false;

    if(d.initialState == null)
      return "\n\nThe machine has no initial state.";

    for(e = d.theStates.elements(); e.hasMoreElements(); )
      ((State) e.nextElement()).checkMark = 0;

    unreachableHelper(d.initialState);

    for(e = d.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      if(aState.checkMark == 0) {
	found = true;
	aState.ss = State.FOCUSED;
      }
    }
    if(!found)
      return NO_UNREACHABLES_STR;
    return "\n\nThe unreachable states are highlighted.";
  }

  /**
    * returns a Vector of all the reachable States in the graph.
    * Overrides Machine.findReachables()
    */
  public Vector findReachables() {
    State aState;
    Vector answer = new Vector();
    // Array temp;

    if(d.initialState == null)
      return answer;

    for(Enumeration e = d.theStates.elements(); e.hasMoreElements(); )
      ((State) e.nextElement()).checkMark = 0;

    unreachableHelper(d.initialState);

    for(Enumeration e = d.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      if(aState.checkMark == 1) {
	answer.addElement(aState);
      }
    }
    return answer;
  }

  /** recursive function for finding unreachable States. */
  private void unreachableHelper(State here) {
    Transition aTransition;
    here.checkMark = 1;
    for(Enumeration e = d.theTransitions.elements(); e.hasMoreElements(); ) {
      aTransition = (Transition) e.nextElement();
      if(aTransition.from == here && aTransition.to.checkMark == 0) 
	unreachableHelper(aTransition.to);
    }
  }

  //useful???
  private Vector mergeVectors(Vector number1, Vector number2) {
    for(Enumeration e = number2.elements(); e.hasMoreElements(); )
      number1.addElement(e.nextElement());
    return number1;
  }  
  
  /**
    * returns a vector of Characters corresponding to the alphabet of this machine.
    * the alphabet is in sorted order.
    * works only for FSA's
    */
  public Vector getAlphabet() {
    Vector alphabet = new Vector();
    Vector orList;
    String lab;
    Character letter;
    Enumeration e2, e3;
    boolean add;
    Transition aTransition;

    for (Enumeration e = d.theTransitions.elements(); e.hasMoreElements(); ) {
      aTransition  = (Transition) e.nextElement();
      for(e3 = aTransition.tokenizeOrList().elements(); e3.hasMoreElements(); ) {
	lab = (String) e3.nextElement();
	lab = lab.trim();
	if(lab.length() == 1) {
	  letter = new Character(lab.charAt(0));
	  add = true;
	  for( e2 = alphabet.elements(); e2.hasMoreElements(); ) {
	    if (( (Character) e2.nextElement()).equals(letter))
	      add = false;
	  }
	  if (add) 
	    alphabet.addElement(letter);
	}
      }
    }

    // sort the alphabet
    VectorArray arr = new VectorArray(alphabet);
    Sorting.sort( arr, new CharacterSorter());
    alphabet = new Vector();
    for ( Enumeration e = arr.elements(); e.hasMoreElements(); ) 
      alphabet.addElement( (Character) e.nextElement()); 

    return alphabet;
  }

  /** returns whether the FSA has any lambda productions or not.
    * Works only on FSA's
    */
  private boolean hasLambdas() {
    Transition aTransition;
    Enumeration e, e2;

    boolean result = false;
    for(e = d.theTransitions.elements(); e.hasMoreElements(); ) {
      aTransition = (Transition) e.nextElement();
      for(e2 = aTransition.tokenizeOrList().elements(); e2.hasMoreElements(); ) {
	if(((String) e2.nextElement()).trim().length() == 0) {
	  //d.selectedTransition = aTransition;
	  aTransition.st = Transition.HIGHLIGHTED;
	  result = true;
	}
      }
    }
    return result;
  }

  // ********************DFA building functions below here **************************************
  
  /** 
    * Builds the DFA associated with the passed NFA into this Machine . 
    */
  public void buildDfa(FSA NFA)  {

    Vector nodes = new Vector();
    int x = 50, y = 50;
    Vector alphabet = NFA.getAlphabet();

    d.initialState = d.addState(x, y);
    d.initialState.stateList = NFA.addLambdas(NFA.d.initialState);
    d.initialState.stateListToLabel();
    processDfaState(d.initialState, alphabet, NFA, x+50, y+50); 
    setDfaFinalStates();
  }


  /** 
    * Goes through a DFA and marks the appropriate final states given the 
    * equivalent NFA.   
    */
  private void setDfaFinalStates() {
    Enumeration e, e2;
    State aState, bState;

    for( e = d.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      for( e2 = aState.stateList.elements(); e2.hasMoreElements(); ) {
	bState = (State) e2.nextElement();
	if(bState.isFinal) {
	  aState.isFinal = true;
	  break;
	}
      }
    }
  }

  /**
    * find a state that matches the list of states passed
    */
  private State findMatchingState(Vector nodes) {
    State stat;
    Enumeration e2, e3;
    boolean found = false;

    for( Enumeration e = d.theStates.elements(); e.hasMoreElements(); ) {
      stat = (State) e.nextElement();
      e2 = stat.stateList.elements();
      e3 = nodes.elements();
      found = true;
      if(nodes.size() == stat.stateList.size()) {
	while(e2.hasMoreElements() && e3.hasMoreElements()) {
	  if( (State) e2.nextElement() != (State) e3.nextElement()) {
	    found = false;
	    break;
	  }
	}
	if(found == true)
	  return stat;
      }
    }
    return null;
  }


  /**
    * build 1 state and all the ones linked to it that are missing
    */
  private void processDfaState(State stat, Vector alphabet, FSA NFA, int x, int y) {
    char letter;
    Vector nodes;
    State newState;
    Enumeration e, e2;
    Transition aTransition;
    boolean found;
    Vector aVector;

    for (e = alphabet.elements(); e.hasMoreElements(); ) {
      letter = ((Character) e.nextElement()).charValue();
      nodes = NFA.leadsTo(stat.stateList, letter);
   
      //ignore trap states that were not present in original NFA
      if (nodes.size() != 0) {
	newState = findMatchingState(nodes);

	if(newState == null) {
	  newState = d.addState(x, y);
	  newState.stateList = nodes;
	  newState.stateListToLabel();
	  x+= 50;
	  y+= 50;
	  processDfaState(newState, alphabet, NFA, x+75, y);
	}
	found = false;
	for (e2 = d.theTransitions.elements(); e2.hasMoreElements(); ) { 
	  aTransition = (Transition) e2.nextElement();
	  if(aTransition.from == stat && aTransition.to == newState) {
	    found = true;
	    aVector = aTransition.tokenizeOrList();
	    aVector.addElement( ""+letter);
	    aTransition.setLabel(aVector);
	  }
	}
	if(!found)
        {
	  Transition trans = d.addTransition(stat, newState);
          trans.label = " " + letter;
          if(stat == newState)
          {
             newState.loopSize += Params._t_distance;
             newState.loopSize = Math.min(newState.p.y, newState.loopSize);
          }
        }
      }
    }
  }




  /** 
    * Returns the list of all nodes this set of nodes can lead to with the given letter
    * precondition: all nodes reachable from any of these nodes by a lambda transition
    * are already part of nodes.
    */
  public Vector leadsTo(Vector nodes, char letter) {
    Enumeration e, e2, e3;
    Vector list = new Vector();
    Transition transi;
    State stat;
    String lab;

    // get the list of nodes thru the letter
    for (e = nodes.elements(); e.hasMoreElements(); ) {
      stat = (State) e.nextElement();
      for (e2 = d.theTransitions.elements(); e2.hasMoreElements(); ) {
	transi = (Transition) e2.nextElement();
	if(transi.from == stat) {
	  for (e3 = transi.tokenizeOrList().elements(); e3.hasMoreElements(); ) {
	    lab = ((String) e3.nextElement()).trim();
	    if((lab.length() == 1) &&  (lab.charAt(0) == letter) && ! list.contains(transi.to)) {
	      list.addElement(transi.to);
	      break;
	    }
	  }
	}
      }
    }
    // get all nodes reachable from them by lambda prods
    for (e = list.elements(); e.hasMoreElements(); ) {
      stat = (State) e.nextElement();
      for (e2 = d.theTransitions.elements(); e2.hasMoreElements(); ) {
	transi = (Transition) e2.nextElement();
	if(transi.from == stat) {
	  for(e3 = transi.tokenizeOrList().elements(); e3.hasMoreElements(); ) {
	    if( ((String) e3.nextElement()).trim().length() == 0) {
	      if ( ! list.contains(transi.to))
		list.addElement(transi.to);
	      break;
	    }
	  }
	}
      }
    }
    VectorArray arr = new VectorArray(list);
    Sorting.sort( arr, stat = new State() );
    list = new Vector();
    for ( e3 = arr.elements(); e3.hasMoreElements(); ) 
      list.addElement( (State) e3.nextElement());
    return list;
  }

  /** Returns a list of all the states that this state can reach through lambda
    * transitions, which always includes itself    */
  private Vector addLambdas(State stat) {
    State aState;
    Transition aTransition;
    Vector nodes = new Vector();
    nodes.addElement(stat);
    Enumeration e, e2, e3;

    for ( e = nodes.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      for (e2 = d.theTransitions.elements(); e2.hasMoreElements(); ) {
	aTransition = (Transition) e2.nextElement();
	if((aTransition.from == aState) && (! nodes.contains(aTransition.to))) {
	  for(e3 = aTransition.tokenizeOrList().elements(); e3.hasMoreElements(); ) {
	    if ( ((String) e3.nextElement()).trim().length() == 0) {
	      nodes.addElement(aTransition.to);	
	     break;
	    }
	  }
	}
      }
    }

    VectorArray arr = new VectorArray(nodes);
    Sorting.sort( arr, stat );
    nodes = new Vector();
    for (e3 = arr.elements(); e3.hasMoreElements(); ) 
      nodes.addElement( (State) e3.nextElement());
    return nodes;
  }


  // ************************** checkdone functions below here ***************************

  /** 
    *returns the first transition that leaves from the given State with the given 
    * character as its label.
    * Does not work for lambda transitions.  
    */
  public Transition findTransition(State from, char trans) {
    Transition aTransition;
    char letter;
    String label;
    Enumeration e, e2;

    for (e = d.theTransitions.elements(); e.hasMoreElements(); ) {
      aTransition = (Transition) e.nextElement();
      for(e2 = aTransition.tokenizeOrList().elements(); e2.hasMoreElements(); ) {
	label = ((String) e2.nextElement()).trim();
	if(label.length() == 1) {
	  letter = label.charAt(0);
	  if(aTransition.from == from && letter == trans)
	    return aTransition;
	}
      }
    }
    return null;
  }
  
  /** 
    * returns the first lambda transition that leaves the passed State
    */
  public Transition findFirstLambda(State from) {
    Transition aTransition;

    for(Enumeration e = d.theTransitions.elements(); e.hasMoreElements(); ) {
      aTransition = (Transition) e.nextElement();
      if((aTransition.from == from) && (aTransition.label.trim().length() == 0))
	return aTransition;
    }
    return null;
  }




  /** 
    * compares the alphabet of this Desktop with that of the passed Desktop.
    */
  private String compareAlphabet(Machine dfa) {
    Vector dfalph = dfa.getAlphabet();
    Vector alph = getAlphabet();
    Character letter;

    for(Enumeration e = alph.elements(); e.hasMoreElements(); ) {
      letter = (Character) e.nextElement();
      if(dfalph.indexOf(letter) == -1) {
	return "The letter \"" +letter+ "\" is not in the FSA's alphabet.";
      }
    }
    return Environment.DFA_IS_CORRECT_STR;
  }


/**
 *   check to see if the regular grammar to FSa stuff is finished.
 */ 
  public String checkregtoFSADone(Machine model1) {
    
    Desktop model = model1.d;

    Enumeration e, e2, e3, e4;
    int i = 0, j=0;
    State aState, aState2= null, aState3 = null;
    Transition aTransition, aTransition2;

    for(e = d.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      if(aState.isFinal){
        if(!aState.label.trim().equals("")) {
          aState.ss = State.FOCUSED;
          return "Final states should have an empty label";
        }
        continue;
      }
      i++;
    }
    for(e = model.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      if(aState.isFinal)
        continue;
      j++;
    }
    if(i != j) 
      return "\nThere should be exactly " + j + "\nnon final states.";

    boolean found;
    for(e = d.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement(); 
      if(aState.isFinal)
        continue;
      if(aState.label.trim().length() == 0) {
        aState.ss = State.FOCUSED;
        return "\nThe highlighted state should not have \n an empty label.";
      }
      found = false;
      for (e2 = model.theStates.elements(); e2.hasMoreElements(); ) {
        aState2 = (State) e2.nextElement();
        if(aState2.label.trim().equals(aState.label.trim()))
           found = true; 
      }
      if(!found) {
        aState.ss = State.FOCUSED;
        return "\n\nThere should be no state labeled: " + aState.label;
      }
    }

    for(e = model.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement(); 
      if(aState.isFinal)
        continue;
      found = false;
      for (e2 = d.theStates.elements(); e2.hasMoreElements(); ) {
        aState2 = (State) e2.nextElement();
        if(aState2.label.trim().equals(aState.label.trim()))
          found = true; 
      }
      if(!found) 
        return "\n\nThere should be a state labeled: " + aState.label;
    }


    for(e = d.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      d.setTransitions(aState, true);      
    }
    for(e = model.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      model.setTransitions(aState, true);      
    }
    for(e = model.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      for(e2 = aState.transitions.elements(); e2.hasMoreElements(); ) {
        aTransition = (Transition) e2.nextElement();
        found = false;
        for( e3 = d.theStates.elements(); e3.hasMoreElements(); ) {
          aState2 = (State) e3.nextElement();
          if(aState2.label.trim().equals(aState.label.trim())) {
            aState3 = aState2;
            for(e4 = aState2.transitions.elements(); e4.hasMoreElements(); ) {
              aTransition2 = (Transition) e4.nextElement();
              if(aTransition2.to.label.trim().equals(aTransition.to.label.trim()) && aTransition.label.trim().equals(aTransition2.label.trim())) {
                found = true;
              }
            }
          }
        }
        if(!found) {
          aState3.ss = State.FOCUSED;
          return "\n\nThere should be a transition labeled:\n\"" + aTransition.label +
            "\" leaving from the highlighted state.";
        }
      }
    }

    for(e = d.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      for(e2 = aState.transitions.elements(); e2.hasMoreElements(); ) {
        aTransition = (Transition) e2.nextElement();
        found = false;
        for(e3 = model.theStates.elements(); e3.hasMoreElements(); ) {
          aState2 = (State) e3.nextElement();
          if(aState2.label.trim().equals(aState.label.trim())) {
            for(e4 = aState2.transitions.elements(); e4.hasMoreElements(); ) {
              aTransition2 = (Transition) e4.nextElement();
              if(aTransition2.to.label.trim().equals(aTransition.to.label.trim()) && aTransition.label.trim().equals(aTransition2.label.trim())) {
                found = true;
              }
            }
          }
        }
        if(!found) {
          aState.ss = State.FOCUSED;
          return "\n\nThere should be no transition labeled:\n\"" + aTransition.label +
            "\" leaving from the highlighted state.";
        }
      }
    }

    if(d.theTransitions.size() != model.theTransitions.size()) 
      return "\nThe machine is correct, \nbut there are duplicate transitions.";

    return FSA_CORRECT_STR;
  }


  /**
  *   check to see if the regular expression to FSa stuff is finished.
  */ 
  public String checkrextoFSADone(Machine model1)
  {
    
    Desktop model = model1.d;

    State aState;
    State compState;
    Vector outnodes = new Vector();
    Vector outnodescomp = new Vector();
    Enumeration enum;
    Enumeration e2;
    Transition atrans;
    Transition temptrans;
    boolean found; 

    for(Enumeration e = model.theStates.elements(); e.hasMoreElements(); )
    {
      aState = (State) e.nextElement(); 
      compState = d.getStateWithId(aState.id);

      if(compState == null)
      {
	 return "A state is missing.";
      }

      if(aState.isFinal != compState.isFinal)
      {
	 compState.ss = State.FOCUSED;
	 if(compState.isFinal)
	    return "The highlighted state\nshould not be final.";
	 else
	    return "The highlighted state\nshould be final.";
      }

      //get all of the transitions that leave 
      // the given state
      outnodes.removeAllElements();
      for(enum = model.theTransitions.elements(); enum.hasMoreElements(); )
      {
	 atrans = (Transition) enum.nextElement();
	 if(atrans.from.id == aState.id)
	 {
	    outnodes.addElement(atrans);
	 }
      }

      //get all of the transitions that leave 
      // the given state
      outnodescomp.removeAllElements();
      for(enum = d.theTransitions.elements(); enum.hasMoreElements(); )
      {
	 atrans = (Transition) enum.nextElement();
	 if(atrans.from.id == aState.id)
	 {
	    outnodescomp.addElement(atrans);
	 }
      }

      //check the number of transitions
      if(outnodescomp.size() < outnodes.size())
      {
	 compState.ss = State.FOCUSED;
	 return "A transition is missing from\nthe highlighted state.";
      }

      //check where the transitions go to.
      for(enum = outnodescomp.elements(); enum.hasMoreElements(); )
      {
	 atrans = (Transition) enum.nextElement();
	 found = false; 
	 for(e2 = outnodes.elements(); e2.hasMoreElements(); )
	 {
	    temptrans = (Transition) e2.nextElement();
	    if(atrans.to.id == temptrans.to.id &&
	       atrans.label.equals(temptrans.label))
	    {
	       found = true;
	       break;
	    }
	 }

	 if(!found)
	 {
	    atrans.st = Transition.HIGHLIGHTED;
	    return "The highlighted transition\nis mislabeled or misplaced.";
	 }
      }
    }

    if((model.initialState != null && d.initialState == null) ||
       (d.initialState.id != model.initialState.id))
    {
      State temp = d.getStateWithId(model.initialState.id);
      if(temp != null)
      {
	 temp.ss = State.FOCUSED;
	 return "Highlighted state should be\n initial state.";
      }
    }

    return FSA_CORRECT_STR;
  }

  /**  returns true if the Desktop matches the given dfa Desktop
    * Precondition: dfa is already a proper DFA.  
    * Works only on FSA's */
  public String checkIfDone(Machine adfa, Machine nfa) {
    
    Enumeration e2, e3;
    State aState, aState2;
    FSA dfa = (FSA) adfa;

    if(hasLambdas())
      return "Your DFA should not have any lambda \n transitions.";

    String error =  compareAlphabet(dfa); 
    if(error != Environment.DFA_IS_CORRECT_STR)
      return error;

    if(d.showDfaLabels) {
      error = convertLabels(nfa);
      if (error != Environment.DFA_IS_CORRECT_STR)
	return error;
    }

    if(d.showDfaLabels) {
      for(e3 = d.theStates.elements(); e3.hasMoreElements(); ) {
	aState2 = (State) e3.nextElement();
	for(e2 = d.theStates.elements(); e2.hasMoreElements(); ) {
	  aState = (State) e2.nextElement();
	  if(aState.compareLabel(aState2) && aState != aState2) {
	    aState.ss = State.FOCUSED;
	    aState2.ss = State.FOCUSED;
	    return "The highlighted states have identical labels.";
	  }
	}
      }
    }
    
    d.currentCheckMark = 0;
    
    if((d.showDfaLabels) && (! d.initialState.compareLabel(dfa.d.initialState))) {
	d.initialState.ss = State.FOCUSED; 
	return "The initial state should be labeled \"" + dfa.d.initialState.label + "\".";
    }

    error = Compareto(dfa, d.initialState, dfa.d.initialState, dfa.getAlphabet());
    if (error != Environment.DFA_IS_CORRECT_STR)
      return error;
    return findLeftOverStates();
  }

  /** Converts all the String labels in the States into Vectors of pointers to States, 
    * and returns a String corresponding to any invalid labels
    */
  private String convertLabels(Machine nfa) {
    State aState;
    int invalid;

    for(Enumeration e = d.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      invalid = aState.labelToStateList(nfa.d);
      if ( invalid >= -1) {
	d.selectedTransition = null;
	d.selectedState = aState;
	d.repaint();
        if(invalid == -1)
	  return "The highlighted label must have a  \n content in all of its fields.";
	return "There is no State named q" + invalid + "\n in the original FSA.";
      }
    }
    return Environment.DFA_IS_CORRECT_STR; 
  }

  /** Recursively compares two machines and returns a proper error
    * message for the checkDone function 
    * Works only on FSA's
    * Preconditions: dfa is the properly formed DFA and the function
    * was originally called with both initialStates. All states in
    * both Desktops are unmarked at start. This Desktop should be
    * deterministic.  */
  private String Compareto(FSA dfa, State thisState, State dfaState, Vector alphabet) {

    char letter;
    String message;
    Transition thisTransition, dfaTransition;
    State aState;

    d.currentCheckMark++;   
    thisState.checkMark = d.currentCheckMark;
    dfaState.checkMark = d.currentCheckMark;
    
    if(thisState.isFinal != dfaState.isFinal) {
      thisState.ss = State.FOCUSED;
      if(thisState.isFinal)
	return "The highlighted state should not \n be a final state.";
      return "The highlighted state should be \n a final state .";
    }

    for(Enumeration e = alphabet.elements(); e.hasMoreElements(); ) {
      letter = ((Character) e.nextElement()).charValue();
      thisTransition = findTransition(thisState, letter);
      dfaTransition = dfa.findTransition(dfaState, letter);
      if( (thisTransition == null) ^ (dfaTransition == null)) {
	thisState.ss = State.FOCUSED;
	if(thisTransition == null) 
	  return "Missing \""+ letter + "\" transition \n on the highlighted state.";
	return "There should be no \"" + letter + "\" transition \n from the highlighted state.";
      }
      if(thisTransition == null)
	continue;
      if((d.showDfaLabels) && (! thisTransition.to.compareLabel(dfaTransition.to))) {
	thisState.ss = State.FOCUSED;
	return "The  transition \"" + letter +"\" from the highlighted \n state should lead to a state labeled \"" + dfaTransition.to.label + "\".";
      }

      if(thisTransition.to.checkMark != dfaTransition.to.checkMark) {
	if(d.showDfaLabels) {
	  for(Enumeration e2 = d.theStates.elements(); e2.hasMoreElements(); ) {
	    aState = (State) e2.nextElement();
	    if(aState.compareLabel(thisTransition.to))
	      aState.ss = State.FOCUSED;
	  }
	  return "The highlighted states have identical labels.";
	}
	thisState.ss = State.FOCUSED;
	return "Wrong transition \"" + letter + "\" on highlighted state.";
      }
      if(thisTransition.to.checkMark == 0) {
	message = Compareto(dfa, thisTransition.to, dfaTransition.to, alphabet);
	if(message != Environment.DFA_IS_CORRECT_STR)
	  return message;
      }
    }

    return Environment.DFA_IS_CORRECT_STR;
  }
  

  /** Finds all States that have not been reached by the algorithm (have a 0 checkMark). */ 
  private String findLeftOverStates() {
    State aState;
    boolean found = false;
    for(Enumeration e = d.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      if(aState.checkMark == 0) {
	aState.ss = State.FOCUSED;
	found = true;
      }
    }
    if(found)
      return "The automaton is correct, but \n the highlighted state(s) are unreachable.";
    return Environment.DFA_IS_CORRECT_STR;
  }


  /** Places all the states for the solved DFA solution */
  public void placeAllStates(Machine model, Machine nfa)
  {
    State currentState;
    State modelState;
    Vector placedStates = new Vector();
    Vector statesToPlace = new Vector();
    Enumeration e, e2;

    for(e = d.theStates.elements(); e.hasMoreElements(); )
    {
      currentState = (State) e.nextElement();
      //find equivalent state in model
      for(e2 = model.d.theStates.elements(); e2.hasMoreElements(); )
      {
	modelState = (State) e2.nextElement();
        if(nfa == null)
          continue;
	if (modelState.labelToStateList(nfa.d) > -2)
	  continue;
	if( !modelState.compareLabel(currentState))
	  continue;
	currentState.p.x = modelState.p.x;
	currentState.p.y = modelState.p.y;
	placedStates.addElement(currentState);
	break;
      }
      if (!placedStates.contains(currentState))
	statesToPlace.addElement(currentState);
    }
    if(placedStates.isEmpty() &&(statesToPlace.contains(d.initialState))) {
      d.initialState.p.x = 60;
      d.initialState.p.y = 60;
      placedStates.addElement(d.initialState);
      statesToPlace.removeElement(d.initialState);
      Transition aTransition;
      for(e = d.theTransitions.elements(); e.hasMoreElements(); ) {
	aTransition = (Transition) e.nextElement();
	if(aTransition.from == aTransition.to && aTransition.from == d.initialState)
        {
          d.initialState.loopSize += Params._t_distance;
        }
      }
    }
    for ( e = statesToPlace.elements(); e.hasMoreElements(); ) {
      currentState = (State) e.nextElement();
      d.placeState(currentState, placedStates);
      placedStates.addElement(currentState);
    }
  } 
      
  public String expandStringLabelState(FSA model) {


    boolean changed = false;
    boolean found = false;

    if(d.selectedState == null) 
      return "No state is currently selected\nto expand. Select a state by\nclicking on its label box.";

    State expandState = d.selectedState;
    State modelState = null;
    State aState;

    if(expandState.label.length() != 1 && !expandState.isFinal)
      return "\n\nThe selected state must have\na one Letter Label";
    if(expandState.isFinal && expandState.label.length() != 0)
      return "\n\nFinal states should not have\na label.";
    
    for(Enumeration e = model.d.theStates.elements(); e.hasMoreElements(); ) {
      modelState = (State) e.nextElement();
      if(modelState.label.equals(expandState.label)) {
        found = true;
        break;
      }
    }
    if(!found) 
      return "\n\nThe selected state has an invalid\nlabel.";


   if(d.initialState == expandState && model.d.initialState != modelState)
     d.initialState = null;

   if(d.initialState != expandState && model.d.initialState == modelState)
     d.initialState = expandState;

   int count = 0;
   if(!expandState.isFinal) {
     for(Enumeration e = d.theStates.elements(); e.hasMoreElements(); ) {
       aState = (State) e.nextElement();
       if(aState.label.trim().equals(expandState.label.trim()))
         count++;
     }
   }
   if(count > 1)
     return "\nThere are multiple states with \n the label \"" +
       expandState.label + "\".";

    Transition t, t2;
    String lab;
    Enumeration e2;

      //remove everything that shouldnt be there
    for(int i = d.theTransitions.size()-1; i >= 0; i--) {
      t = (Transition) d.theTransitions.elementAt(i);
      if(t.from != expandState)
        continue;

      found = false;
      for(e2 = model.d.theTransitions.elements(); e2.hasMoreElements(); ) {
        t2 = (Transition) e2.nextElement();
        if(t2.label.trim().equals(t.label.trim()) && 
           t2.from.label.trim().equals(t.from.label.trim()) &&
           t2.to.label.trim().equals(t.to.label.trim())) {
           found = true;
        }
      }                             

      if(!found)
      {
         d.removeTransition(t);
         changed = true;
      }
      
    }

    model.d.setTransitions(modelState, true);
    d.setTransitions(expandState, true);

    //add everything that isnt already there.
    for(Enumeration e = modelState.transitions.elements(); e.hasMoreElements(); )
    {
      t = (Transition) e.nextElement();
      lab = t.to.label;
      found = false;
      for(e2 = expandState.transitions.elements(); e2.hasMoreElements(); )
      {
        t2 = (Transition) e2.nextElement();
        if(t2.label.trim().equals(t.label.trim()) && 
           t2.from.label.trim().equals(t.from.label.trim()) &&
           t2.to.label.trim().equals(t.to.label.trim()))
        {
           found = true;
        }
      }

      if(found)
        continue;

      changed = true;
      for(e2 = d.theStates.elements(); e2.hasMoreElements(); )
      {
        aState = (State) e2.nextElement();
        if(aState.label.equals(lab))
        {
          t2 = d.addTransition(expandState, aState);
          t2.label = new String(t.label);
          if(t2.from == t2.to)
            t2.from.loopSize += Params._t_distance;
          found = true;
        }
      }
      if(!found) {
        aState = d.addState(0,0);
        aState.isFinal = t.to.isFinal;
        aState.label = new String(lab);
        t2 = d.addTransition(expandState, aState);
        t2.label = new String(t.label);
          if(t2.from == t2.to)
            t2.from.loopSize += Params._t_distance;
        d.theStates.removeElement(aState);
        d.placeState(aState, d.theStates);
        d.theStates.addElement(aState);
      }
    }
    
    if(!changed) 
      return "\n\nThis state is already correct.";

    return Environment.DFA_IS_CORRECT_STR;
  }



/**
 * expand the given state only. gives a partial solution to the machine.
 */

  public String expandState(FSA dfa, FSA nfa) {

    boolean changed = false;
    State targetState;
    Transition aTransition, aTransition2;
    Enumeration e;
    boolean addedstate;

    if(!d.showDfaLabels)
      return "State labels need to be toggled on first.";
    
    if(d.selectedState == null) 
      return "No state is currently selected \n to expand. Select a state by \n clicking on its label box.";
    
    State expandState = d.selectedState;
    
    int status = expandState.labelToStateList(nfa.d);
    if (status == -1)
      return "The selected State must have a label.";
    if (status >= 0)
      return "The selected state's label is incorrect. \n There is no state called \n q"+status+
	" in the original FSA.";
        
    State twinState = dfa.findMatchingState(expandState.stateList);
    if(twinState == null)
      return "The selected state is correct \n but is not needed in the DFA.";
    
    expandState.isFinal = twinState.isFinal;
    if(dfa.d.initialState == twinState) {
      //changed = true;
      d.initialState = expandState;
    } else if(d.initialState == expandState) {
      //changed = true;
      d.initialState = null;
    }

    if(!expandIsDone(dfa , expandState, twinState, dfa.getAlphabet()))
      changed = true;

    for (int i = d.theTransitions.size() -1; i>=0 ; i--) {
      aTransition = (Transition) d.theTransitions.elementAt(i);
      if(aTransition.from == expandState)
	d.removeTransition(aTransition);
    }
    for(e = d.theStates.elements(); e.hasMoreElements(); ) {
      ((State) e.nextElement()).labelToStateList(nfa.d);
    }

    dfa.d.setTransitions(twinState, false);
    for(e = twinState.transitions.elements(); e.hasMoreElements(); )
    {
      aTransition = (Transition) e.nextElement();
      targetState = findMatchingState(aTransition.to.stateList);
      if(targetState == null) {
	targetState = d.addState(-1,-1);
	d.theStates.removeElement(targetState);
	d.placeState(targetState, d.theStates);
	d.theStates.addElement(targetState);
	targetState.stateList = (Vector) aTransition.to.stateList.clone();
	targetState.stateListToLabel();
	d.selectedState = targetState;
	targetState.isFinal = aTransition.to.isFinal;
      }
      if(targetState.isFinal != aTransition.to.isFinal) {
	changed = true;
	targetState.isFinal = aTransition.to.isFinal;
      }
      if((aTransition.to == dfa.d.initialState) &&
         (d.initialState != targetState)) {
	d.initialState = targetState;
	changed = true;
      }

      //remove duplicate transitions
      for(Enumeration te = d.theTransitions.elements(); te.hasMoreElements(); )
      {
         aTransition2 = (Transition) te.nextElement();
         if(aTransition2.from == expandState &&
            aTransition2.to == targetState &&
            aTransition2.equals(aTransition.label))
         {
	    d.removeTransition(aTransition);
         }
      }
      aTransition2 = d.addTransition(expandState, targetState);
      aTransition2.label = new String(aTransition.label);
      if(expandState == targetState)
      {	// for loop transitions
          if(targetState.loopSize == 0)
             targetState.loopSize += Params._t_distance;
          targetState.loopSize += Params._t_distance;
          targetState.loopSize = Math.min(targetState.p.y, targetState.loopSize);
      }
    }
    d.unfocusAll();
    d.repaint();
    if(changed == false)
      return "This state is already correct.";

    return Environment.DFA_IS_CORRECT_STR;
  }

  /**
    * checks if the given state is already properly expanded
    */
  private boolean expandIsDone(FSA dfa, State thisState, State dfaState, Vector alphabet) {

    char letter;
    String message;
    Transition thisTransition, dfaTransition;
    State aState;

    d.setTransitions(thisState, false);
    dfa.d.setTransitions(dfaState, false);
    
    if(thisState.transitions.size() != dfaState.transitions.size())
      return false;

    if(thisState.isFinal != dfaState.isFinal) {
      return false;
    }

    for(Enumeration e = alphabet.elements(); e.hasMoreElements(); ) {
      letter = ((Character) e.nextElement()).charValue();
      thisTransition = findTransition(thisState, letter);
      dfaTransition = dfa.findTransition(dfaState, letter);
      if( (thisTransition == null) ^ (dfaTransition == null)) {
	return false;
      }
      if(thisTransition == null)
	continue;
      if((! thisTransition.to.compareLabel(dfaTransition.to))) {
	return false;
      }
    }
    return true;
  }


  //************************** minimize functions below here *****************************

  /**
    * builds the model minimized machine to compare with
    */
  public void buildMinimized(TreeMachine source, FSA realSource) {
    State aState, aState2, aState3;
    Enumeration e2, e3;
    State from = null;
    State to = null;
    Transition aTransition;
     
    source.d.setAllStateLists(source.minimizeSource.d);

    for(Enumeration e = source.d.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      if((aState.transitions.size() == 0) && (aState.stateList.size() > 0 )) {
	aState2 = new State(aState);
	aState2.isFinal = ((State) aState.stateList.elementAt(0)).isFinal;
	d.theStates.addElement(aState2);
	d.currentId = Math.max(aState.id+1, d.currentId+1);
	for(e2 = aState.stateList.elements(); e2.hasMoreElements(); ) {
	  aState3 = (State) e2.nextElement();
	  if(aState3 == source.minimizeSource.d.initialState)
	    d.initialState = aState2;
	}
      }
    }
    
    for(Enumeration e = source.minimizeSource.d.theTransitions.elements(); e.hasMoreElements(); ) {
      aTransition = (Transition) e.nextElement();
      for(e2 = d.theStates.elements(); e2.hasMoreElements(); ) {
	aState = (State) e2.nextElement(); 
	for(e3 = aState.stateList.elements(); e3.hasMoreElements(); ) {
	  aState2 = (State) e3.nextElement(); 
	  if ( aState2 == aTransition.from)
	    from = aState;
	  if (aState2 == aTransition.to)
	    to = aState;
	}
      }
      if(aTransition.label.trim().length() != 0) {
        if(findTransition(from, aTransition.label.trim().charAt(0)) == null)
        {
	  d.addTransition(from, to).label = new String(aTransition.label);
          if(from == to)
          {  // for loop transitions
             if(to.loopSize <= 0)
                to.loopSize = Params._t_distance;
             to.loopSize += Params._t_distance;
          }
        }
      }
    }
    
    for(Enumeration e = d.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      if(source.minimizeSource.trap != null && 
	 aState.stateList.contains(source.minimizeSource.trap)) {
	if(aState.stateList.size() == 1)
	  d.removeState(aState);
	else aState.stateList.removeElement(source.minimizeSource.trap);
	aState.stateListToLabel();
	break;
      }
    }

    d.setAllStateLists(realSource.d);
  }

  /**
    * puts the states of a minimized machine in the same position the states  
    * originally were in.
    */
  public void putMinimizedStates(TreeMachine source) {
    State aState, aState2, aState3;
    Enumeration e2, e3;
    State from = null;
    State to = null;
    Transition aTransition;

    source.d.setAllStateLists(source.minimizeSource.d);
    
    for(Enumeration e = source.d.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      if((aState.transitions.size() == 0) && (aState.stateList.size() > 0 )) {
	aState2 = new State(aState);
	aState2.p = new Point( ((State) aState.stateList.elementAt(0)).p);
	aState2.isFinal = ((State) aState.stateList.elementAt(0)).isFinal;
	d.currentId = Math.max(aState.id+1, d.currentId+1);
	d.theStates.addElement(aState2);
	for(e2 = aState.stateList.elements(); e2.hasMoreElements(); ) {
	  aState3 = (State) e2.nextElement();
	  if(aState3 == source.minimizeSource.d.initialState)
	    d.initialState = aState2;
	}
      }
    }

    for(Enumeration e = d.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      if(source.minimizeSource.trap != null  && 
	 aState.stateList.contains(source.minimizeSource.trap)) {
	if(aState.stateList.size() == 1)
	  d.removeState(aState);
	else aState.stateList.removeElement(source.minimizeSource.trap);
	aState.stateListToLabel();
	break;
      }
    }

  }

  /**
    * creates all implicit transitions of a dfa and makes them lead to a trap state.
    * @return the trap state's id if one was created. else -1
    */
  public int fillImplicitTransitions() {
    trap = null;
    State aState;
    Vector alphabet = getAlphabet();
    Enumeration e, e2;
    Character aCharacter;

    for(e = d.theStates.elements(); e.hasMoreElements(); ) {
      aState = (State) e.nextElement();
      for(e2 = alphabet.elements(); e2.hasMoreElements(); ) {
	aCharacter = (Character) e2.nextElement(); 
	if(findTransition(aState, aCharacter.charValue()) == null) {
	  if(trap == null)
	    trap = d.addState(-1, -1);
	  d.addTransition(aState, trap).label = new String(String.valueOf(aCharacter.charValue()));
	}
	
      }

    }
    if(trap == null)
      return -1;
    return trap.id;

  }

}  // end of class FSA
