// This program implements some simple operations of the linked list
#include <string.h>
#include <stdio.h>
#include <math.h>
#include "hyper.h"

// display the graph data (for debug)
void show_graph_data(Graph L) {

	Data *temp1,*temp2;
	int i;
   	temp1 = L.Edge; temp2 = L.Path;

	temp1 = L.Edge;
	printf("%d ",L.numEdge);
	for(i=0;i<L.numEdge;i++) {
	  printf("%s ",temp1->value);
      	  temp1 = temp1->next ;
	}

	printf("\n");

	temp2 = L.Path;
	printf("%d ",L.numPath);
	for(i=0;i<L.numPath;i++) {
	  printf("%s ",temp2->value);
      	  temp2 = temp2->next ;
	}
	printf("\n%s\n",L.content);
}

// return the length of the linked list
int DataLength(Data *string) {
     return string->len;
}

// add value to the linked list
Data *setData(Data *head,char *value) {
	Data *temp = new Data;
	head->next = temp;
	temp->value = value;
	head = temp;
	return head;
}

// allocate a new link in the linked list
Data *newData() {
	Data *dd = new Data;
	dd->value = "END";
    dd->len = 0;
	return dd;
}

// add the datatype DataA into the linked list
DataA *setDataA(DataA *head,char *value) {
	DataA *temp = new DataA;
	head->column = temp;
	temp->value = value;
	head = temp;
	return head;
}

// allocate a new link which datatype is DataA
DataA *newDataA() {
	DataA *dd = new DataA;
	dd->value = "END";
	return dd;
}

// add a new graph into the linked list which datatype is graph
GraphList *setGraph(GraphList *head,Graph g) {
	GraphList *temp = new GraphList;
	head->next = temp;
	temp->gg = g;
	head = temp;
	return head;
}

// add a new tree into the linked list which datatype is tree
treeList *setTree(treeList *head,tree t) {
	treeList *temp = new treeList;
	head->next = temp;
	temp->tt = t;
	head = temp;
	return head;
}

// allocate a new link which the datatype is Graph
GraphList *newGraph() {
	GraphList *g = new GraphList;
	g->gg.numEdge = -5;
	g->no = 0;
	return g;
}

// allocate a new link which the datatype is treeList
treeList *newTree() {
	treeList *t = new treeList;
	t->no = 0;
	return t;
}

// delete a link from the linked list
Data *truncateData2(Data *string,char *e) {
	Data *previous,*temp,*head;
	int times = 0;
	head = string;

	while(strcmp(string->value,"END")!=0) {
		if(strcmp(string->value,e)==0) {
			if(times == 0) {     // head
				temp=string;
			    string=string->next;
				string->end = temp->end;
                string->len = temp->len-1;
				delete temp;
				return string;
			} else {
				temp=previous;
				temp->next=string->next;

				if(strcmp(string->next->value,"END")==0)
					head->end = temp;

				delete string;
                head->len = head->len-1;
				return head;
			}
		}
		previous = string;
		times++;
		string = string->next;
	}

    head->len = head->len-1;
	return head;
}

// delete a link from the linked list
DataA *truncateDataA(DataA *string,char *e) {
	DataA *previous,*temp,*head;
	int times = 0;
	head = string;

	while(strcmp(string->value,"END")!=0) {
		if(strcmp(string->value,e)==0) {
			if(times == 0) {     // head
				temp=string;
			    string=string->column;
				delete temp;
				return string;
			} else {
				temp=previous;
				temp->column = string->column;
				delete string;
				string = temp;
				return head;
			}
		} 
		previous = string;
		times++;
		string = string->column;
	}

	if(strcmp(string->value,"END")!=0) 
		delete string;

	return head;
}

// delete a graph from the linked list
void truncateGraph(GraphList *string) {
	GraphList *temp,*head;
	
	head = string;

	while(string->no!=0) {			
		temp=string;
		string=string->next;
		delete temp;			
	} 

	if(string->no==0) 
		delete string;
}

// delete a tree from the linked list
void truncateTree(treeList *string) {
	treeList *temp,*head;
	
	head = string;

	while(string->no!=0) {			
		temp=string;
		string=string->next;
		delete temp;			
	} 
	if(string->no==0) 
		delete string;
}

// delete the whole linked list
void delete_data(Data *dd) {
		int i,len = DataLength(dd);

		for(i=0;i<len;i++) {
			dd = truncateData2(dd,dd->value);
		}
		if(strcmp(dd->value,"END")==0)
			delete dd;
}

// deallocate L
void delete_graph(Graph L) {
	delete_data(L.Edge);
	delete_data(L.Path);
	delete [] L.content;
}

// deallocate T
void delete_tree(tree T) {
	delete_data(T.edge);
	delete_data(T.node);
}

// deallocate the connected components
void delete_ccomponent(CComponent *hhead) {
	while(hhead->number>0) {
		delete_data(hhead->G.Edge);
		delete_data(hhead->G.Path);
		hhead = hhead->next;
	}
}

// delete the whole linked list
void delete_dataA(DataA *dataA) {
	DataA *head = dataA;
	int len = 0;
	
	while(strcmp(dataA->value,"END")!=0) {
		delete_data(dataA->row);
		dataA = dataA->column;
		len++;
	}

	int i;
	for(i=0;i<len;i++) {
		head = truncateDataA(head,head->value);
	}

	if(strcmp(head->value,"END")==0)
		delete head;
}

// delete the whole linked list
void delete_GraphList(GraphList *gl) {
	GraphList *head = gl;
	
	while(gl->gg.numEdge!=-5) {
		delete_graph(gl->gg);
		gl = gl->next;
	}
	
	truncateGraph(head);	
}

// delete the whole linked list
void delete_treeList(treeList *tl) {
	treeList *head = tl;
	
	while(tl->no!=0) {
		delete_tree(tl->tt);
		tl = tl->next;
	}
	
	truncateTree(head);	
}

// display the linked list (for debug)
void show_Data(Data *head) {
	while(strcmp(head->value,"END")!=0) {
		printf("%s ",head->value);
		head = head->next;
	}
	printf("\n");
}

// display the linked list (for debug)
void show_DataA(DataA *head) {
	while(strcmp(head->value,"END")!=0) {
		printf("%s ",head->value);
		head = head->column;
	}
	printf("\n");
}

// add a link to the linked list
Data *appendData(Data *string,char *value) {
	Data *previous,*head;
	head = string;
	
	if(strcmp(string->value,"END")==0) {
		Data *temp = new Data;
		temp->value = value;
        temp->len = 1;
		temp->next = string;
		temp->end = temp;
		return temp;
	} else {
		previous = string->end;
	}

	Data *newEnd = previous->next;
    Data *newTail = setData(previous,value);
	newTail->next = newEnd;

    head->len = head->len+1;
	head->end = newTail;

	return head;
}


// duplicate exactly the same linked list
Data *copyData(Data *string) {
	Data *head = newData();
	Data *shead = string;

	int i,len = DataLength(string);
	
	for(i=0;i<len;i++) {
		head = appendData(head,string->value);
		string = string->next;
	}
	return head;
}

// copy the list and add a new link to the new list
Data *appendData2(Data *string,char *value) {
	Data *previous,*head;
	Data *newdata = copyData(string);
	head = newdata;

	if(strcmp(newdata->value,"END")==0) {
		Data *temp = new Data;
		temp->value = value;
        temp->len = 1;
		temp->next = newdata;
		temp->end = temp;
		return temp;
	} else
		previous = head->end;

	Data *newEnd = previous->next;
    Data *newTail = setData(previous,value);
	newTail->next = newEnd;

    head->len = head->len+1;
	head->end = newTail;
	
	return head;
}

// copy the list and add a new link to the new list
DataA *appendDataA(DataA *string, char *value) {
	DataA *previous,*head;
	head = string;

	if(strcmp(string->value,"END")==0) {
		DataA *temp = new DataA;
		temp->value = value;
		temp->column = string;
		temp->row = newData();
		return temp;
	}

	while(strcmp(string->value,"END")!=0) {
		previous = string;
		string = string->column;
	}

	previous = setDataA(previous,value);
	previous->column = string;
	previous->row = newData();
	return head;
}

// copy the list and add a new link to the new list
GraphList *appendGraph(GraphList *gl, Graph g) {
	GraphList *previous,*head;
	head = gl;

	if(gl->gg.numEdge==-5) {
		GraphList *temp = new GraphList;
		temp->gg = g;
		temp->next = gl;
		temp->no = 1;
		return temp;
	}

	while(gl->gg.numEdge!=-5) {
		previous = gl;
		gl = gl->next;
	}

	previous = setGraph(previous,g);
	previous->next = gl;
	previous->no = 2;	
	return head;
}

// copy the list and add a new link to the new list
treeList *appendTree(treeList *tl, tree t) {
	treeList *previous,*head;
	head = tl;

	if(tl->no==0) {
		treeList *temp = new treeList;
		temp->tt = t;
		temp->next = tl;
		temp->no = 1;
		return temp;
	}

	while(tl->no!=0) {
		previous = tl;
		tl = tl->next;
	}

	previous = setTree(previous,t);
	previous->next = tl;
	previous->no = 2;	
	return head;
}

// delete one link from the linked list
Data *truncateData(Data *dd,char *e) {
	Data *previous,*temp,*head;
	Data *string = copyData(dd);
	int times = 0;
	head = string;

	while(strcmp(string->value,"END")!=0) {
		if(strcmp(string->value,e)==0) {
			if(times == 0) {     // head
				temp=string;
			    string=string->next;
                string->len = temp->len-1;
				string->end = temp->end;
				delete temp;
				return string;
			} else {
				temp=previous;
				temp->next=string->next;

				if(strcmp(string->next->value,"END")==0)
					head->end = temp;

				delete string;
				string = temp;
                head->len = head->len-1;
				return head;
			}
		} 
		previous = string;
		times++;
		string = string->next;
	}
             head->len = head->len-1;
	return head;
}

// string1: original string
// delete a linked list inside a linked list  
Data *truncateDatas(Data *dd,Data *string2) {
	Data *string1 = copyData(dd);
	while(strcmp(string2->value,"END")!=0) {
		string1 = truncateData(string1,string2->value);
		string2 = string2->next;
	}
	return string1;
}

// push an element into the stack
stack push(stack s,char *value) {
	Data *previous,*head;
	head = s.content;

	if(strcmp(s.content->value,"END")==0) {
		Data *temp = new Data;
		temp->value = value;
        temp->len = 1;
		temp->next = s.content;
		temp->end = temp;
		s.top = temp;
		s.content = temp;
		return s;
	} else
		previous = head->end;

	Data *newEnd = previous->next;
    Data *newTail = setData(previous,value);
	newTail->next = newEnd;
    head->len = head->len+1;
	head->end = newTail;
	s.content = head;
	s.top = newTail;
	return s;
}

// pop an item from the stack
stack pop(stack s) {
	int len = DataLength(s.content);
	int i;
	Data *hcontent = s.content;
	
	if(len==0)
		return s;
	
	if(len==1) {
		s.content = truncateData(s.content,s.content->value);
		return s;
	}
			
	for(i=0;i<len-1;i++)
		hcontent = hcontent->next;
		
	s.content = truncateData(s.content,hcontent->value);
	return s;		
}

// search the position of e in the linked list string
int search_pos(Data *string, char *e) {
	int i=0;
	
	while(strcmp(string->value,"END")!=0) {
		if(strcmp(string->value,e)==0)
			return i;
		string = string->next;
		i++;
	}
	return -1;
}

// search the element of position i in the linked list string
char *search_string(Data *string, int i) {
	int j;

	for(j=0;j<i;j++) {
		string = string->next;
	}
	return string->value;
}

// add another linked list into a linked list
Data *Datacat(Data *string1, Data *string2) {
	Data *new1 = copyData(string1);
	Data *new2 = copyData(string2);

	Data *head = new1;
	Data *previous;

	while(strcmp(new1->value,"END")!=0) {
		previous = new1;
		new1 = new1->next;
	}

	previous->next = new2;
	head->end = new2->end;

	return head;
}

// intersection of two sets
Data *intersection(Data *data1, Data *data2) {
	char *string1;
	char *string2;
	int i,j;

	Data *intersect = newData();
	Data *hdata2 = data2;

	int len1 = DataLength(data1);
	int len2 = DataLength(data2);

	for(i=0;i<len1;i++) {
		for(j=0;j<len2;j++) {
			string1 = data1->value;
			string2 = data2->value;
			if(string1==string2)
				intersect = appendData(intersect,string1);
			data2 = data2->next;
		}
		data1 = data1->next;
		data2 = hdata2;
	}
	return intersect;
}

// union of two sets
Data *unions(Data *data1, Data *data2) {
	int i,j;
	int len2 = DataLength(data2);
	int found = 0;
	Data *newdata = copyData(data2);
	Data *hdata2 = data2;

	int len1 = DataLength(data1);

	for(i=0;i<len1;i++) {
		for(j=0;j<len2;j++) {
			if(data1->value==data2->value)
				found = 1;
			data2 = data2->next;
		}
		if(found == 0)
			newdata = appendData(newdata, data1->value);
		found = 0;
		data1 = data1->next;
		data2 = hdata2;
	}
	return newdata;
}

// add a character right behind a string
char *stringcat(char *string, char e) {
	char *temp;
	
	temp = new char[10*strlen(string)+3];

	for(int i=0;i<strlen(string);i++)
		temp[i] = string[i];

	temp[strlen(string)] = e;
	temp[strlen(string)+1] = '\0';
	return temp;
}

// search a character in a string
int searchc(char *string, char e) {
	int i;
	if(string == "")
		return -1;
	
	for(i=0;i<strlen(string);i++) {
		if(string[i]==e)
			return i;
	}
	return -1;
}

// check if both linked lists are equal
bool isEqual(Data *data1, Data *data2) {
	int len1 = DataLength(data1);
	int len2 = DataLength(data2);
	int i;

	if(len1 != len2)
		return false;

	for(i=0;i<len1;i++) {
		if(data1->value!=data2->value)
			return false;
		data1 = data1->next;
		data2 = data2->next;
	}
	return true;
}

// data1 - data2
Data *minusData(Data *data1, Data *data2) {
    Data *result = newData();
	Data *hdata2 = data2;

	int len1 = DataLength(data1);
	int len2 = DataLength(data2);
	int i,j;

	if(len2==0)
		return copyData(data1);
		
	for(i=0;i<len1;i++) {
		for(j=0;j<len2;j++) {
			if(data1->value == data2->value)
				break;
			if(j==len2-1)  // no match at all
				result = appendData(result,data1->value);
			data2 = data2->next;
		}
		data2 = hdata2;
		data1 = data1->next;
	}
	return result;
}

// check if the pair (string1,string2) is in dd
bool check_pair(Data *dd, char *string1, char *string2) {
	int i,len = DataLength(dd);
	Data *hdata = dd;

	for(i=0;i<len;i++) {
		if(strcmp(hdata->value,string1)==0 && i%2==0) {
			char *compare = search_string(dd, i+1);
			if(strcmp(compare,string2)==0)
				return true;
		}
		hdata = hdata->next;
	}

	return false;
}

// check if string1 and string2 are in dd
bool NoDuplicateData(Data *Epc,char *string1,char *string2) {
	int i,len = DataLength(Epc);
	for(i=0;i<(len/2);i++) {
		if(strcmp(string1,Epc->value)==0 && strcmp(string2,Epc->next->value)==0) {
			return false;
		}
		Epc = Epc->next->next;
	}
	return true;
}

// delete the pair (p1,p2) from the linked list dd
Data *truncatePair(Data *dd,char *p1,char *p2) {
	Data *result = newData();
	int i,len = DataLength(dd);
	Data *hdata = dd;
	for(i=0;i<(len/2);i++) {
		if(strcmp(dd->value,p1)!=0 || strcmp(dd->next->value,p2)!=0) {
			result = appendData(result,dd->value);
			result = appendData(result,dd->next->value);
		}
		dd = dd->next->next;
	}
	delete_data(hdata);
	return result;
}

// generate a string which is s plus a number num
char *generate_node(char *s, int num)
{    
	int i, power = 0,times = 0;

	int number = num;
	int test1,test2;

	while(number>0) {
		times++;
		number = number/10;
	}
	
	for(i=0;i<times;i++) {
	
		number = num;
		test1 = (int)pow(10,times-i);
		test2 = (int)pow(10,times-i-1);
		
		if(test2==1)
			test2 = 0;
		
		if(number>=test2 && number<=test1) {	
			while(number>=10) { 
				number = number/10;
				power++;
			}
		} else
			number = 0;
	
		char tt = (char)(number+48);
		s = stringcat(s,tt);
		number = number * (int)pow(10,power);
		power = 0;
		num = num - number;
	}
		
	return s;
}

// find a link in the linked list
DataA *locate_DataA(DataA *dataA, int index) {
	int i;
	for(i=0;i<index;i++)
		dataA = dataA->column;
	return dataA;
}

// find a link in the linked list
GraphList *locate_Graph(GraphList *gl, int index) {
	int i;
	for(i=0;i<index;i++)
		gl = gl->next;
	return gl;
}

// find a link in the linked list
treeList *locate_Tree(treeList *tl, int index) {
	int i;
	for(i=0;i<index;i++)
		tl = tl->next;
	return tl;
}