/* 雙向循環鏈表
 * 
 */

#ifndef DOUBLE_CIRCULAR_LINKEDLIST_CLASS
#define DOUBLE_CIRCULAR_LINKEDLIST_CLASS

#include <stdlib.h>
#include "dnode.h"

template <class T>
class DCLinkedList
{
	private:
		// 指向表頭的指針和當前結點的指針
		DNode<T> *header, *currPtr;
		
		// 表中的元素個數和當前的位置值
		int size;

		// 將表 L 拷貝到當前表尾
		void CopyList(const DCLinkedList<T> &L);
	
	public:
		// 構造函數
		DCLinkedList(void);
		DCLinkedList(const DCLinkedList<T> &L);

		// 析構函數
		~DCLinkedList(void);

		// 賦值運算符
		DCLinkedList<T>& operator= (const DCLinkedList<T> &L);

		// 檢查表狀態的函數
		int ListSize(void) const;               
		bool ListEmpty(void) const;

		// 遍歷表的函數
		void Reset(bool bheader = true);	// 是從表頭開始遍歷，還是表尾（反向遍歷）
		void Next(void);
		void Prev(void);
		bool EndOfList(void) const;

		// 插入函數
		void InsertFront(const T &item);
		void InsertRear(const T &item);
		void InsertAt(const T &item);
		void InsertAfter(const T &item);

		// 刪除函數
		void DeleteFront(void);
		void DeleteRear(void);
		void DeleteAt(void);

		// 訪問／修改數據
		T& Data(void);
		bool Find(const T& item);

		// 清空表的函數
		void ClearList(void);
};

// 構造函數
template <class T>
DCLinkedList<T>::DCLinkedList(void):size(0)
{
	// 創建“哨位”結點，注意 new 可能會拋出異常
	currPtr = header = new DNode<T>();
}

// 構造函數
template <class T>
DCLinkedList<T>::DCLinkedList(const DCLinkedList<T>& L):size(0)
{
	// 創建“哨位”結點，注意 new 可能會拋出異常
	currPtr = header = new DNode<T>();
	CopyList(L);
}

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

// 將 L 拷貝到當前表尾
template <class T>
void DCLinkedList<T>::CopyList(const DCLinkedList<T> &L)
{
	// 用指針 P 遍歷表
	DNode<T> *p = L.header->NextNodeRight();

	// 往當前表的表尾插入 L 的每個元素
	while (p != L.header)
	{
		InsertRear(p->data);
		p = p->NextNodeRight();
	}
}

template <class T>
int DCLinkedList<T>::ListSize(void) const
{
	// 不包括哨位結點
	return size;
}

template <class T>
bool DCLinkedList<T>::ListEmpty(void) const
{
	return (size == 0);
}

template <class T>
void DCLinkedList<T>::Reset(bool bheader)
{
	if (bheader) 
		currPtr = header->NextNodeRight();	// 表頭
	else
		currPtr = header->NextNodeLeft();	// 表尾
}

template <class T>
void DCLinkedList<T>::Next(void)
{
	currPtr = currPtr->NextNodeRight();
}

template <class T>
void DCLinkedList<T>::Prev(void)
{
	currPtr = currPtr->NextNodeLeft();
}

template <class T>
bool DCLinkedList<T>::EndOfList(void) const
{
	return (currPtr == header);
}

// 插入函數
template <class T>
void DCLinkedList<T>::InsertFront(const T &item)
{
	Reset();
	InsertAt(item);
}

template <class T>
void DCLinkedList<T>::InsertRear(const T &item)
{
	currPtr = header;
	InsertAt(item);
}

template <class T>
void DCLinkedList<T>::InsertAt(const T &item)
{
	DNode<T> *newNode = new DNode<T>(item);
	currPtr->InsertLeft(newNode);
	currPtr = newNode;
	size++;
}

template <class T>
void DCLinkedList<T>::InsertAfter(const T &item)
{
	Next();
	InsertAt(item);
}

// 刪除函數
template <class T>
void DCLinkedList<T>::DeleteFront(void)
{
	Reset();
	DeleteAt();
}

template <class T>
void DCLinkedList<T>::DeleteRear(void)
{
	Reset(false);
	DeleteAt();
}

template <class T>
void DCLinkedList<T>::DeleteAt(void)
{
	// 若表為空或已到表尾，則返回
	if (currPtr == header)
		return;

	DNode<T> *p = currPtr->NextNodeRight();
	delete (currPtr->DeleteNode());
	currPtr = p;
	size --;
}

// 訪問／修改數據
template <class T>
T& DCLinkedList<T>::Data(void)
{
	// 若表為空或已到表尾，則出錯
	if (currPtr == header)
		throw "DCLinkedList::Data: invalid reference";

	return currPtr->data;
}

template <class T>
bool DCLinkedList<T>::Find(const T& item)
{
	for (Reset(); !EndOfList(); Next())
		if (Data() == item)
			return true;

	return false;
}

template <class T>
DCLinkedList<T>& DCLinkedList<T>::operator= (const DCLinkedList<T>& L)
{
	if (this == &L)      // 無法賦值給自身
		return *this;
	
	ClearList();
	CopyList(L);
	return *this;
}

template <class T>
void DCLinkedList<T>::ClearList(void)
{
	Reset();
	while (currPtr != header)
		DeleteAt();
}

#endif	// DOUBLE_CIRCULAR_LINKEDLIST_CLASS