809 lines
13 KiB
C++
809 lines
13 KiB
C++
//-------------------------------------------------------------------------------------------------------+
|
|
// 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
|