/*---------------------------------------------------------------------------
File:         			Machine.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 Machine.
				
--------------------------------------------------------------------------*/

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

/**
 * This class implements the concept of a machine
 * in the sense used in the automata theory.
 * It is abstract since its running behavior is not defined.
 * It is used as a wrapper for the different types of 
 * machines: FSA, PDA, TM1, TM2.
 *
 * Any subclass of this class has to override at least
 * the following (non-public) methods:
 * <PRE>
 * 	expand(Configuration)
 *	initialConfig() 
 *	isDeterministic(Transition, Vector) 
 *
 * @see		flap.FSA
 * @see		flap.PDA
 * @see		flap.TM1
 * @see		flap.TM2
 * @author	Magda & Octavian Procopiuc
 * @version	1.0 15 July 1996
 */
abstract public class Machine {

/**
 * Types of messages displayed while doing a step or fast run
 */
  
  final static int NO_FINAL_STATE_MSG	= 0;
  final static int NO_MORE_CONFIGS_MSG	= 1;
  final static int MAXNCONFIGS_MSG	= 2;
  final static int MAXCOUNT_MSG		= 3;
  final static int ACCEPTED_MSG		= 4;
  final static int NO_MESSAGE		= 5;

  /** 
    * Machine types supported by this software
    */  
  public final static int FSA = 0;
  /** 
    * Machine types supported by this software
    */  
  public final static int PDA = 1;
  /** 
    * Machine types supported by this software
    */  
  public final static int TM1 = 2;
  /** 
    * Machine types supported by this software
    */  
  public final static int TM2 = 3;
  /**
    * Machine types supported by this software
    */
  public final static int MTC = 4;
    /**
     * Machine types supported by this software
     */
  public final static int GRA = 5;
    /**
     * Machine types supported by this software
     */
  public final static int REX = 6;
    /**
     * Type of this machine 
     */
  public int		type;		// FSA, PDA, TM1 or TM2
    /** 
     * Is this machine in a special mode? (building an nfa, etc)
     */
  public int mode;
    /**
     * cfg to pda mode. LL.
     */
  public final static int CFGtoPDA = 1;
    /**
     * cfg to pda mode. LR.
     */
  public final static int CFGtoPDALR = 2;
    /**
     * NFa to DFA
     */
  public final static int NFAtoDFA = 3;
    /**
     * Minimize
     */
  public final static int MINIMIZE = 4;
    /**
     * gnf to pda mode
     */
  public final static int GNFtoPDA = 5;
    /**
     * regular gram to FSA mode
     */
  public final static int regtoFSA = 6;
    /**
     * regular epression to FSA mode
     */
  public final static int rextoFSA = 7;


/**
 * Number of configurations generated thus far 
 * (i.e. size of current configuration tree)
 */  
  int 		nConfigs = 0;
/**
 * Number of configurations generated in the current expand step
 * (i.e. number of leaves in current configuration tree) 
 */
  int		nCurrentConfigs;
/**
 * Maximum number of configurations the program should generate.
 * Can be interactively modified up to capacity. 
 */
  public int		maxNConfigs = 100;
/**
 * Capacity of the machine (biggest acceptable value for maxNConfigs).
 */
  public static int	capacity = Params._ma_capacity; 
/**
 * acceptInput is true if input accepted by machine
 */  
  protected boolean 	acceptInput;
/**
 * The configuration of the machine when input is accepted
 */
  public Configuration acceptingConfig;
/**
 * Corresponding desktop (screen image) of the machine
 */ 
  public Desktop	d;
/**
 * Input string
 */ 
  public String	input = "";
/**
 * Configurations generated by current expand step
 */
  Vector	currentConfigs;
  Vector        temp;

/**
 * Creates machine corresponding to its desktop image.
 */
  public Machine(Desktop d) {
    this.d = d;
    this.type = d.type;
    currentConfigs = new Vector();
  }


  public Machine(Machine source) {

    type = source.type;
    mode = source.mode;
    nConfigs = source.nConfigs;
    nCurrentConfigs = source.nCurrentConfigs;
    maxNConfigs = source.maxNConfigs;
    capacity = source.capacity; 
    acceptInput = source.acceptInput;
    acceptingConfig = source.acceptingConfig;
    d = new Desktop(source.d);
    input = new String(source.input);
    if(source.currentConfigs != null)
      currentConfigs = (Vector) source.currentConfigs.clone();
    if(source.temp != null)
      temp = (Vector) source.temp.clone();
  }

/**
 * Initializes machine according to the picture drawn on screen.
 */
  public void init() {
    State	s;
    Transition	t;
    Configuration cc = null;

    maxNConfigs = 100;
    currentConfigs.removeAllElements();
    currentConfigs.addElement(cc = initialConfig());

    nConfigs = 1;
    d.initialState.ss = State.FOCUSED;

    if (cc.isAccept()) {      // lambda accepted here
      acceptInput = true;
      acceptingConfig = (Configuration) currentConfigs.elementAt(0);
    } else 
      acceptInput = false;
    for (Enumeration es=d.theStates.elements(); es.hasMoreElements(); ) {
      s = (State) es.nextElement();
      d.setTransitions(s, true);        
     }
  }	// end of method init.

/**
 * Checks if machine is valid (i.e. has initial state).
 * Will be rewritten in TM1 and TM2, to also check if transition 
 * labels are valid.
 * @return	Message string (null if machine is OK).
 */
  public String checkMachine() {
    if (d.initialState == null)
      return "The machine has no initial state";
    else
      return null;
  }

/**
 * Sets machine input to String argument.
 */ 
  public void setInput(String input) {
    this.input = input;
  }

/**
 * Executes a step run of the machine, by expanding the
 * configurations in currentConfigs.
 * @param maxCount	Maximum number of configurations we can paint 
 * in the step run window.
 * @return	Type of message to be displayed
 */
  public int stepRun(int maxCount) {

    Configuration	c;
    boolean[]		isValid = new boolean[currentConfigs.size()];
    int			i; 

 // Save field isValid of current configurations, to restore it later
    i = 0;
    for (Enumeration e=currentConfigs.elements(); e.hasMoreElements(); ) {
      c = (Configuration) e.nextElement();
      c.isSelected = false;
      isValid[i++] = c.isValid;
    }

    for (Enumeration e=currentConfigs.elements(); e.hasMoreElements(); ) {
      c = (Configuration) e.nextElement();
      c.theState.ss = State.NORMAL;
    }
     
    temp = new Vector(currentConfigs.size());
    nCurrentConfigs = 0;

    for (Enumeration ec=currentConfigs.elements(); ec.hasMoreElements(); ) {
      c = (Configuration) ec.nextElement();
      if (c.isValid) {
        if (c.isFrozen) {		// keep it
          temp.addElement(c);
        } else {			// expand it
          c.isValid = expand(c);
          if (!c.isValid) 		// no children; will cross it
            temp.addElement(c);
        }	// end of if (c.isFrozen).
      } else {
      }	// end of if (c.isValid).
    }	// end of for...

    if (temp.size() <= maxCount) {
      if (temp.size() == 0)
        return NO_MORE_CONFIGS_MSG;
      currentConfigs = temp;
      for (Enumeration e=currentConfigs.elements(); e.hasMoreElements(); ) {
        c = (Configuration) e.nextElement();
        if (c.isValid)
          c.theState.ss = State.FOCUSED;
        c.isSelected = false;
      }
      nConfigs += nCurrentConfigs;
      if (nConfigs >= maxNConfigs) 
        return MAXNCONFIGS_MSG;
      else
        return NO_MESSAGE;
    } else {   // too many new configs, not enough space for display 
               // restore currentConfigs info, and send message to user
      i = 0;
      for (Enumeration e=currentConfigs.elements(); e.hasMoreElements(); ) {
        c = (Configuration) e.nextElement();
        c.isValid = isValid[i++];
        if (c.isValid)
          c.theState.ss = State.FOCUSED;
      }
      return MAXCOUNT_MSG;
    }  
  }	// end of method stepRun.

/**
 * Executes a fast run of the machine
 * @return	Type of message to be displayed.
 */	
  public int fastRun() {
    Configuration c;
    
    if (!existsFinalState()) {
      if(! (this instanceof PDA))
	return NO_FINAL_STATE_MSG;  
      if(! (((PDA) this).acceptanceType.equals( flap.PDA.EMPTY_STACK )))
	return NO_FINAL_STATE_MSG;
    }
    
    while (!acceptInput && (nConfigs <= maxNConfigs) && (currentConfigs.size() > 0)) {
      temp = new Vector(currentConfigs.size());
      nCurrentConfigs = 0;
      for (Enumeration ec=currentConfigs.elements(); ec.hasMoreElements(); ) {
        c = (Configuration) ec.nextElement();
        expand(c);
      }  
      currentConfigs = temp;
      nConfigs += nCurrentConfigs;
    }

    if (acceptInput) {
      currentConfigs.removeAllElements();
      return ACCEPTED_MSG;
    } else if (currentConfigs.size() == 0) 
        return NO_MORE_CONFIGS_MSG;
      else 
        return MAXNCONFIGS_MSG;
  } // end of method fastRun

/**
 * Checks if a configuration has already been generated, to avoid
 * multiple occurences.
 * @param temp	Vector of configurations previously generated
 *        cc	Current configuration to be checked against temp
 * @return	true if cc appears in temp
 */
  boolean isAlreadyIn(Vector temp, Configuration cc) {
    Configuration c;
    boolean result;
 
    for (Enumeration e=temp.elements(); e.hasMoreElements(); ) {
      c = (Configuration) e.nextElement();
      result = ((c.theState == cc.theState) && (c.isValid == cc.isValid));
      if (c.theString != null) 
        result = result && c.theString.equals(cc.theString);
      else
        result = result && (cc.theString == null);
      if (c.theStack != null) 
        result = result && c.theStack.equals(cc.theStack);
      else
        result = result && (cc.theStack == null);
      if (c.secondString != null) 
        result = result && c.secondString.equals(cc.secondString);
      else
        result = result && (cc.secondString == null);
      if (c.secondStack != null) 
        result = result && c.secondStack.equals(cc.secondStack);
      else
        result = result && (cc.secondStack == null);
      if (result)
        return true;
    }
    return false;
  }   // end of method isAlreadyIn

/**
 * Returns true if the machine has at least one final state
 */
  public boolean existsFinalState() {
    for (Enumeration e=d.theStates.elements(); e.hasMoreElements(); ) {
      if (((State) e.nextElement()).isFinal)
        return true;
    }
    return false;
  }   // end of method existsFinalState

/**
 * Checks for nondeterministic states and highlights them.
 * @return	true if machine HAS nondeterministic states
 */ 
  public boolean showNondets() {
    State	s = null;
    boolean	answer = false;
    Transition	t;

    for (Enumeration e = d.theStates.elements(); e.hasMoreElements(); ) {
      s = (State) e.nextElement();
      d.setTransitions(s, true);
      Vector previousLabels = new Vector(s.transitions.size());
      for (Enumeration e1 = s.transitions.elements(); e1.hasMoreElements(); ) {
        t = (Transition) e1.nextElement();
        if (!isDeterministic(t, previousLabels)) {
          s.ss = State.FOCUSED;
          answer = true;
          break;
        } else
          previousLabels.addElement(t);
      }
    }
    return answer;
  }	


 /** 
  * Creates a new configuration starting from configuration c. 
  * Will be overridden by each subclass.
  */
  abstract boolean expand(Configuration c);
  /**
    * Creates the initial configuration. 
    * Will be overridden by each subclass. 
    */
  abstract Configuration initialConfig();
 
  /**
    * Shows all unreachable states in this machine
    */
  public String showUnreachables() {
    return "not implemented on this machine";
  }

   /** Places all the states for the solved DFA solution */
  abstract void placeAllStates(Machine model, Machine nfa);

  /**
    * returns a Vector of all unreachable States in this machine
    */
  public Vector findReachables() {
    return null;
  }


/**
 * 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. 
 * Will be overridden by each subclass .
 */
  abstract boolean isDeterministic(Transition t, Vector v);


    /**
     * checks if the machine matches its model 
     */
    abstract String checkIfDone(Machine amodel, Machine original);

  /**
    * returns a Vector of Charatcters containing the alphabet. Implement this in the subclass
    * if needed.
    */
  public Vector getAlphabet() {
    return null;
  }


/**
 * Strings one and two are in a substring relationship if one of them
 * prefixes the other. The empty string prefixes any string.
 */
  boolean substringRelation(String one, String two) {
    if (one.startsWith(two) || two.startsWith(one) || "".equals(one) || "".equals(two))
      return true;
    else return false;
  }

}	// end of class Machine.
