#pragma once
#include "SHList.h"
#include "SHTable.h"
#include "DListNode.h"

template<class T> class DualPtrList : public SHList< T >
{
public:
	DualPtrList(long initLength = 0);
	DualPtrList(const SHTable<T>& table);
	DualPtrList(const DualPtrList<T>& table);

	DualPtrList<T>&operator =(const DualPtrList<T>& table);
	DualPtrList<T>&operator =(const SHTable<T>& table);

	virtual ~DualPtrList();

	virtual const T& GetAt(long index)const;
	virtual const T* GetPre(const T* p)const;

	virtual void MoveTo(long index);
	virtual void MoveToPre();

	virtual void InsertAfterCur(const T& t);
	virtual void DelCur();
	virtual void Clear();

	virtual void DetachAfterCur();
	virtual long Conbine(SHList<T>& list, long from = 0);

	virtual void Arrange(bool bIncrease = true);
	virtual void Arrange(int (*cmp)(const T&,const T&));
	virtual void ReverseList();
	virtual void Rotate(long iFrom, long iTo);
};

template<class T>
DualPtrList<T>& DualPtrList<T>::operator = (const DualPtrList<T>& table)
{
	DeepCopy(table);
	return *this;
}

template<class T>
DualPtrList<T>& DualPtrList<T>::operator = (const SHTable<T>& table)
{
	DeepCopy(table);
	return *this;
}

template<class T>
void DualPtrList<T>::Clear()
{
	this->tail->next = NULL;
	DListNode<T>*p = (DListNode<T>*)(this->head->next);
	while(p != NULL)
	{
		DListNode<T> *pn = (DListNode<T>*)(p->next);
		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>
const T* DualPtrList<T>::GetPre(const T*p)const
{
	return (p == NULL || p == ((const T*)(this->head->next))) ? NULL : (const T*)(((const DListNode<T>*)p)->pre);
}

template<class T>
const T& DualPtrList<T>::GetAt(long index)const
{
	SHListNode<T>*p = this->curPos;
	long i = this->cur;
	for (; i < index; i++, p = p->next)
	{
		;
	}
	for (; i > index; i--, p = ((DListNode<T>*)p)->pre)
	{
		;
	}
	return p->data;
}

template<class T>
void DualPtrList<T>::ReverseList()
{
	if (this->length < 2)
	{
		return;
	}

	SHListNode<T>*p,*next = this->head->next,*pre = this->head;
	for (long i = 0; i < this->length; i++)
	{
		p = next;
		next = p->next;
		p->next = pre;
		((DListNode<T>*)pre)->pre = p;
		pre = p;
	}

	p = this->head->next;
	this->head->next = this->tail;
	((DListNode<T>*)this->tail)->pre = this->head;
	this->tail = p;
}	
	
template<class T>
void DualPtrList<T>::Arrange(bool bIncrease)
{
	if (this->GetLength() < 2)
	{
		return;
	}
	if (bIncrease)
	{
		this->MoveToFirst();
		this->MoveToNext();
		while(!this->IsBegin())
		{
			T temp = this->GetCurData();
			long i = this->GetCur();
			SHListNode<T>* pos = this->GetCurPos();
			MoveToPre();
			if (this->GetCurData() > temp)
			{
				while(!this->IsBegin() && this->GetCurData() > temp)
				{
					MoveToPre();
				}

				InsertAfterCur(temp);
				this->curPos = pos;
				this->cur = i + 1;
				DelCur();
			}
			else
			{
				this->MoveToNext();
			}
			this->MoveToNext();
		}
	}
	else
	{
		this->MoveToFirst();
		this->MoveToNext();
		while(!this->IsBegin())
		{
			T temp = this->GetCurData();
			long i = this->GetCur();
			SHListNode<T>*pos = this->GetCurPos();
			MoveToPre();
			if (this->GetCurData() < temp)
			{
				while(!this->IsBegin() && this->GetCurData() < temp)
				{
					MoveToPre();
				}
				InsertAfterCur(temp);
				this->curPos = pos;
				this->cur = i + 1;
				DelCur();
			}
			else
			{
				this->MoveToNext();
			}
			this->MoveToNext();
		}
	}
}

template<class T>
void DualPtrList<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();
		SHListNode<T>* pos = this->GetCurPos();
		MoveToPre();
		if (cmp(this->GetCurData(),temp) > 0)
		{
			while(!this->IsBegin() && cmp(this->GetCurData(),temp) > 0)
			{
				MoveToPre();
			}
			InsertAfterCur(temp);
			this->curPos = pos;
			this->cur = i + 1;
			DelCur();
		}
		else
		{
			this->MoveToNext();
		}
		this->MoveToNext();
	}
}

template<class T>
void DualPtrList<T>::InsertAfterCur(const T& t)
{
    DListNode<T>* p = new DListNode<T>;
	p->data = t;
	p->next = this->curPos->next;
	this->curPos->next = p;
	p->pre = this->curPos;
	((DListNode<T>*)(p->next))->pre = p;
	this->length++;
	this->cur++;
	if (this->curPos == this->tail)
	{
		this->tail = p;
	}
	this->curPos = p;
}

template<class T>
void DualPtrList<T>::DelCur()
{
	DListNode<T>* p = (DListNode<T>*)this->curPos;
	MoveToPre();
	this->curPos->next = p->next;
	((DListNode<T>*)(p->next))->pre = this->curPos;
	if (p == this->tail)
	{
		this->tail = this->curPos;
	}
	delete p;
	this->length--;
}

template<class T>
DualPtrList<T>::DualPtrList(long initLength)
{
	delete this->head;
	this->head = this->tail = new DListNode<T>;
	this->head->next = this->head;
	((DListNode<T>*)this->head)->pre = this->head;
	this->curPos = this->head;
	this->Realloc(initLength);
}

template<class T>
DualPtrList<T>::DualPtrList(const SHTable<T>&table)
{
	delete this->head;
	this->head = this->tail = new DListNode<T>;
	this->head->next = this->head;
	((DListNode<T>*)this->head)->pre = this->head;
	this->curPos = this->head;
	DeepCopy(table);
}

template<class T>
DualPtrList<T>::DualPtrList(const DualPtrList<T>&table)
{
	delete this->head;
	this->head = this->tail = new DListNode<T>;
	this->head->next = this->head;
	((DListNode<T>*)this->head)->pre = this->head;
	this->curPos = this->head;
	DeepCopy(table);
}

template<class T>
DualPtrList<T>::~DualPtrList()
{
	if (this->head == NULL)
	{
		return;
	}

	Clear();

	DListNode<T>* p = (DListNode<T>*)this->head;
	delete p;
	this->head = NULL;
}

template<class T>
void DualPtrList<T>::MoveToPre()
{
	this->curPos = ((DListNode<T>*)this->curPos)->pre;
	this->cur--;
	if (this->curPos == this->tail)
	{
		this->cur = this->length - 1;
	}
}

template<class T>
void DualPtrList<T>::MoveTo(long index)
{
	if (this->IsValidIndex(index))
	{
		if (index == 0)
		{
			this->curPos = this->head->next;
			this->cur = 0;
		}
		else if (index == this->GetLastIndex())
		{
			this->curPos = this->tail;
			this->cur = index;
		}
		else if (index >= this->cur)
		{
			while(this->GetCur() != index)
			{
				this->MoveToNext();
			}
		}
		else
		{
			while(this->GetCur() != index)
			{
				MoveToPre();
			}
		}
	}
	else
	{
		this->cur = -1;
		this->curPos = this->head;
	}
}

template<class T>
long DualPtrList<T>::Conbine(SHList<T>&lstConbine,long from)
{
	if (lstConbine.IsValidIndex(from))
	{
		SHListNode<T>*first, *last;
		lstConbine.MoveTo(from);
		first = lstConbine.GetCurPos();
		lstConbine.MoveToLast();
		last = lstConbine.GetCurPos();
		this->length += lstConbine.GetLength() - from;
		lstConbine.DetachAfter(from - 1);
		this->tail->next = first;
		((DListNode<T>*)first)->pre = this->tail;
		this->tail = last;
		this->tail->next = this->head;
		((DListNode<T>*)this->head)->pre = this->tail;
	}
	return this->length;
}

template<class T>
void DualPtrList<T>::Rotate(long iFrom,long iTo)
{
	if (iFrom != iTo)
	{
		long iNewZero = (iFrom - iTo + this->GetLength()) % this->GetLength();
		MoveTo(iNewZero - 1 + this->GetLength() % this->GetLength());
		SHListNode<T>* newTail = this->GetCurPos();
		MoveTo(iNewZero);

		//形成环路
		this->tail->next = this->head->next;
		((DListNode<T>*)this->head->next)->pre = this->tail;

		//更新this->head
		this->head->next = this->curPos;
		((DListNode<T>*)this->curPos)->pre = this->head;
		this->cur = 0;

		//更新tail
		this->tail = newTail;
		this->tail->next = this->head;
		((DListNode<T>*)this->head)->pre = this->tail;
	}
}

template<class T>
void DualPtrList<T>::DetachAfterCur()
{
	this->curPos->next = this->head;
	((DListNode<T>*)this->head)->pre = this->curPos;
	this->tail = this->curPos;
	this->length = this->cur + 1;
}