// REManage.cpp: implementation of the REManage class.
//
//////////////////////////////////////////////////////////////////////
#pragma warning(disable:4786)

#include "REManage.h"
#include <iostream>
#include <fstream>
#include <algorithm>
#include <stack>
#include <windows.h>

using namespace std;
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

REManage::REManage()
{
	out.open("Result.txt");
	this->state=1;
	this->isREUpdate=false;
	this->isNFAUpdate=false;
	this->isDFAUpdate=false;
}	
REManage::REManage(string re)
{
	this->state=1;
	this->re=re;
	this->isREUpdate=true;
}	
REManage::~REManage()
{	
}
void REManage::MakeNFA_S(char input,NFA* n,vector<EDGE>& edge)
{
	EDGE e;
	if(n->start==0&&n->end==0)
	{
		e.start=n->start=state;
		e.input=input;
		e.end=n->end=++state;
		
		state++;
	}
	else
	{
		e.start=n->start;
		e.input=input;
		e.end=n->end;
	}
	
	edge.push_back(e);
}
void REManage::MakeNFA_OR(NFA* result,NFA* left,NFA* right,vector<EDGE>& edge)
{
	NFA temp;
	result->start=temp.start=state;
	temp.end=left->start;
	MakeNFA_S('@',&temp,edge);	
	
	temp.start=state;
	temp.end=right->start;
	MakeNFA_S('@',&temp,edge);
	
	temp.start=left->end;
	temp.end=++state;
	MakeNFA_S('@',&temp,edge);
	
	temp.start=right->end;
	result->end=temp.end=state;
	MakeNFA_S('@',&temp,edge);
	
	state++;
}
void REManage::MakeNFA_AND(NFA* result,NFA* left,NFA* right,vector<EDGE>& edge)
{
	result->start=left->start;
	result->end=right->end;
	
	for(int i=0;i<edge.size();i++)
	{
		if(edge[i].start==right->start)
		{
			edge[i].start=left->end;
		}
	}
}
void REManage::MakeNFA_CL(NFA* result,NFA* op,vector<EDGE>& edge)
{
	NFA temp;
	result->start=temp.start=state;
	temp.end=op->start;
	MakeNFA_S('@',&temp,edge);
	
	temp.start=op->end;
	result->end=temp.end=++state;
	MakeNFA_S('@',&temp,edge);
	
	temp.start=op->end;
	temp.end=op->start;
	MakeNFA_S('@',&temp,edge);
	
	temp.start=result->start;
	temp.end=result->end;
	MakeNFA_S('@',&temp,edge);
	
	state++;	
}
int REManage::type(char re)
{
	if(re=='*'||re=='|')
		return OP;
	else if(re!='('&&re!=')')
		return OP_D;
	else
		return -1;
}

void REManage::ProcessREToNFA()
/*
===================
輸入：
	  re
	  REInput
===================
輸出：
	  NFA_EDGE
	  NFAInput
	  startNFA
	  endNFA
===================
*/
{
	stack<char> st;			//操作符堆棧，保存處理過程中遇到的操作符
	stack<NFA> sNFA;		//NFA堆棧，保存處理過程中產(chǎn)生的NFA

	NFA nfa,temp;
	NFA result;				//臨時(shí)變量

	/**************************Process RE***********************/
	for(int i=0;i<re.length();i++)
	{
		if(re[i]=='(')
		{
			st.push(re[i]);
		}
		else if(type(re[i])==OP_D)
		{
			/************Get input of RE************/
			if(find(REInput.begin(),REInput.end(),re[i])==REInput.end())
				REInput.push_back(re[i]);	
			/******************End*******************/

			nfa.start=0;
			nfa.end=0;
			MakeNFA_S(re[i],&nfa,NFA_EDGE);

			sNFA.push(nfa);
			if(sNFA.size()>=2)
			{
				if(st.size()>0&&st.top()=='|')
				{
					st.pop();
					
					temp=sNFA.top();
					sNFA.pop();
					nfa=sNFA.top();
					sNFA.pop();
					
					MakeNFA_OR(&result,&nfa,&temp,NFA_EDGE);
					sNFA.push(result);
				}
				else if(i>0&&re[i-1]!='(')
				{
					temp=sNFA.top();
					sNFA.pop();
					nfa=sNFA.top();
					sNFA.pop();
					
					MakeNFA_AND(&result,&nfa,&temp,NFA_EDGE);
					sNFA.push(result);
				}
			}
		}
		else if(type(re[i])==OP)
		{
			if(re[i]=='*')
			{
				nfa=sNFA.top();
				sNFA.pop();
				MakeNFA_CL(&result,&nfa,NFA_EDGE);
				sNFA.push(result);
			}
			else if(re[i]=='|')
			{
				st.push(re[i]);
			}
		}
		else if(re[i]==')')
		{
			st.pop();
			if(sNFA.size()>=2)
			{	
				temp=sNFA.top();
				sNFA.pop();
				nfa=sNFA.top();
				sNFA.pop();
				
				MakeNFA_AND(&result,&nfa,&temp,NFA_EDGE);
				sNFA.push(result);
			}
		}
	}
	/*******************************End*********************************/

	/****************Get start and end state of NFA************/
	if(sNFA.size()>0)
	{
		startNFA.push_back(sNFA.top().start);
		endNFA.push_back(sNFA.top().end);

	}
	/**************************End**************************/

}

void REManage::Find_NULL_Closure(vector<int> input, 
								 vector<int>&output,
								 vector<EDGE> edge)
{
	stack<int> state;

	output.clear();

	sort(input.begin(),input.end());

	for(int i=0;i<input.size();i++)
		state.push(input[i]);
	int temp=0;

	while(state.size()>0)
	{		
		output.push_back(state.top());
		temp=state.top();
		state.pop();
		for(int j=0;j<NFA_EDGE.size();j++)
			if(edge[j].start==temp&&edge[j].input=='@')
				state.push(edge[j].end);
	}

	sort(output.begin(),output.end());
}

void REManage::Move(vector<int> input,char in,vector<int>&result,vector<EDGE> edge)
{
	vector<int> temp;
	temp.clear();
	result.clear();
	
	for(int i=0;i<input.size();i++)
	{
		for(int j=0;j<edge.size();j++)
			if(edge[j].start==input[i]&&edge[j].input==in)
				temp.push_back(edge[j].end);
	}
	
	Find_NULL_Closure(temp,result,edge);
}

void REManage::ProcessNFAToDFA()
/*
===================
輸入：
	  NFA_EDGE
	  NFAInput
	  startNFA
	  endNFA
===================
輸出：
	  startDFA
	  endDFA
	  nonEndDFA
	  DFA_EDGE
	  DFAStateGather
===================
*/
{
	EDGE edge;				//臨時(shí)變量
	vector<int> DFAState;	//臨時(shí)變量，保存某一狀態(tài)集

	//vector<int> start;		//開始狀態(tài)集，實(shí)際只有一個(gè)元素
	int	over=-1;			//標(biāo)記已處理過的狀態(tài)集


	//由NFA得到初始狀態(tài)集
	Find_NULL_Closure(startNFA, DFAState,NFA_EDGE);

	DFAStateGather.push_back(DFAState);
	startDFA=DFAStateGather.size()-1;	//得到初始狀態(tài)
	
	/*=========================add=========================*/
	for(int m=0;m<endNFA.size();m++)
	{
		if(find(DFAState.begin(),DFAState.end(),endNFA[m])!=DFAState.end())
			break;
	}
	
	if(m<endNFA.size())
		endDFA.push_back(DFAStateGather.size()-1);
	else
		nonEndDFA.push_back(DFAStateGather.size()-1);
	/*=========================add=========================*/

	/*****************Process NFA**********************/
	queue<vector<int> > tempState;
	tempState.push(DFAState);
	vector<vector<int> >::iterator iter;
	while(tempState.size()>0)
	{
		over++;

		edge.start=find(DFAStateGather.begin(),DFAStateGather.end(),
				tempState.front())-DFAStateGather.begin();

		for(int i=0;i<NFAInput.size();i++)
		{
			//求隊(duì)列首狀態(tài)集在輸入為input[i]時(shí)的結(jié)果狀態(tài)
			Move(tempState.front(),NFAInput[i],DFAState,NFA_EDGE);	
			if(DFAState.size()<1)
				break;
			//填充DFA的邊					
			edge.input=NFAInput[i];
			
			iter=find(DFAStateGather.begin(),DFAStateGather.end(),DFAState);
			
			//如果所產(chǎn)生的狀態(tài)集不在DFAStateGather中，則保存該狀態(tài)集
			if(iter==DFAStateGather.end())
			{	
				DFAStateGather.push_back(DFAState);
				
				/*=========================add=========================*/
				for(int m=0;m<endNFA.size();m++)
				{
					if(find(DFAState.begin(),DFAState.end(),endNFA[m])!=DFAState.end())
						break;
				}
				
				if(m<endNFA.size())
					endDFA.push_back(DFAStateGather.size()-1);
				else
					nonEndDFA.push_back(DFAStateGather.size()-1);
				/*=========================add=========================*/

				edge.end=DFAStateGather.size()-1;	
			}
			else
				edge.end=iter-DFAStateGather.begin();
			//保存邊
			DFA_EDGE.push_back(edge);

			if(DFAState!=tempState.front()&&edge.end>over)
				tempState.push(DFAState);
		}
		tempState.pop();
	}
	/*************************End*******************************/
}

/*消除DFA中的無用狀態(tài)*/
void REManage::RemoveFutility()
/*
===================
輸入：
	  miniStartDFA
	  miniEndDFA
      miniNonEndDFA
	  MiniDFA_EDGE
	  miniStateGather
===================
輸出：
	  miniStartDFA
	  miniEndDFA
      miniNonEndDFA
	  MiniDFA_EDGE
	  miniStateGather	  
===================
*/
{

	vector<int>	reachedState;
	queue<int>	reached;

	vector<int> startGather;
	vector<int>	endGather;

	reachedState.clear();	


	/****************Generate reached state*******************/
	reached.push(miniStartDFA);
	reachedState.push_back(miniStartDFA);

	while(reached.size()>0)
	{
		int front=reached.front();
		reached.pop();

		for(int i=0;i<MiniDFA_EDGE.size();i++)
		{
			if(find(DFAInput.begin(),DFAInput.end(),MiniDFA_EDGE[i].input)
				==DFAInput.end())
				DFAInput.push_back(MiniDFA_EDGE[i].input);

			if(MiniDFA_EDGE[i].start==front)
			{
				if(find(reachedState.begin(),reachedState.end(),MiniDFA_EDGE[i].end)
					==reachedState.end())
				{
					reachedState.push_back(MiniDFA_EDGE[i].end);
					reached.push(MiniDFA_EDGE[i].end);
				}
			}
		}
	}
	sort(reachedState.begin(),reachedState.end());
	/*****************************end******************************/

	/****************Update the edge of DFA*******************/
	vector<EDGE>::iterator iterEDGE;
	
	for(int i=0;i<MiniDFA_EDGE.size();i++)
	{
		if(find(reachedState.begin(),reachedState.end(),MiniDFA_EDGE[i].start)
			==reachedState.end())
		{
			iterEDGE=MiniDFA_EDGE.begin()+i;
			MiniDFA_EDGE.erase(iterEDGE++);
			i--;
		}
	}
	/*****************************end******************************/

	/****************Update the end state of DFA*******************/
	vector<int>::iterator iterEnd;
	for(i=0;i<miniEndDFA.size();i++)
	{
		if(find(reachedState.begin(),reachedState.end(),miniEndDFA[i])
			==reachedState.end())
		{
			iterEnd=miniEndDFA.begin()+i;
			miniEndDFA.erase(iterEnd++);
			i--;
		}
	}
	/*****************************end******************************/
	
	/******************remove not end state************************/	
	int initSize=reachedState.size()+1;

	while(reachedState.size()<initSize)
	{
		initSize=reachedState.size();

		startGather.clear();
		endGather.clear();

		for(int m=0;m<MiniDFA_EDGE.size();m++)
		{
			if(find(startGather.begin(),startGather.end(),MiniDFA_EDGE[m].start)
				==startGather.end())
				startGather.push_back(MiniDFA_EDGE[m].start);