#ifndef GENLIST_H
#define GENLIST_H
#include <iostream>
#include <stdlib.h>
#include<string.h>
#include"SeqList.h"
using namespace std;
template <class T>
struct GenListNode {	          //廣義表結(jié)點(diǎn)類定義
	int utype;			//＝0 / 1 / 2
	GenListNode<T> *tlink;	//同層下一結(jié)點(diǎn)指針
	union {				//等價變量
		int ref;	                     //存放引用計數(shù)
		T value;			//存放數(shù)值
		GenListNode<T> *hlink;	  //存放子表指針	
	} info;
	GenListNode(int u=0): utype(u), tlink(NULL) {} //構(gòu)造函數(shù)
	GenListNode(GenListNode<T>& R) {
		//復(fù)制構(gòu)造函數(shù)
		utype = R.utype;   tlink = R.tlink; 
		info = R.info;
	}
};

template <class T>
struct Items {		//返回值的類結(jié)構(gòu)定義
	int utype;		//結(jié)點(diǎn)類型＝0/1/2
	union {			//聯(lián)合
		int ref;		//utype=0,存放引用計數(shù)
		T value;		//utype=1,存放數(shù)值
		GenListNode<T> *hlink;	
		//utype=2,存放指向子表的指針
	} info;
	Items() : utype(0), info.ref(0) {}    //構(gòu)造函數(shù)	
	Items(Items<T>& R)                     //復(fù)制構(gòu)造函數(shù)
	{ utype = R.utype;  info = R.info; }	
};
template <class T>
class GenList {			  //廣義表類定義
public:
	GenList();			          //構(gòu)造函數(shù)
	~GenList();			//析構(gòu)函數(shù) 
	GenList(GenList<T> & gl);
	bool Head (Items<T>& x);	   //x 返回表頭元素
	bool Tail (GenList<T>& lt);	   //lt 返回表尾
	GenListNode<T> *First();	   //返回第一個元素
	GenListNode<T> *Next (GenListNode<T> *elem);
	//返回表元素elem的直接后繼元素
	void Copy ( const GenList<T>& R);
	//廣義表的復(fù)制
	int Length();    		          //計算廣義表長度
	int depth();			//計算非遞歸表深度     
	void show() {show(first);}
	void delvalue(T x){delvalue(first, x);}
private:
	GenListNode<T> *first;	//廣義表頭指針
	GenListNode<T> *Copy (GenListNode<T> *ls);
	//復(fù)制一個ls指示的無共享非遞歸表
	int Length (GenListNode<T> *ls);
	//求由ls指示的廣義表的長度
	int depth (GenListNode<T> *ls);		
	//計算由ls指示的非遞歸表的深度
	bool equal (GenListNode<T> *s, GenListNode<T> *t);
	//判以s和t為表頭的兩個表是否相等
	void Remove (GenListNode<T> *ls);
	//釋放以ls為附加頭結(jié)點(diǎn)的廣義表
	void CreateList (istream& in, GenListNode<T> *&ls, SeqList<T>& L1, SeqList <GenListNode<T> *>& L2);
	//從輸入流對象輸入廣義表的字符串描述,
	void show (GenListNode<T>* p);
	//建立一個帶頭結(jié)點(diǎn)的廣義表結(jié)構(gòu)
	void delvalue(GenListNode<T> *ls, T x);
	friend istream& operator >> (istream& in, GenList<T>& L){
		SeqList<T> Ls1;	   
		SeqList<GenListNode<T> *>  Ls2;
		L.CreateList (in, L.first, Ls1, Ls2);	//建立存儲結(jié)構(gòu)
		GenListNode<T> *p = L.first;
		L.first = L.first->info.hlink;
		delete p;
		return in;
	}; 
	friend ostream& operator << (ostream& out,GenList<T>& L){
		L.show (L.first);
		return out;
	}
};
//廣義表輸入格式為 A(b,D(s,z),F(#)); 注意中間無空格
template <class T>
GenList<T>::GenList() {		//構(gòu)造函數(shù)
	first = new GenListNode<T>;
	if (first == NULL)
	{ cerr << "Error!\n";  exit(1); }	
};

template<class T>
GenList<T>::GenList(GenList<T> &gl){
	if (this != & gl)
		first = Copy(gl.first);
}

template <class T>
bool GenList<T>::Head (Items<T>& x) {
	//若廣義表非空，則通過x返回其第一個元素的值
	//否則函數(shù)沒有定義		
	if (first->tlink == NULL) return false;	//空表
	else {						//非空表
		x.utype = first->tlink->utype;
		x.info = first->tlink->info;
		return true;		                 //x返回表頭的值
	}
};

template <class T>
bool GenList<T>::Tail(GenList<T>& lt) {
	//若廣義表非空，則通過lt返回廣義表除表頭元素
	//以外其他元素組成的表，否則函數(shù)返回false
	if (first->tlink == NULL) return false;	    //空表
	else { 				//非空表
		lt.first->utype = 0;		//設(shè)置頭結(jié)點(diǎn)
		lt.first->info.ref = 0;
		lt.first->tlink = Copy(first->tlink->tlink);
		return true; 
	}
};

template <class T>
GenListNode<T> *GenList<T>::First() {
	//返回廣義表的第一個元素（若表空，則返回一個
	//特定的空值NULL）	
	if (first->tlink == NULL) return NULL;    //空表
	else return first->tlink;	 	 //非空表
};

template <class T>
GenListNode<T> *GenList<T>::
Next(GenListNode<T> *elem) {
	//返回表元素elem的直接后繼元素
	if (elem->tlink == NULL) return NULL;
	else return elem->tlink;
};

template <class T>                 //公有函數(shù)
void GenList<T>::Copy(const GenList<T>& R) {
	first = Copy(R.first);          //調(diào)用私有函數(shù)
};

template <class T>                 //私有函數(shù)
GenListNode<T>* GenList<T>::
Copy(GenListNode <T> *ls) {
	//復(fù)制一個 ls 指示的無共享子表的非遞歸表
	GenListNode<T> *q = NULL;
	if (ls != NULL) {
		q = new GenListNode<T>;  //處理當(dāng)前的結(jié)點(diǎn)q
		q->utype = ls->utype;	  //復(fù)制結(jié)點(diǎn)類型
		switch (ls->utype) {	  //根據(jù)utype傳送信息
			  case 0: q->info.ref = ls->info.ref;  break;	        	    case 1: q->info.value = ls->info.value;  break;
			  case 2: q->info.hlink = Copy(ls->info.hlink);   
				  break;
		}
		q->tlink = Copy(ls->tlink);  //處理同層下一結(jié)點(diǎn)
	}
	return q;
};

//打印數(shù)據(jù)
template<class T>
void GenList<T>::show (GenListNode<T>* p){
	if (!p)
		return;
	if (p->utype==1)
		cout<<(p->info).value<<"   ";
	else if (p->utype == 0)
		while (p->tlink){
			show(p->tlink);
			p=p->tlink;
		}
	else
		show (p->info.hlink);
}


template <class T>
int GenList<T>::depth() {             //公有函數(shù)
	//計算一個非遞歸表的深度
	return depth(first);
};

template <class T>                      //私有函數(shù)
int GenList<T>::depth(GenListNode<T> *ls) {
	if(!ls) return 0;
	if (!ls->tlink) return 1;
	// ls->tlink ==NULL, 空表，深度為1
	GenListNode<T> *temp = ls->tlink;  
	int m = 0, n;

	while (temp != NULL) {	//在廣義表頂層橫掃
		if (temp->utype == 2) {	   //掃描到表結(jié)點(diǎn) 
			n = depth(temp->info.hlink);	
			//遞歸計算以子表深度
			if (m < n) m = n;	   //取最大深度
		}
		temp = temp->tlink;
	}
	return m+1;			  //返回深度
};

template <class T>
int GenList<T>::Length() {
	//共有函數(shù)，求當(dāng)前廣義表的長度
	return Length(first);
};
template <class T>
int GenList<T>::Length(GenListNode<T> *ls) {
	//私有函數(shù)，求以ls 為頭指針的廣義表的長度
	if (ls != NULL) return 1+Length(ls->tlink);
	else return 0;
};


template <class T>
bool equal(GenListNode<T> *s, GenListNode<T> *t) {
	//私有函數(shù)：設(shè)s 與t 是兩個非遞歸廣義表的表頭指針, 若兩表相等, 函數(shù)返回true, 否則返回
	//false。
	bool x;
	if (s->tlink == NULL && t->tlink == NULL) return true;
	//表s 與表t 都是空表
	if (s->tlink != NULL && t->tlink != NULL
		&& s->tlink->utype == t->tlink->utype) {
			//兩表都非空且結(jié)點(diǎn)類型相同
			if (s->tlink->utype == 1) //原子結(jié)點(diǎn), 比較對應(yīng)數(shù)據(jù)
				x = (s->tlink->info.value == t->tlink->info.value) ? true:false;
			else if (s->tlink->utype == 2) //子表結(jié)點(diǎn), 遞歸比較其子表
				x = equal(s->tlink->info.hlink, t->tlink->info.hlink);
			if (x == true) return equal(s->tlink, t->tlink);
			//相等, 遞歸比較同一層的下一個結(jié)點(diǎn); 不等, 不再遞歸比較
	}
	return false; //不等，返回false
};

template <class T>
void GenList<T>::delvalue(GenListNode<T> *ls, T x) {
	if (ls->tlink != NULL) {		     //非空表 
		GenListNode<T> * p = ls->tlink;  //第一個結(jié)點(diǎn)
		while (p != NULL && (p->utype == 1 &&
			p->info.value == x)) {
				ls->tlink = p->tlink;  delete p;  
				p = ls->tlink;               //p指向同層下一結(jié)點(diǎn)
		}					
		if (p != NULL) {
			if (p->utype == 2)        //遞歸在子表中刪除
				delvalue(p->info.hlink, x);	
			delvalue(p, x);	
			//在以p為表頭的鏈表中遞歸刪除
		}
	}
};
template <class T>
GenList<T>::~GenList() {
	//廣義表的析構(gòu)函數(shù), 每個頭結(jié)點(diǎn)都有引用計數(shù)
		Remove(first);
};

template <class T>
void GenList<T>::Remove(GenListNode<T> *ls) {
	//私有函數(shù)：釋放以ls為表頭指針的廣義表  
	ls->info.ref--;	     	//頭結(jié)點(diǎn)的引用計數(shù)減1
	if (ls->info.ref <= 0) {		//如果減到0
		GenListNode<T> *q;	
		while (ls->tlink != NULL) {	//橫掃表頂層
			q = ls->tlink;			//到第一個結(jié)點(diǎn)
			if (q->utype == 2) {		//遞歸刪除子表
				Remove(q->info.hlink);
				if (q->info.hlink->info.ref <= 0)
					delete q->info.hlink;   //刪子表頭結(jié)點(diǎn)
			}
			ls->tlink = q->tlink;  delete q;
		}
	}
};

template <class T>
void GenList<T>::CreateList(istream& in, GenListNode<T> *& ls, SeqList<T>& L1, SeqList <GenListNode<T> *>& L2) {
	//從廣義表的字符串描述 ls 出發(fā), 建立一個帶頭結(jié)
	//點(diǎn)的廣義表，要求T為char類型。在表L1存儲大
	//寫字母的表名, 在表L2存儲表名對應(yīng)子表結(jié)點(diǎn)的
	//地址。
	T chr; 
	in >> chr;   
	//讀入一個字符，只可能讀入#、左括號和字母
	if (isalpha(chr) && isupper(chr) || chr == '('){
		//大寫字母或'('
		ls = new GenListNode<T>;         //建子表結(jié)點(diǎn)
		ls->utype = 2;		
		if (isalpha(chr) && isupper(chr)) {  //表名處理
			int n = L1.Length();
			int m = L1.Search(chr);
			if (m != 0) {                  //該表已建立
				GenListNode<T> *p = *L2.getData(m);		            //查子表地址
				p->info.hlink->info.ref++;		//引用計數(shù)加1
			} 	
			else {       //該表未建立
				L1.Insert(n, chr);  L2.Insert(n, ls);	
				//保存表名及地址
			}
			in >> chr;
			if (chr != '(') exit(1);	           //表名后必跟'('
		}
		ls->info.hlink = new GenListNode<T>; 
		ls->info.hlink->utype = 0;         //建頭結(jié)點(diǎn)
		ls->info.hlink->info.ref = 1;
		CreateList(in, ls->info.hlink->tlink, L1, L2);
		//遞歸建子表
		CreateList(in, ls, L1, L2);         //遞歸建后繼表
	}
	else if (isalpha(chr) && islower(chr)) {	
		//建原子結(jié)點(diǎn)
		ls = new GenListNode<T>;
		ls->utype = 1;  ls->info.value = chr;
		CreateList(in, ls, L1, L2);
	}
	else if (chr == ','){ 		//建后繼結(jié)點(diǎn)
		if (ls->tlink) delete ls->tlink;
		ls->tlink = new GenListNode<T>;
		CreateList(in, ls->tlink, L1, L2); 
	}
	else if (chr == ')')ls->tlink = NULL;  //鏈?zhǔn)瘴?	else if (chr == '#') ls = NULL;	    //空表, 鏈?zhǔn)瘴?
};


#endif