#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>& Insert(int k,const T&x);
	Double<T>& Delete(int k,  T&x);
//***************************************************************8
//***************************************************************
	Double<T>& SPLIT(Double<T>& L,Double<T>& L1,Double<T>& L2)
	{
		DNode<T> *t1=L1.header,*t2=L2.header,*p;
		p=L.header;
		int LOCATION=0;
		int i=0,j=0;
		while(p->right!=L.header)
		{
			LOCATION++;
//			cout<<"LOc="<<LOCATION<<endl;
				if(LOCATION%2==1)
			{
				int x;
				L.Retrieve(LOCATION,x);
				L1.Insert(i,x);
				i++;
				p=p->right;
//				cout<<"+++"<<p<<endl;
			}
//				if(LOCATION%2==0)
				else
			{
				int x;
				L.Retrieve(LOCATION,x);
				L2.Insert(j,x);
				j++;
				p=p->right;
			}
		}
		return* this;
	}
//**************************************************************
//********************************************************
	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> L,L1,L2;
	L.Insert(0,14);
	L.Insert(1,24);
	L.Insert(2,34);
	L.Insert(3,44);
	L.Insert(4,54);
	L.Insert(5,64);
	L.Insert(6,74);
	L.Insert(7,84);
	L.Insert(8,94);
	L.Insert(9,104);
	L.Insert(10,114);
	L.Insert(11,124);
	L.Insert(12,134);
	L.Insert(13,144);
	L.Insert(14,154);
	L.Insert(15,164);
	L.Insert(16,174);
//	L.Insert(17,184);

cout<<"被拆分的表為： ";
	L.PrintList();
	cout<<endl;
    L.SPLIT(L,L1,L2);
	cout<<"奇位置構(gòu)成的表為：";
	L1.PrintList();
	cout<<endl;
	cout<<"偶位置構(gòu)成的表為：";
	L2.PrintList();
	cout<<endl;
	cout<<endl;
	return 0;
}