// Jevin Olano
// jolano
// CSE 101
// October 24, 2019
// List.c - implementation file for List ADT

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

const int tableSize = 101;

// structs ----------------------------------------------

// NodeObj
typedef struct NodeObj {
	int data;
	struct NodeObj* next;
	struct NodeObj* prev;
} NodeObj;

// Node
typedef NodeObj* Node;

typedef struct ListObj {
	Node front;
	Node back;
	Node cursor;
	int length; // # of elements in the List object
	int index; // numerical location of the cursor element
} ListObj;

// List
typedef ListObj* List;

#include "List.h"

// Constructors & Destructors ---------------------------

// newNode()
// constructor of the Node type
Node newNode(int d) {
	Node N = malloc(sizeof(NodeObj));
	assert(N != NULL);
	N->data = d;
	N->next = NULL;
	N->prev = NULL;
	return N;
}

// freeNode()
// frees heap memory pointed to by *pN, sets *pN to NULL
void freeNode(Node *pN) {
	if (pN != NULL && *pN != NULL) {
		free(*pN);
		*pN = NULL;
	}
}

// newList()
// returns reference to new empty List object.
List newList() {
	List L;
	L = malloc(sizeof(ListObj));
	L->front = NULL;
	L->back = NULL;
	L->cursor = NULL;
	L->length = 0;
	L->index = -1;
	return L;
}

// freeList()
// frees heap memory associated with List *pL, sets *pL to NULL
void freeList(List *pL) {
	if (pL != NULL && *pL != NULL) {
		clear(*pL);
		free(*pL);
		*pL = NULL;
	}
}

// Access Functions -------------------------------------

// length()
// returns the number of elements in L
int length(List L) {
	if (L == NULL) {
		fprintf(stderr, "Error: calling size() on NULL List reference\n");
		exit(1);
	}
	return L->length;
}

// index()
// Returns the index of cursor element if defined, returns -1 otherwise
int index(List L) {
	if (L == NULL) {
		fprintf(stderr, "Error: calling index() on NULL List reference\n");
		exit(1);
	}
	return L->index;
}

// front()
// Returns the front element of L
// pre: length() > 0
int front(List L) {
	if (L == NULL) {
		fprintf(stderr, "Error: calling front() on NULL List reference\n");
		exit(1);
	}
	if (isEmpty(L)) {
		fprintf(stderr, "Error: calling front() on an empty List\n");
		exit(1);
	}
	Node temp = L->front;
	return temp->data;
}

// back()
// Returns the back element of L
// pre: length() > 0
int back(List L) {
	if (L == NULL) {
		fprintf(stderr, "Error: calling back() on NULL List reference\n");
		exit(1);
	}
	if (isEmpty(L)) {
		fprintf(stderr, "Error: calling back() on an empty List\n");
		exit(1);
	}
	Node temp = L->back;
	return temp->data;
}

// get()
// Returns cursor element of L
// pre: length() > 0
int get(List L) {
	if (L == NULL) {
		fprintf(stderr, "Error: calling get() on NULL List reference\n");
		exit(1);
	}
	if (isEmpty(L)) {
		fprintf(stderr, "Error: calling get() on an empty List\n");
		exit(1);
	}
	if (L->cursor == NULL) {
		return -1;
	}
	Node temp = L->cursor;
	return temp->data;
}

// isEmpty()
// Returns true (1) if L is empty, otherwise returns false (0)
int isEmpty(List L) {
	if (L == NULL) {
		fprintf(stderr, "Error: calling isEmpty() on NULL List reference\n");
		exit(1);
	}
	return L->length==0;
}

// equals()
// Returns true(1) iff Lists A and B are in same state, and returns false(0) otherwise
int equals(List A, List B) {
	int eq = 0;
	Node nodeA = NULL;
	Node nodeB = NULL;
	if (A == NULL || B == NULL) {
		fprintf(stderr, "Error: calling equals() on NULL List reference\n");
		exit(1);
	}
	eq = (A->length == B->length);
	nodeA = A->front;
	nodeB = B->front;
	while (eq && nodeA != NULL) {
		eq = (nodeA->data == nodeB->data);
		nodeA = nodeA->next;
		nodeB = nodeB->next;
	}
	return eq;
}

// Manipulation Procedures ------------------------------

// clear()
// Resets L to its original empty state
void clear(List L) {
	while (!isEmpty(L)) {
		deleteFront(L);
	}
	L->cursor = NULL;
	L->index = -1;
}

// moveFront()
// If L is non-empty, sets cursor under the front element, otherwise does nothing
void moveFront(List L) {
	if (!isEmpty(L)) {
		L->cursor = L->front;
		L->index = 0;
	}
}

// moveBack()
// If L is non-empty, sets cursor under the back element, otherwise does nothing
void moveBack(List L) {
	if (!isEmpty(L)) {
		L->cursor = L->back;
		L->index = L->length - 1;
	}
}

// movePrev()
// If cursor is defined and not at front, move cursor one step toward the front of L;
// if cursor is defined and at front, cursor becomes undefined;
// if cursor is undefined do nothing
void movePrev(List L) {
	if (L->cursor != NULL) {
		L->cursor = L->cursor->prev;
		L->index--;
	}
}

// moveNext()
// If cursor is defined and not at back, move cursor one step toward the back of L;
// if cursor is defined and at back, cursor becomes undefined;
// if cursor is undefined do nothing
void moveNext(List L) {
	if (L->cursor != NULL) {
		L->cursor = L->cursor->next; // if cursor is on last Node, this automatically makes it null
		if (L->cursor != NULL) {
			L->index++;
		} else {
			L->index = -1;
		}
	}
}

// prepend()
// Insert new element into L
// If L is non-empty, insertion takes place before front element
void prepend(List L, int data) {
	Node node = newNode(data);
	if (isEmpty(L)) {
		L->front = node;
		L->back = node;
	} else {
		L->front->prev = node;
		node->next = L->front;
		L->front = node;
	}
	L->length++;
	if (L->cursor != NULL) {
		L->index++;
	}
}

// append()
// Insert new element into L
// If L is non-empty, insertion takes place after back element
void append(List L, int data) {
	Node node = newNode(data);
	if (isEmpty(L)) {
		L->front = node;
		L->back = node;
	} else {
		L->back->next = node;
		node->prev = L->back;
		L->back = node;
	}
	L->length++;
}

// insertBefore()
// Insert new element before cursor
// pre: length() > 0, index() >= 0
void insertBefore(List L, int data) {
	if (L == NULL) {
		fprintf(stderr, "Error: calling insertBefore() on NULL List reference\n");
		exit(1);
	}
	Node node = newNode(data);
	node->prev = L->cursor->prev;
	node->next = L->cursor;
	if (node->prev != NULL) {
		L->cursor->prev->next = node;
	} else {
		L->front = node;
	}
	L->cursor->prev = node;
	L->length++;
	L->index++;
}

// insertBefore() OLD CODE
/* void insertBefore(List L, int data) {
	if (L->cursor != NULL) {
		Node node = newNode(data);
		if (L->length == 0;) {
			L->front = node;
			L->back = node;
		}
		L->cursor->prev->next = node;
		node->prev = L->cursor->prev;
		L->cursor->prev = node;
		node->next = L->cursor;
		if (L->cursor == L->front) {
			L->front = node;
		}
		L->length++;
		L->index++;
	}
} */

// insertAfter()
// Insert new element after cursor
// pre: length() > 0, index() >= 0
void insertAfter(List L, int data) {
	if (L == NULL) {
		fprintf(stderr, "Error: calling insertAfter() on NULL List reference\n");
		exit(1);
	}
	Node node = newNode(data);
	node->next = L->cursor->next;
	node->prev = L->cursor;
	if (node->next != NULL) {
		L->cursor->next->prev = node;
	} else {
		L->back = node;
	}
	L->cursor->next = node;
	L->length++;
}

// insertAfter() OLD CODE
/* void insertAfter(List L, int data) {
	if (L->cursor != NULL) {
		Node node = newNode(data);
		L->cursor->next->prev = node;
		node->next = L->cursor->next;
		L->cursor->next = node;
		node->prev = L->cursor;
		if (L->cursor == L->back) {
			L->back = node;
		}
		L->length++;
	}
} */

// deleteFront()
// Delete the front element
// pre: length() > 0
void deleteFront(List L) {
	if (L == NULL) {
		fprintf(stderr, "Error: calling deleteFront() on NULL List reference\n");
		exit(1);
	}
	if (L->length == 0) {
		fprintf(stderr, "Error: calling deleteFront() on empty List reference\n");
		exit(1);
	}
	if (L->length == 1) {
		Node temp = L->front;
		free(temp);
		L->front = NULL;
		L->back = NULL;
		L->cursor = NULL;
		L->index = -1;
	} else {
		Node temp = L->front;
		L->front = L->front->next;
		L->front->prev = NULL;
		if (L->cursor != NULL) {
			L->index--;
		}
		free(temp);
	}
	L->length--;
}

// deleteFront() OLD CODE
/* void deleteFront(List L) {
	if (L == NULL) {
		fprintf(stderr, "Error: calling deleteFront() on NULL List reference\n");
		exit(1);
	}
	if (!isEmpty(L)) {
		Node front = L->front;
		L->front = L->front->next;
		if (L->front != NULL) {
			L->front->prev = NULL;
		}
		L->length--;
		if (L->cursor == front) {
			L->cursor = NULL;
			L->index = -1;
		}
		freeNode(&front);
	}
} */

// deleteBack()
// Delete the back element
// pre: length() > 0
void deleteBack(List L) {
	if (!isEmpty(L)) {
		Node back = L->back;
		L->back = L->back->prev;
		if (L->back != NULL) {
			L->back->next = NULL;
		}
		L->length--;
		if (L->cursor == back) {
			L->cursor = NULL;
			L->index = -1;
		}
		freeNode(&back);
	}
}

// delete()
// Delete cursor element, making cursor undefined
// pre: length() > 0, index() >= 0
void delete(List L) {
	if (L->cursor != NULL) {
		if (L->length == 0) { // one element in the List
			clear(L);
		} else if (L->cursor == L->front) { // cursor is in front
			deleteFront(L);
		} else if (L->cursor == L->back) { // cursor is in back
			deleteBack(L);
		} else { // cursor is in the middle somewhere
			L->cursor->prev->next = L->cursor->next;
			L->cursor->next->prev = L->cursor->prev;
			freeNode(&(L->cursor));
			L->cursor = NULL;
			L->index = -1;
			L->length--;
		}
	}
}

// Other Operations -------------------------------------

// printList()
// Prints to the file pointed to by out,
// a string representation of L consisting of a space separated sequence of integers,
// with front on left
void printList(FILE* out, List L) {
	if (!isEmpty(L)) {
		Node node = L->front;
		while (node != NULL) {
			if (node == L->front) {
				fprintf(out, "%d", node->data);
			} else {
				fprintf(out, " %d", node->data);
			}
			node = node->next;
		}
	}
}

// copyList()
// Returns a new List representing the same integer sequence as L.
// The cursor in the new list is undefined, regardless of the state of the cursor in L.
// The state of L is unchanged.
List copyList(List L) {
	List newL = newList();
	Node temp = L->front;
	if (isEmpty(L)) {
		return newL;
	}
	moveFront(L);
	while (temp != NULL) {
		append(newL, temp->data);
		moveNext(L);
	}
	return newL;
}