#include <stdio.h>

#ifdef MEMDBG
#include "memdbg.h"
#endif

typedef struct LIST *list;

typedef struct LIST {
/* a list of objects */
	list obj;		/* the data item, most likely a pointer of some
						type */
	list next;
	list prev;
	} listd;

/* notes:	root->obj!=NULL */

list newlist()
/* return a new list */
{
	list tmp;

	tmp=(list)malloc(sizeof(listd));
	if(tmp!=NULL)
	{
		tmp->next=NULL;
		tmp->prev=NULL;
		tmp->obj=tmp;
	}
	return(tmp);
}

list addnode(root, obj)
/* adds the object to the list after the current node */
/* returns root if ok, 0 if not */
list root;
void *obj;
{
	list tmp;
	list node=root->obj;

	tmp=(list)malloc(sizeof(listd));
	if(tmp!=NULL)
	{
		tmp->obj=obj;
		tmp->next=node->next;
		tmp->prev=node;
		node->next=tmp;
		if(tmp->next!=NULL)
			tmp->next->prev=tmp;
		root->obj=tmp;
		return(root);
	}
	else
		return((list)0);
}

list findnode(root, obj)
/* finds the object in the list, and sets it to be the current node */
/* returns root if ok, 0 if not */
list root;
void *obj;
{
	list node=root->next;

	for(;node!=NULL;node=node->next)
		if(node->obj==obj)
			break;
	if(node!=NULL)
	{
		root->obj=node;
		return(root);
	}
	else
		return((list)0);
}

list rmnode(n)
/* removes the node n from the list */
list n;
{
	list r;

	if(n->prev==NULL)
		return(n);
	
	n->prev->next=n->next;
	if(n->next!=NULL)
		n->next->prev=n->prev;
	r=n->prev;

	free(n);

	return(r);
}

list rmcurr(root)
/* removes the current node from the list */
list root;
{
	list node=root->obj;

	if(node!=root)
	{
		root->obj=node->next;
		if(root->obj==NULL)
			root->obj=node->prev;

		node->prev->next=node->next;
		if(node->next!=NULL)
			node->next->prev=node->prev;
		free(node);
	}
	return(root);
}

int setcurr(root, obj)
list root;
void *obj;
{
	list node=root->obj;

	if(node!=root)
	{
		node->obj=obj;
		return(1);
	}
	else
		return(0);
}

void freelist(root)
/* frees the memory for the list (but not the objects) */
list root;
{
	list tmp;

	while(root!=NULL)
	{
		tmp=root->next;
		free(root);
		root=tmp;
	}
}

list listnode(root)
list root;
/* returns a pointer to the current node */
{
	return(root->obj);
}

list setnode(root, node)
list root, node;
/* sets the current node to be node */
/* returns root if ok, 0 if not */
{
	root->obj=node;
	return(root);
}

list endlist(root)
/* set current to last node in list */
list root;
{
	root->obj=root;
	while(root->obj->next!=NULL)
		root->obj=root->obj->next;
	return(root);
}

list startlist(root)
/* sets current to before first in list */
/* (next will give first node) */
list root;
{
	root->obj=root;
	return(root);
}

list listgonext(root)
/* sets current to next node in list */
list root;
{
	if(root->obj->next!=NULL)
		root->obj=root->obj->next;
	return(root);
}

list lastnode(root)
/* returns last node in list */
list root;
{
	if(root!=NULL)
		while(root->next!=NULL)
			root=root->next;
	return(root);
}

list listgoprev(root)
/* sets current to the previous node in list */
list root;
{
	if(root->obj->prev!=root)
		root->obj=root->obj->prev;
	return(root);
}

void *listnext(root)
/* sets current to next node in list, and returns that object */
list root;
{
	if(root->obj->next==NULL)
		return(NULL);
	else
		return((root->obj=root->obj->next)->obj);
}

void *listprev(root)
/* sets current to the previous node in list, and returns that object */
list root;
{
	if(root->obj->prev==root)
		return(NULL);
	else
		return((root->obj=root->obj->prev)->obj);
}

void *listcurr(root)
/* returns the current object */
list root;
{
	if(root->obj==root)
		return(NULL);
	else
		return(root->obj->obj);
}

int listlastp(root)
/* returns true if current is last in list */
list root;
{
	return(root->obj->next==NULL);
}

int listfirstp(root)
/* returns true if current is first in list */
list root;
{
	return(root->obj->prev==root);
}

int listemptyp(root)
/* returns true if there is nothing in the list */
list root;
{
	return(root->next==NULL);
}

#ifdef TESTING
printlist(root)
list root;
{
	list tmp;

	printf("(");
	for(tmp=root->next;tmp!=NULL;tmp=tmp->next)
		printf("%s%d ", tmp==root->obj?"+":"", tmp->obj);
	printf(")\n");
}
error(string)
char *string;
{
	printf("Error: %s\n", string);
	exit(0);
}
t_list()
{
	list this;

	this=newlist();
	printf("should be: ()\n");
	printlist(this);
	if(listcurr(this)!=NULL)
		error("listcurr(newlist())!=NULL");
	if(!listemptyp(this))
		error("listemptyp(newlist()) not true");
	addnode(this, (void *)25);
	printf("should be: (+25)\n");
	printlist(this);
	if(listemptyp(this))
		error("list empty after adding a node");
	if(!listlastp(this))
		error("listlastp says no when at end of list");
	addnode(this, (void *)50);
	printf("should be: (25 +50)\n");
	printlist(this);
	if(listcurr(this)!=(void *)50)
		error("not setting current on addnode");
	if(!listlastp(this))
		error("listlastp=no when at end of list, or not adding after node");
	rmcurr(this);
	printf("should be: (+25)\n");
	printlist(this);
	if(listcurr(this)!=(void *)25)
		error("rmcurr didn't work, or not setting current on rmcurr");
	rmcurr(this);
	printf("should be: ()\n");
	printlist(this);
	if(listcurr(this)!=NULL)
		error("after removing all nodes, listcurr doesn't say NULL");
	if(!listemptyp(this))
		error("list not empty after addnode and rmcurr");
	if(listnext(this)!=NULL)
		error("after removing all nodes, listnext doesn't say NULL");
	addnode(this, (void *)25);
	printf("should be: (+25)\n");
	printlist(this);
	if(listnext(this)!=NULL)
		error("current not reset after addnode, or problem with listnext");
	if(listcurr(this)!=(void *)25)
		error("problem with listcurr, or listnext moves at end of list");
	if(listnext(startlist(this))!=(void *)25)
		error("addnode(25);listnext(startlist(this))!=25");
	if(listnext(this)!=NULL)
		error("listnext doesn't return NULL at end of list");
	if(!listfirstp(this))
		error("listfirstp says no at first in list");
	if(!listlastp(this))
		error("listlastp says no at end of list");
	startlist(this);
	addnode(this, (void *)50);
	printf("should be: (+50 25)\n");
	printlist(this);
	if(listcurr(this)!=(void *)50)
		error("startlist();addnode(50);listcurr()!=50");
	if(!listfirstp(this))
		error("startlist();addnode(50);listfirstp() says no");
	if(listnext(this)!=(void *)25)
		error("new();add(25);start();add(50);next()!=25");
	printf("should be: (50 +25)\n");
	printlist(this);
	if(listprev(this)!=(void *)50)
		error("addnode(25);startlist();addnode(50);listnext();listprev()!=50");
	printf("should be: (+50 25)\n");
	printlist(this);
	if(!listfirstp(this))
		error("listfirstp says no at first in list");
	listnext(this);
	printf("should be: (50 +25)\n");
	printlist(this);
	if(!listlastp(this))
		error("listlastp says no at end of list");
	listprev(this);
	printf("should be: (+50 25)\n");
	printlist(this);
	addnode(this, (void *)75);
	printf("should be: (50 +75 25)\n");
	printlist(this);
	listprev(this);
	if(listcurr(this)!=(void *)50)
		error("(+50 25);add(75);prev()!=50");
	if(listnext(this)!=(void *)75)
		error("(+50 25);add(75);prev();next()!=75");
	if(listnext(this)!=(void *)25)
		error("(+50 25);add(75);prev();next();next()!=25");
	startlist(this);
	printf("should be: (50 75 25)\n");
	printlist(this);
	if(listcurr(this)!=NULL)
		error("(50 75 +25);start();listcurr()!=NULL");
	endlist(this);
	if(listcurr(endlist(this))!=(void *)25)
		error("(50 75 25);end();listcurr(end())!=25");
	endlist(this);
	if(listcurr(this)!=(void *)25)
		error("(50 75 +25);end();listcurr()!=25,end fails when at end");
	printf("should be: (50 75 +25)\n");
	printlist(this);
	{
		list tmp;

		tmp=listnode(this);
		if(listprev(listgoprev(this))!=(void *)50)
			error("(50 75 +25);prev(goprev())!=50");
		printf("should be: (+50 75 25)\n");
		printlist(this);
		if(listcurr(listgonext(this))!=(void *)75)
			error("(+50 75 25);curr(gonext())!=75");
		printf("should be: (50 +75 25)\n");
		printlist(this);
		if(listcurr(setnode(this, tmp))!=(void *)25)
			error("(50 75 +25);tmp=listnode();curr(setnode(tmp))!=25");
		printf("should be: (50 75 +25)\n");
		printlist(this);
	}
	rmcurr(this);
	rmcurr(this);
	rmcurr(this);
	printf("should be: ()\n");
	printlist(this);
	if(!listemptyp(this))
		error("(50 75 25);end();rmcurr*3();emptyp() not true");
	if(listcurr(endlist(this))!=NULL)
		error("endlist() fails with empty list");
	freelist(this);
	this=newlist();
	for(i=1;i<40;i++)
		addnode(this, (void *)i);
	printlist(this);
	printf("Sacrifice to the gods!  It all works!\n");
}
#endif /* TESTING */