User:Antigng-bot/regex/DFAMinimize
外观
< User:Antigng-bot | regex
#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();
}