/* Compilerdirektive  */

#include <stdio.h>
#include <stdlib.h>


#define EPS 256
#define MAX_TOKEN_CLASS 50
#define STRETCH 3

/* Datenstrukturen */

struct liste_typ
{   int elem;
	 struct liste_typ *next;
};

struct operation_typ_h
{	 int start, end;
	 struct operation_typ_h *next;
};

struct token_information_typ
{
	  int start;
	  int end;
	  struct liste_typ *DEA_end;
};

typedef struct liste_typ* htyp;
typedef struct operation_typ_h operation_typ;

operation_typ* operations;
htyp **nea;
struct token_information_typ token_information[MAX_TOKEN_CLASS];
struct liste_typ* startzustand;
int token_class=0;
int akt_zustand=0;
int DEA_index, ableitungs_index , endzustaende_index;


/* Funktionsdeklarationen */

/* schaetzt die Anzahl der benoetigten Zustaende des
nichtdeterministischen Automaten */

int max_anzahl_zustaende(char *name);

void init_nea(int bis_zustand);

/* gibt Speicherplatz, der durch die nea-Tabelle allokiert ist,
wieder frei: */
void delete_nea(struct liste_typ *nea[][EPS], int bis_zustand);

/* push fuegt die Nummer eines Folgezustands in liste ein */

void push(struct liste_typ **liste, int nummer);

/* nimmt den in nea[][EPS] gespeicherten NEA und fuehrt darauf den
Kleene-Abschluss durch. */
void huelle(void);

/* Angenommen man hat fuer den regulaeren Ausdruck r den
entsprechenden NEA R in nea stehen. Die folgende
Prozedur schreibt den Automaten R|buchstabe nach nea */
void vereinigung(void);

/* Analog zu vereinigung */
void conc(void);


/* liest eine zeile in datei und macht daraus einen NEA: */
void main_loop(char *name);

void atom(int buchstabe);

void ausgabe(int zustand, int eingabe)
{
	htyp h;
	printf("(%d, %c) ", zustand, (char) eingabe);
	h=nea[zustand][eingabe];
	while (!(h==NULL))
	{   printf("%d ", (*h).elem);
		 h=(*h).next;
	}
	printf("\n");
}

#include "dea.h"

main(int argc, char **argv)
{
	int i, j;

	/*if (argc==1)
	{
		printf("Dateinamen angeben !\n");
		exit(1);
	} */
	init_nea(STRETCH*max_anzahl_zustaende(argv[1]));
	main_loop(argv[1]);
	/* Test */
	for(i=0; i<=EPS; i++)
		for(j=0; j<=akt_zustand; j++)
			if(!(nea[j][i]==NULL)) ausgabe(j, i);
	printf("\n Aktueller Zustand: %d\n", akt_zustand);
	for(i=0; i<token_class; i++)
		printf("(%d, %d)\n", token_information[i].start, token_information[i].end);

	push(&startzustand, 0);
       	NEA2DEA();
	/* Ende des Tests */
	return 0;
}


void huelle(void)
{
	 int start, end;

	 start=(*operations).start;
	 end=(*operations).end;

	 push(&nea[akt_zustand+1][EPS], start);
	 push(&nea[akt_zustand+1][EPS], akt_zustand+2);

	 push(&nea[end][EPS], start);
	 push(&nea[end][EPS], akt_zustand+2);

	 (*operations).start=akt_zustand+1;
	 (*operations).end=akt_zustand+2;

	 akt_zustand=akt_zustand+2;


}

void atom(int buchstabe)
{
	operation_typ *h;

	push(&nea[akt_zustand+1][buchstabe], akt_zustand+2);

	h=(operation_typ*) calloc(1, sizeof(operation_typ));
	(*h).start=akt_zustand+1;
	(*h).end=akt_zustand+2;
	(*h).next=operations;
	akt_zustand=akt_zustand+2;
        operations=h;
}


void vereinigung(void)
{
	int start1, start2, end1, end2;

	start1=(*operations).start;
	end1=(*operations).end;
	operations=(*operations).next;
	start2=(*operations).start;
	end2=(*operations).end;

	push(&nea[akt_zustand+1][EPS], start1);
	push(&nea[akt_zustand+1][EPS], start2);

	push(&nea[end1][EPS], akt_zustand+2);
	push(&nea[end2][EPS], akt_zustand+2);

	(*operations).start=akt_zustand+1;
	(*operations).end=akt_zustand+2;

	akt_zustand=akt_zustand+2;
}





void conc(void)
{
	int start1, end1, start2, end2;

        start2=(*operations).start;
	end2=(*operations).end;
	operations=(*operations).next;
	start1=(*operations).start;
	end1=(*operations).end;

	push(&nea[end1][EPS], start2);
	(*operations).start=start1;
	(*operations).end=end2;
}


void init_nea(int bis_zustand)
{
	 int i,j;
	 if((nea=(htyp**) calloc(bis_zustand+1, sizeof(htyp*))) == NULL) exit(1);
	 for(i=0; i<=bis_zustand; i++)
		if((nea[i]=(htyp *) calloc(EPS+1, sizeof(htyp)))==NULL) exit(1);
	 for(i=0; i<=bis_zustand; i++)
		for(j=0; j<=EPS; j++)
			nea[i][j]=NULL;

}


void push(struct liste_typ **liste, int nummer)
{
		struct liste_typ *h;
		h=(struct liste_typ*) calloc(1, sizeof(struct liste_typ));
		(*h).elem=nummer;
		(*h).next=*liste;
		*liste=h;
}


int max_anzahl_zustaende(char *name)
{
	int count=0;
	FILE *datei;

	if((datei=fopen(name, "r"))==NULL)
	{	printf("Fehler beim Öffnen der Datei !\n");
		exit(2);
	}
	while (!feof(datei))
	{  fgetc(datei);
		count++;
	}
	fclose(datei);
	return count;
}

void main_loop(char *name)
{
	int h1, h2, h;
	int count;
	FILE *datei;

	if ((datei=fopen(name, "r"))==NULL)
	{
		printf("Fehler beim Öffnen der Datei !\n");
		exit(1);
	}
	while (!feof(datei))
	{
		printf("Token: %d\n", token_class);
		operations=NULL;
		while(1)
		{
			h1=fgetc(datei); h2=fgetc(datei);
			if (h1==((int) '\n')) break;
			else if (h1==(int) '\\') atom(h2);
				  else { ungetc(h2, datei);
							switch (h1)
							{ 	case ((int) '+'): conc(); break;
								case ((int) '|'): vereinigung(); break;
								case ((int) '*'): huelle(); break;
								default         : atom(h1);
							}
						  }
		}
		token_information[token_class].start=(*operations).start;
		token_information[token_class].end=(*operations).end;
		token_class++;
		while ((h=fgetc(datei))=='\n');
		if (!(h==EOF)) ungetc(h, datei);
	}
	for(count=0; count<token_class; count++)
		push(&nea[0][EPS], token_information[count].start);

	fclose(datei);
}