/*****************************
*         _DList_h_          *
*      Double Link List      *
*       class template       *
*       create by si.si      *
*          2007.9.19         *
******************************/

#ifndef _DList_h_
#define _DList_h_

//name space sisi's data structure
namespace SSDataS
{
/*
*List node class template 
*  of double link list
*/
#define NULL  0
	template<class T>
	class DListNode
	{
		
		//constructor and destructor
	public:
		~DListNode();
	private:
		/*
		*func constructor
		*the constructor of the node of this double link list
		*/
		DListNode( T newItem , DListNode<T>* prevpoint  = NULL, DListNode<T>* nextpoint = NULL);
		DListNode();


	public:
		/*
		*func getNewNode : DListNode<T>*  static
		*create a new node
		*@param newItem:T  the new data to store in this node
		*@param prevpoint:DListNode<T>* the pointer to prev node
		*@param nextpoint:DListNode<T>* the pointer to next node
		*@return a pointer to a new node
		*/
		static DListNode<T>* getNewNode(const T newItem , DListNode<T>* prevpoint  = NULL, DListNode<T>* nextpoint = NULL);

		//the data in node
		T item;
		//the pointer to next node
		DListNode<T>* next;
		//the pointer to prev node
		DListNode<T>* prev;
	};

/*
*Double link list class template
*/
	template<class T>
	class DList
	{
	public:
	//constructor and destructor
		DList();
		~DList();

	//fence pointer operate function
		/*
		*func getPresentData : T const
		*get the data of the node whitch fence pointer point to
		*@return : T item's data
		*/
		T getPresentData() const;
		
		/*
		*func getHeadData : T const
		*get the data in the head node
		*@return : T item's data
		*/
		T getHeadData() const;

		/*
		*func getTailData : T const
		*get the data in the tail node
		*@return : T item's data
		*/
		T getTailData() const;
		
		/*
		*func moveToHead : void 
		*move the fence pointer to the head of this list
		*/
		void moveToHead();

		/*
		*func moveToTail : void
		*move the fence pointer to the tail of this list
		*/
		void moveToTail();

		/*
		*func moveToNext : void
		*move the fence pointer to next node
		*/
		void moveToNext();

		/*
		*func moveToPrev : void
		*move the fence pointer to the prev node
		*/
		void moveToPrev();

	//insert and remove operate function
		/*
		*func insert : bool
		*insert new item to this list
		*@param newItem : T  the new item
		*@return : bool return true if success , else false
		*/
		bool insert(const T newItem);

		/*
		*func insertAtHead : bool
		*insert new item to the head of this list
		*@param newItem : T the new item
		*@return : bool return true if success , else false
		*/
		bool insertAtHead(const T newItem);

		/*
		*func insertAtTail : bool
		*insert new item to the tail of this list
		*@param newItem : T the new item
		*@return : bool return true if success , else false
		*/
		bool insertAtTail(const T newItem);

		/*
		*func removeFromHead : bool
		*remove the head node and set the next head
		*Return the item value in param reference
		*@param item : T reference to return the item value
		*@return : bool return true if success , else false
		*/
		bool removeFromHead(T& item);

		/*
		*func removeFromTail : bool
		*remove the tail node and set the prev tail.
		*Return the item value in param reference
		*@param item : T& reference to return the item value
		*@return : bool return true if success , else false
		*/
		bool removeFromTail(T& item);

		/*
		*func remove : bool
		*remove the node that the fence point to,and 
		*move the fence to next.
		*@return : bool return true if success , else false
		*/
		bool remove();

		/*
		*func remove : bool
		*remove the node that hold the data of aim item
		*@param aimItem : T the aim item
		*@return : bool return true if success , else false
		*/
		bool remove( const T aimItem );

		/*
		*func removeAll : bool
		*remove all node that in this list
		*@return : bool return true if success ,else false
		*/
		bool removeAll();

	//help function
		/*
		*func isEmpty : bool
		*get the EMPTY inf. of this list
		*@return : bool return true if empty
		*/
		bool isEmpty();

		/*
		*func find : bool
		*try to find the aim item in list, if find , set fence ptr to that node
		*@param aimItem : T the aim item
		*@return : bool return true if find ,else false
		*/
		bool find(const T aimItem);

	//inf get function
		/*
		*func getLength : int
		*get the length of this list
		*@return : int the length value
		*/
		int getLength() const;

		/*
		*func toItemArray : T[]
		*get a array that hold the all data in this list
		*@return : T[] 
		*/
		T* toItemArray(int& len);

	private:
		//the length of this list
		int length;
		//the head pointer;
		DListNode<T>* head;
		//the tail pointer;
		DListNode<T>* tail;
		//the fence pointer;
		DListNode<T>* fence;


	};
};



using namespace SSDataS;


template<class T>
DListNode<T>::DListNode(T newItem, SSDataS::DListNode<T> *prevpoint , SSDataS::DListNode<T> *nextpoint )
{
	item = newItem;
	next = nextpoint;
	prev = prevpoint;
}

template<class T>
DListNode<T>::DListNode()
{
	item = 0;
	next = NULL;
	prev = NULL;
}

template<class T>
DListNode<T>::~DListNode()
{
}

template<class T>
DListNode<T>* DListNode<T>::getNewNode(const T newItem, SSDataS::DListNode<T> *prevpoint , SSDataS::DListNode<T> *nextpoint )
{
	DListNode<T>* newNode = new DListNode<T>( newItem , prevpoint , nextpoint );
	return newNode;
}

template<class T>
DList<T>::DList()
{
	length = 0;
	head = NULL;
	tail = NULL;
	fence = NULL;
}

template<class T>
DList<T>::~DList()
{
}

template<class T>
T DList<T>::getPresentData() const
{
	if(NULL != fence)
		return fence->item;
	else
		return NULL;
}

template<class T>
T DList<T>::getHeadData() const
{
	if(NULL != head)
		return head->item;
	else 
		return NULL;
}

template<class T>
T DList<T>::getTailData() const
{
	if(NULL != tail)
		return tail->item;
	else
		return NULL;
}



template<class T>
void DList<T>::moveToHead()
{
	fence = head;
}

template<class T>
void DList<T>::moveToTail()
{
	fence = tail;
}

template<class T>
void DList<T>::moveToPrev()
{
	fence = fence->prev;
}

template<class T>
void DList<T>::moveToNext()
{
	fence = fence->next;
}

template<class T>
bool DList<T>::insert(const T newItem)
{
	if(isEmpty())
	{
		DListNode<T>* newNode = DListNode<T>::getNewNode(newItem , NULL , NULL);
		fence = head = tail = newNode;
		length++;
	}
	else if( fence == tail)
	{
		insertAtTail(newItem);
	}
	else
	{
		DListNode<T>* newNode = DListNode<T>::getNewNode(newItem , fence , fence->next);
		fence->next->prev = newNode;
		fence->next = newNode;
		length++;
	}
	return true;
}

template<class T>
bool DList<T>::insertAtHead( const T newItem )
{
	if(isEmpty())
	{
		DListNode<T>* newNode = DListNode<T>::getNewNode(newItem , NULL , NULL);
		fence = head = tail = newNode;
		length++;
	}
	else
	{
		DListNode<T>* newNode = DListNode<T>::getNewNode(newItem , NULL , head);
		head->prev = newNode;
		head = newNode;
		length++;
	}
	return true;
}

template<class T>
bool DList<T>::insertAtTail(const T newItem)
{
	if(isEmpty())
	{
		DListNode<T>* newNode = DListNode<T>::getNewNode(newItem , NULL , NULL);
		fence = head = tail = newNode;
		length++;
	}
	else
	{
		DListNode<T>* newNode = DListNode<T>::getNewNode(newItem , tail , NULL);
		tail->next = newNode;
		tail = newNode;
		length++;
	}
	return true;
}

template<class T>
bool DList<T>::remove()
{
	if(isEmpty())
		return false;
	DListNode<T>* temp = NULL;
	if(fence == head)
	{
		return removeFromHead(0);
	}
	else if(fence == tail)
	{
		return removeFromTail(0);
	}
	else
	{
		temp = fence;
		fence = fence->next;
		fence->prev = temp->prev;
		temp->prev->next = fence;
		delete temp;
		length--;
		return true;
	}	
}

template<class T>
bool DList<T>::remove(const T aimItem)
{
	if(fence->item == aimItem)
	{
		return remove();
	}
	if(!find(aimItem))
	{
		return false;
	}
	else
	{
		return remove();
	}
}

template<class T>
bool DList<T>::removeFromHead(T &item)
{
	DListNode<T>* temp = NULL;
	if(isEmpty())
		return false;
	if(head == tail)
	{
		temp = head;
		head = NULL;
		tail = NULL;
		fence = NULL;
		item = temp->item;
		delete temp;
		length--;
		return true;
	}
	else if( fence == head)
	{
		temp = head;
		head = head->next;
		fence = head;
		//fence->prev = NULL;
		item = temp->item;
		delete temp;
		length--;
		return true;
	}
	else
	{
		temp = head;
		head = head->next;
		head->prev = NULL;
		item = temp->item;
		delete temp;
		length--;
		return true;
	}

}

template<class T>
bool DList<T>::removeFromTail(T &item)
{
	DListNode<T>* temp = NULL;
	if(isEmpty())
		return false;
	if(head == tail)
	{
		temp = head;
		head = NULL;
		tail = NULL;
		fence = NULL;
		item = temp->item;
		delete temp;
		length--;
		return true;
	}
	else if( fence == tail)
	{
		temp = tail;
		tail = tail->prev;
		fence = tail;
		tail->next = NULL;
		item = temp->item;
		delete temp;
		length--;
		return true;
	}
	else
	{
		temp = tail;
		tail = tail->prev;
		tail->next = NULL;
		item = temp->item;
		delete temp;
		length--;
		return true;
	}
}

template<class T>
bool DList<T>::removeAll()
{
	if(isEmpty())
		return false;
	DListNode<T>* temp;
	fence = head;
	head = NULL;
	while( fence != tail )
	{
		temp = fence;
		fence = fence->next;
		delete temp;
	}
	fence = NULL;
	temp = tail;
	tail = NULL;
	delete temp;
	length =0;
	return true;
}

template<class T>
bool DList<T>::find(const T aimItem)
{
	if(isEmpty())
		return false;
	if(fence->item == aimItem)
		return true;
	fence = head;
	while(fence->item != aimItem)
	{
		if(fence == tail)
			return false;
		fence = fence->next;
	}
	return true;
}

template<class T>
bool DList<T>::isEmpty()
{
	if(length == 0)
		return true;
	else 
		return false;
}

template<class T>
int DList<T>::getLength() const
{
	return length;
}

template<class T>
T* DList<T>::toItemArray(int &len)
{
	if(isEmpty())
		return NULL;
	int i = 0;
	T* ItemArray = NULL;
	DListNode<T>* temp = fence;
	fence = head;
	ItemArray = new T[length];
	len = length;
	while(i < length)
	{
		ItemArray[i] = fence->item;
		fence = fence->next;
	}
	fence = temp;
	return ItemArray;
}

#endif