/* File: sma2.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, "\\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 frame *
 ********************/
void aut2tex(char *x, int m, int asize, int **trans, FILE *FOUT) {
   int i, j, q;
   char c;

   fprintf(FOUT, "\\begin{frame}\n");
   if (m == 0)
      fprintf(FOUT, "\\frametitle{String Matching Automaton $\\Sigma^*$}\n");
   else {
      fprintf(FOUT, "\\frametitle{String Matching Automaton $");
      for (i = 0; i < m; ++i) fprintf(FOUT, "%c", x[i]);
      fprintf(FOUT, "$}\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, "\\usefonttheme[onlymath]{serif}\n");
   fprintf(FOUT, "\\tikzstyle{myState}=[draw=blue!50,very thick,fill=blue!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;
      aut2tex(x, i+1, asize, trans, FOUT);
   }
   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);
}