#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "String.h"
#include "hyper.h"


char *another2=" ";

Data *search_again2(tree Ti, Data *EdgeSet, char *value,int debug) {
	int len = 0;
	char *edge,*previous;
	int pos;
	previous = Ti.node->value;
	Data *ht = Ti.node;
	
	if(strcmp(EdgeSet->value,"END")==0)
		return EdgeSet;
		
	while(strcmp(ht->value,"END")!=0) {
		if(strcmp(ht->value,value)==0) {
			edge = search_string(Ti.edge,len/2);
			
			pos = search_pos(EdgeSet,edge);
						
			int elen = DataLength(EdgeSet);
		
			if(elen==0) {
				//printf(" and another terminal is %s\n",edge);
				if(len%2==0)
					another2 = ht->next->value;
				else
					another2 = previous;
				//printf("actual: %s\n",value);
				return EdgeSet;
			}
			
			if(pos!=-1) {
				EdgeSet = truncateData2(EdgeSet,edge);
				
				if(debug==2)
					printf("%s ",value);
				//printf("found %s %d %s %s\n",ht->value,len,ht->next->value,previous);
				if(DataLength(EdgeSet)==0) {
					if(len%2==0)
						another2 = ht->next->value;
					else
						another2 = previous;
						
					//printf("actual: %s\n",another);
					return EdgeSet;
				}
				
				if(len%2==0)
					EdgeSet = search_again2(Ti,EdgeSet,ht->next->value,debug);
				else
					EdgeSet = search_again2(Ti,EdgeSet,previous,debug);
				if(DataLength(EdgeSet)==0) 
					return EdgeSet;
			}
		}	
		previous = ht->value;
		ht = ht->next;
		len++;
	}	
	
	//printf("actual: %s\n",value);
	another2 = value;
	//delete_data(EdgeSet);
	EdgeSet = newData();	
	return EdgeSet;
}

char *find_path2(tree Ti, Data *EdgeSet, char *terminal,int debug) {	
	another2 = " ";
	
	search_again2(Ti,EdgeSet,terminal,debug);
	
	if(strcmp(another2," ")==0) {
		//printf("do\n");
		another2 = terminal;
	}
		
	//printf("One terminal is %s\n",another2);
	return another2;
}

Data *son;

char *search_cutpoint(Graph G,int count,char *value,char *root,int *low,int *dfnumber,int *old,int *father,char *compare) {
	int pos,i,j;
	char *newvalue,*rvalue;

	pos = search_pos(G.Edge,value);
	dfnumber[pos] = count;
	old[pos] = 1;
	count++;
	low[pos] = dfnumber[pos];

	for(i=0;i<G.numPath;i++) {
		if(G.content[i*G.numEdge+pos]=='1') {
			for(j=0;j<G.numEdge;j++) {
				if(G.content[i*G.numEdge+j]=='1' && j!=pos) {   // adjacent edge
					if(old[j]!=1) {
						//printf("here1 %s\n",value);
						if(strcmp(value,root)==0)    // record how many sons does root have
							son = appendData(son,root);
						
						father[j] = pos;
						newvalue = search_string(G.Edge,j);
						//printf("count: %d\n",count);
						rvalue = search_cutpoint(G,count,newvalue,root,low,dfnumber,old,father,compare);

						if(strcmp(rvalue," ") != 0)
							return rvalue;

						if(low[j]>=dfnumber[pos] && strcmp(value,compare)!=0) {			
                                                        return value;
						}
						if(low[pos]>low[j])
							low[pos] = low[j];
					} else {
						//printf("here2 %d %d %d %s\n",i,j,pos,value);
						if(j!=father[pos]) {
							if(low[pos]>dfnumber[j]) {
								//printf("replace: %d %d %d %d\n",pos,j,low[pos],dfnumber[j]);
								low[pos] = dfnumber[j];
							}
						}
					}
				}
			}
		}
	}
        return " ";
}

bool check_ancestor(tree T,char *node1,char *node2,char *root) {
	int i;
	int len = DataLength(T.edge);
	Data *hnode = T.node;
	bool result = false;
	
	for(i=0;i<len;i++) {
		if(strcmp(hnode->value,node1)==0) {
			if(strcmp(hnode->next->value,node2)==0)
				return true;
			else if(strcmp(hnode->next->value,root)==0)
				return false;
			else
				return check_ancestor(T,hnode->next->value,node2,root);
			//if(result)
			//	return true;
		}
		hnode = hnode->next->next;
	}
	return false;
}

int depth_first_searchB(Graph G,char *n1,char *n2,tree T) {
	int i,j,k;
	Graph S;
	Data *hedge = G.Edge;
        char *value;
        int isunique = 1;
	char *root;
	
	for(i=0;i<G.numEdge;i++) {
		S.Edge = copyData(G.Edge);
		S.Edge = truncateData2(S.Edge,hedge->value);
		S.Path = newData();
		S.content = new char[(G.numEdge-1)*(G.numPath-1)];
		Data *hpath = G.Path;
		int path = 0;
		int edge;
		
		for(j=0;j<G.numPath;j++) {        // remove one node and its adjacent edges
			
			if(G.content[j*G.numEdge+i]=='0') {
				S.Path = appendData(S.Path,hpath->value);
				edge = 0;
				for(k=0;k<G.numEdge;k++) {
					if(k!=i) {
						S.content[path*(G.numEdge-1)+edge] = G.content[j*G.numEdge+k];
						edge++;
					}
				}
				path++;
			}
			hpath = hpath->next;
		}

		S.numPath = path;
		S.numEdge = G.numEdge-1;
		S.content[path*(G.numEdge-1)] = '\0';
		//printf("Graph S is:\n");
		//show_graph_data(S);
		int count = 1;
		//int *old;
		//int *dfnumber,*low,*father;
		int *low,*dfnumber,*father,*old;
		dfnumber = new int[G.numEdge];
		low = new int[G.numEdge];
		old = new int[G.numEdge];
		father = new int[G.numEdge];
		
		for(j=0;j<G.numEdge;j++) {
			dfnumber[j] = 0;
			low[j] = 0;
			old[j] = 0;
			father[j] = 0;	
		}
		//show_graph_data(G);
		//show_graph_data(S);

		son = newData();
		
		if(strcmp(S.Edge->value,n1)==0)
			value = search_cutpoint(S,count,S.Edge->value,S.Edge->value,low,dfnumber,old,father,n2);
		else if(strcmp(S.Edge->value,n2)==0)
			value = search_cutpoint(S,count,S.Edge->value,S.Edge->value,low,dfnumber,old,father,n1);
		else
			value = search_cutpoint(S,count,S.Edge->value,S.Edge->value,low,dfnumber,old,father," ");
                
                
                
                char *value2 = hedge->value;
		
		//printf("value: %s %s\n",value,value2);
		
		Data *hedge2 = T.edge;
		Data *hnode2 = T.node;
		
		for(j=0;j<T.edge->len;j++) {
			if(strcmp(hedge2->value,"g0")==0) {
				root = hnode2->next->value;
				break;
			}
			hedge2 = hedge2->next;
			hnode2 = hnode2->next->next;
		}
		
		//printf("root is %s\n",root);
		
		bool isroot = true;
		
		if(strcmp(value,S.Edge->value)==0 && DataLength(son)>1) {
			isroot = false;
		}
		
                if((strcmp(value," ")!=0 && strcmp(value,S.Edge->value)!=0) || !isroot)   {
                	
                        if(strcmp(n1,value2)!=0 || strcmp(n2,value)!=0)           // don't count both ends of g0
                        	if(strcmp(n1,value)!=0 || strcmp(n2,value2)!=0) {
                        		if(!check_ancestor(T,value2,value,root) && !check_ancestor(T,value,value2,root) ) {                
                                        	isunique = 0;
                                        	delete_data(son);
                                       		return 0;
                                       	}
                                }
                }
                          
		delete_graph(S);
		delete [] dfnumber;
		delete [] low;
		delete [] old;
		delete [] father;
		delete_data(son);
		hedge = hedge->next;
	}

        if(isunique==1) {
        	//printf("The tree is unique\n");
        	return 1;
        }
	return 0;
}

int check_unique(tree T, Data *II) {
	Graph G;
	G.Edge = newData();
	Data *hnode = T.node;
	int pos,pos1,pos2,i;
	char *n1,*n2;
	int uu;
	char *temp;
	while(strcmp(hnode->value,"END")!=0){
		pos = search_pos(G.Edge,hnode->value);
		if(pos==-1)
			G.Edge = appendData(G.Edge,hnode->value);
		hnode = hnode->next;	
	}
	G.numEdge = DataLength(G.Edge);
	
	///// search for the end nodes of g0
	pos = search_pos(T.edge,"g0");
	n1 = search_string(T.node,2*pos);
	n2 = search_string(T.node,2*pos+1);
	//np1 = search_pos(G.Edge,n1);
	//np2 = search_pos(G.Edge,n2);
	//printf("END NODE IS %s %s %d %d\n",n1,n2,np1,np2);
	
	
	int len1 = DataLength(T.edge);
	int len2 = DataLength(II);
	
	G.content = new char[G.numEdge*(len1+len2)];
	
	for(i=0;i<G.numEdge*(len1+len2);i++)
		G.content[i] = '0';
	G.content[i] = '\0';
		
	Data *hedge = T.edge;
	hnode = T.node;
	i = 0;
	
	G.Path = newData();
	
	while(strcmp(hedge->value,"END")!=0) {
		pos1 = search_pos(G.Edge,hnode->value);
		pos2 = search_pos(G.Edge,hnode->next->value);	
		G.content[i*G.numEdge+pos1] = '1';
		G.content[i*G.numEdge+pos2] = '1';
		G.Path = appendData(G.Path,hedge->value);
		hedge = hedge->next;
		hnode = hnode->next->next;
		i++;
	}
	
	Data *path = newData();
	char *previous,*node1,*node2;
	Data *cpath;
	
	//show_Data(II);
	//show_Data(G.Path);
	
	while(strcmp(II->value,"END")!=0) {		
		if(strcmp(II->value,"|")!=0) {
			path = appendData(path,II->value);
		} else {
			//show_Data(path);
			pos = search_pos(T.edge,path->value);
			node1 = search_string(T.node,2*pos);
			node2 = search_string(T.node,2*pos+1);
			//printf("nodes: %s %s\n",node1,node2);
			cpath = copyData(path);
			//delete_data(cpath);
			//printf("pass1\n");
			path = truncateData2(path,path->value);
			
			node1 = find_path2(T,path,node1,1);
			
			cpath = truncateData2(cpath,cpath->value);
			node2 = find_path2(T,cpath,node2,1);
			//printf("Terminals: %s %s\n",node1,node2);
			
			pos1 = search_pos(G.Edge,node1);
			pos2 = search_pos(G.Edge,node2);
			G.content[i*G.numEdge+pos1] = '1';
			G.content[i*G.numEdge+pos2] = '1';
			
			temp = generate_node("p",i);
			//show_Data(G.Path);
			
			G.Path = appendData(G.Path,temp);
			i++;
			
			//delete_data(path);
			//delete_data(path);
			//delete_data(cpath);
			
			//delete_data(path);
			//delete_data(cpath);
			path = newData();
			//printf("finish\n");
		}
		previous = II->value;
		II = II->next;	
	}
	
	G.numPath = DataLength(G.Path);
	G.content[G.numPath*G.numEdge]='\0';
	
	uu = depth_first_searchB(G,n1,n2,T);
	
	delete_graph(G);
	return uu;
}

void read_file(char *filename, tree *T, Data **Paths,int *no) {
	FILE *fp;
	int num,i;
	char *string;
	
	fp = fopen(filename,"r");
	T->edge = newData();
	T->node = newData();
	*Paths = newData();
	
	if(fp==NULL) {
		printf("File not exit\n");
		exit(1);
	}
	
	fscanf(fp,"%d",&num);
	for(i=0;i<num;i++) {
		string = new char[10];
		fscanf(fp,"%s",string);
		
		if(string[0]!='e' && string[0]!='g') {
			printf("File format is not correct. Maybe enter the wrong file name\n");
			exit(0);	
		}
		T->edge = appendData(T->edge,string);
	}
	
	fscanf(fp,"%d",&num);
	for(i=0;i<num;i++) {
		string = new char[10];
		fscanf(fp,"%s",string);
		T->node = appendData(T->node,string);
	}
	
	fscanf(fp,"%d",&num);
	for(i=0;i<num;i++) {
		string = new char[10];
		fscanf(fp,"%s",string);
		*Paths = appendData(*Paths,string);
	}
	
	fclose(fp);
}

int main(int argc, char *argv[]) {
	tree T;
	Data *Paths;
	int no;
	char *filename;
	FILE *fp;
	int rr;
	
	fp = fopen(argv[1],"r");
	
	if(fp == NULL) {
		printf("%s not exist\n",argv[1]);
		return 0;
	}
	fclose(fp);
	
	filename = argv[1];
	read_file(filename,&T,&Paths,&no);
	
	fp = fopen("dd","w");
			
	rr = check_unique(T, Paths);
	
	fprintf(fp,"%d",rr);
	return 1;
}