//
// GList.h 广义表类,不处理递归广义表
//      lanjingquan 2002.6.29
//////////////////////////////////////////////

#ifndef  _H_GLIST
#define  _H_GLIST

#include"glistnode.h"
#include"queue.h"

enum TTraverseMode{GFOrder,DFOrder,Other}; //广度优先，深度优先

//////////////////////////////////////////////
//广义表抽象类
template<class TElem>
class TGList0
{
public:
TGListNode<TElem>* head; //表头指针

virtual long GetLen()=0; //取表的长度
virtual long GetDepth()=0; //取表的深度

virtual TGList0* GetList(TGListNode0<TElem>* pNode)=0;
//返回pNode所对应的子表对象指针
virtual TGListNode0<TElem>* GetHead()=0; //取表头
virtual TGListNode0<TElem>* GetTail()=0; //取表尾

virtual TElem& GetElem(long idx)=0; //取表中序号为idx的元素内容
virtual TGListNode0<TElem>* GetElemNode(long idx)=0;//取表中序号为idx的结点地址

virtual TGListNode0<TElem>* GetSub(TGListNode0<TElem>* pNode,
   long idx)=0;     //返回子表中序号为idx的结点

virtual long GetFathers(TGListNode0<TElem>* pNode,
TGListNode0<TElem>** father)=0;
//取Node的各父结点
virtual TGListNode0<TElem>* GetFirstFather(TGListNode0<TElem>* pNode)=0;
//取第一个父亲
virtual TGListNode0<TElem>* GetNextFather(TGListNode0<TElem>* pNode)=0;
//取下一父亲结点
virtual long IsMenber(TGListNode0<TElem>* pNode)=0; //是否成员
virtual long Locate(TElem& elem,
TGListNode0<TElem>** pNodes)=0; //在表中查找elem

virtual long Cluster(TGListNode0<TElem>* pNode, //几个串行化函数
 TGListNode0<TElem>** pe,
 TTraverseMode tm)=0;
virtual long ClusterJuniors(TGListNode0<TElem>* pNode,
TGListNode0<TElem>** pe,
TTraverseMode tm=GFOrder,
long startLevel=1,
long endLevl=-1)=0;

virtual long ClusterSeniors(TGListNode0<TElem>* pNode,
TGListNode0<TElem>** pe,
TTraverseMode tm=GFOrder,
long startLevel=1,
long endLevl=-1)=0;

virtual TGListNode0<TElem>* InsertNode(TGListNode0<TElem>* pNode,
   long sn)=0; //插入结点
virtual TGListNode0<TElem>* DeleteNode(long sn)=0; //删除结点
};

//////////////////////////////////////////////
//面向具体存取结构的广义表类
template<class TElem>
class TGList:public TGList0<TElem>
{
public:
TGList();
~TGList();

virtual long GetLen(); //取表的长度,不处理循环广义表
virtual long GetDepth(); //取表的深度,不处理循环广义表


virtual TGList0<TElem>* GetList(TGListNode0<TElem>* pNode);
//返回pNode所对应的子表对象指针
virtual TGListNode0<TElem>* GetHead(); //取表头
virtual TGListNode0<TElem>* GetTail(); //取表尾

virtual TElem& GetElem(long idx); //取表中序号为idx的元素内容
virtual TGListNode0<TElem>* GetElemNode(long idx); //取表中序号为idx的结点地址

virtual TGListNode0<TElem>* GetSub(TGListNode0<TElem>* pNode,
   long idx); //返回子表中序号为idx的结点

virtual long GetFathers(TGListNode0<TElem>* pNode,
TGListNode0<TElem>** father);
//取pNode的各父结点
virtual TGListNode0<TElem>* GetFirstFather(TGListNode0<TElem>* pNode);
//取第一个父亲
virtual TGListNode0<TElem>* GetNextFather(TGListNode0<TElem>* pNode);
//取下一父亲结点
virtual long IsMenber(TGListNode0<TElem>* pNode); //是否成员
virtual long Locate(TElem& elem,
TGListNode0<TElem>** pNodes); //在广义表中查找elem

virtual long Cluster(TGListNode0<TElem>* pNode, //几个串行化函数
 TGListNode0<TElem>** pe,
 TTraverseMode tm);
virtual long ClusterJuniors(TGListNode0<TElem>* pNode,
TGListNode0<TElem>** pe,
TTraverseMode tm=GFOrder,
long startLevel=1,
long endLevel=-1);

virtual long ClusterSeniors(TGListNode0<TElem>* pNode,
TGListNode0<TElem>** pe,
TTraverseMode tm=GFOrder,
long startLevel=1,
long endLevel=-1);

virtual TGListNode0<TElem>* InsertNode(TGListNode0<TElem>* pNode,
   long sn); //插入结点
virtual TGListNode0<TElem>* DeleteNode(long sn); //删除结点

private:
TQueueLink<TGListNode<TElem>*> lastVisted; //记录GetFather的状态
TGListNode<TElem>* lastVistedNode; //记录最后结点
TGListNode<TElem>* lastHead; //记录最后结点之父亲
TElem none; //用于错误时返回
long ReleaseGList(TGListNode<TElem>* pNode);        //释放广义表空间

//一些用于包装cnt的辅助函数
long Depth(TGListNode<TElem>* pNode);
long Locate(TGListNode0<TElem>* pHead,
TElem& elem,
TGListNode0<TElem>** pNodes,
long& cnt);
long IsMenber(TGListNode0<TElem>* pHead,
  TGListNode0<TElem>* pNode,
  long& cnt);
long ClusterGFOrder(TGListNode0<TElem>* pNode,
 TGListNode0<TElem>** pe);
long ClusterDFOrder(TGListNode0<TElem>* pNode,
 TGListNode0<TElem>** pe,
 long& cnt);
long ClusterJuniorsDFOrder(TGListNode0<TElem>* pNode,
   TGListNode0<TElem>** pe,
   long startLevel,
   long endLevel,
   long& cnt,
   long& levelNo);
long ClusterJuniorsGFOrder(TGListNode0<TElem>* pNode,
   TGListNode0<TElem>** pe,
   long startLevel,
   long endLevel);
};

/////////////////////////////////////////////////
//具体函数实现

/////////////////////////////////////////////////
//构造函数
template<class TElem>
TGList<TElem>::TGList()
{
head=new TGListNode<TElem>; //分配带头结点
head->SetSub(NULL);
head->SetNodeTag(1);
head->SetNodeName("headNode");

lastVistedNode=NULL; //设置最后访问状态
lastHead=NULL;
none=(TElem)0; //赋出错返回值
}

/////////////////////////////////////////////////
//析构函数
template<class TElem>
TGList<TElem>::~TGList()
{
ReleaseGList(head); //释放广义表
}

/////////////////////////////////////////////////
//取表的长度,类似单链表的处理方法
template<class TElem>
long TGList<TElem>::GetLen()
{
long cnt=0;
TGListNode<TElem>* p=(TGListNode<TElem>*) head->GetSub();

while(p)
{
p=(TGListNode<TElem>*) p->GetNext();
cnt++;
}

return cnt;
}

/////////////////////////////////////////////////
//取表的深度,不处理递归广义表
template<class TElem>
long TGList<TElem>::GetDepth()
{
return Depth(head);
}

/////////////////////////////////////////////////
//取表的深度,不处理递归广义表,封装了pNode
template<class TElem>
long TGList<TElem>::Depth(TGListNode<TElem>* pNode)
{
if(!pNode->GetSub())
return 1;

long cnt=0;
TGListNode<TElem>* p=(TGListNode<TElem>*) pNode->GetSub();

while(p)
{
if(p->IsList())
{
long n=Depth(p);
cnt=n>cnt?n:cnt;
}
p=(TGListNode<TElem>*) p->GetNext();
}

return cnt+1;
}

/////////////////////////////////////////////////
//返回pNode所对应的子表对象指针
template<class TElem>
TGList0<TElem>* TGList<TElem>::GetList(TGListNode0<TElem>* pNode)
{
if(!(TGListNode<TElem>*)pNode->IsList())
return NULL;

TGList<TElem>* temp=new TGList<TElem>;
temp->head=(TGListNode<TElem>*) pNode;

return temp;
}

/////////////////////////////////////////////////
//取表头
template<class TElem>
TGListNode0<TElem>* TGList<TElem>::GetHead()
{
return head->GetSub(); //取表头
}

/////////////////////////////////////////////////
//取表尾
template<class TElem>
TGListNode0<TElem>* TGList<TElem>::GetTail()
{
if(head->GetSub())
return head->GetSub()->GetNext(); //取表尾

return NULL;
}

/////////////////////////////////////////////////
//取表中序号为idx的元素内容
template<class TElem>
TElem& TGList<TElem>::GetElem(long idx)
{
long nodes=GetLen();
idx=idx>=0?idx:nodes+idx+1;
idx=idx<1?1:idx;
idx=idx>nodes?nodes:idx;

long cnt=0;
TGListNode<TElem>* p=(TGListNode<TElem>*) head->GetSub();
while(p)
{
cnt++;
if(cnt==idx && !p->IsList())
return *p->GetElem();
p=(TGListNode<TElem>*) p->GetNext();
}

return none;
}

/////////////////////////////////////////////////
//取表中序号为idx的结点地址
template<class TElem>
TGListNode0<TElem>* TGList<TElem>::GetElemNode(long idx)
{
long nodes=GetLen();
idx=idx>=0?idx:nodes+idx+1;
idx=idx<1?1:idx;
idx=idx>nodes?nodes:idx;

long cnt=0;
TGListNode<TElem>* p=head;
while(p=(TGListNode<TElem>*) p->GetNext())
{
cnt++;
if(cnt==idx)
return p;
}

return NULL;
}

/////////////////////////////////////////////////
//返回子表中序号为idx的结点
template<class TElem>
TGListNode0<TElem>* TGList<TElem>::GetSub(TGListNode0<TElem>* pNode,
  long idx)
{
TGList<TElem>* temp=(TGList<TElem>*) GetList(pNode);

if(!temp)
return temp->GetElemNode(idx);

return NULL;
}

/////////////////////////////////////////////////
//取pNode的各父结点
template<class TElem>
long TGList<TElem>::GetFathers(TGListNode0<TElem>* pNode,
       TGListNode0<TElem>** father)
{
long cnt=0;

TGListNode<TElem>* tp=head;
TGListNode<TElem>* p=(TGListNode<TElem>*) head->GetSub();
TQueueLink<TGListNode<TElem>*> queue;

while(!queue.IsEmpty()||!p->IsList())
{
if(p==pNode)
father[cnt++]=tp;
queue.QPush(p);

while(p=(TGListNode<TElem>*) p->GetNext())
{
if(p==pNode)
father[cnt++]=tp;

queue.QPush(p);
}

while(!(p=queue.QPop())->IsList())
if(queue.IsEmpty())
return cnt;

tp=p;
p=(TGListNode<TElem>*) p->GetSub();
}

return cnt;
}

/////////////////////////////////////////////////
//取第一个父亲
template<class TElem>
TGListNode0<TElem>* TGList<TElem>::GetFirstFather(TGListNode0<TElem>* pNode)
{
TGListNode<TElem>* tp=head;
TGListNode<TElem>* p=(TGListNode<TElem>*) head->GetSub();

while(!lastVisted.IsEmpty()||!p->IsList())
{
lastVisted.QPush(p);
if(p==pNode)
{
lastHead=tp;
lastVistedNode=p;
return tp;
}

while(p=(TGListNode<TElem>*) p->GetNext())
{
lastVisted.QPush(p);
if(p==pNode)
{
lastHead=tp;
lastVistedNode=p;
return tp;
}
}

while(!(p=lastVisted.QPop())->IsList())
if(lastVisted.IsEmpty())
{
lastHead=NULL;
return NULL;
}

tp=p;
p=(TGListNode<TElem>*) p->GetSub();
}

lastHead=NULL;
return NULL;
}

/////////////////////////////////////////////////
//取下一父亲结点
template<class TElem>
TGListNode0<TElem>* TGList<TElem>::GetNextFather(TGListNode0<TElem>* pNode)
{
TGListNode<TElem>* tp=lastHead;
TGListNode<TElem>* p=lastVistedNode;
if(tp)
goto again;
else
return NULL;

while(!lastVisted.IsEmpty()||!p->IsList())
{
lastVisted.QPush(p);
if(p==pNode)
{
lastHead=tp;
lastVistedNode=p;
return tp;
}

again: while(p=(TGListNode<TElem>*) p->GetNext())
{
lastVisted.QPush(p);
if(p==pNode)
{
lastHead=tp;
lastVistedNode=p;
return tp;
}
}

while(!(p=lastVisted.QPop())->IsList())
if(lastVisted.IsEmpty())
{
lastHead=NULL;
return NULL;
}

tp=p;
p=(TGListNode<TElem>*) p->GetSub();
}

lastHead=NULL;
return NULL;
}

////////////////////////////////////////////////
//是否成员
template<class TElem>
long TGList<TElem>::IsMenber(TGListNode0<TElem>* pNode)
{
long cnt=0;
return IsMenber(head,pNode,cnt);
}

////////////////////////////////////////////////
//是否成员
template<class TElem>
long TGList<TElem>::IsMenber(TGListNode0<TElem>* pHead,
 TGListNode0<TElem>* pNode,
 long& cnt)
{
TGListNode<TElem>* p=(TGListNode<TElem>*) pHead->GetSub();
cnt++;

while(p)
{
if(p==pNode)
return cnt;

if(p->IsList()&&IsMenber(p,pNode,cnt))
return cnt;

cnt--;
p=(TGListNode<TElem>*) p->GetNext();
}

return 0;
}

////////////////////////////////////////////////
//在表中查找elem
template<class TElem>
long TGList<TElem>::Locate(TElem& elem,
       TGListNode0<TElem>** pNodes)
{
long cnt=0;
return Locate(head,elem,pNodes,cnt);
}

////////////////////////////////////////////////
//在表中查找elem
template<class TElem>
long TGList<TElem>::Locate(TGListNode0<TElem>* pHead,
   TElem& elem,
       TGListNode0<TElem>** pNodes,
   long& cnt)
{
if(!pHead->IsList() && *pHead->GetElem()==elem)
pNodes[cnt++]=pHead;

if(pHead->IsList())
Locate(pHead->GetSub(),elem,pNodes,cnt);
if(pHead->GetNext())
Locate(pHead->GetNext(),elem,pNodes,cnt);

return cnt;
}

///////////////////////////////////////////////
//串行化函数，带遍历模式
template<class TElem>
long TGList<TElem>::Cluster(TGListNode0<TElem>* pNode,
TGListNode0<TElem>** pe,
TTraverseMode tm)
{
long cnt=0;
switch(tm)
{
case GFOrder:
return ClusterGFOrder(pNode,pe);
case DFOrder:
return ClusterDFOrder(pNode,pe,cnt);
default:
return 0;
}
}

///////////////////////////////////////////////
//串行化之深度遍历
template<class TElem>
long TGList<TElem>::ClusterDFOrder(TGListNode0<TElem>* pNode,
   TGListNode0<TElem>** pe,
   long& cnt)
{
if(!pNode)
return 0;
if(!pNode->IsList())
{
pe[cnt++]=pNode;
return 0;
}

TGListNode<TElem>* p=(TGListNode<TElem>*) pNode->GetSub();

while(p)
{
ClusterDFOrder(p,pe,cnt);
p=(TGListNode<TElem>*) p->GetNext();
}
return cnt;
}

///////////////////////////////////////////////
//串行化之广度优先
template<class TElem>
long TGList<TElem>::ClusterGFOrder(TGListNode0<TElem>* pNode,
TGListNode0<TElem>** pe)
{
long cnt=0;

if(!pNode)
return 0;
if(!pNode->IsList())
return 0;

TGListNode<TElem>* p=(TGListNode<TElem>*) pNode->GetSub();
TQueueLink<TGListNode<TElem>*> queue;

while(!queue.IsEmpty()||!p->IsList())
{
queue.QPush(p);
while(p=(TGListNode<TElem>*) p->GetNext())
queue.QPush(p);

while(!(p=queue.QPop())->IsList())
{
pe[cnt++]=p;
if(queue.IsEmpty())
return cnt;
}

p=(TGListNode<TElem>*) p->GetSub();
}

return cnt;
}

///////////////////////////////////////////////
//串行化后辈
template<class TElem>
long TGList<TElem>::ClusterJuniors(TGListNode0<TElem>* pNode,
   TGListNode0<TElem>** pe,
   TTraverseMode tm,
   long startLevel,
   long endLevel)
{
long cnt=0,
 levelNo=0,
 height;

if((height=GetDepth())<=0)
return 0;
startLevel=startLevel<0?height+startLevel+1:startLevel;
endLevel=endLevel<0?height+endLevel+1:endLevel; //正负层号处理

if((levelNo=IsMenber(pNode))<=0) //取层号并判空
return 0;

startLevel=startLevel-levelNo+1;
endLevel=endLevel-levelNo+1; //层号转换

switch(tm)
{
case DFOrder:
return ClusterJuniorsDFOrder(pNode,
 pe,
 startLevel,
 endLevel,
 cnt,
 levelNo);
case GFOrder:
return ClusterJuniorsGFOrder(pNode,
 pe,
 startLevel,
 endLevel);
default:
return 0;
}
}

///////////////////////////////////////////////
//串行化后辈之深度优先
template<class TElem>
long TGList<TElem>::ClusterJuniorsDFOrder(TGListNode0<TElem>* pNode,
  TGListNode0<TElem>** pe,
  long startLevel,
  long endLevel,
  long& cnt,
  long& levelNo)
{
if(!pNode)
return 0;
if(!pNode->IsList())
{
if(startLevel<=levelNo && endLevel>=levelNo)
pe[cnt++]=pNode;
return 0;
}

TGListNode<TElem>* p=(TGListNode<TElem>*) pNode->GetSub();
levelNo++;

while(p)
{
ClusterJuniorsDFOrder(p,pe,startLevel,endLevel,cnt,levelNo);
p=(TGListNode<TElem>*) p->GetNext();
}

levelNo--;
return cnt;
}

///////////////////////////////////////////////
//串行化后辈之广度优先
template<class TElem>
long TGList<TElem>::ClusterJuniorsGFOrder(TGListNode0<TElem>* pNode,
  TGListNode0<TElem>** pe,   
  long startLevel,
  long endLevel)
{
long cnt=0,
 levelNo=0;

if(!pNode)
return 0;
if(!pNode->IsList())
return 0;

TGListNode<TElem>* p=(TGListNode<TElem>*) pNode->GetSub();
TQueueLink<TGListNode<TElem>*> queue;
queue.QPush(NULL);

while(!queue.IsEmpty()||!p->IsList())
{
queue.QPush(p);
while(p=(TGListNode<TElem>*) p->GetNext())
queue.QPush(p);

p=queue.QPop();
if(!p)
{
queue.QPush(NULL);
levelNo++;
p=queue.QPop();
}

while(!p->IsList())
{
if(levelNo>=startLevel && levelNo<=endLevel)
pe[cnt++]=p;

p=queue.QPop();
if(queue.IsEmpty())
return cnt;

if(!p)
{
queue.QPush(NULL);
levelNo++;
p=queue.QPop();
}
}

p=(TGListNode<TElem>*) p->GetSub();
}

return cnt;
}

///////////////////////////////////////////////
//串行化祖先
template<class TElem>
long TGList<TElem>::ClusterSeniors(TGListNode0<TElem>* pNode,
   TGListNode0<TElem>** pe,
   TTraverseMode tm,
   long startLevel,
   long endLevel)
{
long cnt=0,
 levelNo=0,
 height;

if((height=GetDepth())<=0)
return 0;
startLevel=startLevel<0?height+startLevel+1:startLevel;
endLevel=endLevel<0?height+endLevel+1:endLevel; //正负层号处理

switch(tm)
{
case DFOrder:
return ClusterJuniorsDFOrder(pNode,
 pe,
 startLevel,
 endLevel,
 cnt,
 levelNo);
case GFOrder:
return ClusterJuniorsGFOrder(pNode,
 pe,
 startLevel,
 endLevel);
default:
return 0;
}
}

////////////////////////////////////////////////
//插入结点
template<class TElem>
TGListNode0<TElem>* TGList<TElem>::InsertNode(TGListNode0<TElem>* pNode,
  long sn)
{
if(!pNode)
return NULL;

long len=GetLen();
sn=sn>0?sn:len+sn+1;
sn=sn>len?len:sn;
sn=sn<=0?1:sn;

if(sn==1)
{
pNode->SetNext(head->GetSub());
head->SetSub(pNode);
return pNode;
}

long find=1;
TGListNode<TElem>* p=(TGListNode<TElem>*) head->GetSub();
while(find+1!=sn)
{
p=(TGListNode<TElem>*) p->GetNext();
find++;
}

pNode->SetNext(p->GetNext());
p->SetNext(pNode);

return p;
}

////////////////////////////////////////////////
//删除结点
template<class TElem>
TGListNode0<TElem>* TGList<TElem>::DeleteNode(long sn)
{
long find=1;

long len=GetLen();
sn=sn>0?sn:len+sn+1;
sn=sn>len?len:sn;
sn=sn<0?1:sn;

TGListNode<TElem>* p=(TGListNode<TElem>*) head->GetSub();
TGListNode<TElem>* temp;

if(sn=1)
{
head->SetSub(p->GetNext());
return p;
}

while(find+1!=sn)
{
p=(TGListNode<TElem>*) p->GetNext();
find++;
}

temp=(TGListNode<TElem>*) p->GetNext();
p->SetNext(temp->GetNext());
return temp;

}

////////////////////////////////////////////////
//释放pNode带头的表空间
template<class TElem>
long TGList<TElem>::ReleaseGList(TGListNode<TElem>* pNode)
{
static long cnt=0;

if(!pNode->IsList()&&!pNode->GetNext())
{
delete pNode;
return ++cnt;
}

if(pNode->IsList())
ReleaseGList((TGListNode<TElem>*) pNode->GetSub());
if(pNode->GetNext())
ReleaseGList((TGListNode<TElem>*) pNode->GetNext());

delete pNode;
return ++cnt;
}

#endif