//linkedListDev.c
//John T. Rine
//October 28, 2011


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

struct Node
{
	int data;
	struct Node * prev;
	struct Node * next;
};

typedef struct Node node;

void createList(node **, node **, int);
void destroyListHead(node *);
void destroyListTail(node *);
int listSizeHead(node *);
int listSizeTail(node *);
void printIntDataHead(node *);
void insert(node **, node **, int, int);
void append(node **, node **, int, int);
void deleteNode(node **, node **, int);
void loadListData(node *);
void loadNode(node *, int, int);
void createNode(node*, node*);
void copyList(node *, node **, node **);
int findData(node *, int);

int main(int argc, char **argv)
{
	
	node *head, *tail, *copyHead, *copyTail, *temp;
	head = tail = copyHead = copyTail = NULL;

	int i = 1;

	printf("Creating a list of 4 nodes...\n");
	createList(&head, &tail, 4);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printf("Load list data\n");
	loadListData(head);
	printIntDataHead(head);
	printf("Inserting node 0 with data of 3200 before head node...\n");
	insert(&head, &tail, 0, 3200);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printIntDataHead(head);
	printf("Inserting node with data of -3200 before tail node...\n");
	insert(&head, &tail, listSizeHead(head) - 1, -3200);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printIntDataHead(head);
	printf("Appending node with data of 2300 after head node...\n");
	append(&head, &tail, 0, 2300);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printIntDataHead(head);
	printf("Appending node with data of -2300 after tail node...\n");
	append(&head, &tail, listSizeHead(head) - 1, -2300);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printIntDataHead(head);
	printf("Loading node 0 with data of 0...\n");
	loadNode(head, 0, 0);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printIntDataHead(head);
	printf("Loading tail node with data of 255...\n");
	loadNode(head, listSizeHead(head) - 1, 255);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printIntDataHead(head);
	printf("Deleting head node...\n");
	deleteNode(&head, &tail, 0);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printIntDataHead(head);
	printf("Deleting tail node...\n");
	deleteNode(&head, &tail, listSizeHead(head) - 1);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printIntDataHead(head);
	printf("Deleting node 2...\n");
	deleteNode(&head, &tail, 2);
	printf("Size of the list is: %d\n", listSizeHead(head));
	printIntDataHead(head);
	copyList(head, &copyHead, &copyTail);
	printf("Size of the list is: %d\n", listSizeHead(copyHead));
	printIntDataHead(copyHead);
	printf("The node location of 3 is %d\n", findData(copyHead, 3));

	destroyListHead(head);
	return 0;
}

void createList(node **headd, node **taill, int elements)
{
	int i;
	node *new, *head, *tail;
	new = head  = tail = NULL;

	for(i = 1; i<=elements; i++)
	{
		if (head == NULL)
		{
			head = (node *) malloc(sizeof(node));
			tail = head;
			head->prev = NULL;
			head->next = NULL;
		}
		else
		{
			new = (node *) malloc(sizeof(node));
			new->prev = tail;
			new->next = NULL;
			tail->next = new;
			tail = new;
		}
	}
	*headd = head;
	*taill = tail;
}

void destroyListHead(node *head)
{
	node *temp;
	node *temp2;
	temp = NULL;
	temp2 = NULL;
	temp = head;
	while(temp != NULL)
	{
		temp2 = temp->next;
		if (temp->prev != NULL) temp->prev = NULL;
		if (temp->next != NULL) temp->next = NULL;
		free(temp);
		temp = temp2;	
	}
}

void destroyListTail(node *tail)
{
	node *temp;
	node *temp2;
	temp = NULL;
	temp2 = NULL;
	temp = tail;
	while(temp != NULL)
	{
		temp2 = temp->prev;
		if (temp->prev != NULL) temp->prev = NULL;
		if (temp->next != NULL) temp->next = NULL;
		free(temp);
		temp = temp2;	
	}
}

int listSizeHead(node *head)
{
	int size = 0;
	while (head != NULL)
	{	
		head = head->next;
		size++;
	}
	return size;
}

int listSizeTail(node *tail)
{
        int size = 0;
        while (tail != NULL)
        {
                tail = tail->prev;
                size++;
        }
        return size;
}

void printIntDataHead(node * head)
{
	node * temp = NULL;
	
	temp = head;
	while(temp != NULL)
	{
		printf("%d ",temp->data);
		temp = temp->next;
	}
	printf("\n");
}

void insert(node ** head, node ** tail, int position, int data)
{
	int i;
	node *temp, *temp2;
	temp = temp2 = NULL;

	temp = *head;
	for(i = 0; i < position; i++)
	{
		temp = temp -> next;
	}

		if (*head == NULL)
		{
			*head = (node *) malloc(sizeof(node));
			*tail = *head;
			(*head)->prev = NULL;
			(*head)->next = NULL;
			(*head)->data = data;
		}
		else if (*head == temp)
		{
			temp2 = (node *) malloc (sizeof(node));
			temp2->next = *head;
			(*head)->prev = temp2;
			*head = (*head)->prev;
			(*head)->prev = NULL;
			(*head)->data = data;
		}
		else
		{
			temp2 = (node *) malloc (sizeof(node));	
			temp2->next = temp;
			temp2->prev = temp->prev;
			temp->prev->next = temp2;
			temp->prev = temp2;
			temp2->data = data;
		}
}

void append(node **head, node **tail, int position, int data)
{
	int i;
	node *temp, *temp2;
	temp = temp2 = NULL;

	temp = *head;
	for(i = 0; i < position; i++)
	{
		temp = temp -> next;
	}

		if (*head == NULL)
		{
			*head = (node *) malloc(sizeof(node));
			*tail = *head;
			(*head)->prev = NULL;
			(*head)->next = NULL;
			(*head)->data = data;
		}
		else if (*tail == temp)
		{
			temp2 = (node *) malloc (sizeof(node));
			temp2->prev = *tail;
			temp2->next = NULL;
			(*tail)->next = temp2;
			*tail = temp2;
			(*tail)->data = data;
		}
		else
		{
			temp2 = (node *) malloc (sizeof(node));
			temp2->prev = temp;
			temp2->next = temp->next;
			temp->next->prev = temp2;
			temp->next = temp2;
			temp2->data = data;
			
		}

}

void deleteNode(node **head, node **tail, int position)
{
	int i;
	node * temp = NULL;

	temp = *head;
	for(i = 0; i < position; i++)
	{
		temp = temp->next;
	}
	if(temp != *head && temp != *tail)
	{
		temp->next->prev = temp->prev;
		temp->prev->next = temp->next;
		temp->prev = NULL;
		temp->next = NULL;
	}
	else if (temp == *head)
	{
		temp->next->prev = NULL;
		*head = temp->next;
		temp->next = NULL;
	}
	else
	{
		temp->prev->next = NULL;
		*tail = temp->prev;
		temp->prev = NULL;
	}
	free(temp);
}

void loadListData(node *head)
{
	int i = 0;
	node *temp = NULL;
	temp = head;
	printf("Enter a value or -1 to quit: ");
	scanf("%d", &i);
	while(i != -1)
	{
		temp->data = i;
		temp = temp->next;
		if(temp == NULL)
		{
			printf("List is full of data!\n");
			break;
		}
		printf("Enter a value or -1 to quit: ");
		scanf("%d", &i);
	}

}


void loadNode(node *head, int position, int value)
{
	int i;
	node *temp = NULL;
	temp = head;

	temp = head;
	for(i = 0; i < position; i++)
	{
		temp = temp->next;
	}
	temp->data = value;
}

void createNode(node* head, node* tail)
{
	head = (node *) malloc(sizeof(node));
	tail = head;
	head->prev = NULL;
	head->next = NULL;
}

void copyList(node *head, node **copyHead, node **copyTail)
{
	node *new, *temp;
	new = *copyHead = *copyTail = temp = NULL;
	temp = head;
	while(temp != NULL)
	{
		if (*copyHead == NULL)
		{
			*copyHead = (node *) malloc(sizeof(node));
			*copyTail = *copyHead;
			(*copyHead)->prev = NULL;
			(*copyHead)->next = NULL;
			(*copyHead)->data = temp->data;
		}
		else
		{
			new = (node *) malloc(sizeof(node));
			new->prev = *copyTail;
			new->next = NULL;
			(*copyTail)->next = new;
			*copyTail = new;
			(*copyTail)->data = temp->data;
		}
		temp = temp->next;
	}
}

int findData(node *head, int data)
{
	int counter = 0;
	while(head != NULL)
	{
		if(head->data == data) break;
		counter++;
		head = head->next;
	}
	return counter;
}