/* Various functions for dealing with Linked Lists. 05-02-2005 */

#include <stdlib.h>

#define ERROR	1
#define SUCCESS	0

typedef struct dlist_node {
	int key;
	struct dlist_node *next;
	struct dlist_node *prev;
}LinkedListNode;

typedef struct dlist {
	LinkedListNode *Head;
	LinkedListNode *Tail;
	int length;
}LinkedList;

/**
 * Inserts the given node at the end of the list.
 *
 * @List    - the list into which the node is to be inserted.
 * @NewNode - the node to be inserted at the end of the list.
 */
void InsertLast(LinkedList *List, LinkedListNode *NewNode) {

	if (List->Head == NULL) {
		NewNode->prev = NULL;
		NewNode->next = NULL;
		List->Head = NewNode;
		List->Tail = NewNode;
	}

	else {
		NewNode->prev = List->Tail;
		NewNode->next = NULL;
		List->Tail->next = NewNode;
		List->Tail = NewNode;
	}

	List->length++;

	return;

}


/**
 * Inserts the given node at the beginning of the list.
 *
 * @List    - the list into which the node is to be inserted.
 * @NewNode - the node to be inserted at the beginning of the list.
 */
void InsertFirst(LinkedList *List, LinkedListNode *NewNode) {

	if (List->Head == NULL) {
		NewNode->prev = NULL;
		NewNode->next = NULL;
		List->Head = NewNode;
	}

	else {
		List->Head->prev = NewNode;
		NewNode->next = List->Head;
		NewNode->prev = NULL;
		List->Head = NewNode;
	}

	List->length++;

	return;

}


/**
 * Inserts the given node at the at the specified index in the list.
 *
 * @List    - the list into which the node is to be inserted.
 * @NewNode - the node to be inserted at the specified index in the list.
 * @index   - Index at which new node is to be inserted.
 *
 * @returns - 1 if the specified index is out of range; 0 otherwise.
 */
int Insert(LinkedList *List, LinkedListNode *NewNode, int index) {

	if (index < 0 || (index >= List->length && index > 0))
		return ERROR;

	if (index == 0) {
		InsertFirst(List, NewNode);
		return SUCCESS;
	}
	else {
		LinkedListNode *temp = List->Head;
		int i;

		for (i=0; i<index && temp->next; i++)
			temp = temp->next;

		if (!temp->next && i != index) {
			NewNode->prev = temp;
			NewNode->next = NULL;
			temp->next = NewNode;
		}
		else {
			NewNode->prev = temp->prev;
			NewNode->next = temp;
			if (NewNode->next)
				NewNode->next->prev = NewNode;
			NewNode->prev->next = NewNode;
		}

	}

	List->length++;

	return SUCCESS;
}


/**
 * Removes the node at the specified index in the list.
 *
 * @List    - the list from which the node is to be removed.
 * @index   - the index of the node to be removed from the list,
 *
 * @returns - 1 if the specified index is out of range; 0 otherwise.
 */
int Delete(LinkedList *List, int index) {

	LinkedListNode *temp = List->Head;
	int i;

	if (index < 0 || (index >= List->length && index > 0) || List->Head == NULL)
		return ERROR;


	for (i=0; i<index && temp->next; i++ )
		temp = temp->next;

	if (!temp->prev)
		List->Head = List->Head->next;
	else
		temp->prev->next = temp->next;

	if (temp->next)
		temp->next->prev = temp->prev;

	free(temp);

	List->length--;

	return SUCCESS;
}


/**
 * Replaces the node at the specified position in the list with
 * the specified element.
 *
 * @List    - the list into which the node is to be inserted.
 * @index   - index of node to replace.
 * @NewNode - node to be stored at the specified position.
 *
 * @returns - 1 if the specified index is out of range; 0 otherwise.
 */
int Set(LinkedList *List, LinkedListNode *NewNode, int index) {

	if (Delete(List, index))
		return ERROR;
	
	return Insert(List, NewNode, index);
}


/**
 * Returns the node at the specified position in this list.
 *
 * @List    - the list.
 * @index   - index of node to return.
 *
 * @returns - the node at the specified position in the list
 *            or NULL if the specified index is out of range.
 */
LinkedListNode *Get(LinkedList *List, int index) {

	LinkedListNode *temp = List->Head;
	int i;

	if (index < 0 || (index >= List->length && index > 0))
		return NULL;

	for(i=0 ; i<index && temp->next; i++ )
		temp = temp->next;

	return temp;
}


/**
 * Returns the number of nodes in the list.
 *
 * @List    - the list.
 *
 * @returns - the number of nodes in the list.
 */
int Length(LinkedList *List) {

	return List->length;

}