/*
    Copyright (C) 2005, 2006      Robin Redeker <elmex@ta-sa.org>, <r.redeker@gmail.com>
*/

// Version: 1.2
// Changes:
// 1.2 - implemented command line arguments for start-state and start-pos setting,
//       and the @<start-pos>,<start-state> syntax in TM file.
// 1.1 - fixed a bug with newline handling

// NOTE: The code is a little bit messy, but it works. I maybe document it further when
// i've got time to.

#include <iostream>
#include <cstdio>
#include <map>
#include <string>
#include <list>
#include <cstring>
#include <cstdlib>
#include <cerrno>
#include <cctype>

extern "C"
{
#include <limits.h>
}

using namespace std;

struct state
{
  string name;

  char *output;
  char *dir;
  state **next;

  state (const string &n) : name (n) {
    output = new char[CHAR_MAX + 1];
    dir    = new char[CHAR_MAX + 1];
    next   = new state*[CHAR_MAX + 1];
    memset (output, 0, sizeof (char)    * (CHAR_MAX + 1));
    memset (dir, 0,    sizeof (char)    * (CHAR_MAX + 1));
    memset (next, 0,   sizeof (state *) * (CHAR_MAX + 1));
  }

  void add_edge (char in, char o, char d, state *n)
  {
    output[in] = o;
    dir[in]    = d;
    next[in]   = n;
  }

  bool get_next (char in, char &o, char &d, state **n)
  {
    if (next[in])
      {
        o  = output[in];
        d  = dir[in];
        *n = next[in];

        return true;
      }
    else
      return false;
  }
};

struct TurM
{
  int bllen, brlen;
  int bpos;
  char *rband;
  char *lband;
  char fill;

  int startpos;

  state *start_state;

  map <string, state *> defined_states;

  TurM (char f = '0') 
    : fill (f), bllen (0), brlen (0), bpos (0), 
      rband (0), lband (0), start_state (0),
      startpos (0)
  {
    ext_band (1, true);
    ext_band (1, false);
  }

  void set_fill (char f) {
    fill = f;
    memset (rband, f, sizeof (char) * brlen);
    memset (lband, f, sizeof (char) * bllen);
  }

  state *get_state (const char *name)
  {
    state *s = 0;

    if (!(s = defined_states[name]))
      s = defined_states[name] = new state (name);

    return s;
  }

  void read (FILE *f);
  void read_input (FILE *f);

  void ext_band (int newcnt, bool right) 
  {
    int olen   = right ? brlen : bllen;
    int newlen = olen + newcnt;
    char *band = right ? rband : lband;

    if (!band)
      {
        band = new char[newlen];
        memset (band, fill, sizeof (char) * newlen);
      }
    else
      {
        char *nband = new char[newlen];
        memset (nband, fill, sizeof (char) * newlen);
        memcpy (nband, band, sizeof (char) * olen);
        delete[] band;
        band = nband;
      }

    if (right)
      {
        rband = band;
        brlen = newlen;
      }
    else
      {
        lband = band;
        bllen = newlen;
      }
  }

  char get_cur_band_cell ()
  {
    if (bpos >= 0)
      return rband[bpos];
    else
      return lband[abs(bpos) - 1];
  }

  void set_cur_band_cell (char o)
  {
    char *band = bpos >= 0 ? rband : lband;
    int pos = bpos >= 0 ? bpos : abs (bpos) - 1;

    band[pos] = o;
  }

  void move_band (char dir)
  {
    if (dir == 'n' || dir == 'N')
      return;

    if (dir == 'r' || dir == 'R')
      bpos++;
    else if (dir == 'l' || dir == 'L')
      bpos--;
    else
      {
        cerr << "unknown direction for band moving: " << dir << endl;
        exit (1);
      }

    if (bpos >= 0)
      {
        if (bpos + 1 >= brlen)
          ext_band (10, true);
      }
    else
      {
        if ((abs (bpos) - 1) + 1 >= bllen)
          ext_band (10, false);
      }
  }

  void eval (bool quiet)
  {
    bool halt = false;
    state *cur_state = start_state;

    bpos = startpos;

    if (!cur_state)
      return;

    while (!halt)
      {
        char out = 0, dir = 0;
        state *next_st = 0;
        char in = get_cur_band_cell ();

        if (cur_state->get_next (in, out, dir, &next_st))
          {
            if (!quiet)
              this->print_band (cur_state);

            set_cur_band_cell (out);
            move_band (dir);

            if (in == out && (dir == 'n' || dir == 'N') && cur_state == next_st)
              halt = true;

            cur_state = next_st;
          }
        else
          {
            cerr << "undefined state occured! band pos: " << bpos << " char: '" << in
                 << "' current state: " << cur_state->name << endl;
            print_band ();
            exit (1);
          }
      }
    if (!quiet)
      cerr << "machine halted at position " << bpos << " on char '" << get_cur_band_cell () 
           << "' in state: " << cur_state->name << endl;
  }

  void print_band (state *cur_state = 0)
  {
    int i = 0;

    for (i = 0; i < bllen; i++)
      {
        int pos = (bllen - 1) - i;
        char c = lband[pos];

        if (cur_state && bpos < 0 && pos == (abs (bpos) - 1))
          {
            cout << "(" << cur_state->name << ")" << c;
          }
        else if (bpos < 0 && pos <= (abs (bpos) - 1))
          cout << "'" << c << "'";

        else if (c != '\0' && c != fill)
          {
            cout << c;
          }
      }

    for (i = 0; i < brlen; i++)
      {
        if (rband[i] != '\0')
          {
            if (cur_state && bpos >= 0 && i == bpos)
              cout << "(" << cur_state->name << ")";

            cout << rband[i];
          }
      }

    cout << endl;
  }
};

void ignore_to (string &s, const string &chrs)
{
  size_t p = s.find_first_of (chrs);
  if (p != 0)
    s.erase (0, p);
}

void ignore_to_not (string &s, const string &chrs)
{
  size_t p = s.find_first_not_of (chrs);
  if (p != 0)
    s.erase (0, p);
}

string get_to (string &s, const string &chrs)
{
  size_t p = s.find_first_of (chrs);
  string r;
  if (p != 0)
    {
      r = s.substr (0, p);
      s.erase (0, p);
    }
  return r;
}

string get_to_not (string &s, const string &chrs)
{
  size_t p = s.find_first_not_of (chrs);
  string r;
  if (p != 0)
    {
      r = s.substr (0, p);
      s.erase (0, p);
    }
  return r;
}

string get_delim (string &s, const string &d1, const string &d2)
{
  string r;

  ignore_to (s, d1);
  s.erase (0, 1);

  size_t p = s.find_first_of (d2);
  if (p != 0)
    {
      r = s.substr (0, p);
      s.erase (0, p + 1);
    }
  return r;
}

void TurM::read (FILE *f)
{
  char buf[1024];

  char *ostate = 0;
  char *instate = 0;
  char chr, dir, out;

  state *cur_state = 0;

  string input;
  char buffer[1024];

  while (fgets (buffer, 1024, f) != NULL)
    {
      input.append (buffer);
      input.append ("\n");
      input.erase (input.size () - 1, 1);
    }

  cerr << "reading turing machine definition:" << endl;

  string st;
  while (input.size () > 0)
    {
      switch (input[0])
        {
          case 'f':
            if (input.substr (0, 4) == "fill")
              {
                string nfill = get_delim (input, "'", "'");
                if (nfill.size () > 0)
                  {
                    set_fill (nfill[0]);
                    cout << "set fill character: '" << nfill[0] << "'" << endl;
                  }
              }
            break;
          case '@':
            {
              input.erase (0, 1);
              ignore_to_not (input, " \t\v\n\r");
              string pos = get_to (input, " \t\v\n\r,");
              ignore_to_not (input, " \t\v\n\r,");
              string stat = get_to (input, " \t\v\n\r");

              start_state = get_state (stat.c_str ());
              startpos = atoi (pos.c_str ());

              cerr << "Start State: " << stat << endl;
            }
            break;

          case '=':
            if (input.substr (0, 2) == "=>")
              {
                input.erase (0, 2);
                ignore_to_not (input, " \t\v\n\r");
                string st = get_to (input, " \t\v\n\r:=");

                cur_state = get_state (st.c_str ());

                if (!start_state)
                  {
                    start_state = cur_state;
                    cerr << "Start State: " << st << endl;
                  }

                cerr << "=> " << st << endl;
              }
            break;

          case ':':
            {
              string ins  = get_delim (input, ":", "|");
              string outs = get_to (input, ",");
              input.erase (0, 1);
              string dirs = get_to (input, "=");
              ignore_to (input, ">");
              input.erase (0, 1);
              ignore_to_not (input, " \t\v\n\r");
              string ost  = get_to (input, " \t\v\r\n:=");

              chr = ins[0];
              out = outs[0];
              dir = dirs[0];

              cur_state->add_edge (chr, out, dir, get_state (ost.c_str ()));
              cerr << ":" << chr << "|" << out << "," << dir << " => " << ost << endl;
            }
            break;

          default:
            input.erase (0, 1);
        }
    }

  cerr << "finished reading turing machine definition" << endl;
}

void TurM::read_input (FILE *f)
{
  string input;
  char buffer[1024];

  while (fgets (buffer, 1024, f) != NULL)
    {
      input.append (buffer);
      input.erase (input.size () - 1, 1);
    }

  if (input.size () > 0)
    {
      ext_band (input.size (), true);
      memcpy (rband, input.c_str (), sizeof (char) * input.size ());
      cerr << "band:" << endl;
      this->print_band ();
    }
}

int main (int argc, char *argv[])
{
  TurM t;

  if (argc < 2)
    {
      cerr << "usage: tmeval <machinedef-file> [<start-pos> [<start-state>]]" << endl;
      exit (1);
    }

  cerr << "Reading Machine definition from: " << argv[1] << endl;

  FILE *in = fopen (argv[1], "r");

  if (!in)
    {
      cerr << "COULDN't OPEN: " << argv[1] << ":" << strerror (errno) << endl;
      exit (1);
    }

  t.read (in);

  t.read_input (stdin);

  if (argc >= 3)
    {
      t.startpos = atoi (argv[2]);
    }

  if (argc > 3)
    {
      t.start_state = t.get_state (argv[3]);
    }

  t.eval (0);

  cerr << "band after execution:" << endl;
  t.print_band ();
  return 0;
}