#include "stdio.h"
#include <malloc.h>

#define OK                 1
#define ERROR              0
#define OVERFLOW          -1
#define TRUE               1
#define FALSE              0

typedef int ElemType;
typedef int Status;

typedef struct DulNode
{
	ElemType data;
	DulNode *next,*pre;
}DulNode,*DuLinkList;

Status InitList(DuLinkList &L)
{
	L = (DuLinkList)malloc(sizeof(DulNode));
	if(!L) return OVERFLOW;
	L->pre = L->next = L;
	return OK;
}

Status DestroyList(DuLinkList &L)
{
	DulNode *p,*q;
	q = p = L->next;
	while(p != L)
	{
		p = p->next;
		free(q);
		q = p;
	}
	free(L);
	L = NULL;
	
	return OK;
}

Status ClearList(DuLinkList &L)
{
	DulNode *p,*q;
	q = p = L->next;
	while(p != L)
	{
		p = p->next;
		free(q);
		q = p;
	}
	L->next = L->pre = L;
	return OK;
}

Status ListEmpty(DuLinkList &L)
{
	if(L->next == L && L->pre == L)
		return TRUE;
	else
		return FALSE;
}

int LocateElem(DuLinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{
	int i = 0;
	DulNode *p = L->next;
	while(p != L)
	{
		++i;
		if(compare(p->data,e))
			return i;
		p = p->next;
	}
	return 0;
}

Status PriorElem(DuLinkList L,ElemType cur_e,ElemType &pre_e)
{
	DulNode *p;
	p = L->next->next;
	while(p != L)
	{
		if(p->data == cur_e)
		{
			pre_e = p->pre->data;
			return TRUE;
		}
		p = p->next;
	}	
	return FALSE;
}

Status NextElem(DuLinkList &L,ElemType cur_e,ElemType &next_e)
{
	DulNode *p;

	p = L->next->next;
	while(p != L)
	{
		if(p->pre->data == cur_e)
		{
			next_e = p->data;
			return TRUE;
		}
		p = p->next;
	}
	return FALSE;
}

int ListLength(DuLinkList L)
{
	int i = 0;
	DulNode *p = L;
	while(p->next != L)
	{
		p = p->next;
		++i;
	}
	return i;
}

DulNode *GetElemP(DuLinkList L,int i)
{
	DulNode *p = L;
	int j;
	for(j = 0;j < i; ++j)
	{
		p = p->next;
	}
	return p;
}

Status GetElem(DuLinkList L,int i,ElemType &e)
{
	int j;
	DulNode *p = L;
	if(i < 0 || i > ListLength(L)) return ERROR;
	for(j = 0;j < i; ++j)
	{
		p = p->next;
	}
	e = p->data;
	return OK;
}

Status ListInsert(DuLinkList &L,int i,ElemType e)
{
	DulNode *p,*q;
	if(i < 1 || i > ListLength(L) + 1) return ERROR;
	p = GetElemP(L,i-1);

	q = (DuLinkList)malloc(sizeof(DulNode));
	if(!q) return OVERFLOW;
	
	q->next = p->next;
	p->next->pre = q;
	p->next = q;
	q->pre = p;
	q->data = e;

	return OK;
}

Status ListDelete(DuLinkList &L,int i,ElemType &e)
{
	DulNode *p;
	p = L->next;
	if(i < 0 || i > ListLength(L))
		return ERROR;
	p = GetElemP(L,i);

	p->pre->next = p->next;
	p->next->pre = p->pre;
	e = p->data;
	free(p);

	return OK;
}

void ListTraverse(DuLinkList L,void(*print)(ElemType))
{
	DulNode *p = L->next;
	while(p != L)
	{
		print(p->data);
		p = p->next;
	}
	printf("\n");
}

void ListTraverseBack(DuLinkList &L,void(*visit)(ElemType))
{
	DulNode *p = L->pre;
	while(p != L)
	{
		visit(p->data);
		p = p->pre;
	}
	printf("\n");
}

Status compare(ElemType e1,ElemType e2)
{
	if(e1 == e2)
		return TRUE;
	else
		return FALSE;
}

void print(ElemType e)
{
	printf("%d ",e);
}

int main()
{
	DuLinkList L;
	InitList(L);
	int i,n;
	Status j;
	ElemType e;
	for(i = 1; i < 5 ; ++i)
	{
		ListInsert(L,i,i);
	}
	printf("Output double link list:\n");
	ListTraverse(L,print);
	printf("Inverted order output double link list\n");
	ListTraverseBack(L,print);
	n = 2;
	ListDelete(L,n,e);
	printf("The deleted number is %d,which is %dth node:\n",e,n);
	printf("Output double link list:\n");
	ListTraverse(L,print);
	printf("Number of linklist is:%d\n",ListLength(L));
	printf("Is it empty? %d(1:YES 0:NO)\n",ListEmpty(L));
	ClearList(L);
	printf("Is it empty? %d(1:YES 0:NO)\n",ListEmpty(L));
	for(i = 1;i < 5; ++i)
	{
		ListInsert(L,i,i);
	}
	printf("Output double link list:\n");
	ListTraverse(L,print);
	n = 3;
	j = GetElem(L,n,e);
	if(j)
		printf("The %dth element of linklist is:%d\n",n,e);
	else
		printf("There is no %dth element.\n",n);
	e = 4;
	n = LocateElem(L,e,compare);
	if(n)
		printf("Equal %d number is %dth\n",e,n);
	else
		printf("There is no number\n");
	j = PriorElem(L,e,n);
	if(j)
		printf("%d pre number is %d\n",e,n);
	else
		printf("There is no precursor\n");
	j = NextElem(L,e,n);
	if(j)
		printf("%d next number is %d\n",e,n);
	else
		printf("There is no next number ater %d\n",e);
	DestroyList(L);

	return 0;
}