195 lines
3.6 KiB
C++
195 lines
3.6 KiB
C++
//-----------------------------------------------------------------------------+
|
|
// Copyright (C), 1998-2007, SH Software Co. Ltd.
|
|
// = FileName : XDualList 模板类
|
|
// = Version : ver2.0
|
|
// = Author : zjq
|
|
// = CreateDate : 2002-09-09
|
|
// = Description: XDualList 声明
|
|
// = Maintainers:
|
|
//
|
|
//-----------------------------------------------------------------------------+
|
|
#ifndef _XDualList_H_
|
|
#define _XDualList_H_
|
|
|
|
#ifndef _DUALLIST_H_
|
|
#include "DualList.h"
|
|
#endif
|
|
|
|
#ifndef _LIST_H_
|
|
#include "List.h"
|
|
#endif
|
|
|
|
#ifndef _LISTNODE_H_
|
|
#include "ListNode.h"
|
|
#endif
|
|
|
|
#ifndef _SQPTABLE_H_
|
|
#include "SqPTable.h"
|
|
#endif
|
|
|
|
//扩展双向链表，分组以提高数据访问速度，适用于大规模数据链
|
|
template<class T> class XDualList : public DualList<T>
|
|
{
|
|
public:
|
|
|
|
XDualList(long initLength = 0, long groupLen = 25, long allocSize = 100);
|
|
virtual ~XDualList(){}
|
|
|
|
virtual void MoveTo(long index);
|
|
|
|
virtual void InsertAfterCur(const T&t);
|
|
|
|
virtual void DelCur();
|
|
|
|
virtual void Clear();
|
|
|
|
virtual void DetachAfterCur();
|
|
|
|
virtual long Conbine(List<T>&list,long from = 0);
|
|
|
|
virtual void ReverseList();
|
|
|
|
virtual void Rotate(long iFrom,long iTo);
|
|
|
|
protected:
|
|
|
|
void UpdateGroup(long iFromGroup);
|
|
|
|
protected:
|
|
|
|
//分组索引，记录各组第一个链表节点
|
|
SqTable<ListNode<T>* > group;
|
|
|
|
//分组的最大长度
|
|
long groupMaxLen;
|
|
};
|
|
|
|
|
|
template<class T>
|
|
XDualList<T>::XDualList(long initLength,long groupLen,long allocSize)
|
|
: DualList<T>(initLength),group(0,allocSize),groupMaxLen(groupLen)
|
|
{
|
|
UpdateGroup(0);
|
|
}
|
|
|
|
template<class T>
|
|
void XDualList<T>::UpdateGroup(long iFromGroup)
|
|
{
|
|
for (long i = iFromGroup * groupMaxLen; i < this->GetLength(); i += groupMaxLen)
|
|
{
|
|
DualList<T>::MoveTo(i);
|
|
group.AddTail(this->curPos);
|
|
}
|
|
}
|
|
|
|
template<class T>
|
|
void XDualList<T>::MoveTo(long index)
|
|
{
|
|
long iGroup = index / groupMaxLen;
|
|
if (group.IsValidIndex(iGroup))
|
|
{
|
|
this->curPos = group[iGroup];
|
|
this->cur = iGroup * groupMaxLen;
|
|
}
|
|
|
|
DualList<T>::MoveTo(index);
|
|
}
|
|
|
|
template<class T>
|
|
void XDualList<T>::InsertAfterCur(const T&t)
|
|
{
|
|
DualList<T>::InsertAfterCur(t);
|
|
|
|
long iFrom; //受影响的一组
|
|
if (this->GetCur() == 0) //最前插入
|
|
{
|
|
iFrom = 0;
|
|
}
|
|
else
|
|
{
|
|
iFrom = (this->GetCur() - 1) / groupMaxLen + 1;
|
|
}
|
|
|
|
for (long i = iFrom; i < group.GetLength(); i++) //从下一组开始前移
|
|
{
|
|
DListNode<T> *pNode = (DListNode<T>*)group[i];
|
|
group[i] = pNode->pre;
|
|
}
|
|
|
|
if ((this->GetLength() % groupMaxLen) == 1) //最后一组只有一个，新一组
|
|
{
|
|
group.AddTail(this->tail);
|
|
}
|
|
}
|
|
|
|
template<class T>
|
|
void XDualList<T>::DelCur()
|
|
{
|
|
if ((this->GetLength() % groupMaxLen) == 1) //最后一组只有一个，删除组
|
|
{
|
|
group.DelTail();
|
|
}
|
|
|
|
long iFrom;
|
|
if (this->GetCur() == 0) //最前删除
|
|
{
|
|
iFrom = 0;
|
|
}
|
|
else
|
|
{
|
|
iFrom = (this->GetCur() - 1) / groupMaxLen + 1;
|
|
}
|
|
|
|
for (long i = iFrom; i < group.GetLength(); i++) //从下一组开始后移
|
|
{
|
|
ListNode<T> *pNode = group[i];
|
|
group[i] = pNode->next;
|
|
}
|
|
|
|
DualList<T>::DelCur();
|
|
}
|
|
|
|
template<class T>
|
|
void XDualList<T>::DetachAfterCur()
|
|
{
|
|
DualList<T>::DetachAfterCur();
|
|
group.Realloc(this->GetLength()/groupMaxLen);
|
|
}
|
|
|
|
template<class T>
|
|
long XDualList<T>::Conbine(List<T>&list,long from)
|
|
{
|
|
long len = DualList<T>::Conbine(list,from);
|
|
UpdateGroup(group.GetLength());
|
|
|
|
return len;
|
|
}
|
|
|
|
template<class T>
|
|
void XDualList<T>::Clear()
|
|
{
|
|
group.Clear();
|
|
DualList<T>::Clear();
|
|
}
|
|
|
|
template<class T>
|
|
void XDualList<T>::ReverseList()
|
|
{
|
|
group.Clear();
|
|
DualList<T>::ReverseList();
|
|
|
|
UpdateGroup(0);
|
|
}
|
|
|
|
template<class T>
|
|
void XDualList<T>::Rotate(long iFrom,long iTo)
|
|
{
|
|
group.Clear();
|
|
DualList<T>::Rotate(iFrom,iTo);
|
|
|
|
UpdateGroup(0);
|
|
}
|
|
|
|
#endif
|
|
|