User:Antigng-bot/regex/DFAMinimize

#include <stdlib.h>
#include "DFAProcess.h"
#include "struct.h"

int *GroupList=NULL;
int *Offset=NULL;
int MDFATop=0;
struct _DFANode *MDFAStates=NULL;
struct queue *GroupQueue=NULL;
static void DFAMIni()
{
	int count=0;
	struct queue *local_queue=queueini();
	GroupQueue=queueini();
	GroupList=(int *)calloc(sizeof(int)*DFATop,1);
	Offset=(int *)calloc(sizeof(int)*DFATop,1);
	for(;count<DFATop;count++)
	{
		Offset[count]=count;
		if(!(GroupList[count]=DFAStates[count].type))
		{
			queuepush(GroupQueue,Offset+count);
		}
		else
		{
			queuepush(local_queue,Offset+count);
		}
	}
	while(!queueisnull(local_queue))
	{
		int *p=NULL;
		queuepop(local_queue,&p);
		queuepush(GroupQueue,p);
	}
	MDFATop=2;
	free(local_queue);
	return;
}
static int DFAMEssentiallyTheSame(struct _DFACharChain *chain1,struct _DFACharChain *chain2)
{
	while(chain1&&chain2)
	{
		if((chain1->ch)!=(chain2->ch)) return 0;
		if(GroupList[chain1->state]!=GroupList[chain2->state]) return 0;
		chain1=chain1->next;
		chain2=chain2->next;
	}
	return !(chain1||chain2);
}
static void DFAGroupStates()
{
	struct queue *local_queue=queueini();
	while(1)
	{
		int count=0;
		int splitted=0;
		int pre_state=-1;
		int *p=NULL,*compare_p=NULL;
		for(count=0;count<DFATop;count++)
		{
			queuepop(GroupQueue,&p);
			if(pre_state!=GroupList[*p])
			{

				pre_state=GroupList[*p];
				if(count)
				{
					if(!queueisnull(local_queue))
					{
						int *q=NULL;
						splitted=1;
						do
						{
							queuepop(local_queue,&q);
							GroupList[*q]=MDFATop;
							queuepush(GroupQueue,q);
						}while(!queueisnull(local_queue));
						MDFATop++;
					}
				}
				queuepush(GroupQueue,p);
				compare_p=p;
			}
			else
			{
				pre_state=GroupList[*p];
				if(DFAMEssentiallyTheSame(DFAStates[*p].actionlist,DFAStates[*compare_p].actionlist))
				{
					queuepush(GroupQueue,p);
				}
				else queuepush(local_queue,p);
			}
		}
		if(!queueisnull(local_queue))
		{
			int *q=NULL;
			splitted=1;
			do
			{
				queuepop(local_queue,&q);
				GroupList[*q]=MDFATop;
				queuepush(GroupQueue,q);
			}while(!queueisnull(local_queue));
			MDFATop++;
		}
		if(!splitted) break;
	}
	free(local_queue);
	return;
}
int *ReOffset=NULL;
static int DFAMPostProcess()
{
	int pre_state=-1;
	int count=0;
	int *p=NULL;
	ReOffset=(int *)calloc(sizeof(int)*DFATop,1);
	MDFAStates=(struct _DFANode *)calloc(sizeof(struct _DFANode)*DFATop,1);
	MDFATop=0;
	for(count=0;count<DFATop;count++)
	{
		queuepop(GroupQueue,&p);
		if(pre_state!=GroupList[*p])
		{
			struct _DFACharChain temp;
			struct _DFACharChain *actionlist=NULL,*fork_actionlist=NULL;
			MDFAStates[MDFATop].id=NULL;
			MDFAStates[MDFATop].type=DFAStates[*p].type;
			actionlist=DFAStates[*p].actionlist;
			temp.next=NULL;
			fork_actionlist=&temp;
			while(actionlist)
			{
				fork_actionlist->next=(struct _DFACharChain *)calloc(sizeof(struct _DFACharChain),1);
				fork_actionlist=fork_actionlist->next;
				fork_actionlist->ch=actionlist->ch;
				fork_actionlist->state=actionlist->state;
				actionlist=actionlist->next;
			}
			MDFAStates[MDFATop].actionlist=temp.next;
			ReOffset[GroupList[*p]]=MDFATop;
			MDFATop++;
		}
		pre_state=GroupList[*p];
	}
	for(count=0;count<MDFATop;count++)
	{
		struct _DFACharChain *actionlist=MDFAStates[count].actionlist;
		while(actionlist)
		{
			actionlist->state=ReOffset[GroupList[actionlist->state]];
			actionlist=actionlist->next;
		}
	}
	return ReOffset[GroupList[0]];
}
int DFAMinimize()
{
	int count=0;
	DFAMIni();
	DFAGroupStates();
	return DFAMPostProcess();
}