//-------------------------------------------------------------------------------------------------------+
// Copyright (C), 1998-2007, SH Software Co. Ltd.
// = FileName	:   PDList 模板类
// = Version	:   ver2.0
// = Author		:   zjq
// = CreateDate	:   2002-09-09
// = Description:   PDList 声明 双向指针链表，内存外部分配，自动释放，也提供外部释放接口。支持空指针。
//				适用于大型数据对象，随机访问较少，空间动态分配经常发生的情况。
// = Maintainers: 
//                  
//-------------------------------------------------------------------------------------------------------+
#ifndef _PDLIST_H_
#define _PDLIST_H_

#ifndef _DUALLIST_H_
#include "DualList.h"
#endif

template<class T>class PDList:public DualList<T*>
{
public:
	PDList(long size = 0);
	virtual ~PDList();

	virtual void DelCur();
	virtual void Clear();

	//索引以未移动时为准
	virtual bool Move(long from,long to);
	
	//稳定插入排序,空数据将排列在最后
	virtual void Arrange(bool bIncrease = true);
	
	//稳定插入排序
	virtual void Arrange(int (*cmp)(const T&,const T&));

	//attribute
	bool operator == (const PDList<T>&list) const;
	bool operator != (const PDList<T>&list) const;

	//返回已经分配空间、实际存在的数据数目， <= this->GetLength().
	long   GetDataNum() const;
	
	bool IsCurEmpty() const;
	bool IsEmptyData(long index) const;

	//direct data access
	T &GetCurPData();
	const T& GetPData(long i) const;
	T &operator()(long index);
	
	//fetch
	//取走数据，并删除结点
	T* FetchCur();
	T* Fetch(long i);
	T* FetchFirst();
	T* FetchLast();

	//release
	//仅释放数据空间，不删除指针空间,不改变链表长度，不移动cur;
	void ReleaseCur();
	void Release(long i);
	void ReleaseAll();

	long    FillIn(T*t);

	//search
	//仅仅为了速度而替换Table<T>
	long FindAndDel(T*t);
	
	//没发现，加到最后，并返回index;
	long FindDataOrAddTail(const T&t);
	
	//没发现插入Head
    void FindDataOrInsertHead(const T&t);
	long FindDataAndDel(const T&t);
	long FindData(const T&t,long from = 0,long to = -1) const;
	long FindData(const T&t,Quene<long>&quene,long from = 0,long to = -1) const;

	//sort
	//二分查找,适用于升序表
	long BFindData(const T&t,long from = 0,long to = -1) const;
	
	//二分查找,并移动游标,适用于升序表
	bool BFindDataTo(const T&t,long from = 0,long to = -1);
	
	//构造升序表,如返回false,外部释放p
	bool SortIn(T*p,bool bAllowDup = false);

protected:
	virtual void Realloc(long newLength);

};


template<class T>
bool PDList<T>::operator != (const PDList<T>&list) const
{
	return !((*this) == list);
}

template<class T>
bool PDList<T>::IsCurEmpty() const
{
	return this->IsOut() ? true : this->curPos->data == NULL;
}

template<class T>
T& PDList<T>::GetCurPData()
{
	return *this->GetCurData();
}

template<class T>
const T& PDList<T>::GetPData(long i) const
{
	return *this->GetAt(i);
}

template<class T>
T& PDList<T>::operator()(long index)
{
	return *((*this)[index]);
}

template<class T>
void PDList<T>::Release(long i)
{
	this->MoveTo(i);
	ReleaseCur();
}

template<class T>
T* PDList<T>::Fetch(long i)
{
	this->MoveTo(i);
	return FetchCur();
}

template<class T>
T* PDList<T>::FetchFirst()
{
	this->MoveToFirst();
	return FetchCur();
}

template<class T>
T* PDList<T>::FetchLast()
{
	this->MoveToLast();
	return FetchCur();
}

template<class T>
long PDList<T>::BFindData(const T&t,long from,long to) const
{
	if (to < 0 || to >= this->GetLength())
	{
		to = this->GetLastIndex();
	}
	
	if (from > to)
	{
		return NOT_FOUND;
	}

	if (t < GetPData(from))
	{
		return NOT_FOUND;
	}
	if (t > GetPData(to))
	{
		return NOT_FOUND;
	}

	while(from <= to)
	{
		long mid = (from+to)/2;
		const T& tCur = GetPData(mid);
		if (t > tCur)
		{
			from = mid+1;
		}
		else if (t < tCur)
		{
			to = mid-1;
		}
		else 
		{
			return mid;
		}
	}
	return NOT_FOUND;
}

template<class T>
bool PDList<T>::BFindDataTo(const T&t,long from,long to)
{
	if (to < 0 || to >= this->GetLength())
	{
		to = this->GetLastIndex();
	}

	if (this->IsEmpty())
	{
		this->MoveTo(0);
		return false;
	}
	
	this->MoveTo(from);
	if (t < GetCurPData())
	{
		return false;
	}

	this->MoveTo(to);
	if (t > GetCurPData())
	{
		this->MoveToNext();
		return false;
	}
	
	while(from < to)
	{
		long mid = (from+to)/2;
		this->MoveTo(mid);
		const T& tCur = GetCurPData();
		if (t > tCur)
		{
			from = mid+1;
		}
		else if (t < tCur)
		{
			to = mid-1;
		}
		else 
		{
			return true;
		}
	}
	if (from == to)
	{
		this->MoveTo(from);
		const T& tCur = GetCurPData();
		if (t > tCur)
		{
			this->MoveToNext();
		}
		else if (!(t < tCur))
		{
			return true;
		}
		return false;
	}
	return false;
}

template<class T>
bool PDList<T>::SortIn(T*p,bool bAllowDup)
{
	if (BFindDataTo(*p))
	{
		if (!bAllowDup)
		{
			return false;
		}

		//需要找最后一个
		this->MoveToNext();
		while(!this->IsOut() && GetCurPData() == *p)
		{
			this->MoveToNext();
		}
	}
	this->InsertCur(p);
	return true;
}

template<class T>
void PDList<T>::Clear()
{
	this->tail->next = NULL;
	DListNode<T*>*p = (DListNode<T*>*)(this->head->next);
	while(p != NULL)
	{
		DListNode<T*> *pn = (DListNode<T*>*)(p->next);
		if (p->data != NULL)
		{
			delete p->data;
		}
		delete p;
		p = pn;
	}
	this->curPos = this->tail = this->head->next = this->head;
	((DListNode<T*>*)this->head)->pre = this->head;
	this->length = 0;
	this->cur = -1;
}

template<class T>
PDList<T>::PDList(long size)
{
	//作为遍历结束条件
	this->head->data = NULL;
	
	if (size > 0)
	{//未用基类的构造函数来调用Realloc(size)!!!，因为那时子类还未创建
		Realloc(size);
	}
}

template<class T>
long PDList<T>::FindAndDel(T*t)
{
	for (this->MoveToFirst();!this->IsOut();this->MoveToNext())
	{
		if (this->GetCurData() == t)
		{
			DelCur();
			return 1;
		}
	}
	return 0;
}

template<class T>
long PDList<T>::FillIn(T*t)
{
	for (this->MoveToFirst();!IsCurEmpty();this->MoveToNext());
	if (this->IsOut())
	{
		this->AddTail(t);
	}
	else
	{
		this->SetCurData(t);
	}
	return this->GetCur();
}

template<class T>
void PDList<T>::ReleaseAll()
{
	for (this->MoveToFirst();!this->IsOut();this->MoveToNext())
	{
		ReleaseCur();
	}
}

template<class T>
bool PDList<T>::operator  == (const PDList<T>&list) const
{
	if (list.GetLength() != this->GetLength())
	{
		return false;
	}

	T* const*pCur0,*const*pCur1;
	for (pCur0 = this->GetFirst(),pCur1 = list.GetFirst();pCur0 != NULL;
	     pCur0 = this->GetNext(pCur0), pCur1 = list.GetNext(pCur1))
	{
		if (*pCur0 != NULL && *pCur1 != NULL && **pCur0 != **pCur1)
		{
			return false;
		}
		else if (!(*pCur0 == NULL && *pCur1 == NULL))
		{
			return false;
		}
	}
	return true;
}

template<class T>
T* PDList<T>::FetchCur()
{
	if (this->IsOut())
	{
		return NULL;
	}
	T* p = this->GetCurData();
	this->SetCurData(NULL);
	DelCur();
	return p;
}

template<class T>
void PDList<T>::Realloc(long newLength)
{
	if (newLength>this->GetLength())
	{
		long oldCur = this->cur; 
		ListNode<T*>*oldPos = this->curPos;
		while(this->GetLength()<newLength)	
		{
			this->AddTail(NULL);
		}
		this->curPos = oldPos;
		this->cur = oldCur;
	}
}

template<class T>
PDList<T>::~PDList()
{
	if (this->head == NULL)
	{
		return;
	}
	ReleaseAll();
}

template<class T>
long PDList<T>::GetDataNum() const
{
	long count = 0;
	T* const*pCur = this->GetFirst();
	for (long i = 0;i<this->GetLength();i++,pCur = this->GetNext(pCur))
	{
		if (*pCur != NULL)
		{
			count++;
		}
	}
	return count;
}

template<class T>
bool PDList<T>::IsEmptyData(long index) const
{
	return this->IsValidIndex(index)?this->GetAt(index) == NULL:true;
}

template<class T>
void PDList<T>::ReleaseCur()
{
	if (IsCurEmpty())
	{
		return;
	}
	delete this->GetCurData();
	this->SetCurData(NULL);
}

template<class T>
void PDList<T>::DelCur()
{
	if (this->GetCurData() != NULL)
	{
		delete this->GetCurData();
	}
	DualList<T*>::DelCur();
}

template<class T>
long PDList<T>::FindDataOrAddTail(const T&t)
{
	long pos = FindData(t,0,this->GetLastIndex());
	if (pos == NOT_FOUND)
	{
		T*p = new T;
		*p = t;
		return this->AddTail(p);
	}
	else
	{
		return pos;
	}
}

template<class T>
void PDList<T>::FindDataOrInsertHead(const T&t)
{
	long pos = FindData(t,0,this->GetLastIndex());
	if (pos == NOT_FOUND)
	{
		T*p = new T;
		*p = t;
		this->InsertHead(p);
	}
}	

template<class T>
long PDList<T>::FindDataAndDel(const T&t)
{
	long count = 0;
	for (this->MoveToFirst();!this->IsOut();this->MoveToNext())
	{
		if (this->GetCurData() != NULL && *(this->GetCurData()) == t)
		{
			DelCur();
			count++;
		}
	}
	return count;
}

template<class T>
long PDList<T>::FindData(const T&t,long from,long to) const
{
	if (to < 0 || to >= this->GetLength())
	{
		to = this->GetLastIndex();
	}

	T* const* pCur = NULL;
	long i;
	for (pCur = this->GetTo(from),i = from;i <= to;pCur = this->GetNext(pCur),i++)
	{
		if (*pCur != NULL && **pCur == t)
		{
			return i;
		}
	}
	return NOT_FOUND;
}

template<class T>
long PDList<T>::FindData(const T&t,Quene<long>&quene,long from,long to) const
{
	if (to < 0 || to >= this->GetLength())
	{
		to = this->GetLastIndex();
	}

	T*const* pCur = NULL;
	long i;
	for (pCur = this->GetTo(from),i = from;i <= to;pCur = this->GetNext(pCur),i++)
	{
		if (*pCur != NULL && **pCur == t)
		{
			return quene.EnQuene(i);
		}
	}
	return quene.GetLength();
}

template<class T>
bool PDList<T>::Move(long from,long to)
{
	if (from == to || from == to-1)
	{
		return false;
	}

	this->MoveTo(from);
	T* t = this->GetCurData();
	this->SetCurData(NULL);
	this->Insert(to,t);
	if (from > to)
	{
		this->Del(from+1);//from数据已经后移
		this->MoveTo(to);//to是最终位置
	}
	else
	{
		this->Del(from);
		this->MoveTo(to-1);//to-1是最终位置
	}
	return true;
}

template<class T>
void PDList<T>::Arrange(bool bIncrease)
{
	if (this->GetLength() < 2)
	{
		return;
	}
	long nullCount = 0;
	if (bIncrease)
	{
		this->MoveToFirst();
		while(IsCurEmpty())
		{
			this->DelFirst();
			nullCount++;
			this->MoveToFirst();
		}
		this->MoveToNext();
		while(!this->IsBegin())
		{
			if (!IsCurEmpty())
			{
				T *temp = this->GetCurData();
				long i = this->GetCur();
				ListNode<T*>*pos = this->GetCurPos();
				this->MoveToPre();
				if (*this->GetCurData() > *temp)
				{
					while(!this->IsBegin() && *this->GetCurData() > *temp)
					{
						this->MoveToPre();
					}
					this->InsertAfterCur(temp);
					this->curPos = pos;
					this->cur = i+1;
					this->SetCurData(NULL);
					DelCur();
				}
				else
				{
					this->MoveToNext();
				}
			}
			else
			{
				DelCur();
				nullCount++;
			}
			this->MoveToNext();
		}
	}
	else
	{
		this->MoveToFirst();
		while(IsCurEmpty())
		{
			this->DelFirst();
			nullCount++;
			this->MoveToFirst();
		}
		this->MoveToNext();
		while(!this->IsBegin())
		{
			if (!IsCurEmpty())
			{
				T *temp = this->GetCurData();
				long i = this->GetCur();
				ListNode<T*>*pos = this->GetCurPos();
				this->MoveToPre();
				if (*this->GetCurData() < *temp)
				{
					while(!this->IsBegin() && *this->GetCurData() < *temp)
					{
						this->MoveToPre();
					}
					this->InsertAfterCur(temp);
					this->curPos = pos;
					this->cur = i+1;
					this->SetCurData(NULL);
					DelCur();
				}
				else
				{
					this->MoveToNext();
				}
			}
			else
			{
				DelCur();
				nullCount++;
			}
			this->MoveToNext();
		}
	}
	while(nullCount-- != NULL)
	{
		this->AddTail(NULL);
	}
}

template<class T>
void PDList<T>::Arrange(int (*cmp)(const T&,const T&))
{
	if (this->GetLength() < 2)
	{
		return;
	}

	this->MoveToFirst();
	this->MoveToNext();
	while(!this->IsBegin())
	{
		T *temp = this->GetCurData();
		long i = this->GetCur();
		ListNode<T*>*pos = this->GetCurPos();
		this->MoveToPre();
		if (cmp(*this->GetCurData(),*temp) > 0)
		{
			while(!this->IsBegin() && cmp(*this->GetCurData(),*temp) > 0)
			{
				this->MoveToPre();
			}
			this->InsertAfterCur(temp);
			this->curPos = pos;
			this->cur = i+1;
			this->SetCurData(NULL);
			DelCur();
		}
		else
		{
			this->MoveToNext();
		}

		this->MoveToNext();
	}
}


#endif