/*
CSE 303, Spring 2009, Marty Stepp
Homework 5: T9 (solution)
This file implements a provided library of linked lists of strings.
*/

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"

// local static function declarations
static void list_check_index(char*, int, int, int);
static void list_check_not_null(char*, void*, char*);
static void list_check_list(char*, List*);
static void list_crash(int);
static ListNode* list_node_at(char*, List*, int);
static ListNode* list_new_node(char*, char*, ListNode*, ListNode*);

// makes sure that the given index is in the given range; else crashes.
// all functions take a 'context' parameter so that if things go wrong,
// we can print a descriptive error message about what method started the call
static void list_check_index(char* context, int index, int min, int max) {
    if (!(min <= index && index <= max)) {
        printf("*** List error in %s: index %d out of range\n", context, index);
        list_crash(1);
    }
}

// makes sure that the given pointer is not null; else crashes
static void list_check_not_null(char* context, void* p, char* name) {
    if (!p) {
        printf("*** List error in %s: pointer '%s' must not be NULL\n", context, name);
        list_crash(2);
    }
}

// makes sure that the given list is valid (non-null, and blessed); else crashes
static void list_check_list(char* context, List* list) {
    list_check_not_null(context, list, "list");
    list_check_not_null(context, list->front, "list->front");
    list_check_not_null(context, list->back, "list->back");
    if (!list->blessed) {
        printf("*** List error in %s: you must create lists using list_new, not malloc/calloc\n", context);
        list_crash(3);
    }
    if (list->size < 0) {
        printf("*** List error in %s: size must be >= 0, but found %d\n", context, list->size);
        list_crash(4);
    }
}

// intentionally causes a segfault by deferencing a NULL pointer
static void list_crash(int code) {
    int* bad = NULL;
    *bad = 42;   // oh noez, crash
    exit(code);  // won't be reached
}

// returns the linked list node that corresponds to the given index
static ListNode* list_node_at(char* context, List* list, int index) {
    int i;
    list_check_list(context, list);
    list_check_index(context, index, -1, list->size);
    
    if (index < list->size / 2) {
        // closer to front
        ListNode* current = list->front;
        for (i = 0; i <= index; i++) {
            current = current->next;
        }
        return current;
    } else {
        // closer to back, so start there
        ListNode* current = list->back;
        for (i = list->size; i > index; i--) {
            current = current->prev;
        }
        return current;
    }
}

// allocates and returns a new linked list node with the given data, 
// previous, and next pointers
static ListNode* list_new_node(char* context, char* data, ListNode* prev, ListNode* next) {
    ListNode* new_node = (ListNode*) calloc(1, sizeof(ListNode));

    // unlikely, but still
    if (!new_node) {
        printf("*** List error in %s: not enough memory to create new node\n", context);
        list_crash(5);
    }
    
    new_node->data = data;
    new_node->prev = prev;
    new_node->next = next;
    return new_node;
}

/**
 * Constructs a new linked list and returns a pointer to it.
 * The list is implemented with "dummy" header and tail nodes that
 * contain meaningless data, to make implementation of the functions easier.
 */
List* list_new(void) {
    List* list = (List*) calloc(1, sizeof(List));

    // unlikely, but still
    if (!list) {
        printf("*** LIST ERROR in list_new: not enough memory to create list\n");
        list_crash(5);
    }
    list->size = 0;
    
    // set up dummy header/tail nodes
    list->front = list_new_node("list_new", "(dummy header)", NULL, NULL);
    list->back  = list_new_node("list_new", "(dummy tail)", list->front, NULL);
    list->front->next = list->back;
    list->blessed = true;
    
    return list;
}

/**
 * Inserts the given word into the given list at the given index.
 * Prints an error and exits if the index is out of bounds or if
 * the list or word is null.
 */
void list_add(List* list, int index, char* word) {
    ListNode* current;
    ListNode* new_node;
    list_check_list("list_add", list);
    list_check_not_null("list_add", word, "word");
    list_check_index("list_add", index, 0, list->size);
    
    current = list_node_at("list_add", list, index);
    new_node = list_new_node("list_add", word, current->prev, current);
    new_node->prev->next = new_node;
    new_node->next->prev = new_node;
    list->size++;
}

/**
 * Adds the given word to the end of the given list.
 * Prints an error and exits if the list or word is null.
 */
void list_append(List* list, char* word) {
    list_check_list("list_append", list);
    list_check_not_null("list_append", word, "word");
    list_add(list, list->size, word);
}

/**
 * Returns true if the given word is contained in the given list, else false.
 * Prints an error and exits if the list or word is null.
 */
bool list_contains(List* list, char* word) {
    list_check_list("list_contains", list);
    list_check_not_null("list_contains", word, "word");
    return list_index_of(list, word) >= 0 ? true : false;
}

/**
 * Frees all memory associated with the given list, not including
 * the strings stored as data in any of the nodes.
 * Prints an error and exits if the list is null or invalid.
 */
void list_free(List* list) {
    list_check_list("list_free", list);
    
    // free all nodes
    ListNode* current = list->front;
    while (current) {
        ListNode* next = current->next;
        free(current);
        current = next;
    }
    
    // free list itself
    free(list);
}

/**
 * Frees all memory associated with the given list, including
 * the strings stored as data in any of the nodes.
 * Prints an error and exits if the list is null or invalid.
 */
void list_free_deep(List* list) {
    list_check_list("list_free_deep", list);
    
    // free all nodes AND their data
    ListNode* current = list->front;
    while (current) {
        ListNode* next = current->next;
        if (current != list->front && current != list->back && current->data) {
            free(current->data);
        }
        free(current);
        current = next;
    }
    
    // free list itself
    free(list);
}

/**
 * Returns the string stored at the given index in the given list.
 * Prints an error and exits if the index is out of bounds or if
 * the list is null.
 */
char* list_get(List* list, int index) {
    list_check_list("list_get", list);
    list_check_index("list_get", index, 0, list->size - 1);
    return list_node_at("list_get", list, index)->data;
}

/**
 * Returns the index of the first occurrence of the given string in the given
 * list, or -1 if the string is not found in the list.
 * Prints an error and exits if the list or word is null.
 */
int list_index_of(List* list, char* word) {
    int index;
    ListNode* current;
    
    list_check_list("list_index_of", list);
    list_check_not_null("list_index_of", word, "word");
    
    current = list->front->next;
    for (index = 0;
         index < list->size && strcmp(current->data, word);
         index++) {
        current = current->next;
    }
    
    if (index < list->size) {
        return index;
    } else {
        return -1;
    }
}

/**
 * Adds the given word to the front of the given list.
 * Prints an error and exits if the list or word is null.
 */
void list_insert(List* list, char* word) {
    list_add(list, 0, word);
}

/**
 * Returns true if the size of the given list is 0, else false.
 * Prints an error and exits if the list is null or invalid.
 */
bool list_is_empty(List* list) {
    list_check_list("list_is_empty", list);
    return list->size == 0 ? true : false;
}

/**
 * Returns the index of the last occurrence of the given string in the given
 * list, or -1 if the string is not found in the list.
 * Prints an error and exits if the list or word is null.
 */
int list_last_index_of(List* list, char* word) {
    int index;
    ListNode* current;
    
    list_check_list("list_last_index_of", list);
    list_check_not_null("list_last_index_of", word, "word");
    
    current = list->back->prev;
    for (index = list->size - 1;
         index >= 0 && strcmp(current->data, word);
         index--) {
        current = current->prev;
    }
    return index;   // will be -1 if walked off end of list
}

/**
 * Prints the elements of the given list, in a format such as:
 * [element1, element2, element3, ..., elementN].
 * Prints an error and exits if the list or word is null.
 */
void list_print(List* list) {
    if (list_is_empty(list)) {
        printf("NULL\n");
    } else {
        ListNode* current = list->front->next;
        printf("[%s", current->data ? current->data : "NULL");
        while (current->next != list->back) {
            current = current->next;
            printf(", %s", current->data ? current->data : "NULL");
        }
        printf("]\n");
    }
}

/**
 * Removes and returns the element in the given list at the given index.
 * Also frees the memory that had been used by that node.
 * Prints an error and exits if the index is out of bounds or if the list is null.
 */
char* list_remove(List* list, int index) {
    ListNode* current;
    char* data;
    
    list_check_list("list_remove", list);
    list_check_index("list_remove", index, 0, list->size - 1);
    
    current = list_node_at("list_remove", list, index);
    current->next->prev = current->prev;
    current->prev->next = current->next;
    data = current->data;
    free(current);
    list->size--;
    return data;
}

/**
 * Removes the first occurrence of the given string from the given list.
 * Also frees the memory that had been used by its node.
 * Does nothing if the word is not found in the list.
 * Prints an error and exits if the list or word is null.
 */
void list_remove_element(List* list, char* word) {
    int index;
    list_check_list("list_remove_element", list);
    list_check_not_null("list_remove_element", word, "word");

    index = list_index_of(list, word);
    if (index >= 0 && index < list->size) {
        list_remove(list, index);
    }
}

/**
 * Sets the given index of the given list to store the given word.
 * Prints an error and exits if the index is out of bounds or if
 * the list or word is null.
 */
void list_set(List* list, int index, char* word) {
    list_check_list("list_set", list);
    list_check_index("list_set", index, 0, list->size - 1);
    list_check_not_null("list_set", word, "word");
    list_node_at("list_set", list, index)->data = word;
}

/**
 * Returns the number of elements in the given list.
 * Prints an error and exits if the list is null or invalid.
 */
int list_size(List* list) {
    list_check_list("list_size", list);
    return list->size;
}