#include "Node.h"
#include "stdlib.h"

template<class T>
class LinkedList
{
	Node<T>*front,*rear;                                    //一個頭指針和一個尾指針
	Node<T>*prevPtr,*currPtr;                               //前指針和當(dāng)前指針
	int size,position;                                      //鏈表長度    和 當(dāng)前位置
	Node<T>*GetNode(const T&item,Node<T>*ptrNext=NULL);      //得到一個節(jié)點
	void FreeNode(Node<T>*p);                               //釋放節(jié)點
	void CopyList(const LinkedList<T>&L);                   //復(fù)制鏈表
public:
	LinkedList(void);                                       //無參構(gòu)造函數(shù)
	LinkedList(const LinkedList <T>&L);                     //有參構(gòu)造函數(shù)
	~LinkedList(void);                                      //析構(gòu)函數(shù)
	LinkedList<T>& operator=(const LinkedList<T>&L);        //重載賦值符號
	int ListSize(void)const;                          //取鏈表長度
	int ListEmpty(void)const;                         //判斷鏈表是不是空
	void Reset(int pos=0);                            //把當(dāng)前指針重置在鏈表的頭
	void Next(void);                                  //把當(dāng)前指針移到下一個   
	int EndOfList(void)const;                         //判斷是否是鏈表的尾
	int CurrentPosition(void)const;                   //求當(dāng)前指針的位置
	void InsertFront(const T&item);                    //插入頭        
	void InsertRear(const T&item);                    //插入尾
	void InsertAt(const T&item);                      //插在當(dāng)前位置
	void InsertAfter(const T&item);                   //插在當(dāng)前節(jié)點后面
	T DeleteFront(void);                              //去掉頭指針
	void DeleteAt(void);                              //去掉當(dāng)前指針
	T& Data(void);                                    //取this指針中的數(shù)據(jù)
	void ClearList(void);                             //清空指針
};

template <class T>
LinkedList<T>::LinkedList(void):   
          front(NULL), rear(NULL),prevPtr(NULL),
		  currPtr(NULL),size(0),position(-1){}


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>
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>::FreeNode(Node<T> *p)
{
   delete p;
}

template <class T>
void LinkedList<T>::CopyList(const LinkedList<T>& L)
{   
	// use p to chain through L
    Node<T> *p = L.front;   int  pos;
    // insert each element in L at the rear of current object
    while (p != NULL)
    {  
		InsertRear(p->data);   
		p = p->NextNode( );  
	}
    if (position == -1) return;   // if list is empty return
    // reset prevPtr and currPtr in the new list
    prevPtr = NULL;   currPtr = front;
    for (pos = 0; pos != position; pos++)
    {  
		prevPtr = currPtr;
        currPtr = currPtr->NextNode( ); 
	}
}
template <class T>
void LinkedList<T>::ClearList(void)
{  
	Node<T> *currPosition, *nextPosition;
    currPosition = front;
    while(currPosition != NULL)
    {  
		// get address of next node and delete current node
        nextPosition = currPosition->NextNode( );
        FreeNode(currPosition);
        currPosition = nextPosition;  // Move to next node 
	}
    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)      // Can't assign list to itself
        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)
{  // if traversal has reached the end of the list or
   // the list is empty, just return
   if (currPtr != NULL)
   { // advance the two pointers one node forward
      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)
{   
	int startPos;     
	if (front == NULL) return;
    if (pos < 0 || pos > size-1) 
    { 
		cerr << "Reset: Invalid list position: " <<pos << endl;            
		return;  
	}
    if(pos == 0)  
    {
		prevPtr = NULL;   
		currPtr = front;     
		position = 0;   
	}
    else 
	{  
		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)
{
   // error if list is empty or traversal completed
   if (size == 0 || currPtr == NULL)
   {
      cerr << "Data: invalid reference!" << endl;
      exit(1);
   }
   return currPtr->data;
}
template <class T>
void LinkedList<T>::InsertAt(const T& item)
{   
	Node<T> *newNode;
    if (prevPtr == NULL)
    { 
		newNode = GetNode(item, front);
        front = newNode;   
	}
   else  
   {
	   newNode = GetNode(item);
       prevPtr->InsertAfter(newNode);   
   }
   if (prevPtr == rear)
   {
	   rear = newNode; 
	   position = size;   
   }
   currPtr = newNode;   
   size++;
}
template <class T>
void LinkedList<T>::InsertFront(const T& item)
{
      // call Reset if the list is not empty
      if (front != NULL)
           Reset( );
      InsertAt(item);        // inserts at front
}
template <class T>
void LinkedList<T>::InsertAfter(const T& item)
{   
	Node<T> *p;   
	p = GetNode(item);
    if (front == NULL)       // inserting into an empty list
    {  
		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++;              // increment list size
}
template <class T>
void LinkedList<T>::InsertRear(const T& item)
{  
	Node<T> *newNode;
    prevPtr = rear;
    newNode = GetNode(item);	// create the new node
    if (rear == NULL) // if list empty, insert at front
      front=rear = newNode;
    else 
	{ 
		rear->InsertAfter(newNode);  
        rear = newNode;  
	}
    currPtr = rear;   
	position = size;   
	size++;
}
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  p = prevPtr->DeleteAfter( );
   if (p == rear)  
   {  
	   rear = prevPtr;  
	   position--;  
   }
   currPtr = p->NextNode( );  
   FreeNode(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;
}