//-----------------------------------------------------------------------------+
// 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