992 lines
16 KiB
C++
992 lines
16 KiB
C++
//-------------------------------------------------------------------------------------------------------+
|
|
// Copyright (C), 1998-2007, Beijing Tangent Software Co. Ltd.
|
|
// = FileName : TSqPTable 模板类
|
|
// = Version : ver2.0
|
|
// = Author : wlw
|
|
// = CreateDate : 2002-09-09
|
|
// = Description: TSqPTable 声明
|
|
// 动态指针数组，内部可以自动分配、释放内存,同时提供外部内存分配、释放接口。
|
|
// 同名函数功能、使用方法、要求与SqTable<T>完全相同。
|
|
// 未访问的数据不分配内存,数据一经访问，自动分配内存,支持空数据。
|
|
// = Maintainers:
|
|
//
|
|
//-------------------------------------------------------------------------------------------------------+
|
|
#ifndef _TSQPTABLE_H_
|
|
#define _TSQPTABLE_H_
|
|
|
|
#ifndef _TSQTABLE_H_
|
|
#include "TSqTable.h"
|
|
#endif
|
|
|
|
template<class T>class TSqPTable
|
|
{
|
|
public:
|
|
|
|
TSqPTable(long size = 0,long unit = 10);
|
|
|
|
TSqPTable(const TSqPTable<T>&ptable);
|
|
|
|
TSqPTable(const TTable<T>&table);
|
|
|
|
virtual ~TSqPTable();
|
|
|
|
TSqPTable<T>& operator = (const TSqPTable<T>&ptable);
|
|
|
|
TSqPTable<T>& operator = (const TTable<T>&table);
|
|
|
|
bool operator == (const TSqPTable<T>&pTable) const;
|
|
|
|
bool operator != (const TSqPTable<T>&pTable) const;
|
|
|
|
void Increase(long num);
|
|
void Decrease(long num);
|
|
|
|
//always copy old data
|
|
void SetLength(long newLength,bool bCopy = true);
|
|
|
|
//attribute
|
|
bool IsValidIndex(long index) const;
|
|
|
|
bool IsEmpty() const;
|
|
|
|
long GetLength() const;
|
|
|
|
long GetLastIndex() const;
|
|
|
|
void SetAllocUnit(long size);
|
|
|
|
long GetAllocUnit() const;
|
|
|
|
long GetDataNum() const;
|
|
|
|
bool IsEmptyData(long index) const;
|
|
|
|
bool IsCurEmpty() const;
|
|
|
|
//sequence visit interface
|
|
bool IsOut() const;
|
|
|
|
bool IsBegin() const;
|
|
|
|
bool IsEnd() const;
|
|
|
|
long GetCur() const;
|
|
|
|
void MoveTo(long index);
|
|
|
|
void MoveToFirst();
|
|
|
|
void MoveToLast();
|
|
|
|
void MoveToNext();
|
|
|
|
void MoveToPre();
|
|
|
|
T& GetCurData();
|
|
|
|
void SetCurData(const T&t);
|
|
|
|
//ramdon visit interface,index must be valid!!!
|
|
const T& GetAt(long index) const;
|
|
|
|
T& operator[](long index);
|
|
|
|
//pointer interface
|
|
T* operator()(long index);
|
|
|
|
//不能对它返加的指针本身进行delete操作!!!
|
|
void SetCurData(T*p);
|
|
|
|
//将外部分配的数据填入指针表,p 可以是NULL指针;自动调整指针表长度;
|
|
//外部一般应在堆中分配内存，以使TSqPTable正确对其进行管理;
|
|
//否则应使用SetOutData(index,NULL)及时将其清理。
|
|
//if index<0,ignore.
|
|
void SetOutData(long index,T*p);
|
|
|
|
void Insert(long index,T*p);
|
|
|
|
void InsertCur(T*p);
|
|
|
|
void InsertHead(T*p);
|
|
|
|
long AddTail(T*p);
|
|
|
|
//在第一个空数据处添加，无空数据项则末尾添加,返回索引。
|
|
long FillIn(T*p);
|
|
|
|
//仅释放数据空间，不删除指针空间,不改变数组长度，不移动cur.
|
|
void ReleaseCur();
|
|
|
|
void Release(long i);
|
|
|
|
void ReleaseAll();
|
|
|
|
void InsertCur(const T&t);
|
|
|
|
void DelCur();
|
|
|
|
void Insert(long index,const T&t);
|
|
|
|
void InsertHead(const T&t);
|
|
|
|
long AddTail(const T&t);
|
|
|
|
//在第一个空数据处添加，无空数据项则末尾添加,返回索引。
|
|
long FillIn(const T&t);
|
|
|
|
void Del(long index);
|
|
|
|
void DelFirst();
|
|
|
|
void DelTail();
|
|
|
|
//取走数据，清空指针，但不删除指针表项!
|
|
T* FetchCur();
|
|
|
|
T* Fetch(long i);
|
|
|
|
T* FetchFirst();
|
|
|
|
T* FetchLast();
|
|
|
|
void Clear();
|
|
|
|
void ExChange(long i,long j);
|
|
|
|
//索引以未移动时为准
|
|
bool Move(long from,long to);
|
|
|
|
long FindOrAddTail(const T& t);
|
|
|
|
void FindOrInsertHead(const T& t);
|
|
|
|
long FindAndDel(const T& t);
|
|
|
|
long Find(const T& t,long from = 0,long to = -1) const;
|
|
|
|
long Find(const T& t,TQuene<long>& quene,long from = 0,long to = -1) const;
|
|
|
|
void SetAll(const T&t);
|
|
|
|
//稳定计数排序, 不支持空数据!但速度快。
|
|
void Arrange(bool bIncrease = true);
|
|
|
|
//稳定计数排序
|
|
void Arrange(int (*cmp)(const T&,const T&));
|
|
|
|
//稳定计数排序,空数据将排列在最后
|
|
void ArrangeEx(bool bIncrease = true);
|
|
|
|
void Reverse(long start = 0,long end = -1);
|
|
|
|
protected:
|
|
|
|
TSqTable<T* > table;
|
|
};
|
|
|
|
template<class T>
|
|
TSqPTable<T>::TSqPTable(long size,long unit):table(size,unit)
|
|
{
|
|
|
|
}
|
|
|
|
template<class T>
|
|
TSqPTable<T>::TSqPTable(const TSqPTable<T>&ptable)
|
|
{
|
|
*this = ptable;
|
|
}
|
|
|
|
template<class T>
|
|
TSqPTable<T>::TSqPTable(const TTable<T>&table)
|
|
{
|
|
*this = table;
|
|
}
|
|
|
|
template<class T>
|
|
bool TSqPTable<T>::IsValidIndex(long index) const
|
|
{
|
|
return table.IsValidIndex(index);
|
|
}
|
|
|
|
template<class T>
|
|
bool TSqPTable<T>::IsEmpty() const
|
|
{
|
|
return table.IsEmpty();
|
|
}
|
|
|
|
template<class T>
|
|
long TSqPTable<T>::GetLength() const
|
|
{
|
|
return table.GetLength();
|
|
}
|
|
template<class T>
|
|
long TSqPTable<T>::GetLastIndex() const
|
|
{
|
|
return table.GetLastIndex();
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::SetAllocUnit(long size)
|
|
{
|
|
table.SetAllocUnit(size);
|
|
}
|
|
|
|
template<class T>
|
|
long TSqPTable<T>::GetAllocUnit() const
|
|
{
|
|
return table.GetAllocUnit();
|
|
}
|
|
|
|
template<class T>
|
|
bool TSqPTable<T>::IsCurEmpty() const
|
|
{
|
|
return IsEmptyData(GetCur());
|
|
}
|
|
|
|
template<class T>
|
|
bool TSqPTable<T>::operator != (const TSqPTable<T>&pTable) const
|
|
{
|
|
return !(*this == pTable);
|
|
}
|
|
|
|
template<class T>
|
|
bool TSqPTable<T>::IsOut() const
|
|
{
|
|
return table.IsOut();
|
|
}
|
|
|
|
template<class T>
|
|
bool TSqPTable<T>::IsBegin() const
|
|
{
|
|
return table.IsBegin();
|
|
}
|
|
|
|
template<class T>
|
|
bool TSqPTable<T>::IsEnd() const
|
|
{
|
|
return table.IsEnd();
|
|
}
|
|
|
|
template<class T>
|
|
long TSqPTable<T>::GetCur() const
|
|
{
|
|
return table.GetCur();
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::MoveTo(long index)
|
|
{
|
|
table.MoveTo(index);
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::MoveToFirst()
|
|
{
|
|
table.MoveToFirst();
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::MoveToLast()
|
|
{
|
|
table.MoveToLast();
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::MoveToNext()
|
|
{
|
|
table.MoveToNext();
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::MoveToPre()
|
|
{
|
|
table.MoveToPre();
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::SetCurData(T*p)
|
|
{
|
|
if (!IsOut())
|
|
{
|
|
SetOutData(GetCur(),p);
|
|
}
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::Insert(long index,T*p)
|
|
{
|
|
MoveTo(index);
|
|
InsertCur(p);
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::InsertCur(T*p)
|
|
{
|
|
table.InsertCur(p);
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::InsertHead(T*p)
|
|
{
|
|
Insert(0,p);
|
|
}
|
|
|
|
template<class T>
|
|
long TSqPTable<T>::AddTail(T*p)
|
|
{
|
|
Insert(GetLength(),p);
|
|
return GetLastIndex();
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::Release(long i)
|
|
{
|
|
MoveTo(i);
|
|
ReleaseCur();
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::Insert(long index,const T&t)
|
|
{
|
|
MoveTo(index);
|
|
InsertCur(t);
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::InsertHead(const T&t)
|
|
{
|
|
MoveToFirst();
|
|
InsertCur(t);
|
|
}
|
|
|
|
template<class T>
|
|
long TSqPTable<T>::AddTail(const T&t)
|
|
{
|
|
MoveTo(GetLength());
|
|
InsertCur(t);
|
|
return GetLastIndex();
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::Del(long index)
|
|
{
|
|
MoveTo(index);
|
|
DelCur();
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::DelFirst()
|
|
{
|
|
MoveToFirst();
|
|
DelCur();
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::DelTail()
|
|
{
|
|
MoveToLast();
|
|
DelCur();
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::ExChange(long i,long j)
|
|
{
|
|
table.Exchange(i,j);
|
|
}
|
|
|
|
template<class T>
|
|
bool TSqPTable<T>::Move(long from,long to)
|
|
{
|
|
return table.Move(from,to);
|
|
}
|
|
|
|
template<class T>
|
|
long TSqPTable<T>::FindOrAddTail(const T&t)
|
|
{
|
|
long pos = Find(t,0,GetLastIndex());
|
|
return pos != NOT_FOUND ? pos : AddTail(t);
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::FindOrInsertHead(const T&t)
|
|
{
|
|
long pos = Find(t,0,GetLastIndex());
|
|
if (pos == NOT_FOUND)
|
|
{
|
|
InsertHead(t);
|
|
}
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::Reverse(long start,long end)
|
|
{
|
|
table.Reverse(start,end);
|
|
}
|
|
|
|
template<class T>
|
|
T* TSqPTable<T>::Fetch(long i)
|
|
{
|
|
MoveTo(i);
|
|
return FetchCur();
|
|
}
|
|
|
|
template<class T>
|
|
T* TSqPTable<T>::FetchFirst()
|
|
{
|
|
MoveToFirst();
|
|
return FetchCur();
|
|
}
|
|
|
|
template<class T>
|
|
T* TSqPTable<T>::FetchLast()
|
|
{
|
|
MoveToLast();
|
|
return FetchCur();
|
|
}
|
|
|
|
template<class T>
|
|
const T& TSqPTable<T>::GetAt(long index) const
|
|
{
|
|
return *(table.GetAt(index));
|
|
}
|
|
|
|
template<class T>
|
|
T* TSqPTable<T>::FetchCur()
|
|
{
|
|
if (IsOut())
|
|
{
|
|
return NULL;
|
|
}
|
|
T*p = table.GetCurData();
|
|
table.SetCurData(NULL);
|
|
return p;
|
|
}
|
|
|
|
template<class T>
|
|
bool TSqPTable<T>::IsEmptyData(long index) const
|
|
{
|
|
return IsValidIndex(index)?table.GetAt(index) == NULL:true;
|
|
}
|
|
|
|
template<class T>
|
|
T& TSqPTable<T>::GetCurData()
|
|
{
|
|
if (IsCurEmpty())
|
|
{
|
|
T *p = new T;
|
|
table.SetCurData(p);
|
|
}
|
|
return *(table.GetCurData());
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::SetCurData(const T&t)
|
|
{
|
|
if (IsCurEmpty())
|
|
{
|
|
T *p = new T;
|
|
table.SetCurData(p);
|
|
}
|
|
*(table.GetCurData()) = t;
|
|
}
|
|
|
|
template<class T>
|
|
T& TSqPTable<T>::operator[](long index)
|
|
{//index must be >= 0!!!
|
|
if (index >= GetLength())
|
|
{
|
|
Increase(index+1-GetLength());
|
|
}
|
|
MoveTo(index);
|
|
return GetCurData();
|
|
}
|
|
|
|
template<class T>
|
|
T* TSqPTable<T>::operator()(long index)
|
|
{
|
|
if (index >= GetLength())
|
|
{
|
|
Increase(index+1-GetLength());
|
|
}
|
|
MoveTo(index);
|
|
return table.GetCurData();
|
|
}
|
|
|
|
template<class T>
|
|
long TSqPTable<T>::FillIn(const T&t)
|
|
{
|
|
long i(0);
|
|
for (i = 0;!IsEmptyData(i);i++);
|
|
(*this)[i] = t;
|
|
return i;
|
|
}
|
|
|
|
template<class T>
|
|
long TSqPTable<T>::FillIn(T*p)
|
|
{
|
|
long i(0);
|
|
for (i = 0;!IsEmptyData(i);i++);
|
|
SetOutData(i,p);
|
|
return i;
|
|
}
|
|
|
|
template<class T>
|
|
long TSqPTable<T>::GetDataNum() const
|
|
{
|
|
long count = 0;
|
|
for (long i = 0;i<GetLength();i++)
|
|
{
|
|
if (!IsEmptyData(i))
|
|
{
|
|
count++;
|
|
}
|
|
}
|
|
return count;
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::SetOutData(long index,T*p)
|
|
{
|
|
if (index<0)
|
|
{
|
|
return;
|
|
}
|
|
if (IsEmptyData(index))
|
|
{
|
|
if (index >= GetLength())
|
|
{
|
|
Increase(index+1-GetLength());
|
|
}
|
|
table[index] = p;
|
|
}
|
|
else
|
|
{
|
|
delete table[index];
|
|
table[index] = p;
|
|
}
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::ReleaseCur()
|
|
{//仅释放数据空间，不删除指针空间,不改变数组长度，不移动cur.
|
|
if (IsCurEmpty())
|
|
{
|
|
return;
|
|
}
|
|
delete table.GetCurData();
|
|
table.SetCurData(NULL);
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::InsertCur(const T&t)
|
|
{
|
|
T*p = new T;
|
|
*p = t;
|
|
table.InsertCur(p);
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::DelCur()
|
|
{
|
|
if (table.GetCurData() == NULL)
|
|
{
|
|
delete table.GetCurData();
|
|
}
|
|
table.DelCur();
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::ReleaseAll()
|
|
{
|
|
for (MoveToFirst();!IsOut();MoveToNext())
|
|
{
|
|
ReleaseCur();
|
|
}
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::Clear()
|
|
{
|
|
ReleaseAll();
|
|
table.Clear();
|
|
}
|
|
|
|
template<class T>
|
|
long TSqPTable<T>::FindAndDel(const T&t)
|
|
{
|
|
int count(0);
|
|
for (long i = 0;i<GetLength();i++)
|
|
{
|
|
if (!IsEmptyData(i) && GetAt(i) == t)
|
|
{
|
|
Del(i);
|
|
i--;
|
|
count++;
|
|
}
|
|
}
|
|
return count;
|
|
}
|
|
|
|
template<class T>
|
|
long TSqPTable<T>::Find(const T&t,long from,long to) const
|
|
{
|
|
if (to == -1 || to >= GetLength())
|
|
{
|
|
to = GetLastIndex();
|
|
}
|
|
for (long i = from;i <= to;i++)
|
|
{
|
|
if (!IsEmptyData(i) && GetAt(i) == t)
|
|
{
|
|
return i;
|
|
}
|
|
}
|
|
return NOT_FOUND;
|
|
}
|
|
|
|
template<class T>
|
|
long TSqPTable<T>::Find(const T&t,TQuene<long>&quene,long from,long to) const
|
|
{
|
|
if (to == -1 || to >= GetLength())
|
|
{
|
|
to = GetLastIndex();
|
|
}
|
|
for (long i = from;i <= to;i++)
|
|
{
|
|
if (!IsEmptyData(i) && GetAt(i) == t)
|
|
{
|
|
return quene.EnQuene(i);
|
|
}
|
|
}
|
|
return quene.GetLength();
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::SetAll(const T&t)
|
|
{
|
|
for (MoveToFirst();!IsOut();MoveToNext())
|
|
{
|
|
SetCurData(t);
|
|
}
|
|
}
|
|
|
|
template<class T>
|
|
TSqPTable<T>& TSqPTable<T>::operator = (const TSqPTable<T>&ptable)
|
|
{
|
|
SetLength(ptable.GetLength());
|
|
for (long i = 0;i<GetLength();i++)
|
|
{
|
|
if (!ptable.IsEmptyData(i))
|
|
{
|
|
SetCurData(ptable.GetAt(i));
|
|
}
|
|
else
|
|
{
|
|
ReleaseCur();
|
|
}
|
|
}
|
|
|
|
return *this;
|
|
}
|
|
|
|
template<class T>
|
|
bool TSqPTable<T>::operator == (const TSqPTable<T>&pTable) const
|
|
{
|
|
if (pTable.GetLength() != GetLength())
|
|
{
|
|
return false;
|
|
}
|
|
for (long i = 0;i<GetLength();i++)
|
|
{
|
|
if (!pTable.IsEmptyData(i) && !IsEmptyData(i) && pTable.GetAt(i) != GetAt(i))
|
|
{
|
|
return false;
|
|
}
|
|
else if (!(pTable.IsEmptyData(i) && IsEmptyData(i)))
|
|
{
|
|
return false;
|
|
}
|
|
}
|
|
return true;
|
|
}
|
|
|
|
template<class T>
|
|
TSqPTable<T>& TSqPTable<T>::operator = (const TTable<T>&t)
|
|
{
|
|
SetLength(t.GetLength(),false);
|
|
const T*pCur = NULL;
|
|
for (MoveToFirst(),pCur = t.GetFirst();!IsOut();MoveToNext(),pCur = t.GetNext(pCur))
|
|
{
|
|
SetCurData(*pCur);
|
|
}
|
|
return *this;
|
|
}
|
|
|
|
template<class T>
|
|
TSqPTable<T>::~TSqPTable()
|
|
{
|
|
ReleaseAll();
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::Increase(long num)
|
|
{
|
|
long oldLength = GetLength();
|
|
long oldCur = GetCur();
|
|
table.Increase(num);
|
|
for (long i = oldLength;i<GetLength();i++)
|
|
{
|
|
table[i] = NULL;
|
|
}
|
|
MoveTo(oldCur);
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::Decrease(long num)
|
|
{
|
|
long oldLength = GetLength();
|
|
long oldCur = GetCur();
|
|
for (long i = oldLength-num;i<oldLength;i++)
|
|
{
|
|
if (table[i] != NULL)
|
|
{
|
|
delete table[i];
|
|
}
|
|
}
|
|
table.Decrease(num);
|
|
MoveTo(oldCur);
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::SetLength(long newLength,bool bCopy)
|
|
{
|
|
long oldCur = GetCur();
|
|
long oldLength = GetLength();
|
|
for (MoveTo(newLength);!IsOut();MoveToNext())
|
|
{
|
|
if (!IsCurEmpty())
|
|
{
|
|
delete table.GetCurData();
|
|
}
|
|
}
|
|
table.SetLength(newLength);
|
|
for (MoveTo(oldLength);!IsOut();MoveToNext())
|
|
{
|
|
table.SetCurData(NULL);
|
|
}
|
|
MoveTo(oldCur);
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::Arrange(bool bIncrease)
|
|
{
|
|
if (GetLength()<2)
|
|
{
|
|
return;
|
|
}
|
|
long *count = new long[GetLength()];
|
|
long i;
|
|
for (i = 0;i<GetLength();i++)
|
|
{
|
|
count[i] = i;
|
|
}
|
|
if (bIncrease)
|
|
{
|
|
for (i = 0;i<GetLastIndex();i++)
|
|
{
|
|
for (long j = i+1;j<GetLength();j++)
|
|
{
|
|
if (*(table[i])>*(table[j]))
|
|
{
|
|
count[i]++;
|
|
count[j]--;
|
|
}
|
|
}
|
|
}
|
|
for (i = 0;i<GetLength();i++)
|
|
{
|
|
if (count[i] != i)
|
|
{
|
|
long k,j;
|
|
T *temp1 = table[i],*temp2;
|
|
k = count[i];
|
|
while(k != i)
|
|
{
|
|
temp2 = table[k];//save
|
|
table[k] = temp1;//transport data
|
|
temp1 = temp2;
|
|
j = k;
|
|
k = count[j];//save
|
|
count[j] = j;//count ok
|
|
}
|
|
table[i] = temp1;
|
|
count[i] = i;
|
|
}
|
|
}
|
|
}
|
|
else
|
|
{
|
|
for (i = 0;i<GetLastIndex();i++)
|
|
{
|
|
for (long j = i+1;j<GetLength();j++)
|
|
{
|
|
if (*(table[i])<*(table[j]))
|
|
{
|
|
count[i]++;
|
|
count[j]--;
|
|
}
|
|
}
|
|
}
|
|
for (i = 0;i<GetLength();i++)
|
|
{
|
|
if (count[i] != i)
|
|
{
|
|
long k,j;
|
|
T *temp1 = table[i],*temp2;
|
|
k = count[i];
|
|
while(k != i)
|
|
{
|
|
temp2 = table[k];//save
|
|
table[k] = temp1;//transport data
|
|
temp1 = temp2;
|
|
j = k;
|
|
k = count[j];//save
|
|
count[j] = j;//count ok
|
|
}
|
|
table[i] = temp1;
|
|
count[i] = i;
|
|
}
|
|
}
|
|
}
|
|
delete[] count;
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::Arrange(int (*cmp)(const T&,const T&))
|
|
{
|
|
if (GetLength()<2)
|
|
{
|
|
return;
|
|
}
|
|
long *count = new long[GetLength()];
|
|
long i;
|
|
for (i = 0;i<GetLength();i++)
|
|
{
|
|
count[i] = i;
|
|
}
|
|
for (i = 0;i<GetLastIndex();i++)
|
|
{
|
|
for (long j = i+1;j<GetLength();j++)
|
|
{
|
|
if (cmp(*(table[i]),*(table[j]))>0)
|
|
{
|
|
count[i]++;
|
|
count[j]--;
|
|
}
|
|
}
|
|
}
|
|
for (i = 0;i<GetLength();i++)
|
|
{
|
|
if (count[i] != i)
|
|
{
|
|
long k,j;
|
|
T *temp1 = table[i],*temp2;
|
|
k = count[i];
|
|
while(k != i)
|
|
{
|
|
temp2 = table[k];//save
|
|
table[k] = temp1;//transport data
|
|
temp1 = temp2;
|
|
j = k;
|
|
k = count[j];//save
|
|
count[j] = j;//count ok
|
|
}
|
|
table[i] = temp1;
|
|
count[i] = i;
|
|
}
|
|
}
|
|
delete[] count;
|
|
}
|
|
|
|
template<class T>
|
|
void TSqPTable<T>::ArrangeEx(bool bIncrease)
|
|
{
|
|
if (GetLength()<2)
|
|
return;
|
|
long *count = new long[GetLength()];
|
|
long i;
|
|
for (i = 0;i<GetLength();i++)
|
|
count[i] = i;
|
|
if (bIncrease)
|
|
{
|
|
for (i = 0;i<GetLastIndex();i++)
|
|
{
|
|
for (long j = i+1;j<GetLength();j++)
|
|
{
|
|
if (table[j] != NULL && (table[i] == NULL || *(table[i])>*(table[j])))
|
|
{
|
|
count[i]++;
|
|
count[j]--;
|
|
}
|
|
}
|
|
}
|
|
for (i = 0;i<GetLength();i++)
|
|
{
|
|
if (count[i] != i)
|
|
{
|
|
long k,j;
|
|
T *temp1 = table[i],*temp2;
|
|
k = count[i];
|
|
while(k != i)
|
|
{
|
|
temp2 = table[k];//save
|
|
table[k] = temp1;//transport data
|
|
temp1 = temp2;
|
|
j = k;
|
|
k = count[j];//save
|
|
count[j] = j;//count ok
|
|
}
|
|
table[i] = temp1;
|
|
count[i] = i;
|
|
}
|
|
}
|
|
}
|
|
else
|
|
{
|
|
for (i = 0;i<GetLastIndex();i++)
|
|
{
|
|
for (long j = i+1;j<GetLength();j++)
|
|
{
|
|
if (table[j] != NULL && (table[i] == NULL || *(table[i])<*(table[j])))
|
|
{
|
|
count[i]++;
|
|
count[j]--;
|
|
}
|
|
}
|
|
}
|
|
for (i = 0;i<GetLength();i++)
|
|
{
|
|
if (count[i] != i)
|
|
{
|
|
long k,j;
|
|
T *temp1 = table[i],*temp2;
|
|
k = count[i];
|
|
while(k != i)
|
|
{
|
|
temp2 = table[k];//save
|
|
table[k] = temp1;//transport data
|
|
temp1 = temp2;
|
|
j = k;
|
|
k = count[j];//save
|
|
count[j] = j;//count ok
|
|
}
|
|
table[i] = temp1;
|
|
count[i] = i;
|
|
}
|
|
}
|
|
}
|
|
delete[] count;
|
|
}
|
|
|
|
#endif
|