757 lines
12 KiB
C++
757 lines
12 KiB
C++
//-----------------------------------------------------------------------------+
|
|
// 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
|