#include<iostream>
using namespace std;

class OutOfBound{};

template<class T>
class Double;
template<class T>
class Iterator;

template<class T>
class DNode
{
	friend class Double< T >;
	friend class Iterator<T>;
private:
	T data;
	DNode<T> *left, *right;
};

template<class T>
class Iterator
{
public:
	T* Init(const Double<T>& c)
	{
		location=c.header->right;
		PIsHeader=c.header;		
		if(location!=c.header)
			return &location->data;
		return 0;
	}
	
	T* Next()
	{
		if(location==PIsHeader)
			location=location->right;
		location=location->right;		
		if(location==PIsHeader)
			location=location->right;
		return &location->data;
		
	}
private:
	DNode<T> *location;
	DNode<T> *PIsHeader;
};



template<class T>
class Double
{
	friend Iterator<T>;
public:
	Double();
	~Double();
	bool Empty() const{return n==0;}
	int Length() const {return n;}
	bool Retrieve(int k,T&x)const;
	int Locate(const T&x)const;
	
	void Clear()
	{
		DNode<T> *current;
		DNode<T> *next;
		current=header->right;
		while(!Empty())
		{
			next=current->right;
			delete current;
			n--;
			current=next;
		}
	}

    Double<T>& Reverse()
	{
		DNode<T>* p = 0;//排序后的鏈表頭
		DNode<T>* p1 = header;//排序前的鏈表頭
		DNode<T>* p2 = p1;//在排序過程中，保存原始鏈表頭
		cout<<"---"<<p1<<" "<<p1->right<<" "<<p1->right->right<<" "<<p1->right->right->right<<" "<<p1->right->right->right->right<<" "<<endl;
			//<<p1->next->next->next->next->next<<endl;
		for(;p2;)
		{
			
			p2 = p1->right;
			cout<<"+++++"<<p2<<" ";
			p1->right = p;
			cout<<(p1->right)<<" ";
			//以上2步，是將當前節點從鏈表中取出然后將指針反向指向
			p = p1;//將排序好的鏈表的頭，給p
			cout<<p<<" ";
			p1 = p2;//將p1重新指向鏈表的首位置
			cout<<p1<<"++++"<<endl;

		}
		header = p;//讓head重新指向排序好的鏈表頭
		cout<<"---"<<p<<" "<<p->right<<" "<<p->right->right<<" "<<p->right->right->right<<" "<<p->right->right->right->right<<" "<<endl;

		return *this;
	}
	
	Double<T>& Insert(int k,const T&x);
	Double<T>& Delete(int k,  T&x);
	void PrintList () const;
	
private:
	int n;
	DNode<T> *header;
};

template<class T>
Double<T>::Double()
{
	DNode<T> *y=new DNode<T>;
	y->left=y;
	y->right=y;
	header=y;
	n=0;
}

template<class T>
Double<T>::~Double()
{
	DNode<T> *current;
	DNode<T> *next;
    current=header->right;
	while(!Empty())
	{
		next=current->right;
		delete current;
		n--;
		current=next;
	}
	delete header;
}

template<class T>
bool Double<T>::Retrieve(int k,T& x)const
{
	if(k<1 || k>n) return false;
	DNode<T> *current=header->right;
	int index =1;
	while(index<k)
	{
		current=current->right;
		index++;
	}
	x=current->data;
	return true;
}

template<class T>
int Double<T>::Locate(const T& x)const
{
	DNode<T> *current=header->right;
	int index =1;
	header->data=x;
	while(current->data!=x)
	{
		current=current->right;
		index++;
	}
	
	return ((current==header)?0:index);
}

template<class T>
Double<T>& Double<T>::Insert(int k,const T& x)
{
	if(k<0 || k>n) throw OutOfBound();
	DNode<T>* p=header->right;
	for(int index=1;index<k;index++)
		p=p->right;
	DNode<T> *y=new DNode<T>;
	y->data=x;
	y->left=p;
	y->right=p->right;
	p->right->left=y;
	p->right=y;
	n++;
	return * this;
	
}

template<class T>
Double<T>& Double<T>::Delete(int k, T& x)
{
	if(k<1 || k>n) throw OutOfBound();
	DNode<T>* q=header->right;
	for(int index=1;index<k;index++)
		q=q->right;
	q->left->right=q->right;
	q->right->left=q->left;
	x=q->data;
	delete q;
	n--;
	return * this;
	
}

template<class T>
void Double<T>::PrintList () const
{
	DNode<T> *current;
	for(current=header->right;current!=header;current=current->right)
		cout<<current->data<<" ";
}

int main()
{
	Double<int> y;
	y.Insert(0,1);
	y.Insert(1,2);
	y.Insert(2,3);
	y.Insert(3,4);
	y.Insert(4,5);
	y.Insert(5,6);
	y.Insert(6,7);
	y.Insert(7,8);
	y.Insert(8,9);
	y.Insert(9,10);
	y.Insert(10,11);
	y.Insert(11,12);



	cout<<"倒序前：";
	y.PrintList();
	cout<<endl;
	y.Reverse();
	cout<<"倒序后：";
	y.PrintList();
	cout<<endl;
	return 0;
}
/*

int main()
{
return 0;
}
*/