//-----------------------------------------------------------------------------+
// Copyright (C), 1998-2007, SH Software Co. Ltd.
// = FileName	:   XPDList 模板类
// = Version	:   ver2.0
// = Author		:   zjq
// = CreateDate	:   2002-09-09
// = Description:   XPDList 声明
// = Maintainers: 
//                  
//-----------------------------------------------------------------------------+
#ifndef _XPDList_H_
#define _XPDList_H_

#ifndef _XDualList_H_
#include "XDualList.h"
#endif

#ifndef _QUENE_H_
#include "Quene.h"
#endif

//双向指针链表，内存外部分配，自动释放，也提供外部释放接口。支持空指针。
//适用于大型数据对象，随机访问较少，空间动态分配经常发生的情况。
template<class T>class XPDList : public XDualList<T*>
{
public:
	XPDList(long size = 0,long groupMax = 25,long allocSize = 100);

	virtual ~XPDList();

	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&));

	bool operator == (const XPDList<T>&list)const;
	bool operator != (const XPDList<T>&list)const;

	//返回已经分配空间、实际存在的数据数目，＜＝GetLength().
	long GetDataNum()const;

	bool IsCurEmpty()const;
	bool IsEmptyData(long index)const;

	//直接数据访问
	//非空数据
	T &GetCurPData();					
	
	//非空数据
	const T& GetPData(long i)const;	
	
	//非空数据
	T &operator()(long index);		
	
	//取走数据，并删除结点
	T* FetchCur();						
	T* Fetch(long i);
	T* FetchFirst();
	T* FetchLast();

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

	long FillIn(T*t);

	//search
	long FindAndDel(T*t);
	//找不到，添加并返回索引值
	long FindDataOrAddTail(const T&t);
 	//找不到，插到表头
	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;

	//二分查找,适用于升序表
	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);
	void SetAll(const T*p);//禁止操作
};


//二分查找
template<class T>
long XPDList<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 XPDList<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 XPDList<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 XPDList<T>::Clear()
{
	this->group.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>
XPDList<T>::XPDList(long size, long groupMax, long allocSize)
	: XDualList<T*>(0,groupMax,allocSize)
{
	this->head->data = NULL;//作为遍历结束条件
	
	if (size > 0)
	{
		Realloc(size);//未用基类的构造函数来调用Realloc(size)!!!，因为那时子类还未创建
	}
}

template<class T>
long XPDList<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 XPDList<T>::ReleaseAll()
{
	for (this->MoveToFirst(); !this->IsOut(); this->MoveToNext())
	{
		ReleaseCur();
	}
}

template<class T>
bool XPDList<T>::operator ==(const XPDList<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>
void XPDList<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>
XPDList<T>::~XPDList()
{
	if (this->head == NULL)
	{
		return;
	}

	ReleaseAll();
}

template<class T>
long XPDList<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>
void XPDList<T>::DelCur()
{
	if (this->GetCurData() != NULL)
	{
		delete this->GetCurData();
	}

	XDualList<T*>::DelCur();
}
	
template<class T>
long XPDList<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 XPDList<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 XPDList<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 XPDList<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 XPDList<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 XPDList<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();
	}
}

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

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

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

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

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

template<class T>
T* XPDList<T>::Fetch(long i)
{
	this->MoveTo(i);

	return FetchCur();
}

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

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

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

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

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

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

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

template<class T>
long XPDList<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 XPDList<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);
	}
}


#endif