/*---------------------------------------------------------------------------
File:         			TM1.java
Package:                        JFLAP Version 1.0
Author:				Magda & Octavian Procopiuc V1.0 07/15/96
                                
Description of Contents:	Contains class TM1.
				
--------------------------------------------------------------------------*/

/* 
 * 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 simulates the behavior of a 
 * one-tape Turing Machine.
 *
 * @author	Magda & Octavian Procopiuc
 * @version	1.0 15 July 1996
 */ 
public class TM1 extends Machine { 

/**
 * Creates a 1-tape Turing Machine corresponding to its desktop image.
 */
  public TM1(Desktop d) {
    super(d);
  }

    /** Places all the states for the solved DFA solution */
    public void placeAllStates(Machine model, Machine nfa) {
    }
    

    /** not implemented  */
    public String checkIfDone(Machine amodel, Machine original) {
	return "function not implemented.";
    }
    


/*
 * Checks whether the machine is "legal" (i.e. has initial state,
 * and all transition labels are OK)
 * Overrides Machine.checkMachine()
 */
  public String checkMachine() {
    String answer = super.checkMachine();
    String message =  "At least one transition has an\n incorrect label. The correct form is\n read; write, move\n where read and write are one letter,\n and move is R, L or S.";

    if (answer == null) {
      Transition t;
      for (Enumeration et=d.theTransitions.elements(); et.hasMoreElements(); ) {
        t = (Transition) et.nextElement();
        if (!checkLabel(t.label))
          return message;
      } 
      return null;
    } else return answer;
  }

/*
 * Creates a new configuration starting from configuration c, according
 * to the transition rule of a 1-tape TM.
 * Overrides Machine.expand().
 */
  boolean expand(Configuration c) {
    boolean willBeValid;
    Transition t;
    Configuration cc;

    String read, write, move;
    Tape newTape = new Tape();

    willBeValid = false;
    for (Enumeration et=c.theState.transitions.elements(); et.hasMoreElements(); )   {
      t = (Transition) et.nextElement();
      StringTokenizer stk = new StringTokenizer(t.label, ";,", false);
      read = stk.nextToken().trim();
      write = stk.nextToken().trim();
      move = stk.nextToken().trim();
      if (c.theString.startsWith(read) || ("B".equals(read) && c.theString.length() == 0)) {
        willBeValid = true;
        executeMove(c.theStack, c.theString, newTape, write, move);
        cc = new Configuration(t.to, newTape.right, newTape.left, 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;
    String read, write, move;
    String vread, vwrite, vmove;

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

    StringTokenizer stk = new StringTokenizer(t.label, ";,", false);
    read = stk.nextToken().trim();
    write = stk.nextToken().trim();
    move = stk.nextToken().trim();

    for (e = v.elements(); e.hasMoreElements(); ) {
      vt = (Transition) e.nextElement();
      stk = new StringTokenizer(vt.label, ";,", false);
      vread = stk.nextToken().trim();
      vwrite = stk.nextToken().trim();
      vmove = stk.nextToken().trim();

      if (read.equals(vread)) 
        if ((t.to != vt.to) || (!write.equals(vwrite)) || (!move.equals(vmove)))
             return false;
    } 

    return true;
  }  // end of method isDeterministic

// Checks if a transition label is legal (will be more complex for TM2).
  boolean checkLabel(String label) {
    return labelOK(label);
  }  // end of method checkLabel

// Checks if a transition label is legal.
  boolean labelOK(String label) {
    boolean isOK = true;
    char c;
 
    if (label.length() != 8) {
      isOK = false;
    }
    else if (';' != label.charAt(2) || ',' != label.charAt(5)) {
      isOK = false;
    }
    else {
      c = label.charAt(1);
      if (',' == c || ';' == c || '|' == c || ' ' == c)
        isOK = false;
      else {
        c = label.charAt(4);
        if (',' == c || ';' == c || '|' == c || ' ' == c)
          isOK = false;
        else {
          c = label.charAt(7);
          if ('R' != c && 'L' != c && 'S' != c)
            isOK = false;
        }
      }
    } 

    return isOK;
  }  // end of method labelOK

/*
 * Executes a TM step.
 * theStack represents the string to the left of the head, while
 * the String represents the string to the right.
 */
  void executeMove(String theStack, String theString, Tape newTape, String write, String move) {
    if ("L".equals(move)) {          // move left
      if (theStack.length() > 1)
        newTape.left = theStack.substring(0, theStack.length() - 1);
      else
        newTape.left = "";
      if (theStack.length() > 0)
        newTape.right = theStack.substring(theStack.length() - 1) + write;  
      else
        newTape.right = "B" + write; 
      if (theString.length() > 1)
        newTape.right += theString.substring(1); 
    } else if ("R".equals(move)) {   // move right
      newTape.left = theStack + write; 
      if (theString.length() > 1)
        newTape.right = theString.substring(1);
      else 
        newTape.right = ""; 
    } else {                         // stay
      newTape.left = theStack; 
      newTape.right = write;
      if (theString.length() > 1)
        newTape.right += theString.substring(1); 
    }
    if (newTape.left == null)
      newTape.left = "";
    if (newTape.right == null)
      newTape.right = "";
  }  // end of method executeMove

}  // end of class TM1


 
