#include<iostream.h>
#include<assert.h>
template<class T>
class list;
template<class T>
class listiterator;
//*******************************************************************************
template<class T>
class link
{
public:
	//插入一個新結點
	link<T>*insert(T val);
	//構造函數(shù)
	link(T linkvalue,link<T>* np);
	link(const link<T>& s);
	//復制
    link<T>* duplicate()const;
    friend class list<T>;
    friend class listiterator<T>;
//private:	
    T value;
	link<T>* ptrtonextlink;
};
//--------------------------------------------------------------------
template<class T>
link<T>*link<T>::insert(T val)
{
    ptrtonextlink=new link<T>(val,ptrtonextlink);
    assert(ptrtonextlink!=0);
    return ptrtonextlink;
}

//------------------------------
template<class T>
link<T>::link(T val,link<T>* nxt)
:value(val),ptrtonextlink(nxt){}

//-------------------------------
template<class T>
link<T>::link(const link<T>& s)
:value(s.value),ptrtonextlink(s.ptrtonextlink){}

//------------------------------------
template<class T>
link<T>*link<T>::duplicate()const
{
    link<T>* newlink;
    if(ptrtonextlink!=0)             //當還有下一個結點時遞歸調用復制函數(shù)
    newlink=new link<T>(value,ptrtonextlink->duplicate());
    else
    newlink=new link<T>(value,0);
    assert(newlink!=0);              //檢查動態(tài)分配是否成功
    return newlink;
}

//***********************************************************************
template<class T>
class list
{
public:
    list();
    list(const list<T> &);
    virtual  ~list();
    virtual  void  add(T );
    virtual  void  deleteallvalues();
    T  firstelement( )const;
    virtual  int  includes(T)const;
    int  isempty()const; 
    virtual  void  removefirst();
    list<T> *duplicate()const;
//	friend class listiterator<T>;
//protected:
    link<T>* ptrtofirstlink;
};

//-------------------------------------------------------
template<class T>list<T>::list():ptrtofirstlink(0){}

//--------------------------------------------------
template<class T> list<T>::list(const list<T>&source)
{  
	if(source.isempty())
      ptrtofirstlink=0;
    else
	{
		link<T>*firstlink=source.ptrtofirstlink;
        ptrtofirstlink=firstlink->duplicate();
	}
}

//--------------------------------------------
template<class T> list<T>::~list()
{
	deleteallvalues();
}

//---------------------------------------------------------
template<class T>void list<T>::add(T val)
{
	ptrtofirstlink=new link<T>(val,ptrtofirstlink);
    assert(ptrtofirstlink!=0);
}

//-----------------------------------------------------
template<class T>void list<T>::deleteallvalues()
{
	link<T>*next;
    for(link<T>*p=ptrtofirstlink;p!=0;p=next)
	{
		next=p->ptrtonextlink;
        p->ptrtonextlink=0;
        delete p;
	}
    ptrtofirstlink=0;
}

//---------------------------------------------------------
template<class T>T list<T>::firstelement()const
{
	assert(ptrtofirstlink!=0);
	return ptrtofirstlink->value;
}

//-------------------------------------------------------
template<class T>int list<T>::includes(T  v)const
{
	for(link<T>*p=ptrtofirstlink;p;p=p->ptrtonextlink)
       if(v==p->value)return 1;
               return 0;
}

//-------------------------------------------------------
template<class T>int list<T>::isempty()const
{
	return ptrtofirstlink==0;
}

//-------------------------------------------------------
template<class T>void list<T>::removefirst()
{	
	assert(ptrtofirstlink!=0);
    link<T>*p=ptrtofirstlink;
    ptrtofirstlink=p->ptrtonextlink;
    delete p;
}

//------------------------------------------------------
template<class T>list<T>* list<T>::duplicate()const
{
	list<T>*newlist=new list<T>;
    assert(newlist!=0);
    if(ptrtofirstlink)
      newlist->ptrtofirstlink=ptrtofirstlink->duplicate();
    return newlist;
}

//********************************************************************iterator類定義
template<class T>
class iterator{
public:
	//對循環(huán)做初始化
	virtual int init()=0;
	//檢查是否還有元素
	virtual int operator!()=0;
	//訪問當前元素
	virtual T operator()()=0;
	//訪問下一個元素
	virtual int operator++()=0;
	//改變當前元素
	virtual void operator=(T newvalue)=0;
};

//***********************************************************************listiterator
template<class T>class listiterator:public iterator<T>{//表遍歷
	public: 
		listiterator(list<T>& );
		virtual  int  init();//初始化游標
  		virtual  int operator!();
  		virtual  T  operator()();
  		virtual  int operator++();//只有該操作能改變游標指向
  		virtual  void operator=(T);
		void  removecurrent();//刪除當前結點
		void  addbefore(T);//在當前結點前插入
		void  addafter(T);//在當前結點后插入
	protected:
		link<T> * currentlink;      //遍歷中的游標（指針）
		link<T> * previouslink;            //遍歷中的前驅游標（指針）
		list<T>& thelist;        //引用一個表
};

//-----------------------------------------------------------------------
template<class T>listiterator<T>::listiterator(list<T>& alist):thelist(alist)
{
	init();
}

//------------------------------------------------------------------------
template<class T>int listiterator<T>::init()
{    
	previouslink=0;
	currentlink=thelist.ptrtofirstlink;
	return currentlink!=0;
}

//--------------------------------------------------------
template<class T>int listiterator<T>::operator!()
{
	if(currentlink!=0)
		return 1;
    if(previouslink!=0)
        return previouslink->ptrtonextlink!=0;
    return thelist.ptrtofirstlink!=0;
}

//------------------------------------------------------------------
template<class T>T listiterator<T>::operator()(){
	if (currentlink!=NULL) 	return  currentlink->value;
	else
if (previouslink!=NULL&&previouslink->ptrtonextlink!=NULL)
			return  previouslink->ptrtonextlink->value;
    else if (previouslink==NULL&&thelist.ptrtofirstlink!=NULL)
			return thelist.ptrtofirstlink->value;

assert(previouslink!=NULL&&previouslink->ptrtonextlink
!=NULL||previouslink==NULL&&thelist.ptrtofirstlink!=NULL);
}

//----------------------------------------------------------------------------
template<class T>int listiterator<T>::operator++()
{
	if(currentlink==0)
	{  
		if(previouslink==0)
            currentlink=thelist.ptrtofirstlink;
        else	
			currentlink=previouslink->ptrtonextlink;
	}
    else 
	{
		previouslink=currentlink;
        currentlink=currentlink->ptrtonextlink;
	}
    return currentlink!=0;
}

//---------------------------------------------------------------
template<class T> void listiterator<T>::operator=(T val){
	if (currentlink!=NULL)
	{
		currentlink->value=val; return;
	}
	else
if (previouslink!=NULL&&previouslink->ptrtonextlink!=NULL)
previouslink->ptrtonextlink->value=val;
return;
    if (previouslink==NULL&&thelist.ptrtofirstlink!=NULL)
thelist.ptrtofirstlink->value=val; return ;
	
assert(previouslink!=NULL&&previouslink->ptrtonextlink
!=NULL||previouslink==NULL&&thelist.ptrtofirstlink!=NULL);
}

//--------------------------------------------------------------
template<class T>void listiterator<T>::removecurrent()
{//刪除當前結點
  link<T> *p;
  if (currentlink!=NULL) {
	if (previouslink==NULL) 
		thelist.ptrtofirstlink=currentlink->ptrtonextlink;
	else previouslink->ptrtonextlink=currentlink->ptrtonextlink;
	delete currentlink;	currentlink=0; 
	return;
  }
  else 
	if (previouslink!=NULL&&previouslink->ptrtonextlink!=NULL){
		p=previouslink->ptrtonextlink;
		previouslink->ptrtonextlink=p->ptrtonextlink;
		delete p; 	return ;
  	}
  	else 
		if (previouslink==NULL&&thelist.ptrtofirstlink!=NULL){
			p=thelist.ptrtofirstlink;
			thelist.ptrtofirstlink=p->ptrtonextlink;
			delete p;
			return ;
  		}
        assert(previouslink!=NULL&&previouslink->ptrtonextlink!=NULL
        ||previouslink==NULL&&thelist.ptrtofirstlink!=NULL);
}

//-----------------------------------------------------------
template<class T>void listiterator<T>::addbefore(T val)
{  
	if(previouslink)
       previouslink=previouslink->insert(val);
    else
	{  
	   thelist.list<T>::add(val);
	   previouslink=thelist.ptrtofirstlink;
	}
}

//-----------------------------------------------------------------
template<class T>
void listiterator<T>::addafter(T val){
	//當前結點非空，在當前結點后插入
	if (currentlink!=NULL) 
		currentlink->insert(val);
	else if (previouslink!=NULL) //當前結點空，但前驅非空
		if (previouslink->ptrtonextlink!=NULL)
			 //前的后繼非空，在前驅的后繼結點后插入
			previouslink->ptrtonextlink->insert(val);
		else 	
		previouslink->insert(val);
	else  if  (thelist.ptrtofirstlink)//表非空，在第一個結點后插入
		 	thelist.ptrtofirstlink-> insert(val);
	else  thelist.add(val);
						//表空，作為第一個結點插入
}