stuff

#include "linkedList.h"







#include <stdio.h> /* REMOVE LATER OR FAIL */









/*
    What is a linked list?
    A linked list is a set of dynamically allocated nodes, arranged in
    such a way that each node contains one value and one pointer.
    The pointer always points to the next member of the list.
    If the pointer is NULL, then it is the last node in the list.

    A linked list is held using a local pointer variable which
    points to the first item of the list. If that pointer is also NULL,
    then the list is considered to be empty.
    -----------------------------              -------------------------------
    |              |             |            \ |              |             |
    |     DATA     |     NEXT    |--------------|     DATA     |     NEXT    |
    |              |             |            / |              |             |
    ------------------------------              ------------------------------
*/

void insertFront(List_t* list, void* valref) {
    node_t** head = &(list->head);

    node_t* new_node;
    new_node = malloc(sizeof(node_t));

    new_node->value = valref;
    new_node->next = *head;

    *head = new_node;

    /* bug here: increment length by 1 after adding */
    list->length++;
}

void insertRear(List_t* list, void* valref) {
    node_t* head = list->head;
    node_t* current = head;
    while (current->next != NULL) {
        current = current->next;
    }

    current->next = malloc(sizeof(node_t));
    current->next->value = valref;
    current->next->next = NULL;
    list->length++;
}

void insertInOrder(List_t* list, void* valref) {
    if (list->length == 0) {
        insertFront(list, valref);
        return;
    }

    node_t** head = &(list->head);
    node_t* new_node;
    new_node = malloc(sizeof(node_t));
    new_node->value = valref;
    new_node->next = NULL;

    if (list->comparator(new_node->value, (*head)->value) <= 0) {
        new_node->next = *head;
        *head = new_node;
    } else {
        node_t* prev = *head;
        node_t* current = prev->next;
        while (current != NULL) {
            if (list->comparator(new_node->value, current->value) > 0) {
                if (current->next != NULL) {
                    prev = current;
                    current = current->next;
                } else {
                    current->next = new_node;
                    break;
                }
            } else {
                prev->next = new_node;
                new_node->next = current;
                break;
            }
        }
    }
    list->length++;
}

void* removeFront(List_t* list) {
    node_t** head = &(list->head);
    void* retval = NULL;
    node_t* next_node = NULL;

    if (list->length == 0) {
        return NULL;
    }

    next_node = (*head)->next;
    retval = (*head)->value;
    list->length--;

    /* bug here: must free the head before reassigning it */
    free(*head);

    *head = next_node;

    return retval;
}

void* removeRear(List_t* list) {
    if (list->length == 0) {
        return NULL;
    } else if (list->length == 1) {
        return removeFront(list);
    }

    void* retval = NULL;
    node_t* head = list->head;
    node_t* current = head;

    /* bug here: added another ->next to current->next->next */
    while (current->next->next != NULL) {
        current = current->next;
    }

    retval = current->next->value;
    free(current->next);
    current->next = NULL;
    list->length--;
    return retval;
}

/* indexed by 0 */
void* removeByIndex(List_t* list, int index) {
    if (list->length <= index) {
        return NULL;
    }

    node_t** head = &(list->head);
    void* retval = NULL;
    node_t* current = *head;
    node_t* prev = NULL;
    int i = 0;

    if (index == 0) {
	return removeFront(list);
        /*retval = (*head)->value;
        *head = current->next;
        free(current);
        list->length--;
        return retval; - not a bug but can remove this...*/
    }

    /* bug here: changed ++i to i++ */
    while (i++ != index) {
        prev = current;
        current = current->next;
    }

    prev->next = current->next;
    retval = current->value;
    free(current);
    list->length--;

    return retval;
}

void deleteList(List_t* list) {
    node_t* head = list->head;

    while (head != NULL) {

	/* bug here: remove the element at the front and move the head */
        removeFront(list);
       	head = list->head;
    }

    list->length = 0;
}

void printList(List_t* list, char mode) {
    node_t* head = list->head;
    node_t* current = head;

    if (list->length == 0) {
        printf("List is empty");
        return;
    }

    /* bug here: changed current->next to current */
    while (current != NULL) {
        switch (mode) {
            case 0:
                printf("%d ", (int)(current->value));
		break;
            case 1:
                printf("%s ", (char*)(current->value));
                break;
            default:
                fprintf(stderr, "Unsupported Mode\n");
                exit(1);
        }
        current = current->next;
    }
    return;
}

int intComparator(void* p, void* q) {
    return ((int)p - (int)q);
}

/* returns -1 if str1 < str2, 1 if str1 > str2, 0 if str1 == str2 */
int strComparator(void* str1, void* str2) {

	int i = 0;
	char *tmp = str1;
	char *tmp2 = str2;

	/* iterate until a null terminator is reached */
	while (*(tmp + i) != '\0' || *(tmp2 + i) != '\0') {

		if (*(tmp + i) < *(tmp2 + i)) return -1;
		if (*(tmp + i) > *(tmp2 + i)) return 1;
		i++;
	}

	if (*(tmp + i) == '\0' && *(tmp2 + i)  == '\0') return 0;
	if (*(tmp + i) == '\0') return -1;
	if (*(tmp2 + i) == '\0') return 1;

	/* should never get here */
	return 0;
}

void sortElement(List_t* list, void* value) {

	node_t * current = list->head;
	node_t * prev = list->head;

	/* iterate until you get to a value that is bigger than you */
	while (current) {

		/* handle first node case */
		if (list->comparator(value, list->head->value) < 0) {
			insertFront(list, value);
			return;
		}

		/* if the value < current->value, add it before */
		else if (list->comparator(value, current->value) < 0) {

			/* create a new node */
			node_t* new_node;
    			new_node = malloc(sizeof(node_t));

    			new_node->value = value;
    			new_node->next = current;

    			prev->next = new_node;
    			list->length++;

			return;

		}

		/* add to the end of the list */
		if (current->next == NULL) {
			insertRear(list, value);
			return;
		}
		else {
			prev = current;
			current = current->next;
		}
	}



	return;
}

void sortList(List_t* list) {

	/* create the new sorted list */
	List_t * sortedList = malloc(sizeof(List_t));
	sortedList->length = 0;
	sortedList->comparator = list->comparator;

	/* insert the first node */
	insertFront(sortedList, (void*)list->head->value);

	/* start with the 2nd node since the first was added already */
	node_t * current = list->head->next;

	/* iterate through the list and create the new, sorted one */
	while (current) {

		sortElement(sortedList, current->value);
		free(current);
		current = current->next;
	}

	//deleteList(list);
	list->head = sortedList->head;

	return;
}

int removeDups(List_t* list) {

	/* keeps track of the ptr that moves across the list */
	node_t * current = list->head;

	/* keeps track of the prev node */
	node_t * prev = NULL;

	/* keeps track of the current dup value to test against */
	node_t * tmp = list->head;

	/* iterate through the list */
	while (tmp != NULL) {

		if (current == NULL) {
			/* reset the iterator ptr to point at the beginning */
			current = list->head;

			/* move the tmp pointer to the next value */
			tmp = tmp->next;
		}

		/* check if value is a duplicate and remove it */
		if (tmp->value == current->value
		    && tmp != current) {

			prev->next = current->next;
			free(current);
			list->length--;

			current = prev->next;

			// remove duplicates

		}

		/* move prev ptr to the current node */
		prev = current;

		/* move the current ptr to the next position */
		current = current->next;

		}

	return 0;  // Change this as needed!
}