/**
 *
 * PROGRAM:     Sethi Deterministic Turing Machine Simulator (turing.cpp)
 * SYNTAX:      turing tm_transitions.tm <input_string>
 * OUTPUT:      turing automagickally outputs:
 *                - "Accept"
 *                - "Reject"
 *                - "Invalid TM"
 *                - "Invalid Input"
 * RETURN:      Returns return_int code to indicate successful conclusion
 * VERSION:     0.1.8
 *              
 * AUTHOR:      Ricky J. Sethi (rickys@sethi.org) -- http://www.sethi.org
 * 
 * DESCRIPTION: The turing program is a Turing Machine Simulator.  It
 *              takes a text file containing the Turing Machine's
 *              description.  The filename is followed by the Input
 *              String, which consists of {0,1}.  Finally, it outputs
 *              one of the above output messages.
 *              
 *              The turing machine transitions file contains the
 *              transition function, which is simply a sequence of
 *              instructions, one per line where blank lines are
 *              ignored.  Each instruction has the following form:
 *              q a p b m   <comment>
 *              
 *              Where q and p are states, a and b are tape symbols,
 *              and m is in {L,R}, which is the head move.  Spaces and
 *              tabs are ignored and the intructions end with EOF.
 *              This is a deterministic TM so not only will it reject
 *              if the transition function isn't specified for some
 *              given arguments (of the tape and state symbols) but it
 *              will also report "Invalid TM" if multiple transitions
 *              are specified for a given pair (state, tape symbol).
 * 
 * LICENSE:     ****************************************************
 *              GPL & Postcard-Ware!  This program is distributed
 *              under the standard GPL and is freely useable or
 *              distributable as long as this license is attached and
 *              the authors are credited.  Also, if you like or use
 *              this program, you're required to send me a postcard!
 *              ****************************************************
 * 
 * REFERENCES:  Original idea proposed by Dr. Alan Turing
 * 
 * ALGORITHM:   Briefly, turing simulates a generic, deterministic
 *              Turing Machine.  It reads in the input file and parses
 *              it to ensure it's a valid machine (i.e., that there
 *              aren't any multiple transitions).  It stores the
 *              instructions (the transitions) into a map that
 *              represents the transition function.  It then runs the
 *              TM simulator, which reads and writes the input string
 *              onto a private tape, finally deciding to accept or
 *              reject the input string.  In addition, it checks the
 *              input string to make sure it consists of valid input
 *              alphabet symbols.
 * 
 * CHANGES:
 *              Created by Ricky J. Sethi on 2004-10-01
 *              Modified by Ricky J. Sethi on 2004-10-03
 *              Modified by Ricky J. Sethi on 2004-10-10
 *                - Fixed EOF bug (seems to be in GCC 3.2.2 where
 *                  infile.eof() doesn't seem to work)
 * TODO:         
 *              * Item Number 1
 *                - Sub-Item 1
 *
 ********************************************************************/

#include <iostream>  // Need to do tons of I/O 
#include <string>    // Make sure we use strings
#include <fstream>   // Get the filestream stuff (in and out)
#include <map>       // Navigate dem mulimaps!
#include <cstdio>    // For stderr, etc.
//#include <vector>    // Gotta love vectors!
//#include <algorithm> // Some nice algorithms
//#include <cctype>    // For isdigit(), etc.
using namespace std;



//====================================================================
// Some Constant Variables:
//====================================================================
const int DEBUG                           = 0;
const char BLANK                          = '_';
const string ACCEPT                       = "accept";
const string REJECT                       = "reject";
const string INVALIDSTATE                 = "+++===+++";
const int NUM_TAPE_SYM                    = 27;
const char TAPE_SYM[NUM_TAPE_SYM]         = {'_','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
const int NUM_ALPHABET_SYM                = 3;
const char ALPHABET_SYM[NUM_ALPHABET_SYM] = {'_','0','1'};
const int NUM_MOVES                       = 2;
const char MOVE_SYM[NUM_MOVES]            = {'L','R'};


//====================================================================
// Some Class Definitions:
//====================================================================
class Transition {                                // Class for each input/output Transition
public:
  string composite;                               // Used as the primary key (of the Key) in the map; see .find() note below
  string state;
  char symbol;
  Transition(string st=INVALIDSTATE, char s='A') { // Explicit-Value Constructor with Default Values Only -- Unneeded
    composite = st + s;
    state = st;
    symbol = s;
  }
};

class NextTransition : public Transition {        // Class derived from Transition; used for the TO portion of transition function
public:
  char move;
  NextTransition(string st=INVALIDSTATE, char s='A', char m='L') : Transition(st,s) {
    move = m;
  }
};

class Lesser {                                   // For compare fxn in map which has a Transition as the Key
public:
  bool operator()(Transition a, Transition b) { 
    return a.composite < b.composite;            // This was essential for .find() later (this determines they key for uniqueness)
  }
};



//====================================================================
// Prototypes:
//====================================================================
void dbg(string msg);
void load_transitions(char * szTransitionsFile, map<Transition,NextTransition,Lesser> & mTransitionFunction);
bool validate_input_string(char * szInputString);
void simulate_tm(char * szInputString, map<Transition,NextTransition,Lesser> & mTransitionFunction);
void print_transitions(map<Transition,NextTransition,Lesser> & mTransitionFunction);








int main(int argc, char ** argv) {
  //==================================================================
  // Some important variables and declarations:
  //==================================================================
  map<Transition, NextTransition, Lesser> mTransFxn;    // map of transitions to transition


  //==================================================================
  // Get all the input data:
  //==================================================================
  if (argc != 3) {                                     // Do we have enough inputs?
    fprintf (stderr, "Syntax: turing <transitions_file> <input_string>\n");
    exit (0);
  }

  validate_input_string(argv[2]);
  load_transitions(argv[1], mTransFxn);
  if(DEBUG) {print_transitions(mTransFxn);}


  //==================================================================
  // Run the simulator!
  //==================================================================
  simulate_tm(argv[2], mTransFxn);


  return 0;
}








/**
 * 
 * FUNCTION:      dbg(msg)
 * DESCRIPTION:   Local debug fxn
 * RECEIVE:       Uses the following EXPLICIT parameters:
 *                  - msg: string, message to print out
 *                Uses the following IMPLICIT parameters:
 *                  - ostream & cout
 * RETURN:        EXPLICITLY returns:
 *                  - nothing
 *                IMPLICITLY returns:
 *                  - none
 * OUTPUT:        Prints out the msg (if active only)
 * PRECONDITION:  msg is a valid string
 * POSTCONDITION: msg was printed 
 * 
 *******************************************************************/

void dbg(string msg) {
  //cout << msg << endl;
  //msg = "";
  return;
}



/**
 * 
 * FUNCTION:      validate_input_string()
 * DESCRIPTION:   Validate input string
 * RECEIVE:       Uses the following EXPLICIT parameters:
 *                  - char *: szInputString, the input string
 *                Uses the following IMPLICIT parameters:
 *                  - The Global Constants
 * RETURN:        EXPLICITLY returns:
 *                  - bool
 *                IMPLICITLY returns:
 *                  - none
 * OUTPUT:        Prints "Input invalid" and quits the program if invalid
 * PRECONDITION:  Input string is not empty
 * POSTCONDITION: Input string is made up of the input alphabet symbols only
 * 
 *******************************************************************/

bool validate_input_string(char * szInputString) {
  string s(szInputString);

  for (unsigned int i=0; i<s.length(); i++) {
    bool okay = false;
    
    // Check if it consists of valid input characters:
    for (int j=0; j<NUM_ALPHABET_SYM; j++) {
      if (DEBUG) {cout << "Checking: " << i << "th entry: " << s[i] << " with " << ALPHABET_SYM[j] << endl;}
      if (s[i] == ALPHABET_SYM[j]) {
	okay = true;
      }
    }

    if (okay == false) {
      fprintf (stderr, "Input invalid\n");
      exit (0);
    }
  }

  return true;
}



/**
 * 
 * FUNCTION:      load_transitions()
 * DESCRIPTION:   Loads transitions from transition_file.tm to mTransitionFunction and validates transitions for a deterministic TM (no multiple transitions)
 * RECEIVE:       Uses the following EXPLICIT parameters:
 *                  - char *: szTransitionsFile, the text file containing the transitions
 *                  - map<Transition,NextTransition,Lesser> &: mTransitionFunction, the Transition Function map
 *                Uses the following IMPLICIT parameters:
 *                  - The Global Constants
 * RETURN:        EXPLICITLY returns:
 *                  - nothing
 *                IMPLICITLY returns:
 *                  - none
 * OUTPUT:        Prints "Invalid TM" and quits the program if more than one transition is specified for a given pair (state,symbol)
 * PRECONDITION:  File is valid
 * POSTCONDITION: mTransitionFunction is populated with valid transitions
 * 
 *******************************************************************/

void load_transitions(char * szTransitionsFile, map<Transition,NextTransition,Lesser> & mTransitionFunction) {
  // Some temporary variables:
  string startstate = "", nextstate = "";
  char inputsymbol = 'A', writesymbol = 'A', move = 'L';
  typedef pair<Transition,NextTransition> entry;         // Define a useful pair entry type for the map entries

  ifstream infile(szTransitionsFile, ios::in | ios::binary);
  if(!infile) {
    fprintf (stderr, "Sorry, couldn't open the input file %s\n", szTransitionsFile);
    exit (0);
  }

  int num = 0;
  while ( !infile.eof() ) {
    char foo = 'a';

    // If we're already at end (despite the infile.eof() above), exit -- fix for an issue with GCC 3.2.2
    if (infile.peek() == EOF) break;

    // Skip empty lines:
    if (infile.peek() == '\n') {
      infile.get(foo);
      foo = 'a'; startstate = ""; inputsymbol = 'A';
      continue;
    } 

    // Read the data:
    infile >> startstate >> inputsymbol >> nextstate >> writesymbol >> move;
    
    // Skip to end of line
    while (foo != '\n') {
      infile.get(foo);
      if (foo == '\n') num++;
      if (infile.peek() == EOF) break;  // Needed this to prevent it from re-reading the last line
    }

    if (DEBUG) {cout << "Got number of lines: " << num << endl;}
    dbg("Got to here: start: "+ startstate +" INSYMBOL: "+ inputsymbol +" End: "+ nextstate +" WriteSym: "+ writesymbol +" Move: "+ move);
    
    Transition start(startstate,inputsymbol);
    NextTransition next(nextstate,writesymbol,move);

    
    if ( mTransitionFunction.find(start) == mTransitionFunction.end() ) {   // Couldn't use mTransitionFunction.count for some reason!
      if (startstate != "")                                                 // Skip those states that bypass skip empty lines routine (when two lines in a row?)
	  mTransitionFunction.insert( entry(start, next) );
    } else {
      fprintf (stderr, "Invalid TM\n");
      dbg("Exiting program with: start: "+ startstate +" INSYMBOL: "+ inputsymbol +" End: "+ nextstate +" WriteSym: "+ writesymbol +" Move: "+ move);
      exit (0);
    }
  }

  infile.close();
  
  return;
}



/**
 * 
 * FUNCTION:      print_transitions()
 * DESCRIPTION:   Prints the map (the transition function) of transitions
 * RECEIVE:       Uses the following EXPLICIT parameters:
 *                  - map<Transition,NextTransition,Lesser> &: mTransitionFunction, the Transition Function map
 *                Uses the following IMPLICIT parameters:
 *                  - The Global Constants
 * RETURN:        EXPLICITLY returns:
 *                  - nothing
 *                IMPLICITLY returns:
 *                  - none
 * OUTPUT:        Prints the contents of the transition function map (the transitions)
 * PRECONDITION:  mTransitionFunction exists
 * POSTCONDITION: Contents of mTransitionFunction were printed out
 * 
 *******************************************************************/

void print_transitions(map<Transition,NextTransition,Lesser> & mTransitionFunction) {
  map<Transition,NextTransition,Lesser>::iterator pos;             // Iterator

  for(pos = mTransitionFunction.begin(); pos != mTransitionFunction.end(); pos++) {
    cout << "Transition from: " << (pos->first).composite << " To: " << (pos->second).composite << endl;
  }

  return;
}



/**
 * 
 * FUNCTION:      simulate_tm()
 * DESCRIPTION:   Simulates the TM with transitions in mTransitionFunction and input string in szInputString
 * RECEIVE:       Uses the following EXPLICIT parameters:
 *                  - char *: szInputString, the input string
 *                  - map<Transition,NextTransition,Lesser> &: mTransitionFunction, the Transition Function map
 *                Uses the following IMPLICIT parameters:
 *                  - The Global Constants
 * RETURN:        EXPLICITLY returns:
 *                  - nothing
 *                IMPLICITLY returns:
 *                  - none
 * OUTPUT:        Prints either "Accept" or "Reject"
 * PRECONDITION:  mTransitionFunction and szInputString exist and are valid (szInputString starts with state "start")
 * POSTCONDITION: Ran through simulation and printed "Accept" or "Reject"
 * 
 *******************************************************************/

void simulate_tm(char * szInputString, map<Transition,NextTransition,Lesser> & mTransitionFunction) {
  string s(szInputString);
  //vector<Transition> vInputTransitions;                  // vector of the input transitions
  typedef pair<Transition,NextTransition> entry;         // Define a useful pair entry type for the map entries

  string state = "start";
  
  // KLUDGE: Check if it ends with a BLANK; if not, add a BLANK:
  if (s[s.length() - 1] != BLANK) {
    s += BLANK;
    if (DEBUG) {cout << "New string is: " << s << endl;}
  }

  int size = s.length();         // Avoid comparison of unsigned int with signed below (since i gets value -1 below)
  for (int i=0; i<size; i++) {
    Transition input(state,s[i]);
    NextTransition next = mTransitionFunction[input];
    if(DEBUG) {cout << "NEXT state: " << next.state << " symbol: " << next.symbol << " Move: " << next.move << endl;}
    
    state = next.state;
    s[i] = next.symbol;

    if (next.move == 'L') {
      i = (i >= 1) ? i-2 : -1;   // Decrement i by 2 if i>0 (if i=0, stay at 0) since i gets incremented in loop's i++
    }


    // Endgame?
    if (next.state == ACCEPT) {
      cout << "Accept" << endl;
      exit(0);
    }

    if (next.state == INVALIDSTATE) {
      cout << "Reject" << endl;
      exit(0);
    }
  }

  // Came out of for loop without accept; therefore, reject!
  cout << "Reject" << endl;


  return;
}






/*** Here's a sample Turing Machine that accepts the language L = {0^i1^j : j = i^i} -- Save as exp.tm ***
 *** The TM for this exponential function looks like this:
 *** <img src="tm_exponential.png" width="768" height="1979" alt="TM State Diagram" />

start 0 case1 A R                                           // START INITIALIZATION

case1 1 possibleaccept 1 R                                  // Case i = 1?
possibleaccept _ accept _ R				    // ACCEPT

case1 0 rewind1 C L
   rewind1 C rewind1 C L
rewind1 A multiplication B L				    // END INITIALIZATION

multiplication B initial1 B R				    // ENTER MULTIPLICATION
   initial1 0 initial1 0 R
   initial1 C initial1 C R
initial1 1 initiallooprewind F L
   initiallooprewind 0 initiallooprewind 0 L
   initiallooprewind C initiallooprewind C L
   initiallooprewind D initiallooprewind D L
   initiallooprewind E initiallooprewind E L
   initiallooprewind F initiallooprewind F L
initiallooprewind B findunusedzero B R
   findunusedzero D findunusedzero D R
   findunusedzero E findunusedzero E R
findunusedzero 0 findunusedone D R
findunusedzero C findunusedone E R
   findunusedone 0 findunusedone 0 R
   findunusedone C findunusedone C R
   findunusedone F findunusedone F R
findunusedone 1 initiallooprewind F L

findunusedzero F erasetempzerom F L			    // GO TO REGULAR MULTIPLICATION
   erasetempzerom D erasetempzerom 0 L
   erasetempzerom E erasetempzerom C L
erasetempzerom B findunusedzerotwo A R			    // At regular mult.

multiplication A findunusedzerotwo A R			    // At regular mult.
   findunusedzerotwo D findunusedzerotwo D R
   findunusedzerotwo E findunusedzerotwo E R
findunusedzerotwo 0 enteronexmarking D R
findunusedzerotwo C enteronexmarking E R
   enteronexmarking 0 enteronexmarking 0 R
   enteronexmarking C enteronexmarking C R
enteronexmarking F findunmarkedone G R
   findunmarkedone F findunmarkedone F R
   findunmarkedone H findunmarkedone H R
findunmarkedone 1 rewindtoonex H L
   rewindtoonex H rewindtoonex H L
   rewindtoonex F rewindtoonex F L
rewindtoonex G continueloop G R
continueloop F findunmarkedone G R
continueloop H erasetemponexo H L
   erasetemponexo G erasetemponexo F L
erasetemponexo 0 rewindtostart 0 L
erasetemponexo C rewindtostart C L
erasetemponexo D rewindtostart D L
erasetemponexo E rewindtostart E L
   rewindtostart 0 rewindtostart 0 L
   rewindtostart C rewindtostart C L
   rewindtostart D rewindtostart D L
   rewindtostart E rewindtostart E L
rewindtostart A findunusedzerotwo A R
findunusedzerotwo F erasetemponezero F R
   erasetemponezero H erasetemponezero F R
   erasetemponezero F erasetemponezero F R
erasetemponezero 1 rewindtozeros 1 L
erasetemponezero _ rewindtozeros _ L
   rewindtozeros F rewindtozeros F L
rewindtozeros D erasetempzeromxm 0 L
rewindtozeros E erasetempzeromxm C L
   erasetempzeromxm D erasetempzeromxm 0 L
   erasetempzeromxm E erasetempzeromxm C L
erasetempzeromxm A exitmultiplication A L		    // EXIT MULTIPLICATION ROUTINE

exitmultiplication A loopstart A R			    // START ITERATION
   loopstart C loopstart C R
loopstart 0 rewind2 C L
   rewind2 C rewind2 C L
rewind2 A multiplication A L				    // Start Iterative Mult.

loopstart F terminationcheck F R			    // START TERMINATION
   terminationcheck F terminationcheck F R
terminationcheck _ accept _ R				    // ACCEPT
*/