//Stephen Bassoli

#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#include "state.h"

#ifndef FAMANIP_H
#define FAMANIP_H

extern int currStateName = -1;
extern char alphabet[10] = "abcdefghi";

class FAmanip
{
	private:
		state *states[50];
		int numOfStates;
		state *comboStates[10];
		int numComboStates;

		int *Eclosure_helper(state* stateName);
		int *Condense(int *array);
		bool memberOf(int member, int *set);
		bool isEndState(int stateNum);

	public:
		FAmanip(int num = 1, int alphabetSize = 1);
		~FAmanip();
		int *Eclosure(int stateNum);
		int *alphaClosure(int stateNum, char a);
		int *EdEClosure(int stateNum, char a);
		void setConnection(int from, int to, char via);
		void setEndState(int stateNum);
		void printFA(void);
		void CONVERTtoNFA(void);
		void findComboStates(void);
		bool makeNewCombo(int stateNum);
		state *getComboState(int stateNum);
		state *getComboState(int *setOfStates);
		void NFAtoDFA(int stateNum);
		void COMBOStoDFA(void);
		void CONVERTtoDFA(void);
};

FAmanip::FAmanip(int num, int alphabetSize)
{
	for (int i = 0; i < num ; i++)
	{
		states[i] = new state;
	}
	numOfStates = num;
	numComboStates = 0;
	alphabet[alphabetSize] = '\0';
}

FAmanip::~FAmanip()
{
	delete [] *states;
}

void FAmanip::setConnection(int from, int to, char via)
{
	states[from]->Connect(states[to],via);
}

void FAmanip::printFA(void)
{
	char useless[2];
	for (int i = 0 ; i < numOfStates ; i++)
	{
		states[i]->printState();
		if (i%3 == 2)
		{
			cout << "Press Enter to continue";
			cin.getline(useless,2,'\n');
		}
	}
}

void FAmanip::setEndState(int stateNum)
{
	states[stateNum]->setEndState();
}

int *FAmanip::Eclosure(int stateNum)
{
	return Condense(Eclosure_helper(states[stateNum]));
}

int *FAmanip::Eclosure_helper(state *stateName)
{
	int *Etransversals;
	Etransversals = new int[60];
	Etransversals[0] = 1;
	Etransversals[1] = stateName->getName();
	if ((stateName->getEconnections()[0]) == 0)
		return Etransversals;
	else
	{
		for (int i = 1 ; i <= stateName->getEconnections()[0] ; i++)
		{
			Etransversals[++Etransversals[0]] = stateName->getEconnections()[i];
			if (Eclosure_helper(states[stateName->getEconnections()[i]])[0] > 1)
			{
				for (int j = 1 ; j <= Eclosure_helper(states[stateName->getEconnections()[i]])[0] ; j++)
				{
					Etransversals[++Etransversals[0]] = Eclosure_helper(states[stateName->getEconnections()[i]])[j];
				}
			}			
		}
		return Etransversals;
	}
}

int *FAmanip::alphaClosure(int stateNum, char a)
{
	return states[stateNum]->getConnections(a);
}

int *FAmanip::EdEClosure(int stateNum, char a)
{
	int *holder, *aholder, *Eholder;
	holder = aholder = Eholder = new int[30];
	holder = Eclosure(stateNum);
	aholder[0] = 0;
	Eholder[0] = 0;
	for (int i = 1 ; i <= holder[0] ; i++)
	{
		if (alphaClosure(holder[i],a)[0] > 0)
		{
			for (int j = 1 ; j <= alphaClosure(holder[i],a)[0] ; j++)
			{	
				aholder[++aholder[0]] = alphaClosure(holder[i],a)[j];
			}

		}
	}
	int index = aholder[0];
	for (int k = 1 ; k <= index ; k++)
	{
		for (int x = 1 ; x <= Eclosure(aholder[k])[0] ; x++)
		{
			Eholder[++Eholder[0]] = Eclosure(aholder[k])[x];
		}
	}
	return Condense(Eholder);
}

int *FAmanip::Condense(int *array)
{
	int *holder;
	holder = new int[15];
	holder[0] = 0;
	int size = array[0];
	int count = 1;
	bool add = true;
	for (int i = 1 ; i <= size ; i++)
	{
		for (int j = 1 ; j <= size ; j++)
		{
			if (array[i] == holder[j])
				add = false;
		}
		if (add)
		{
			holder[0]++;
			holder[count++] = array[i];
		}
		add = true;
	}
	return holder;
}

void FAmanip::CONVERTtoNFA(void)
{
	currStateName = -1;
	state* stateHolder;
	int alphaSize = strlen(alphabet);
	for (int i = 0 ; i < numOfStates ; i++)
	{
		stateHolder = new state;
		for (int j = 0 ; j < alphaSize ; j++)
		{
			for (int k = 1; k <= EdEClosure(i,alphabet[j])[0] ; k++)
			{
				if (EdEClosure(i,alphabet[j])[k] == i)
					stateHolder->Connect(stateHolder,alphabet[j]);
				else
					stateHolder->Connect(states[EdEClosure(i,alphabet[j])[k]],alphabet[j]);

			}
		}
		if (isEndState(i))
			stateHolder->setEndState();
		states[i]=stateHolder;
	}

}

bool FAmanip::isEndState(int stateNum)
{
	return states[stateNum]->IsEndState();
}

bool FAmanip::memberOf(int member, int *set)
{
	for (int i = 1 ; i <= set[0] ; i++)
	{
		if (member == set[i])
			return true;
	}
	return false;
}

void FAmanip::findComboStates(void)
{
	char numHolder[15] = "\0"; 
	char intTemp [15];
	for (int i = 0 ; i < numOfStates ; i++)
	{
		for (unsigned int j = 0 ; j < strlen(alphabet) ; j++)
		{
			if (states[i]->getConnections(alphabet[j])[0] == 0)				
				makeNewCombo(-1);
			else if (states[i]->getConnections(alphabet[j])[0] == 1)
				continue;
			else
			{
				for (int k = 1 ; k <= states[i]->getConnections(alphabet[j])[0] ; k++)
				{
					strcat(numHolder, itoa(states[i]->getConnections(alphabet[j])[k],intTemp,10));
					strcat(numHolder, "0");
				}
				numHolder[strlen(numHolder)-1] = '\0';
				makeNewCombo(atoi(numHolder));
				numHolder[0] = '\0';
			}
		}
	}
}

bool FAmanip::makeNewCombo(int stateNum)
{
	bool newState = true;
	for (int i = 0 ; i < numComboStates ; i++)
	{
		if ((comboStates[i]->getName()) == stateNum)
		{
			newState = false;
		}
	}
	if (newState)
	{
		comboStates[numComboStates++] = new state(stateNum);
		return true;
	}
	else
		return false;
}

state *FAmanip::getComboState(int stateNum)
{
	for (int i = 0 ; i < numComboStates ; i++)
	{
		if (comboStates[i]->getName() == stateNum)
		{
			return comboStates[i];
		}
	}
	return getComboState(-1);

}

state *FAmanip::getComboState(int *setOfStates)
{
	int *holder;
	bool one = false, two = false;
	char temp[20];
	holder = new int[20];
	if (setOfStates[0] == 0)
		return getComboState(-1);
	else if (setOfStates[0] == 1)
		return states[setOfStates[1]];
	for (int i = 0; i < numComboStates ; i++)
	{
		if (((strlen(itoa(comboStates[i]->getName(),temp,10))+1)/2) == setOfStates[0])
		{
			for (int x = 1 ; x <= setOfStates[0] ; x++)
			{
				if (int(temp[0]-48) == setOfStates[x])
				{
					one = true;
				}
				else if (int(temp[2]-48) == setOfStates[x])
				{
					two = true;
				}
			}
			if (one&&two)
				return comboStates[i];
			else
				one = two = false;
		}
	}
	return getComboState(-1);

}
void FAmanip::NFAtoDFA(int stateNum)
{
	char intTemp [15];
	state *stateHolder;
	stateHolder = new state;
	char numHolder[15] = "\0"; 
	for (unsigned int j = 0 ; j < strlen(alphabet) ; j++)
	{
		if (states[stateNum]->getConnections(alphabet[j])[0] == 0)
		{
			stateHolder->Connect(getComboState(-1),alphabet[j]);
		}
		else if (states[stateNum]->getConnections(alphabet[j])[0] == 1)
		{
			stateHolder->Connect(states[states[stateNum]->getConnections(alphabet[j])[1]],alphabet[j]);
		}
		else 
		{
			for (int k = 1 ; k <= states[stateNum]->getConnections(alphabet[j])[0] ; k++)
			{
				strcat(numHolder, itoa(states[stateNum]->getConnections(alphabet[j])[k],intTemp,10));
				strcat(numHolder, "0");
			}	
			numHolder[strlen(numHolder)-1] = '\0';
			stateHolder->Connect(getComboState(atoi(numHolder)),alphabet[j]);
			numHolder[0] = '\0';
		}
	}
	states[stateNum] = stateHolder;
}

void FAmanip::COMBOStoDFA(void)
{
	char intTemp[15];
	int theHolder[20];
	theHolder[0] = 0;
	bool setState = false;
	char numHolder[20] = "\0";
	for (int i = 0 ; i < numComboStates ; i++)
	{
		if (comboStates[i]->getName() == -1)
		{
			states[numOfStates++] = new state(-1);
			for (unsigned int j = 0 ; j < strlen(alphabet) ; j++)
				states[numOfStates-1]->Connect(states[numOfStates-1],alphabet[j]);
		}
		else
		{
			states[numOfStates++] = new state(comboStates[i]->getName());
			for (unsigned int y = 0 ; y < strlen(alphabet) ; y++)
			{	
				for (unsigned int x = 0 ; x <= strlen(itoa(states[numOfStates-1]->getName(),intTemp,10))-1 ; x = x + 2)
				{
					char temp[2];
					temp[0] = itoa(states[numOfStates-1]->getName(),intTemp,10)[x];
					temp[1] = '\0';
					int theNum = atoi(temp);
					for (int z = 1 ; z <= states[theNum]->getConnections(alphabet[y])[0] ; z++)
					{
						theHolder[++theHolder[0]] = states[theNum]->getConnections(alphabet[y])[z];
					}
				}
				states[numOfStates-1]->Connect(getComboState(Condense(theHolder)),alphabet[y]);
				theHolder[0] = 0;
			}
			
		}
	}
}

void FAmanip::CONVERTtoDFA(void)
{
	bool end = false;
	currStateName = -1;
	findComboStates();
	COMBOStoDFA();
	for (int y = numOfStates-numComboStates ; y < numOfStates ; y++)
	{
		char temp[20];
		char temp2[2];
		itoa(states[y]->getName(),temp,10);
		for (unsigned int x = 0 ; x <= strlen(temp)-1 ; x = x + 2)
		{
			temp2[0] = temp[x];
			temp2[1] = '\0';
			if (states[atoi(temp2)]->IsEndState())
				end = true;
		}
		if (end)
		{
			states[y]->setEndState();
			end = false;
		}
	}
	bool setState = false;
	for (int i = 0 ; i < numOfStates-numComboStates ; i++)
	{
		if (states[i]->IsEndState())
			setState = true;
		NFAtoDFA(i);
		if (setState)
		{
			states[i]->setEndState();
			setState = false;
		}
	}
}
#endif