//9_6.cpp
#include <iostream>
#include <cstdlib>
#include "9_6.h"
using namespace std;
template <class T>
Node<T> *LinkedList<T>::GetNode(const T& item, Node<T>* ptrNext)	//生成新結點
{
   Node<T> *p;
   p = new Node<T>(item,ptrNext);
   if (p == NULL)
   {
      cout << "Memory allocation failure!\n";
      exit(1);
   }
   return p;
}

template <class T>
void LinkedList<T>::FreeNode(Node<T> *p) //釋放結點
{
   delete p;
}

template <class T>
void LinkedList<T>::CopyList(const LinkedList<T>& L) //鏈表復制函數
{
   Node<T> *p = L.front;	//P用來遍歷L 
   int pos;
   while (p != NULL)	//將L中的每一個元素插入到當前鏈表最后
   {
      InsertRear(p->data);
      p = p->NextNode();
   }
   if (position == -1)	//如果鏈表空,返回
      return;
   //在新鏈表中重新設置prevPtr和currPtr
   prevPtr = NULL;
   currPtr = front;
   for (pos = 0; pos != position; pos++)
   {
      prevPtr = currPtr;
      currPtr = currPtr->NextNode();
   }
}

template <class T>  //構造一個新鏈表，將有關指針設置為空，size為0，position為-1
LinkedList<T>::LinkedList(void): front(NULL), rear(NULL),
      prevPtr(NULL),currPtr(NULL), size(0), position(-1)
{}

template <class T>
LinkedList<T>::LinkedList(const LinkedList<T>& L)  //拷貝構造函數
{
   front = rear = NULL;
   prevPtr = currPtr = NULL;
   size = 0;
   position = -1;
   CopyList(L);
}

template <class T>
void LinkedList<T>::ClearList(void)	//清空鏈表
{
   Node<T> *currPosition, *nextPosition;
   currPosition = front;
   while(currPosition != NULL)
   {
      nextPosition = currPosition->NextNode(); //取得下一結點的地址
      FreeNode(currPosition);	//刪除當前結點
      currPosition = nextPosition;	//當前指針移動到下一結點
   }
   front = rear = NULL;
   prevPtr = currPtr = NULL;
   size = 0;
   position = -1;
}

template <class T>
LinkedList<T>::~LinkedList(void)	//析構函數
{   ClearList();  }

template <class T>
LinkedList<T>& LinkedList<T>::operator=(const LinkedList<T>& L)//重載"="
{
   if (this == &L)	// 不能將鏈表賦值給它自身
      return *this;
   ClearList();
   CopyList(L);
   return *this;
}

template <class T>
int LinkedList<T>::ListSize(void) const	//返回鏈表大小的函數
{   return size;  }

template <class T>
int LinkedList<T>::ListEmpty(void) const	//判斷鏈表為空否
{   return size == 0;  }

template <class T>
void LinkedList<T>::Next(void)	//將prevPtr和currPtr向前移動一個結點
{
   if (currPtr != NULL)
   {
      prevPtr = currPtr;
      currPtr = currPtr->NextNode();
      position++;
   }
}

template <class T>
int LinkedList<T>::EndOfList(void) const	// 判斷是否已達表尾
{   return currPtr == NULL;  }


template <class T>
int LinkedList<T>::CurrentPosition(void) const  // 返回當前結點的位置
{   return position;  }


template <class T>
void LinkedList<T>::Reset(int pos)	//將鏈表當前位置設置為pos 
{
   int startPos;
   if (front == NULL)	// 如果鏈表為空，返回
      return;
   if (pos < 0 || pos > size-1)	// 如果指定位置不合法，中止程序
   {
      cerr << "Reset: Invalid list position: " << pos << endl;
      return;
   }
   // 設置與遍歷鏈表有關的成員
   if(pos == 0)	// 如果pos為0，將指針重新設置到表頭
   {
      prevPtr = NULL;
      currPtr = front;
      position = 0;
   }
   else	// 重新設置 currPtr, prevPtr, 和 position 
   {
       currPtr = front->NextNode();
       prevPtr = front;
       startPos = 1;
	   for(position=startPos; position != pos; position++)
	   {
	       prevPtr = currPtr;
	       currPtr = currPtr->NextNode();
      }
   }
}

template <class T>
T& LinkedList<T>::Data(void)	//返回一個當前結點數值的引用
{
   if (size == 0 || currPtr == NULL)	// 如果鏈表為空或已經完成遍歷則出錯
   {
      cerr << "Data: invalid reference!" << endl;
      exit(1);
   }
   return currPtr->data;
}

template <class T>
void LinkedList<T>::InsertFront(const T& item)   // 將item插入在表頭
{
   if (front != NULL)	// 如果鏈表不空則調用Reset 
      Reset();
   InsertAt(item);	// 在表頭插入
}


template <class T>
void LinkedList<T>::InsertRear(const T& item)   // 在表尾插入結點
{
   Node<T> *newNode;
   prevPtr = rear;
   newNode = GetNode(item);	// 創建新結點
   if (rear == NULL)	// 如果表空則插入在表頭
      front = rear = newNode;
   else
   {
      rear->InsertAfter(newNode);
      rear = newNode;
   }
   currPtr = rear;
   position = size;
   size++;
}


template <class T>
void LinkedList<T>::InsertAt(const T& item)	// 將item插入在鏈表當前位置
{
   Node<T> *newNode;
   if (prevPtr == NULL)	// 插入在鏈表頭，包括將結點插入到空表中
   {
      newNode = GetNode(item,front);
      front = newNode;
   }
   else	// 插入到鏈表之中. 將結點置于prevPtr之后
   {
      newNode = GetNode(item);
      prevPtr->InsertAfter(newNode);
   }
   if (prevPtr == rear)	//正在向空表中插入，或者是插入到非空表的表尾
   {
      rear = newNode;	//更新rear 
      position = size;	//更新position 
   }
   currPtr = newNode;	//更新currPtr
   size++;	//使size增值
}


template <class T>
void LinkedList<T>::InsertAfter(const T& item)  // 將item 插入到鏈表當前位置之后
{
   Node<T> *p;
   p = GetNode(item);
   if (front == NULL)	 // 向空表中插入
   {
      front = currPtr = rear = p;
      position = 0;
   }
   else	// 插入到最后一個結點之后
   {
      if (currPtr == NULL)
        currPtr = prevPtr;
      currPtr->InsertAfter(p);
      if (currPtr == rear)
      {
        rear = p;
        position = size;
      }
      else
        position++;
      prevPtr = currPtr;
      currPtr = p;
   }
   size++;              // 使鏈表長度增值
}


template <class T>
T LinkedList<T>::DeleteFront(void)	// 刪除表頭結點
{
   T item;
   Reset();
   if (front == NULL)
   {
      cerr << "Invalid deletion!" << endl;
      exit(1);
   }
   item = currPtr->data;
   DeleteAt();
   return item;
}

     
template <class T>
void LinkedList<T>::DeleteAt(void)	// 刪除鏈表當前位置的結點
{
   Node<T> *p;
   if (currPtr == NULL)	// 如果表空或達到表尾則出錯
   {
      cerr << "Invalid deletion!" << endl;
      exit(1);
   }
   if (prevPtr == NULL)	// 刪除將發生在表頭或鏈表之中
   {
      p = front;	// 保存頭結點地址
      front = front->NextNode();	//將其從鏈表中分離
   }
   else	//分離prevPtr之后的一個內部結點，保存其地址
      p = prevPtr->DeleteAfter();

   if (p == rear)	// 如果表尾結點被刪除
   {
      rear = prevPtr;	//新的表尾是prevPtr 
      position--;	//position自減
   }
   currPtr = p->NextNode();	// 使currPtr越過被刪除的結點
   FreeNode(p);	// 釋放結點，并
   size--;	//使鏈表長度自減
}