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

// Version: 1.1
// Changes:
// 1.1 - Fixed a bug with newline handling

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <list>
#include <stack>
#include <cerrno>
#include <map>

using namespace std;

struct state
{
  string name;
  bool end_state;
  map<char, list <state*> > transitions;

  state (const string &n)
    : name (n)
  {
    end_state = (n[0] == '*');
  }

  void add_edge (char c, state *s)
  {
    transitions[c].push_back (s);
  }

  list <state *> get_edges (char c)
  {
    list <state*> l;

    if (transitions.find (c) != transitions.end ())
      return transitions[c];
    else
      return l;
  }

  void print ()
  {
    map<char, list <state*> >::iterator i = transitions.begin ();

    for (; i != transitions.end (); i++)
      {
        cout << name << " -" << i->first << "-> ";

        for (list<state*>::iterator j = i->second.begin (); j != i->second.end (); j++)
          cout << (*j)->name << ",";

        cout << endl;
      }
  }
};



struct state_coll
{
  list <state *> states;

  void add (state *s)
  {
    states.push_back (s);
  }

  bool operator==(const state_coll &s)
  {
    for (list<state*>::const_iterator i = states.begin (); i != states.end (); i++)
      {
        const string &n = (*i)->name;

        bool found = false;

        for (list<state*>::const_iterator j = s.states.begin (); j != s.states.end (); j++)
          {
            if (n == (*j)->name)
              {
                found = true;
                break;
              }
          }

        if (!found)
          return false;
      }

    for (list<state*>::const_iterator i = s.states.begin (); i != s.states.end (); i++)
      {
        const string &n = (*i)->name;

        bool found = false;

        for (list<state*>::const_iterator j = states.begin (); j != states.end (); j++)
          {
            if (n == (*j)->name)
              {
                found = true;
                break;
              }
          }

        if (!found)
          return false;
      }

    return true;
  }

  state_coll *states_for (char c)
  {
    state_coll *stc = new state_coll;

    for (list<state*>::iterator i = states.begin (); i != states.end (); i++)
      {
        list <state*> s = (*i)->get_edges (c);

        if (s.size () > 0)
          for (list<state*>::iterator j = s.begin (); j != s.end (); j++)
            stc->add (*j);
      }

    return stc;
  }

  void print () const
  {
    cout << "{ ";

    for (list<state*>::const_iterator i = states.begin (); i != states.end (); i++)
      cout << (*i)->name << " ";

    cout << "}" << endl;
  }
};

struct nfa
{
  map<string, state*> states;

  state *start_state;

  list<state*> end_states;

  char *charset;
  char epsilon_char;

  nfa () : start_state (0), charset (0) {}

  void read (FILE *f)
  {
    if (fscanf (f, "charset: %as (%c) ", &charset, &epsilon_char) != 2)
    {
      cerr << "No charset given on first line!" << endl;
      exit (1);
    }
    cout << "charset: '" << charset << "' epsilon: " << epsilon_char << endl;

    char *state_from, *state_to, *chr;

    int cnt = 0;
    while ((cnt = fscanf (f, "%as %as %as ", &state_from, &chr, &state_to)) != EOF)
      {
        if (cnt != 3)
          continue;

        for (int i = 0; i < strlen (chr); i++)
          this->add_state (state_from, state_to, chr[i]);

        if (!start_state)
          start_state = get_state (state_from);

        free (state_from);
        free (state_to);
        free (chr);
      }
  }

  state *get_state (const string &name)
  {
    if (states.find (name) == states.end ())
      {
        state *s = new state (name);

        if (s->end_state)
          end_states.push_back (s);

        return states[name] = s;
      }

    return states[name];
  }

  void add_state (const string &from, const string &to, const char &c)
  {
    get_state (from)->add_edge (c, get_state (to));
  }

  void print_states ()
  {
    map<string, state*>::iterator i = states.begin ();

    for (; i != states.end (); i++)
      {
        cout << i->first << ":" << endl;
        i->second->print ();
        cout << "------------" << endl;
      }
  }


  void subset_trans ()
  {
    list<state_coll *> outst;
    stack<state_coll *> work;

    state_coll *c = new state_coll;
    c->add (start_state);

    outst.push_back (c);
    work.push (c);

    while (!work.empty ())
      {
        c = work.top ();
        work.pop ();

        for (int i = 0; i < strlen (charset); i++)
          {
            state_coll *c2 = c->states_for (charset[i]);

            bool found = false;

            for (list<state_coll*>::iterator i = outst.begin (); i != outst.end (); i++)
              {
                if (*(*i) == (*c2))
                  {
                    found = true;
                    break;
                  }
              }

            if (!found)
              {
                outst.push_back (c2);
                work.push (c2);
              }
            else
              delete c2;
          }
      }

    for (list<state_coll*>::iterator i = outst.begin (); i != outst.end (); i++)
      {
        (*i)->print ();
      }
  }
};

int main (int argc, char *argv[])
{
  nfa a;

  if (argc > 1)
    {
      if (string (argv[1]) == "-h")
        {
          cerr << "usage: nfa-util [<input-file>]" << endl;
          exit (0);
        }

      FILE *f = fopen (argv[1], "r");
      if (!f)
        {
          cerr << "Couldn't open '" << argv[1] << "' :" << strerror (errno) << endl;
          exit (1);
        }

      a.read (f);
    }
  else
    a.read (stdin);

  a.print_states ();
  cout << "DFA (from subset construction):" << endl;
  a.subset_trans ();
}