#include <stdlib.h>
#include <string.h>
#include <stdio.h>

//Status是函數的類型,其值是函數結果狀態代碼
typedef int Status;
#define INT_MAX 32767
#define LINESIZE 80//設一行字符數為80
#define MAXKEYLEN 26//關鍵字的長度
#define MAXNUM 100//統計單詞的最大數
typedef struct{	  
	char *ch;  //關鍵字
	int  num;  //關鍵字的長度
	char *info;//關鍵字有關信息
}KeysType;     //關鍵字類型

typedef enum{LEAF,BRANCH} NodeKind;//結點種類：{葉子，分支}

typedef struct DLTNode{
	char symbol;
	struct DLTNode *next;     //指向兄弟結點的指針
	NodeKind kind;            //結點標志
	union{
		struct DLTNode *first;//分支結點的孩子鏈指針
		struct {
			int idx;          //葉子結點的count數組下標指針
			KeysType infoptr;
		};
	};
}DLTNode,*DLTree;   //雙鏈樹類型
char line[LINESIZE];//用于緩存文章中每行的字符串
struct{
	int times;
	KeysType info;
}count[MAXNUM];
int NUM=0;//記錄整個文章的單詞總數
char ch1[17][100]={"a","an","the","them","there","here","they","are","that","this","those","what","which","why","then","and","these"};

void InitTree(DLTree &root){
	//初始化鍵樹
	root=new DLTNode;
	root->next =NULL;
	root->first=NULL;
}//InitTree

Status Insert_DLTree(DLTree &root,KeysType K,int &n){
	//指針root所指雙鏈樹中已含n個關鍵字，若不存在和K相同的關鍵字，
	//則將關鍵字K插入到雙鏈樹中相應位置，樹中關鍵字個數n增1且返回TRUE；..
	//否則不再插入返回FALSE
	DLTree p=root->first,f=root,pre,s;
	int j=0;
    while (p && j<K.num ){//在鍵樹中進行查找
        pre=NULL;
		while (p && p->symbol <K.ch [j]){//查找和K.ch[j]相同的結點
			pre=p;
			p=p->next ;
		}
		if (p && p->symbol ==K.ch[j]){
			f=p;
			p=p->first ;
			j++;
		}//找到后進入鍵樹的下一層，即查找和K.ch[j+1]相同的結點
		else{//沒有找到和K.ch[j]相同的結點，插入K.ch[j]
			s=new DLTNode;
			s->kind =BRANCH;
			s->symbol =K.ch [j++];
			if (pre) pre->next =s;
			else f->first =s;
			s->next =p;
			s->first =NULL;
			p=s;
			break;
		}//else
	}//while
    if (p&&j==K.num && p->first&&p->first ->kind ==LEAF) return FALSE;
	else{//鍵樹中已存在相同前綴的單詞，插入由剩余字符構成的單支樹
		while (j<=K.num ){
				s=new DLTNode;
				s->next =NULL;
				if (p){
				s->next =p->next ;
				p->first =s;
				p=s;
				}
				else {
					f->first =s;
					p=s;
				}
				if(j<K.num ){
					s->kind =BRANCH;
					s->symbol =K.ch [j++];
					s->first =NULL;
				}
				else{
					s->symbol ='$';
					s->kind =LEAF;
					n++;
					s->idx =n;
					s->infoptr.ch =count[s->idx ].info.ch =K.ch ;
					s->infoptr.info =count[s->idx ].info.info =K.info ;
					s->infoptr.num =count[s->idx ].info.num=K.num ;
					count[s->idx ].times=0;
					j++;
				}
			}//while
		return TRUE;
		}//else
}//Insert_DLTree


void CreatDLTree(DLTree &T,KeysType *key,int &n){
	//建立鍵樹模型
	for (int i=0;i<=16;i++){
		key[i].ch=ch1[i];
        key[i].info=NULL;
		key[i].num =strlen(key[i].ch );
	}
	key[0].info ="indefinite article.";//a
	key[1].info ="indefinite articles.";//an
	key[2].info ="definite article.";//the
    key[3].info ="personal pronoun";//them
    key[4].info ="adv. of place and direction";//there
    key[5].info ="to this point or place";//here
    key[6].info ="pronoun";//they
    key[7].info ="v.i. joining subject & predicate";//are
    key[8].info ="adj. & pron.";//that
    key[9].info ="adj. & pron.";//this
    key[10].info ="adj. & pron.";//those
    key[11].info ="adj. & pron.,asking for a selection from an indefinite number";//what
    key[12].info ="adj. & pron.,asking for a selection from two or a group";//which
    key[13].info ="adj. & int.,for what reason,with what purpose";//why
    key[14].info ="adv.,at what time";//then
    key[15].info ="conj.,connecting words";//and 
    key[16].info ="adj. & pron.";//these
    for(i=0;i<=16;i++)
      Insert_DLTree(T,key[i],n);//建立鍵樹模型
}//CreatDLTree

Status Search_DLTree(DLTree rt,int j,int &k){
	//若line中從第j個字符起長度為k的子串和指針rt所指向雙鏈樹中單詞相同，
	//則數組count中相應分量增1，并返回TRUE，否則返回FALSE
	DLTree p;
	int found;
	k=0;
	found=FALSE;
	p=rt->first ;//p指向雙鏈樹中的第一棵子樹的樹根
    while (p && !found){
		while (p && p->symbol <line[j+k]) p=p->next ;
		if (!p||p->symbol >line[j+k]) break;//在鍵樹的第k+1層上匹配失敗
		else{//繼續匹配
			p=p->first ;
			k++;
			if (p->kind ==LEAF){//找到一個單詞
				if (!(line[j+k]>='a'&&line[j+k]<='z')||(line[j+k]>='A'&&line[j+k]<='Z' )){
				count[p->idx ].times++;//統計數組對應元素加1
				found=TRUE;
				}//若鍵樹中含有"commit"，文本行中為commit則為找到，若為committing則為沒找到
			}//if
		}//else
	}//while
	return found;
}//Search_DLTree

void setmatch(DLTree root,char *line,FILE *f){
	//統計以root為根指針的鍵樹中，各關鍵字在本文本串line中重復出現的次數，
	//并將其累加到統計數組count中去
	unsigned i=0;
	int k;//若查找成功，返回的k為所查找的關鍵字長度
	while (fgets(line,LINESIZE,f)!=NULL){
		cout<<line;
        i=0;
		while (i<=strlen(line)){//LINESIZE){
			if (!Search_DLTree(root,i,k)) {
				if (((line[i]>='a' && line[i]<='z')||(line[i]>='A'&&line[i]<='Z')||(line[i]>='0'&&line[i]<='9')) &&!((line[i+1]>='a'&&line[i+1]<='z')||(line[i+1]>='A'&&line[i+1]<='Z')||(line[i+1]>='0'&&line[i+1]<='9')))
					NUM++;//單詞總數加1
    				i++;  //若查找不成功，則從下一個字符開始查找
				}//if
	    	else {
		 		i+=k;     //查找成功，繼續在文本串中的第i+k-1個字符開始查找
				NUM++;
			}//else
		}//while
	}//while
}//setmatch

void Input(FILE *&f){
	char fname[30];
	cout<<"please input the file name:";
	cin>>fname;                     //輸入文件名
	if ((f=fopen(fname,"r"))==NULL){//輸入錯誤文件名, 無法打開
		cout<<"Can NOT open the file!"<<endl;
		exit(1);
	}
}//Input

void output(int n){
	cout<<endl;
	for(int i=1;i<=n;i++)
		if (count[i].times){
			cout<<count[i].info.ch<<" : ";
			if(count[i].info.info) cout<<count[i].info.info<<endl;
			cout<<float(count[i].times)/float(NUM)<<" in the sentence."<<endl;
		}//輸出文章中含有鍵樹中的關鍵字及有關解釋，出現頻率。即：該關鍵字出現次數/文章單詞總數
 	cout<<endl;
}