// ADS, Uebungsblatt 2, Aufgabe 2
// 03.11.2009
// Andreas Loibl <aloibl@mytum.de>

#include <stdio.h>
#include <stdlib.h>

struct node
{
	int data;
	unsigned int np;
};

node *new_node()
{
	node *n = (node *) malloc(sizeof(node));
	n->np = NULL;
	return n;
}

node *next(node *cur, node *prev)
{
	return (struct node*)(cur->np ^ (unsigned int)prev);
}

node *prev(node *cur, node *next)
{
	return (struct node*)(cur->np ^ (unsigned int)next);
}

node *insert(node *after, node *before, int data)
{
	node *tmp = new_node();
	tmp->data = data;
	tmp->np = (unsigned int)after ^ (unsigned int)before;
	after->np ^= (unsigned int)before ^ (unsigned int)tmp;
	before->np ^= (unsigned int)after ^ (unsigned int)tmp;
	return tmp;
}

node *search_node(int value, node *head, node *tail, node** prev_ptr)
{
	node *next_ptr = NULL;
	*prev_ptr = NULL;
	node *cur_ptr = head;

	while(next(cur_ptr, *prev_ptr)!=tail)
	{
		next_ptr = next(cur_ptr, *prev_ptr);
		*prev_ptr = cur_ptr;
		cur_ptr = next_ptr;
		if(cur_ptr->data == value) return cur_ptr;
	}
	return NULL;
}

void delete_node(node *prev_ptr, node *del)
{
	node *next_ptr = next(del, prev_ptr);
	prev_ptr->np ^= (unsigned int)del;
	prev_ptr->np ^= (unsigned int)next_ptr;
	next_ptr->np ^= (unsigned int)del;
	next_ptr->np ^= (unsigned int)prev_ptr;
	free(del);	
}

int main(int argc, char *argv[])
{
	node *head = new_node();
	node *tail = new_node();
	head->np = (unsigned int)tail;
	tail->np = (unsigned int)head;
	node *cur_ptr = head;
	node *prev_ptr = NULL;
	node *next_ptr = NULL;

	printf("head: 0x%X, ", (unsigned int)head);
	printf("tail: 0x%X\n", (unsigned int)tail);

	// fill list
	for(int i=0; i < 17; i++)
	{
		cur_ptr = insert(cur_ptr, tail, i);
		printf("node %d: 0x%X\n", i, (unsigned int)cur_ptr);
	}

	// print
	printf("\nlist:\n");
	prev_ptr = NULL;
	cur_ptr = head;
	while(next(cur_ptr, prev_ptr)!=tail)
	{
		next_ptr = next(cur_ptr, prev_ptr);
		prev_ptr = cur_ptr;
		cur_ptr = next_ptr;
		printf("data: %d, addr: 0x%X, prev: 0x%X, next: 0x%X, np: 0x%X\n", cur_ptr->data, (unsigned int)cur_ptr, (unsigned int)prev_ptr, (unsigned int)next(cur_ptr, prev_ptr), cur_ptr->np);
	}
	
	// search node with value 7
	if((cur_ptr = search_node(7, head, tail, &prev_ptr)))
	{
		printf("\nfound node with value 7 at 0x%X, will delete the next 4 nodes now.\n", (unsigned int)cur_ptr);
		// delete the following 4 nodes (8,9,10,11)
		for(int i=0; i < 4; i++)
		{
			printf("deleted node (data: %d, addr: 0x%X)\n", next(cur_ptr, prev_ptr)->data, (unsigned int)next(cur_ptr, prev_ptr));
			delete_node(cur_ptr, next(cur_ptr, prev_ptr));
		}
	}
	else
	{
		printf("\nno node with value 7 found.\n");
	}

	// mirror
	node *tmp;
	tmp = head;
	head = tail;
	tail = tmp;

	// print
	printf("\nmirrored list:\n");
	prev_ptr = NULL;
	cur_ptr = head;
	while(next(cur_ptr, prev_ptr)!=tail)
	{
		next_ptr = next(cur_ptr, prev_ptr);
		prev_ptr = cur_ptr;
		cur_ptr = next_ptr;
		printf("data: %d, addr: 0x%X, prev: 0x%X, next: 0x%X, np: 0x%X\n", cur_ptr->data, (unsigned int)cur_ptr, (unsigned int)prev_ptr, (unsigned int)next(cur_ptr, prev_ptr), cur_ptr->np);
	}

	// delete all nodes
	prev_ptr = NULL; cur_ptr = head;
	while(next(cur_ptr, prev_ptr)!=tail) delete_node(cur_ptr, next(cur_ptr, prev_ptr));	

	// delete head and tail
	free(head);
	free(tail);

	return 0;
}