//-------------------------------------------------------------------------------------------------------+
// Copyright (C), 1998-2007, SH Software Co. Ltd.
//  =  FileName	:   SPTable 模板类
//  =  Version	:   ver2.0
//  =  Author		:   zjq
//  =  CreateDate	:   2002-09-09
//  =  Description:   SPTable 声明 动态指针数据，外部分配内存，内部释放，也可外部释放，支持空数据
//					适用于大型数据类，用于减小动态分配空间和数据复制开销,同时保持较高的数据访问速度。
//  =  Maintainers: 
//                  
//-------------------------------------------------------------------------------------------------------+

#ifndef _SPTABLE_H_
#define _SPTABLE_H_

#ifndef _SQTABLE_H_
#include "SqTable.h"
#endif

template<class T>class SPTable : public SqTable<T*>
{
public:
	SPTable(long size = 0,long unit = 10);

	virtual ~SPTable();

	virtual void Realloc(long newLength);
	
	//bCopy = false 将释放所有数据空间!
	virtual void SetLength(long newLength,bool bCopy = true);
	
	virtual bool Move(long from,long to);

	virtual void DelCur();

	virtual void Clear();

	virtual void ReleaseCur();

	//取走数据，清空指针，但不删除指针表项!
	virtual T* FetchCur();

	//attribute
	long GetDataNum() const;

	bool IsCurEmpty() const;
	
	bool IsEmptyData(long i) const;
	
	bool operator  == (const SPTable<T>&table) const;
	
	bool operator != (const SPTable<T>&table) const;

	T& GetCurPData();
	
	T& operator ()(long i);
	
	const T& GetPData(long i) const;
	
	//在第一个空数据处填入新数据，返回索引,move cur
    long FillIn(T*p);

	void Release(long i);
	
	//释放数据空间，清空所有指针
	void ReleaseAll();

	T* Fetch(long i);

	T* FetchFirst();
	
	T* FetchLast();

	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);
	
	//稳定计数排序, 不支持空数据!但速度快。
	virtual void Arrange(bool bIncrease = true);
	
	//稳定计数排序。
	virtual void Arrange(int (*cmp)(const T&,const T&));
	
	//稳定计数排序,空数据将排列在最后
	void ArrangeEx(bool bIncrease = true);
};

template<class T>
SPTable<T>::SPTable(long size,long unit):SqTable<T*>(size,unit)
{

}

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

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

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

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

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

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

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

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

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

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

template<class T>
long SPTable<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 SPTable<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 SPTable<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>
long SPTable<T>::FindAndDel(T*t)
{
	//只可能有一个t指针
	long i = this->Find(t);
	if (i != NOT_FOUND)
	{
		this->Del(i);
		return 1;
	}
	return 0;
}

template<class T>
long SPTable<T>::FillIn(T*p)
{
	long i(0);
	for (i = 0;!IsEmptyData(i);i++);
	{//可能是末尾增加
		(*this)[i] = p;
	}

	return i;
}

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

	for (long i = 0;i<this->GetLength();i++)
	{
		if (this->GetAt(i) != NULL && table.GetAt(i) != NULL)
		{
			if (!(*(this->GetAt(i)) == *(table.GetAt(i))))
			{
				return false;
			}
		}
		else if (!(this->GetAt(i) == NULL && table.GetAt(i) == NULL))
		{
			return false;
		}
	}
	return true;
}

template<class T>
SPTable<T>::~SPTable()
{
	ReleaseAll();
}

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

template<class T>
void SPTable<T>::Clear()
{
	ReleaseAll();
	SqTable<T*>::Clear();
}

template<class T>
bool SPTable<T>::IsCurEmpty() const
{
	return this->IsOut() ? true : this->GetAt(this->GetCur()) == NULL;
}

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

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

template<class T>
void SPTable<T>::DelCur() 
{
	ReleaseCur();

	long last = this->GetLastIndex();
	if (this->GetCur() < last)
	{//至少两项、且非最后项

		//保存、清零最后项，否则将被SqTable<T*>::DelCur() delete!
		T* pLast = this->pData[last];
		this->pData[last] = NULL;
		SqTable<T*>::DelCur();
		//重新推入最后项
		this->pData[last-1] = pLast;
	}
	else
	{
		SqTable<T*>::DelCur();
	}
}

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

template<class T>
void SPTable<T>::Realloc(long newLength)
{
	if (newLength>this->GetLength())
	{
		long oldLength = this->GetLength();
		SqTable<T*>::Realloc(newLength);
		for (long i = oldLength;i<newLength;i++)
		{
			this->pData[i] = NULL;
		}
	}
	else if (newLength<this->GetLength())
	{
		for (long i = newLength;i<this->GetLength();i++)
		{
			if (this->pData[i] != NULL)
			{
				delete this->pData[i];
			}
		}
		SqTable<T*>::Realloc(newLength);
	}
}

template<class T>
void SPTable<T>::SetLength(long newLength,bool bCopy)
{
	if (bCopy)
	{
		if (newLength>this->GetLength())
		{
			long oldLength = this->GetLength();
			SqTable<T*>::SetLength(newLength,true);
			for (long i = oldLength;i<newLength;i++)
			{
				this->pData[i] = NULL;
			}
		}
		else if (newLength<this->GetLength())
		{
			for (long i = newLength;i<this->GetLength();i++)
			{
				if (this->pData[i] != NULL)
				{
					delete this->pData[i];
				}
			}
			SqTable<T*>::SetLength(newLength,true);
		}	
	}
	else
	{
		ReleaseAll();
		SqTable<T*>::SetLength(newLength,false);
	}
}

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

	this->MoveTo(from);
	T* p = this->GetCurData();
	this->SetCurData(NULL);
	this->Insert(to,p);
	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>
long SPTable<T>::FindData(const T&t,long from,long to) const
{
	if (to < 0 || to >= this->GetLength())
	{
		to = this->GetLastIndex();
	}
	for (long i = from;i <= to;i++)
	{
		if (this->pData[i] != NULL && *(this->pData[i]) == t)
		{
			return i;
		}
	}
	return NOT_FOUND;
}

template<class T>
long SPTable<T>::FindData(const T&t,Quene<long>&quene,long from,long to) const
{
	if (to < 0 || to >= this->GetLength())
	{
		to = this->GetLastIndex();
	}
	for (long i = from;i <= to;i++)
	{
		if (this->pData[i] != NULL && *(this->pData[i]) == t)
		{
			quene.EnQuene(i);
		}
	}
	return quene.GetLength();
}

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

template<class T>
long SPTable<T>::GetDataNum() const
{
	long count = 0;
	for (long i = 0;i<this->GetLength();i++)
	{
		if (this->pData[i] != NULL)
		{
			count++;
		}
	}
	return count;
}

template<class T>
void SPTable<T>::Arrange(bool bIncrease)
{
	if (this->GetLength()<2)
	{
		return;
	}
	long *count = new long[this->GetLength()];
	long i;
	for (i = 0;i<this->GetLength();i++)
	{
		count[i] = i;
	}
	if (bIncrease)
	{
		for (i = 0; i < this->GetLastIndex();i++)
		{
			for (long j = i + 1; j < this->GetLength(); j++)
			{
				if (*(this->pData[i]) > *(this->pData[j]))
				{
					count[i]++;
					count[j]--;
				}
			}
		}
		for (i = 0;i<this->GetLength();i++)
		{
			if (count[i] != i)
			{
				long k,j;
				T *temp1 = this->pData[i],*temp2;
				k = count[i];
				while(k != i)
				{
					temp2 = this->pData[k];
					this->pData[k] = temp1;
					temp1 = temp2;
					j = k;
					k = count[j];
					count[j] = j;
				}
				this->pData[i] = temp1;
				count[i] = i;
			}
		}
	}
	else
	{   
		for (i = 0;i<this->GetLastIndex();i++)
		{
			for (long j = i+1; j < this->GetLength(); j++)
			{
				if (*(this->pData[i]) < *(this->pData[j]))
				{
					count[i]++;
					count[j]--;
				}
			}
		}
		for (i = 0;i<this->GetLength();i++)
		{
			if (count[i] != i)
			{
				long k,j;
				T *temp1 = this->pData[i],*temp2;
				k = count[i];
				while(k != i)
				{
					temp2 = this->pData[k];
					this->pData[k] = temp1;
					temp1 = temp2;
					j = k;
					k = count[j];
					count[j] = j;
				}
				this->pData[i] = temp1;
				count[i] = i;
			}
		}
	}
	delete[] count;
}

template<class T>
void SPTable<T>::Arrange(int (*cmp)(const T&,const T&))
{
	if (this->GetLength() < 2)
	{
		return;
	}
	long *count = new long[this->GetLength()];
	long i;
	for (i = 0;i<this->GetLength();i++)
	{
		count[i] = i;
	}

	for (i = 0;i<this->GetLastIndex();i++)
	{
		for (long j = i+1;j<this->GetLength();j++)
		{
			if (cmp(*(this->pData[i]),*(this->pData[j]))>0)
			{
				count[i]++;
				count[j]--;
			}
		}
	}
	for (i = 0;i<this->GetLength();i++)
	{
		if (count[i] != i)
		{
			long k,j;
			T *temp1 = this->pData[i],*temp2;
			k = count[i];
			while(k != i)
			{
				temp2 = this->pData[k];
				this->pData[k] = temp1;
				temp1 = temp2;
				j = k;
				k = count[j];
				count[j] = j;
			}
			this->pData[i] = temp1;
			count[i] = i;
		}
	}

	delete[] count;
}

template<class T>
void SPTable<T>::ArrangeEx(bool bIncrease)
{
	if (this->GetLength() < 2)
	{
		return;
	}
	long *count = new long[this->GetLength()];
	long i;
	for (i = 0;i<this->GetLength();i++)
	{
		count[i] = i;
	}
	if (bIncrease)
	{
		for (i = 0;i<this->GetLastIndex();i++)
		{
			for (long j = i+1;j<this->GetLength();j++)
			{
				if (this->pData[j] != NULL && (this->pData[i] == NULL || *(this->pData[i]) > *(this->pData[j])))
				{
					count[i]++;
					count[j]--;
				}
			}
		}
		for (i = 0;i<this->GetLength();i++)
		{
			if (count[i] != i)
			{
				long k,j;
				T *temp1 = this->pData[i],*temp2;
				k = count[i];
				while(k != i)
				{
					temp2 = this->pData[k];
					this->pData[k] = temp1;
					temp1 = temp2;
					j = k;
					k = count[j];
					count[j] = j;
				}
				this->pData[i] = temp1;
				count[i] = i;
			}
		}
	}
	else
	{
		for (i = 0;i<this->GetLastIndex();i++)
		{
			for (long j = i+1;j<this->GetLength();j++)
			{
				if (this->pData[j] != NULL && (this->pData[i] == NULL || *(this->pData[i]) < *(this->pData[j])))
				{
					count[i]++;
					count[j]--;
				}
			}
		}
		for (i = 0;i<this->GetLength();i++)
		{
			if (count[i] != i)
			{
				long k,j;
				T *temp1 = this->pData[i],*temp2;
				k = count[i];
				while(k != i)
				{
					temp2 = this->pData[k];
					this->pData[k] = temp1;
					temp1 = temp2;
					j = k;
					k = count[j];
					count[j] = j;
				}
				this->pData[i] = temp1;
				count[i] = i;
			}
		}
	}
	delete[] count;
}

#endif