//header.h

#include<iostream>

using namespace std;

/*

 * 双向循环链表头文件，

 * 其声明中封装有指向链表附加头节点的头x指针first

 */

template<class T>

struct DbNode

{

	T data;

	DbNode<T> *pred, *next;

	DbNode(T value, DbNode<T> *a = NULL, DbNode<T> *b = NULL):\

		data(value), pred(a), next(b){}

	DbNode(DbNode<T> *a = NULL, DbNode<T> *b = NULL):pred(a), next(b){}

};

template<class T>

class Dblist

{

private: DbNode<T> *first;

public:

	Dblist(T value);

 	~Dblist(){makeEmpty();}

	void makeEmpty();

	int Length()const;

	bool IsEmpty(){return (this->first->pred == this->pred);}

	DbNode<T> *getHead()const{return this->first;}

	DbNode<T> *Locate(int i, int d);

	DbNode<T> *Search(const T& x);

	bool Insert(int i, const T& x, int d);

	bool Remove(int i, T& x, int d);

	void Print(int d);

};

template<class T>

int Dblist<T>::Length()const

{

	DbNode<T> *tmp = this->first;

	int i = 1;

	while(tmp->next!=this->first)

	{

		++i;

		tmp = tmp->next;

	}

	return i;

}

template<class T>

bool Dblist<T>::Remove(int i, T& x, int d)

{

	DbNode<T> *p = this->Locate(i, d);

	if(!p)

		return false;

	x = p->data;

	if(p==this->first && this->Length()>1)

		this->first = p->next;

	else

		cout<<"仅有头节点的双向循环链表已被删除！请勿在没添加新元素前对其调用。"<<endl;

	p->pred->next = p->next;

	p->next->pred = p->pred;

	delete p;

	return true;

}

template<class T>

DbNode<T>* Dblist<T>::Search(const T& x)

{

	DbNode<T> *tmp = this->first;

	do

	{

		if(tmp->data==x)

		{

			cout<<"address of x is "<<tmp<<"   x = "<<tmp->data<<endl;

			return tmp;

		}

		tmp = tmp->pred;

	}while(tmp!=this->first);

	return NULL;

}

template<class T>//定位元素，d=0时从头节点向前(pred)查第i个元素，d!=0时，从头节点向后(next)找第i个元素

DbNode<T>* Dblist<T>::Locate(int i, int d)

{

	if(this->first->next==this->first || i==0)

		return this->first;

	int t = 1;

	DbNode<T>* tmp = this->first;

	if(d)				//向后找

	{

		while(tmp->next!=this->first && t!=i)//查找到的条件为，在没把双向循环链表遍历一遍前，t=i

		{

			tmp = tmp->next;

			++t;

		}

		if(tmp->next==this->first&&t!=i)

			return NULL;

		else

			return tmp;

	}

	else				//向前找

	{

		while(tmp->pred!=this->first && t!=i)

		{

			tmp = tmp->pred;

			++t;

		}

		if(tmp->pred==this->first&&t!=i)

			return NULL;

		else

			return tmp;

	}

}

template<class T>

bool Dblist<T>::Insert(int i, const T& x, int d)

{

	DbNode<T> *p = this->Locate(i, d);

	if(!p)

		return false;

	DbNode<T> *newnode = new DbNode<T>;

	if(newnode==NULL)

	{

		cout<<"申请内存错误！"<<endl;

		exit(1);

	}

	newnode->data = x;

	if(d)			//p节点后插入

	{

		p->next->pred = newnode;

		newnode->pred = p;

		newnode->next = p->next;

		p->next = newnode;

	}

	else			//p节点前插入

	{

		p->pred->next = newnode;

		newnode->next = p;

		newnode->pred = p->pred;

		p->pred = newnode;

	}

	return true;

}

template<class T>

void Dblist<T>::makeEmpty()

{

	DbNode<T> *p, *q = this->first->pred;

	while(q != this->first)

	{

		p = q;

		q = q->pred;

		delete p;

	}

}

template<class T>

void Dblist<T>::Print(int d)

{

	if(d)			//正序打印

	{

		cout<<"Positive order: ";

		DbNode<T> *tmp = this->first;

		while(tmp->next != this->first)

		{

			cout<<tmp->data<<"->";

			tmp = tmp->next;

		}

		cout<<tmp->data<<"->over."<<endl;

	}

	else			//逆序打印

	{

		DbNode<T> *tmp = this->first;

		cout<<"Reverse sequence: ";

		while(tmp->pred != this->first)

		{

			cout<<tmp->data<<"->";

			tmp = tmp->pred;

		}

		cout<<tmp->data<<"->over."<<endl;

	}

}

template<class T>

Dblist<T>::Dblist(T value)

{

	this->first = new DbNode<T>(value);

	if(this->first == NULL)

	{

		cerr<<"内存分配错误！"<<endl;

		exit(1);

	}

	this->first->next = this->first->pred = this->first;

}

//main.cpp

#include"header.h"

int main()

{

	Dblist<int> dl(888);

	dl.Print(0);

	for(int i=1; i<=4; ++i)

	{

		dl.Insert(1, i, 0);

	}

	dl.Print(1);

	int l = 999, k = 0;

	dl.Insert(0, l, 0);

	//int k = 0;

	dl.Print(1);

	dl.Remove(0, k, 0);

	dl.Print(1);

	k = 5;

　　　　 dl.Search(k);
　　　　 dl.Print(0);

	return 0;

}