//-------------------------------------------------------------------------------------------------------+
// Copyright (C), 1998-2007, SH Software Co. Ltd.
// = FileName	:   Table 模板类
// = Version	:   ver2.0
// = Author		:   zjq
// = CreateDate	:   2002-09-09
// = Description:   Table 声明支持游标和空间自动增长的高级顺序表抽象类
// = Maintainers: 
//                  
//-------------------------------------------------------------------------------------------------------+
#ifndef _TABLE_H_
#define _TABLE_H_

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

#include "XPrivateGlobalFunc.h"

template <class T> class Array;

template<class T> class Table
{
public:

	Table();

	virtual ~Table(); 

	//alloc memory
	virtual void SetLength(long newLength,bool bCopy = true) = 0;
	
	//visit by cur
	virtual T& GetCurData() = 0;
	
	virtual void SetCurData(const T&t) = 0;
	
	virtual void MoveTo(long index);
	
	virtual void MoveToFirst();
	
	virtual void MoveToLast();
	
	virtual void MoveToNext();
	
	virtual void MoveToPre();
	
	//random visit
	virtual T& operator[](long index);

	//const visit
	virtual const T& GetAt(long index) const = 0;
	
	virtual const T* GetFirst() const = 0;
	
	virtual const T* GetLast() const = 0;
	
	virtual const T* GetNext(const T*p) const = 0;
	
	virtual const T* GetPre(const T*p) const = 0;
	
	//insert/delete
	//cur可以是length,用以在末尾插入!
	virtual void InsertCur(const T&t) = 0;
	
	//index可以是length,用以在末尾插入!
	virtual void Insert(long index,const T&t);
	
	virtual void InsertHead(const T&t);
	
	virtual long AddTail(const T&t);
	
	virtual void DelCur() = 0;
    
	virtual void Clear();
	
	//索引参数以未移动时为准!无法移动时返加false,移动游标到目标位置
	virtual bool Move(long from,long to);
	
	virtual void Arrange(bool bIncrease = true) = 0;
	
	virtual void Arrange(int (*cmp)(const T&,const T&)) = 0;

	void DeepCopy(const Table<T> &table);
	
	void DeepCopy(const Array<T> &array);
   
	void Increase(long num);

	void Decrease(long num);
	
	void Del(long index);
	
	void DelFirst();
	
	void DelTail();
	
	bool IsOut() const;
	
	bool IsBegin() const;
	
	bool IsEnd() const;
	
	long GetCur() const;

	//attribute
	bool IsValidIndex(long index) const;
	
	bool IsEmpty() const;
	
	long GetLength() const;
	
	long GetLastIndex() const;
	
	bool operator == (const Table<T>&table) const;
	
	bool operator != (const Table<T>&table) const;
	
	Table<T>& operator<<(const T&t);
	
	Table<T>& operator<<(const Table<T>&table);
	
	Table<T>& operator<<(const Array<T>&array);

  	const T* GetTo(long i) const;

	//search
	bool FindTo(const T&t,long from = 0);
	
	long Find(const T &t,long from = 0,long to = -1) const;
	
	long FindOrAddTail(const T&t);
    
	void FindOrInsertHead(const T&t);
	
	long FindAndDel(const T&t);
	
	long Find(const T &t,Quene<long>&quene,long from = 0,long to = -1) const;

	//sort
	//二分查找,适用于升序表
	long BFind(const T&t,long from = 0,long to = -1) const;
	
	//二分查找,游标将移动到新插入处,适用于升序表
	bool BFindTo(const T&t,long from = 0,long to = -1);
	
	//如已有相同数据，是否需要增加;如果bAllowDup == false可能返回fals
	bool SortIn(const T&t,bool bAllowDup = false);

	//operator
	void SetAll(const T&t);
	
	void Exchange(long i,long j);
	
	void Reverse(long from = 0,long to = -1);
	
	void Left(long count,Table<T>&table) const;
	
	void Right(long count,Table<T>&table) const;
	
	void Mid(long from,long to,Table<T>&table) const;

protected:

	virtual void Realloc(long newLength) = 0;

protected:

	//当前index
	long cur;

	long length;
};

template<class T>
Table<T>::Table():length(0),cur(-1)
{

}

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

template<class T>
void Table<T>::Increase(long num)
{
	Realloc(length+num);
}

template<class T>
void Table<T>::Decrease(long num)
{
	Realloc(length-num);
}

template<class T>
bool Table<T>::IsValidIndex(long index) const
{
	return index >= 0 && index<length;
}

template<class T>
bool Table<T>::IsEmpty() const
{
	return length == 0;
}

template<class T>
long Table<T>::GetLength() const
{
	return length;
}

template<class T>
long Table<T>::GetLastIndex() const
{
	return length-1;
}

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

template<class T>
void Table<T>::MoveTo(long index)
{
	cur = index;
}

template<class T>
void Table<T>::MoveToFirst()
{
	cur = 0;
}

template<class T>
void Table<T>::MoveToLast()
{
	cur = length-1;
}

template<class T>
void Table<T>::MoveToNext()
{
	cur++;
}

template<class T>
void Table<T>::MoveToPre()
{
	cur--;
}

template<class T>
void Table<T>::Insert(long index,const T&t)
{
	MoveTo(index);
	InsertCur(t);
}

template<class T>
void Table<T>::InsertHead(const T&t)
{
	MoveToFirst();
	InsertCur(t);
}

template<class T>
long Table<T>::AddTail(const T&t)
{
	MoveTo(length);
	InsertCur(t);
	return cur;
}

template<class T>
void Table<T>::Del(long index)
{
	MoveTo(index);
	DelCur();
}

template<class T>
void Table<T>::DelFirst()
{
	MoveToFirst();
	DelCur();
}

template<class T>
void Table<T>::DelTail()
{
	MoveToLast();
	DelCur();
}

template<class T>
bool Table<T>::IsOut() const
{
	return cur >= length || cur<0;
}

template<class T>
bool Table<T>::IsBegin() const
{
	return cur<0;
}

template<class T>
bool Table<T>::IsEnd() const
{
	return cur >= length;
}

template<class T>
long Table<T>::GetCur() const
{
	return cur;
}

template<class T>
long Table<T>::FindOrAddTail(const T&t)
{
	long pos = Find(t);
	return pos != NOT_FOUND ? pos : AddTail(t);
}

template<class T>
void Table<T>::FindOrInsertHead(const T&t)
{
	long pos = Find(t);
	if (pos == NOT_FOUND)
	{
		InsertHead(t);
	}
}

template<class T>
void Table<T>::Exchange(long i,long j)
{
	XPrivate::Exchange((*this)[i],(*this)[j]);
}

template<class T>
Table<T>& Table<T>::operator<<(const T&t)
{
	AddTail(t);
	return *this;
}

template<class T>
const T* Table<T>::GetTo(long i) const
{
	return IsValidIndex(i) ? &(GetAt(i)) : NULL;
}

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

	if (from > to)
	{
		return NOT_FOUND;
	}

	if (t < GetAt(from))
	{
		return NOT_FOUND;
	}

	if (t > GetAt(to))
	{
		return NOT_FOUND;
	}

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

	return NOT_FOUND;
}

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

	if (IsEmpty())
	{
		MoveTo(0);
		return false;
	}

	MoveTo(from);
	if (t < GetCurData())
	{
		return false;
	}

	MoveTo(to);
	if (t > GetCurData())
	{
		MoveToNext();
		return false;
	}

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

	if (from == to)
	{
		MoveTo(from);
		const T& tCur = GetCurData();
		if (t > tCur)
		{
			MoveToNext();
		}
		else if (!(t < tCur))
		{
			return true;
		}

		return false;
	}

	return false;
}

template<class T>
bool Table<T>::SortIn(const T&t,bool bAllowDup)
{
	if (BFindTo(t))
	{
		if (!bAllowDup)
		{
			return false;
		}

		//需要找最后一个
		MoveToNext();
		while(!IsOut() && GetCurData() == t)
		{
			MoveToNext();
		}
	}

	InsertCur(t);
	return true;
}

template<class T>
T& Table<T>::operator[](long i)
{
	if (i >= GetLength())
	{
		Realloc(i + 1);
	}

	MoveTo(i);
	return GetCurData();
}

template<class T>
void Table<T>::Left(long count,Table<T>&table) const
{
	table.SetLength(count,false);
	const T*pCur = GetFirst();
	for (table.MoveToFirst(); !table.IsOut(); table.MoveToNext(),pCur = GetNext(pCur))
	{
		table.SetCurData(*pCur);
	}
}

template<class T>
void Table<T>::Right(long count,Table<T>&table) const
{
	table.SetLength(count,false);
	const T*pCur = GetTo(length - count);
	for (table.MoveToFirst(); !table.IsOut(); table.MoveToNext(),pCur = GetNext(pCur))
	{
		table.SetCurData(*pCur);
	}
}

template<class T>
void Table<T>::Mid(long from,long to,Table<T>&table) const
{
	table.SetLength(to - from + 1,false);
	const T*pCur = GetTo(from);
	for (table.MoveToFirst(); !table.IsOut(); table.MoveToNext(),pCur = GetNext(pCur))
	{
		table.SetCurData(*pCur);
	}
}

template<class T>
Table<T>& Table<T>::operator<<(const Table<T>&table)
{
	long oldLength = length;
	SetLength(length + table.GetLength());
	const T* pCur = NULL;
	for (MoveTo(oldLength),pCur = table.GetFirst(); !IsOut(); MoveToNext(),pCur = table.GetNext(pCur))
	{
		SetCurData(*pCur);
	}
	return *this;
}

template<class T>
Table<T>& Table<T>::operator<<(const Array<T>&array)
{
	long oldLength = length;
	SetLength(length+array.GetLength());

	MoveTo(oldLength);
	for (long i = 0; !IsOut(); MoveToNext(),i++)
	{
		SetCurData(array.GetAt(i));
	}

	return *this;
}

template<class T>
void Table<T>::Reverse(long start,long end)
{
	if (end == -1)
	{
		end = length - 1;
	}
	long halfLength = (end - start + 1) / 2;
	for (long i = 0; i < halfLength; i++)
	{
		T temp = (*this)[i + start];
		long j = end - i;
		(*this)[i + start] = (*this)[j];
		(*this)[j] = temp;
	}
}

template<class T>
void Table<T>::DeepCopy(const Table<T>&table)
{
	SetLength(table.GetLength(),false);
	const T* pCur = NULL;
	for (MoveToFirst(),pCur = table.GetFirst(); !IsOut(); MoveToNext(),pCur = table.GetNext(pCur))
	{
		SetCurData(*pCur);
	}
}

template<class T>
void Table<T>::DeepCopy(const Array<T>&array)
{
	SetLength(array.GetLength(),false);

	long i;
	for (MoveToFirst(),i = 0; !IsOut(); MoveToNext(),i++)
	{
		SetCurData(array.GetAt(i));
	}
}

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

	const T*pCur1 = NULL,*pCur0 = NULL;
	long i = 0;
	for (pCur0 = GetFirst(),pCur1 = table.GetFirst();
		i < GetLength();
		pCur0 = GetNext(pCur0),pCur1 = table.GetNext(pCur1),i++)
	{
		if (*pCur0 != *pCur1)
		{
			return false;
		}

	}

	return true;
}

template<class T>
void Table<T>::Clear()
{
	while(!IsEmpty())
	{
		DelTail();
	}
}

template<class T>
void Table<T>::SetAll(const T&t)
{
	for (MoveToFirst();!IsOut();MoveToNext())
	{
		SetCurData(t);
	}
}

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

	MoveTo(from);
	T&t = GetCurData();

	Insert(to,t);
	if (from>to)
	{
		Del(from + 1);	//from数据已经后移
		MoveTo(to);		//前移时to是最终位置
	}
	else
	{
		Del(from);
		MoveTo(to - 1);	//后移时to-1时最终位置
	}

	return true;
}

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

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

	return NOT_FOUND;
}

template<class T>
bool Table<T>::FindTo(const T&t,long from)
{
	for (MoveTo(from); !IsOut(); MoveToNext())
	{
		if (GetCurData() == t)
		{
			return true;
		}
	}
	return false;
}

template<class T>
long Table<T>::Find(const T&t,Quene<long>&quene,long from,long to) const
{
	if (to == -1 || to >= GetLength())
	{
		to = GetLastIndex();
	}

	const T*pCur = NULL;
	long i;
	for (pCur = GetTo(from),i = from; i <= to; pCur = GetNext(pCur),i++)
	{
		if (*pCur == t)
		{
			quene.EnQuene(i);
		}
	}

	return quene.GetLength();
}

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

#endif