/* Dieses Programm macht aus einem NEA einen DEA 	*/



/* Definition des Typ: liste_typ */
typedef struct liste_typ liste_typ;



/* malloc fuer den Typ: liste_typ */
liste_typ* alloc_liste_typ()
{
	liste_typ *liste ;
		  if (( liste = (liste_typ *) malloc(sizeof(liste_typ ))) == NULL)
	{
		printf("Nicht genug Speicher vorhanden\n");
		exit(1);  /* bricht das Programm ab */
	};
	liste->next=NULL;
	liste->elem=NULL;
	return (liste);
}



/* Definiton des Typ: DEA_zustand */
typedef struct ableitungs_zeichen ableitungs_zeichen;
struct ableitungs_zeichen
{
  int symbol;
  liste_typ *folgezustand;
  int int_zustand;
  ableitungs_zeichen *next;
};

typedef struct DEA_zustand DEA_zustand;
struct DEA_zustand
{
  ableitungs_zeichen *eingaben;
  liste_typ *zustand_name;
  int int_zustand;
  int zuordnung;
  DEA_zustand *next;
};


/* malloc fuer den Typ: ableitungs_zeichen */
ableitungs_zeichen* alloc_ableitungs_zeichen()
{
	ableitungs_zeichen *zeichen_temp;
	if (( zeichen_temp = (ableitungs_zeichen *) malloc(sizeof(ableitungs_zeichen))) == NULL)
	{
		printf("Nicht genug Speicher vorhanden\n");
		exit(1);  /* bricht das Programm ab */
	};
	zeichen_temp->folgezustand=NULL;
	zeichen_temp->next=NULL;
	return (zeichen_temp);
}



/* malloc fuer den Typ: DEA_zustand */
DEA_zustand* alloc_DEA_zustand()
{
	DEA_zustand *DEA_temp;
	if (( DEA_temp = (DEA_zustand *) malloc(sizeof(DEA_zustand))) == NULL)
	{
		printf("Nicht genug Speicher vorhanden\n");
		exit(1);  /* bricht das Programm ab */
	};
	DEA_temp->eingaben=NULL;
	DEA_temp->zustand_name=NULL;
	DEA_temp->next=NULL;
	DEA_temp->zuordnung=0;
	return (DEA_temp);
}



/*Ueberprueft, ob die Liste leer ist */
int leer(liste_typ *liste)
{
	return (!liste);
}

/*Ueberprueft, ob ein Element schon in einer Liste steht */
int enthalten(liste_typ *liste,int element)
{
	while (!leer(liste))
	{
		if (liste->elem == element) return (1);
		liste=liste->next;
	};
	return(NULL);
}


/* einfuegen eines Elementes in eine Liste */
liste_typ* einfuegen(liste_typ *liste,int element)
{
	liste_typ *neues_elem , *anfangszustand;
	anfangszustand=liste;
	neues_elem=alloc_liste_typ();
	neues_elem->elem=element;
	if (leer(liste))
	{
		anfangszustand=neues_elem;
		neues_elem->next=NULL;
	} else                    /*was ist, wenn das erste elem > element ist? */
	{
		if (liste->elem > element)
		{
			neues_elem->next=liste;
			anfangszustand=neues_elem;
		} else
		{
			while (!leer(liste->next) && (liste->next->elem > element))
			{
				liste=liste->next;
			};
			neues_elem->next=liste->next;
			liste->next=neues_elem;
		};
	};
	return (anfangszustand);
}

/* entfernt des erste Element aus einer Liste */
liste_typ* remove_first(liste_typ *stack)
{
	liste_typ *first;       /* ist das richtig???? */
	if (!leer(stack))
	{
		first=stack->next;
		free(stack);
		return (first);
	} else return (NULL);
}

/* kopiert eine Liste in eine andere */
liste_typ* kopiere_liste(liste_typ *quelle)
{
	liste_typ *next_elem , *ziel_anfang , *ziel;
	if (!leer(quelle))
	{
		ziel=alloc_liste_typ();
		ziel_anfang=ziel;
		ziel->elem=quelle->elem;
	
	} else	return(NULL);


	while (!leer(quelle->next))
	{	quelle=quelle->next;
		next_elem=alloc_liste_typ();
		ziel->next=next_elem;
		ziel=ziel->next;
		ziel->elem=quelle->elem;
	
	};
	ziel->next=NULL;
	return (ziel_anfang);
}


/*vergleicht zwei Listen miteinander */
int gleich(liste_typ *erste_liste,liste_typ *zweite_liste)
{
	while ((!leer(erste_liste)) && (!leer(zweite_liste)))
	{
		if (erste_liste->elem == zweite_liste->elem)
		{
			erste_liste=erste_liste->next;
			zweite_liste=zweite_liste->next;
		} else return (NULL);
	};
	if (leer(erste_liste) && leer(zweite_liste))
		return (1);
		else return (NULL);
}



/* erstellt eine Menge von moeglichen Epsilon-Uebergaengen  */
liste_typ* e_umgebung(liste_typ *zustand_liste)
{
	liste_typ *stack , *e_liste;
	int elem , e_elem;

	stack=kopiere_liste(zustand_liste);
	while (!leer(stack))
	{
		elem=stack->elem;
		stack=remove_first(stack);
		e_liste=nea[elem][EPS];
		while (!leer(e_liste))
		{
			e_elem=e_liste->elem;
			e_liste=e_liste->next;
			if (!enthalten(zustand_liste,e_elem))
			{
				stack=einfuegen(stack,e_elem);
				zustand_liste=einfuegen(zustand_liste,e_elem);
			};
		};
	};
	return (zustand_liste);
}


/* erstellen der Ableitungsmenge einer Zustandsmenge mit einem Symbol */
liste_typ* move(liste_typ *liste, int symbol)
{
	liste_typ *ableitungsliste , *zustaendeliste;
	int element , zustand;

	ableitungsliste=alloc_liste_typ();
	ableitungsliste=NULL;

	while (!leer(liste))
	{
		element=liste->elem;
		liste=liste->next;
		zustaendeliste=nea[element][symbol];

		while (!leer(zustaendeliste))
		{
			zustand=zustaendeliste->elem;
			zustaendeliste=zustaendeliste->next;
			if (!enthalten(ableitungsliste,zustand))
			{
				ableitungsliste=einfuegen(ableitungsliste,zustand);
			};
		};
	};
	return (ableitungsliste);
}


/* Fuegt ein neues DEA-Element in den DEA ein */
void einfuegen_DEA(DEA_zustand *DEA,liste_typ *name)
{
	DEA_zustand *neuer_DEA_zustand;
	neuer_DEA_zustand=alloc_DEA_zustand();
	neuer_DEA_zustand->int_zustand = DEA_index;
	neuer_DEA_zustand->zustand_name = name;

	while (!(DEA->next)==NULL) DEA=DEA->next;
	DEA->next = neuer_DEA_zustand;
}


/* Prueft, ob eine Zustand schon im DEA vorhanden ist */
int ableitung_enthalten_DEA(liste_typ *ableitung,DEA_zustand *DEA)
{
	while (!DEA==NULL)
	{
		if (gleich(ableitung,DEA->zustand_name)) return (1);
		else DEA=DEA->next;
	};
	return (NULL);
}



/* Fuegt ein neues Zeichen mit zugehoeriger Ableitung zu einem DEA-Zustand hinzu */
void einfuegen_DEA_zeichen(DEA_zustand *DEA_anfang,DEA_zustand *DEA,int symbol,liste_typ *ableitung)
{
	ableitungs_zeichen *neues_ableitungs_zeichen,*einfuege_stelle;
	neues_ableitungs_zeichen = alloc_ableitungs_zeichen();
	neues_ableitungs_zeichen->symbol = symbol;
	neues_ableitungs_zeichen->folgezustand = ableitung;
	neues_ableitungs_zeichen->next = NULL;
	if (ableitung_enthalten_DEA(ableitung,DEA_anfang))
	{
		DEA_zustand *temp_DEA;
		temp_DEA=DEA_anfang;
		while (!leer(temp_DEA->zustand_name))
		{
			if (gleich(temp_DEA->zustand_name,ableitung))
			{
				neues_ableitungs_zeichen->int_zustand=temp_DEA->int_zustand;
				break;
			} else temp_DEA=temp_DEA->next;
		};
	} else
	{
		DEA_index++;  
		neues_ableitungs_zeichen->int_zustand= DEA_index;
		einfuegen_DEA(DEA_anfang,ableitung);
	};
	if (!(DEA->eingaben)==NULL)
	    {
	      einfuege_stelle=DEA->eingaben;
	      while (!(einfuege_stelle->next) == NULL)	einfuege_stelle=einfuege_stelle->next;
	      einfuege_stelle->next=neues_ableitungs_zeichen;
	    } else DEA->eingaben=neues_ableitungs_zeichen;
	      

}

/* Token neu zuordnen */
void token_neu_zuordnen(DEA_zustand *DEA_anfang)
{
	DEA_zustand *DEA_temp;
	int token;
	endzustaende_index=0;
	for (token=0 ; token < token_class ; token++)
	{
		DEA_temp = DEA_anfang;
		while (!leer(DEA_temp->zustand_name))
		{
			if (enthalten(DEA_temp->zustand_name,token_information[token].end) && DEA_temp->zuordnung==0)
			{
				token_information[token].DEA_end=einfuegen(token_information[token].DEA_end,DEA_temp->int_zustand);
				endzustaende_index++;
				DEA_temp->zuordnung=1;
				/*	break; */
			}; 
			  if (!DEA_temp->next==NULL) DEA_temp = DEA_temp->next;
			  else break;
		};
	};
}


/* ausgeben des DEA in eine Datei */
void DEA_ausgeben(DEA_zustand *DEA)
{
	ableitungs_zeichen *ableitungs_temp;
	int token;
	liste_typ *DEA_end_liste;
	FILE *stream;
	remove("DEA.OUT");
	stream = fopen("DEA.OUT", "w");
	fprintf(stream, "anzahl_der_Zustaende: %d\n",(DEA_index+1));
	fprintf(stream, "anzahl_der_Endzustaende: %d\n",endzustaende_index);
	for (token = 0 ; token < token_class ; token ++)
	{
   	        DEA_end_liste=token_information[token].DEA_end;
		while(!leer(DEA_end_liste))
		  {
		    fprintf(stream, "%d %d\n",DEA_end_liste->elem,(token+1));
		    DEA_end_liste=DEA_end_liste->next;
		  };
	};
	fprintf(stream, "anzahl_der_Abbildungen: %d\n",ableitungs_index);


	while (!leer(DEA->zustand_name))
	{
		ableitungs_temp=DEA->eingaben;
		while (!ableitungs_temp == NULL)
		{
			fprintf(stream, "%d %d %d\n",DEA->int_zustand,ableitungs_temp->symbol,ableitungs_temp->int_zustand);
			ableitungs_temp = ableitungs_temp->next;
		};
		if (!DEA->next==NULL) DEA = DEA->next;
		else break;
	};

	fclose(stream);
}


/* Das NEA2DEA-Hauptprogramm */

void NEA2DEA()
  {

	 DEA_zustand *DEA_anfang;
	 DEA_zustand *DEA;
	 int symbol ;
	 DEA_index = 0 ;
	 ableitungs_index = 0 ;

	 printf("bin in NEA2DEA \n");
	 DEA = alloc_DEA_zustand();
	 DEA_anfang = DEA;
         DEA->int_zustand = DEA_index;
	
	 DEA->zustand_name = e_umgebung(startzustand);


	 while (!leer(DEA->zustand_name))
	 {
		for (symbol=0 ;symbol <= (EPS-1) ; symbol++)
		{
			liste_typ *ableitungen;
			ableitungen = e_umgebung(move(DEA->zustand_name,symbol));
			if (!leer(ableitungen))
			{
				ableitungs_index++;
				einfuegen_DEA_zeichen(DEA_anfang,DEA,symbol,ableitungen);

			};

		};
		if (!DEA->next==NULL) DEA = DEA->next;
		else break;printf("DEA_index:von %d noch %d \n",DEA_index,(DEA_index - DEA->int_zustand));
	 };
	 token_neu_zuordnen(DEA_anfang);
	 DEA_ausgeben(DEA_anfang);
}