//linkedlist.h文件
#include<iostream.h>
#include "node.cpp"

template <class T>

class LinkedList
{
private:
	//指向表頭和表尾的指針
	Node<T>  *front, *rear;
	//用于訪問數據，插入和刪除結點的指針
	Node<T>  *prevPtr, *currPtr;
	//表中的結點數
	int size;
	//表中當前結點位置計數
	int position;
	//申請及釋放結點空間的函數
	Node<T> *GetNode(const T& item ,Node<T> *ptr=NULL);
	void FreeNode(Node<T> *p);
public:
	//構造函數和析構函數
	LinkedList(void);
	~LinkedList(void);
	//重載的賦值運算符
	LinkedList<T> & operator = (const LinkedList<T> &orgList) ;
    //取表的大小
	int Size(void) const ;
	//判斷表是否為空
	bool IsEmpty(void) const;
	//重定位當前結點
	int NextNode(void) ;
	int SetPosition(int pos);
    int GetPosition(void) const; 
	//插入結點的函數
	void InsertAt(const T& item);
	void InsertAfter(const T& item);
	//刪除結點的函數
	void DeleteAt(void);
	void DeleteAfter(void);
	//修改和訪問數據的函數
	T GetData(void) const;
	void SetData(const T& item);
	//清空鏈表的函數
	void Clear(void);
};

//linkedlist.cpp文件
#include<iostream.h>
#include"linkedlist.h"
#include<stdlib.h>

//鏈表類中申請結點空間的函數
template <class T>
Node<T> *LinkedList<T>::GetNode(const T& item,Node<T> *ptr)
{
	Node<T> *newNode=new Node<T> (item,ptr);
	//若動態內存申請失敗，則給出相應提示并返回空指針
	if(!newNode)
	{
		cerr<<"GetNode:Memory allocation failed!"<<endl;
		return NULL;
	}
	//返回指向新生成結點的指針
	return newNode;
}

//鏈表類中釋放結點空間的函數
template <class T>
void LinkedList <T>::FreeNode(Node<T> *ptr)
{
	//若ptr為空，則給出相應提示并返回
	if(!ptr)
	{
		cerr<<"FreeNode: invalid node pointer!"<<endl;
		return ;
	}
   //釋放結點占用的內存空間
	delete ptr;
}

//鏈表類的構造函數（建立一個空鏈表）
template <class T>
LinkedList<T>::LinkedList(void): front(NULL),rear(NULL),prevPtr(NULL),currPtr(NULL),size(0),position(-1)
{}

//鏈表類的析構函數
template <class T>
LinkedList <T>::~LinkedList(void)
{
	//清空鏈表，釋放所有結點空間
	Clear();
}

//鏈表類中重載賦值運算符的函數
template <class T>
LinkedList<T> & LinkedList<T>::operator = (const LinkedList<T> &orgList)
{
	Node<T> *p=orgList.front;
	//清空本鏈表
	Clear();
	//將表orgList中的元素復制到本表
	while(p)
	{
		InsertAfter(p->date);
		p=p->NextNode();
	}
	//設置當前結點
	SetPosition(orgList.position);
	return *this;
}

//鏈表類中取表大小的函數
template <class T>
int LinkedList<T>::Size(void) const
{
	return size;
}

//鏈表類中判斷是否為空的函數
template<class T>
bool LinkedList<T>::IsEmpty(void) const
{
	return size?false:true ;
}

//鏈表類中將后繼結點設置為當前結點的函數
template <class T>
int LinkedList<T>::NextNode(void) 
{
	//若當前結點存在，則將其后繼結點設置為當前結點
	if((position>=0)&&(position<size))
	{
		position++;
		prevPtr=currPtr;
		currPtr=currPtr->NextNode();
	}
	else
	{
		//否則將當前位置設為表尾后
		position=size;
	}
	//返回新位置
	return position;
}

//鏈表類中重置當前位置的函數
template <class T>
int LinkedList<T>::SetPosition(int pos)
{
	//若鏈表為空，則返回
	if(!size) return -1;
	//若鏈表為空，則返回
	if(pos<0 || pos>size-1)
	{
		cerr<<"position error"<<endl;
		return -1;
	}
	//尋找對應結點
	prevPtr=NULL;
	currPtr=front;
	position=0;
	for(int k=0;k<pos ;k++)
	{
		position++;
		prevPtr=currPtr;
		currPtr=currPtr->NextNode();
	}
	//返回當前結點位置
	return position;
}

//鏈表類中取當前結點位置的函數
template <class T>
int LinkedList<T>::GetPosition(void) const
{
	return position;
}

//鏈表類中在當前結點處插入新結點的函數
template <class T>
void LinkedList<T>::InsertAt(const T& item)
{
	Node<T> *newNode;
	if(!size)
	{
		//在空表中插入
		newNode=GetNode(item,front);
		front=rear=newNode;
		position=0;
	}
	else if(!prevPtr)
	{
		//在表頭結點處插入
		newNode=GetNode(item,front);
		front=newNode;
	}
	else
	{
		//在鏈表的中間位置插入
		newNode=GetNode(item,currPtr);
		prevPtr->InsertAfter(newNode);
	}
	//增加鏈表的大小
	size++;
	//新插入的結點為當前結點
	currPtr=newNode;
}

//鏈表類中在當前結點后插入新結點的函數
template<class T>
void LinkedList<T>::InsertAfter(const T& item)
{
	Node<T> *newNode;
	if(!size)
	{
		//在空表中插入
		newNode=GetNode(item);
		front=rear=newNode;
        position=0;
	}
	else if (currPtr==rear|| !currPtr)
	{
		//在表尾結點后插入
		newNode=GetNode(item);
		rear->InsertAfter(newNode);
		prevPtr=rear;
		rear=newNode;
		position=size;
	}
	else
	{
		//在鏈表的中間位置插入
		newNode=GetNode(item,currPtr->NextNode());
		currPtr->InsertAfter(newNode);
		prevPtr=currPtr;
		position++;
	}
	//增加鏈表的大小
	size++;
	//新插入的結點為當前結點
	currPtr=newNode;
}

//鏈表類中刪除當前結點的函數
template <class T>
void LinkedList<T>::DeleteAt(void)
{
	Node<T> *oldNode;
	//若表為空或已到表尾之后，則給出錯誤提示并返回
	if(!currPtr)
	{
		cerr<<"DeleteAt: current position is invalid!"<<endl;
		return ;
	}
	if(!prevPtr)
	{
		//刪除的是表頭結點
		oldNode=front;
		front=currPtr->NextNode();
	}
	else
	{
		//刪除的是表中結點
		oldNode=prevPtr->DeleteAfter();
	}
    if(oldNode==rear)
	{
	//刪除的是表尾結點，則修改表尾指針和當前結點位置值
	rear=prevPtr;
	position--;
	}
	//后繼結點作為新的當前結點 
	currPtr=oldNode->NextNode();
	//釋放原當前結點
	FreeNode(oldNode);
	//鏈表大小減1
	size--;
}

//鏈表類中刪除當前結點后繼的函數
template <class T>
void LinkedList<T>::DeleteAfter(void)
{
	Node<T> *oldNode;
	//若表為空或已到表尾，則給出錯誤提示并返回
	if(!currPtr|| currPtr==rear)
	{
		cerr<<"DeleteAfter:current position is invalid!"<<endl;
		return;
	}
	//保存被刪除結點的指針并從鏈表中刪除該結點
	oldNode=currPtr->DeleteAfter();
	if(oldNode==rear)
	{
		//刪除的是表尾結點
		rear=currPtr;
	}
	//釋放被刪除結點
	FreeNode(oldNode);
	//鏈表大小減1
	size--;
}

//鏈表類中獲取當前結點數據的函數
template <class T>
T LinkedList<T>::GetData(void) const 
{
	//若表為空或已到達表尾之后，則出錯
	if(!size || !currPtr)
	{
		//給出出錯信息并退出
		cerr<<"Data:current node not exist!"<<endl;
		exit(1);
	}
	return currPtr->data ;
}

//鏈表類中修改當前結點數據的函數
template <class T>
void LinkedList<T>::SetData(const T& item)
{
	//若表為空或已經達到表尾之后，則出錯
	if(!size || !currPtr)
	{
		cerr<<"Data:current node not exist!"<<endl;
		exit(1);
	}
	//修改當前結點的值
	currPtr->data=item;
}

//鏈表類中清空鏈表的函數
template <class T>								  
void LinkedList<T>::Clear(void)
{
	Node<T> *currNode=front, *nextNode ;
	while(currNode)
	{
		//保存后繼結點指針
		nextNode=currNode->NextNode();
		//釋放當前結點
		FreeNode(currNode);
		//原后繼結點成為當前結點
		currNode=nextNode;
	}
	//修改空鏈表數據
	front=rear=prevPtr=currPtr=NULL ;
	size=0;position=-1;
}