public class TM
{
   static int MAX_INSTRUCTION = 500;
   static int TAPE_LENGTH= 200;
   static int MAX_STEP= 500;
   int step;

   String state, start_state;
   int n_instruction;
   Instruction [] tm;
   Instruction t;
   int n_final_state;
   String [] final_state;
   String [] h= {"STATE", "S", "STATE", "HEAD"};

   String rule_applied;
   String next_rule;
   String current_configuration;
   String message;

   Instruction header= new Instruction(h);

   String tm_description;
    
   int head_position;
   char [] tape;
   String w;
   int min, max;

   public TM(Input in)
   {
      String comment;

      Instruction.num=0;

      tm_description= "The TM:\n";
      start_state= in.readOneString();

      while (Instruction.is_comment(start_state))
      { 
         comment= in.flush_line();
	 
	 tm_description+= start_state + comment + "\n";
         start_state= in.readOneString();
      }

      tm_description += "Start state for the TM: ";
      comment=in.flush_line();      
      tm_description+= start_state + comment + "\n";

      n_final_state= 1;
      final_state = new String[n_final_state];
      final_state[0]= "h";

      tm_description += print_header();
      tm= new Instruction[MAX_INSTRUCTION];
      n_instruction=0;
      do
      {
          t = new Instruction(in, tm_description);
          if (t.transition!= null)
          {
              tm_description+= t.precomment + t.print_instr;
              tm[n_instruction]= t;
              n_instruction++;
          }
      } while (t.transition != null);
   } 
   public void set_input(String w)
   {
      int i;
      int limit;

      step=0;
      state= start_state;
      tape= new char[TAPE_LENGTH];
      for (i=0; i < TAPE_LENGTH; i++)
          tape[i]= '#';

      limit= w.length();
      if (limit >= TAPE_LENGTH-1) limit = TAPE_LENGTH -1; 

      for (head_position=1; head_position <= limit; head_position++)
          tape[head_position]= w.charAt(head_position-1);

      min= 0;
      max= head_position;

      rule_applied= null;
      next_rule=null;

/*    Treat a # alone as input in a special way, as an empty string. */
      if (w.length() ==1 && tape[1]== '#') head_position--;
   }
   public boolean new_input(Input in)
   {
      String comment;
      int i;

      step=0;
      state= start_state;
      tape= new char[TAPE_LENGTH];
      for (i=0; i < TAPE_LENGTH; i++)
          tape[i]= '#';

      w= in.readOneString();
      if (w==null) return(false);


      while (Instruction.is_comment(w))
      {
         comment= in.flush_line();
         System.out.println(w + comment);
         w= in.readOneString();
         if (w==null) return(false);
      }

      for (head_position=1; head_position <= w.length(); head_position++)
          tape[head_position]= w.charAt(head_position-1);

/*    Treat a # alone as input in a special way, as an empty string. */
      if (w.length() ==1 && tape[1]== '#') head_position--;

      min= 0;
      max= head_position;

      rule_applied= null;
      next_rule=null;
      return(true);
   }

   public String print_header()
   {
      String s;
      int i;

      s= header.table_print_instruction();
      s+="\n";
      return(s);
   }
   public String print_configuration()
   {
       String s;
       int i;

       s= "Step " + Instruction.pad("" + step, 3) + ": (" + Instruction.pad(state + ",", 6);
       
       for (i=min; i < head_position; i++)
           s+= tape[i];
       if (head_position >= 0)
          s+="[" + tape[head_position] + "]";
       else
          s+="[]";
       for (i=head_position+1; i <= max; i++)
           s+=tape[i];
       s+=")\n";
       return(s);
   }
   public boolean is_final_state()
   {
       int i;
   
       for (i=0; i < n_final_state; i++)
       {
           if (state.equals(final_state[i]))
               return(true);
       }
       return(false);
   }
   public boolean move()
   {
       int num;

       rule_applied= null;
       next_rule=null;
       message= null;

       step++;
       /* Find the first available transition. */

       if (step >= MAX_STEP)
       {
	   message="CSC 320 Infinite loop protection.\n";
	   message+=
           "If you really need more steps, increase MAX_STEP and recompile\n";
           return(false);
       }
       if (is_final_state())
       {
           message= "Halts because the state is final.\n";
           return(false);
       }
       current_configuration= null;

       num= find_transition();
       if (num < 0)
       {
	   message= "No valid transition, TM hangs.\n";
           return(false);
       }
       rule_applied= tm[num].print_instr;
       state= tm[num].transition[Instruction.NEXT_STATE];

       if (tm[num].transition[Instruction.HEAD_INSTRUCTION].equals("L"))
       {
           head_position--;
           if (head_position < min) 
           {
              current_configuration= print_configuration();
              message="Tape head fell off tape, TM hangs.\n";
              return(false);
           }
           if (max == head_position +1 && tape[head_position+1]== '#') max--;
       }
       else if (tm[num].transition[Instruction.HEAD_INSTRUCTION].equals("R"))
       {
           head_position++;
           if (max < head_position) max= head_position;
       }
       else // replace current symbol. */
       {
           tape[head_position]= 
              (tm[num].transition[Instruction.HEAD_INSTRUCTION]).charAt(0);
       }
       if (head_position >= TAPE_LENGTH)
       {
	  message= "Inadequate amount of tape.\n";
	  message+= "Increase TAPE_LENGTH and recompile.\n";
          return(false);
       }
       current_configuration=print_configuration();

       if (is_final_state()) next_rule="Halts because in the halt state.\n";
       else
       {
          num= find_transition();
          if (num < 0)
          {
	      next_rule= "No valid transition, TM will hang.\n";
          }
	  else next_rule= tm[num].print_instr;
       }
       return(true);
   }
   public int find_transition()
   {
       String symbol;
       int i;

       symbol= "" + tape[head_position];
       for (i=0; i < n_instruction; i++)
       {
           if (tm[i].valid_move(state, symbol))
                return(i);
       }
       return(-1);
   }
   public static void execute_TM()
   {
       int n_input=0;
       Input in;

       TM turing_machine;

       in= new Input(System.in);

       turing_machine= new TM(in);
       System.out.print(turing_machine.tm_description);

       while (turing_machine.new_input(in))
       {
           n_input++;
           System.out.print("Input " + n_input + " computation: ");
           System.out.println("w of length " + 
                 turing_machine.w.length() + "=[" + 
                 turing_machine.w + "]");
           System.out.print(turing_machine.print_configuration());
           while (turing_machine.move())
           {
/*
           Don't print the rule applied- too much clutter. 
		   if (turing_machine.rule_applied != null)
		       System.out.print(turing_machine.rule_applied);
*/
		   if (turing_machine.current_configuration != null)
		       System.out.print(turing_machine.current_configuration);
           }
/*
           Don't print the rule applied- too much clutter. 
	   if (turing_machine.rule_applied != null)
		   System.out.print(turing_machine.rule_applied);
	   if (turing_machine.current_configuration != null)
		   System.out.print(turing_machine.current_configuration);
*/
	   if (turing_machine.message != null)
	   {
	       System.out.print(turing_machine.message);
	   }
           System.out.println("End computation " + n_input);
       }
   }

   public static void main(String args[])
   {
       execute_TM();
   }
}