/* File: sma3.c
 * Author: Thierry Lecroq
 * Affiliation: University of Rouen, LITIS EA 4108
 * E-Mail: Thierry.Lecroq@univ-rouen.fr
 */

#include <stdio.h>

#define MAXSIZE 10
#define FIRSTLETTER 'a'
#define LASTLETTER  'z'
#define DELTA(q,c) trans[(q)][(c)-FIRSTLETTER]


/********************************
 * Output the initial automaton *
 ********************************/
void firstStep(FILE *FOUT) {

   fprintf(FOUT, "\\begin{frame}\n");
   fprintf(FOUT, "\\frametitle{String Matching Automaton of $\\varepsilon$}\n");

   fprintf(FOUT, "Initial automaton\n");
   fprintf(FOUT, "\\begin{tikzpicture}\n");
   fprintf(FOUT, "\\draw \\boundb;\n");
   fprintf(FOUT, "\\node[myState] at (-2,0) (q0) {$0$};\n");
   fprintf(FOUT, "\\path[->]\n");
   fprintf(FOUT, "(q0) edge [thick, loop above] node {$\\Sigma$} (q0)\n");
   fprintf(FOUT, ";\n");
   fprintf(FOUT, "\\end{tikzpicture}\n");
   fprintf(FOUT, "\\end{frame}\n");
}


/******************************
 * Output one step where:     *
 * - state m is added         *
 * - it is a clone of state r *
 ******************************/
void oneStep(char *x, int m, int r, int asize, int **trans, FILE *FOUT) {
   int i, j, q;
   char c;
   float ray, mid;

   fprintf(FOUT, "%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%\n");
   fprintf(FOUT, "\\newcommand{\\myCommand%c}[2]{%%\n", m+FIRSTLETTER);
   fprintf(FOUT, "\\begin{tikzpicture}\n");
   fprintf(FOUT, "\\draw \\boundb;\n");
   for (i = 0; i < m; ++i) {
      if (i == r)
         fprintf(FOUT, "\\node[mySourceState] at (%d,0) (q%d) {$%d$};\n", i-2, i, i);
      else
         fprintf(FOUT, "\\node[myState] at (%d,0) (q%d) {$%d$};\n", i-2, i, i);
   }
   fprintf(FOUT, "\\node[myActiveState] at (#1,#2) (q%d) {$%d$};\n", m, m);
   fprintf(FOUT, "\\path[->]\n");
   for (i = 0; i <= m; ++i) {
      for (j = 0; j < asize; ++j) {
         c = j+FIRSTLETTER;
         q = DELTA(i, c);
         if (q == i)
            if (q == 0)
               fprintf(FOUT, "(q0) edge [thick, loop above] node {$\\Sigma\\setminus\\{%c\\}$} (q0)\n", x[0]);
            else
               fprintf(FOUT, "(q%d) edge [thick, loop above] node {$%c$} (q%d)\n", i, c, q);
         else if (q == i+1)
            if (i == m-1 && q == m)
               fprintf(FOUT, "(q%d) edge [thick] node [above] {{\\color{red!50} $%c$}} (q%d)\n", i, c, q);
	    else
               fprintf(FOUT, "(q%d) edge [thick] node [above] {$%c$} (q%d)\n", i, c, q);
         else
            fprintf(FOUT, "(q%d) edge [thick, bend left = 75] node [above] {$%c$} (q%d)\n", i, c, q);
      }
   }
   fprintf(FOUT, ";\n");
   fprintf(FOUT, "\\end{tikzpicture}\n");
   fprintf(FOUT, "}\n");
   fprintf(FOUT, "\n");

   fprintf(FOUT, "\\begin{frame}\n");
   fprintf(FOUT, "\\frametitle{String Matching Automaton of $");
   for (i = 0; i < m-1; ++i) fprintf(FOUT, "%c", x[i]);
   fprintf(FOUT, "\\alert{%c}$}\n", x[m-1]);
   fprintf(FOUT, "State {\\color{red!50} %d} is a clone of state {\\color{green!50} %d}\n", m, r); 
   fprintf(FOUT, "\\begin{animateinline}[autoplay]{5}\n");
   fprintf(FOUT, "\\begin{tikzpicture}\n");
   fprintf(FOUT, "\\draw \\boundb;\n");
   for (i = 0; i < m; ++i) {
      if (i == r)
         fprintf(FOUT, "\\node[mySourceState] at (%d,0) (q%d) {$%d$};\n", i-2, i, i);
      else
         fprintf(FOUT, "\\node[myState] at (%d,0) (q%d) {$%d$};\n", i-2, i, i);
   }
   fprintf(FOUT, "\\node[myActiveState] at (%d,0) (q%d) {$%d$};\n", r-2, m, m);
   fprintf(FOUT, "\\path[->]\n");
   for (i = 0; i <= m; ++i) {
      for (j = 0; j < asize; ++j) {
         c = j+FIRSTLETTER;
         q = DELTA(i, c);
         if (q == i)
            if (q == 0)
               fprintf(FOUT, "(q0) edge [thick, loop above] node {$\\Sigma\\setminus\\{%c\\}$} (q0)\n", x[0]);
            else
               fprintf(FOUT, "(q%d) edge [thick, loop above] node {$%c$} (q%d)\n", i, c, q);
         else if (q == i+1)
            if (i == m-1 && q == m)
               fprintf(FOUT, "(q%d) edge [thick] node [above] {{\\color{red!50} $%c$}} (q%d)\n", i, c, q);
	    else
              fprintf(FOUT, "(q%d) edge [thick] node [above] {$%c$} (q%d)\n", i, c, q);
         else
            fprintf(FOUT, "(q%d) edge [thick, bend left = 75] node [above] {$%c$} (q%d)\n", i, c, q);
      }
   }
   fprintf(FOUT, ";\n");
   fprintf(FOUT, "\\end{tikzpicture}\n");

   fprintf(FOUT, "\\gdef\\x{%d}%% x initial value\n", r-2);
   fprintf(FOUT, "\\gdef\\y{0}%% y initial value\n");
   mid = ((r-2)+(m-2))/2.0;
   ray = mid - r + 2;
   fprintf(FOUT, "\\whiledo{\\lengthtest{\\x pt < %d pt}}{%%\n", m-2);
   fprintf(FOUT, "   \\FPeval{x}{0.1+(\\x)}%% new x\n");
   fprintf(FOUT, "   \\xdef\\x{\\x}%% make \\x global\n");
   fprintf(FOUT, "   \\FPeval{y}{((%f)*(%f)-(%f)*(%f)-(\\x)*(\\x)+2*(%f)*(\\x))^0.5}\n", ray, ray, mid, mid, mid);
   fprintf(FOUT, "   \\xdef\\y{\\y}%% make \\y global\n");
   fprintf(FOUT, "   \\newframe\n");
   fprintf(FOUT, "   \\myCommand%c{\\x}{\\y}%%\n", FIRSTLETTER+m);
   fprintf(FOUT, "}%%\n");

   fprintf(FOUT, "\\newframe\n");
   fprintf(FOUT, "\\begin{tikzpicture}\n");
   fprintf(FOUT, "\\draw \\boundb;\n");
   for (i = 0; i < m; ++i) {
      if (i == r)
         fprintf(FOUT, "\\node[mySourceState] at (%d,0) (q%d) {$%d$};\n", i-2, i, i);
      else
         fprintf(FOUT, "\\node[myState] at (%d,0) (q%d) {$%d$};\n", i-2, i, i);
   }
   fprintf(FOUT, "\\node[myActiveState] at (%d,0) (q%d) {$%d$};\n", m-2, m, m);
   fprintf(FOUT, "\\path[->]\n");
   for (i = 0; i <= m; ++i) {
      for (j = 0; j < asize; ++j) {
         c = j+FIRSTLETTER;
         q = DELTA(i, c);
         if (q == i)
            if (q == 0)
               fprintf(FOUT, "(q0) edge [thick, loop above] node {$\\Sigma\\setminus\\{%c\\}$} (q0)\n", x[0]);
            else
               fprintf(FOUT, "(q%d) edge [thick, loop above] node {$%c$} (q%d)\n", i, c, q);
         else if (q == i+1)
            if (i == m-1 && q == m)
               fprintf(FOUT, "(q%d) edge [thick] node [above] {{\\color{red!50} $%c$}} (q%d)\n", i, c, q);
	    else
               fprintf(FOUT, "(q%d) edge [thick] node [above] {$%c$} (q%d)\n", i, c, q);
         else
            fprintf(FOUT, "(q%d) edge [thick, bend left = 75] node [above] {$%c$} (q%d)\n", i, c, q);
      }
   }
   fprintf(FOUT, ";\n");
   fprintf(FOUT, "\\end{tikzpicture}\n");
   
   fprintf(FOUT, "\\end{animateinline}\n");

   fprintf(FOUT, "\\end{frame}\n");

}


/******************************
 * Output the final automaton *
 ******************************/
void lastStep(char *x, int m, int asize, int **trans, FILE *FOUT) {
   int i, j, q;
   char c;

   fprintf(FOUT, "\\begin{frame}\n");
   fprintf(FOUT, "\\frametitle{String Matching Automaton of $%s$}", x);
   fprintf(FOUT, "Final Automaton\n");
   fprintf(FOUT, "\\begin{tikzpicture}\n");
   fprintf(FOUT, "\\draw \\boundb;\n");
   for (i = 0; i <= m; ++i) {
         fprintf(FOUT, "\\node[myState] at (%d,0) (q%d) {$%d$};\n", i-2, i, i);
   }
   fprintf(FOUT, "\\path[->]\n");
   for (i = 0; i <= m; ++i) {
      for (j = 0; j < asize; ++j) {
         c = j+FIRSTLETTER;
         q = DELTA(i, c);
         if (q == i)
            if (q == 0)
               fprintf(FOUT, "(q0) edge [thick, loop above] node {$\\Sigma\\setminus\\{%c\\}$} (q0)\n", x[0]);
	    else
               fprintf(FOUT, "(q%d) edge [thick, loop above] node {$%c$} (q%d)\n", i, c, q);
         else if (q == i+1)
            fprintf(FOUT, "(q%d) edge [thick] node [above] {$%c$} (q%d)\n", i, c, q);
         else
            fprintf(FOUT, "(q%d) edge [thick, bend left = 75] node [above] {$%c$} (q%d)\n", i, c, q);
      }
   }
   fprintf(FOUT, ";\n");
   fprintf(FOUT, "\\end{tikzpicture}\n");
   fprintf(FOUT, "\\end{frame}\n");
}


/******************************************************************
 * Construction of the string matching automaton of x of length m *
 ******************************************************************/
int **smaComplete(char *x, int m, int asize) {
   int stateNb, i, q0, r, t, p;
   int **trans;
   char fileName[MAXSIZE];
   FILE *FOUT;

   strcpy(fileName, x);
   strcat(fileName, ".tex");
   FOUT = fopen(fileName, "w");
   fprintf(FOUT, "\\documentclass{beamer}\n");
   fprintf(FOUT, "\\usepackage{tikz}\n");
   fprintf(FOUT, "\\usepackage{animate}\n");
   fprintf(FOUT, "\\usepackage{fp}\n");
   fprintf(FOUT, "\\usefonttheme[onlymath]{serif}\n");

   fprintf(FOUT, "\\tikzstyle{myState}=[draw=blue!50,very thick,fill=blue!20,circle,inner sep =1pt]\n");
   fprintf(FOUT, "\\tikzstyle{myActiveState}=[draw=red!50,very thick,fill=red!20,circle,inner sep =1pt]\n");
   fprintf(FOUT, "\\tikzstyle{mySourceState}=[draw=green!50,very thick,fill=green!20,circle,inner sep =1pt]\n");
   fprintf(FOUT, "\\def\\boundb{(-3,3.5) rectangle (8,-3)}\n");
   fprintf(FOUT, "\\begin{document}\n");

   trans = (int **)malloc((m+1)*sizeof(int *));
   for (i = 0; i <= m; ++i)
      trans[i] = (int *)calloc(asize, sizeof(int));
   q0 = 0;
   stateNb = 1;
   t = q0;
   firstStep(FOUT);
   for (i = 0; i < m; ++i) {
      p = stateNb++;
      r = DELTA(t,x[i]);
      DELTA(t,x[i]) = p;
      memcpy(trans[p], trans[r], asize*sizeof(int));
      t = p;
      oneStep(x, p, r, asize, trans, FOUT);
   }
   lastStep(x, m, asize, trans, FOUT);
   // output the last frame
   fprintf(FOUT, "\\begin{frame}\n");
   fprintf(FOUT, "\\frametitle{Please cite}\n");
   fprintf(FOUT, "\\textit{Algorithms on strings}\n\n");
   fprintf(FOUT, "M. Crochemore, C. Hancart and T. Lecroq\n\n");
   fprintf(FOUT, "Cambridge University Press, 2007\n\n");
   fprintf(FOUT, "\\end{frame}\n");
   fprintf(FOUT, "\\end{document}\n");
   fclose(FOUT);
   return trans;
}


/********
 * Main *
 ********/
int main(int argc, char *argv[]) {
   char x[MAXSIZE];
   int asize, i, m;
   char c;
   int **trans;

   if (argc != 2) {
      printf("usage: %s string\n", argv[0]);
      exit(1);
   }
   strcpy(x, argv[1]);
   m = strlen(x);
   if (m > MAXSIZE-1) {
      printf("String length should not exceed %d\n", MAXSIZE-1);
      exit(1);
   }
   asize = 0;
   for (i = 0; i < m; ++i) {
      if (x[i] < FIRSTLETTER || x[i] > LASTLETTER) {
	 printf("Letters should be within %c and %c\n", FIRSTLETTER, LASTLETTER);
         exit(1);
      }
      if (x[i]-FIRSTLETTER+1 > asize) asize = x[i]-FIRSTLETTER+1;
   }
   trans = smaComplete(x, m, asize);
}