// A singly linked list which contains pointers to the head and tail of the list.

#include "List.h"

typedef struct node Node;

struct node {
    Item data;
    struct node * next;
};

struct list {
    struct node * head;
    struct node * tail;
};

Node * create_node(Item item);
Node * do_reverse_list(Node * start);

List * ListNew() {
    List * new_list = malloc(sizeof(struct list));
    new_list->head = NULL;
    new_list->tail = NULL;
    return new_list;
}

void ListDestroy(List * l) {
    while (!ListIsEmpty(l)) {
        ListRemoveStart(l);
    }
    free(l);
}

void ListInsertStart(List * l, Item item) {
    Node * n = create_node(item);
    n->next = l->head;
    l->head = n;
    if (l->tail == NULL) {
        l->tail = n;
    }
}

void ListInsertEnd(List * l, Item item) {
    Node * n = create_node(item);
    if (l->tail) {
        l->tail->next = n;
    }
    l->tail = n;
    if (l->head == NULL) {
        l->head = n;
    }
}

Item ListRemoveStart(List * l) {
    assert(!ListIsEmpty(l));
    Node * node_removing = l->head;
    l->head = l->head->next;
    Item data_to_return = node_removing->data;
    if (l->tail == node_removing) {
        l->tail = NULL;
    }
    free(node_removing);
    return data_to_return;
}

Item ListRemoveEnd(List * l) {
    assert(!ListIsEmpty(l));
    Node * prev = NULL;
    Node * curr = l->head;
    while (curr->next != NULL) {
        prev = curr;
        curr = curr->next;
    }
    Item data_to_return = curr->data;
    if (curr == l->head) {
        l->head = NULL;
    }
    free(curr);
    if (prev) {
        prev->next = NULL;
    }
    l->tail = prev;
    return data_to_return;
}

int ListSize(List * l) {
    int count = 0;
    Node * curr = l->head;
    while (curr != NULL) {
        count++;
        curr = curr->next;
    }
    return count;
}

bool ListIsEmpty(List * l) {
    if (l->head == NULL) {
        return true;
    }
    return false;
}

void ListReverse(List * l) {
    l->head = do_reverse_list(l->head);
    Node * curr = l->head;
    while (curr->next != NULL) {
        curr = curr->next;
    }
    l->tail = curr;
}

char * ListToString(List * l) {
    char * s = calloc(MAX_PRINT_LENGTH, sizeof(char));
    Node * curr = l->head;
    char snum[5];
    while (curr != NULL) {
        snprintf(snum, 5, " %d", curr->data);
        strncat(s, snum, MAX_PRINT_LENGTH);
        curr = curr->next;
    }
    return s;
}

void ListDisplay(List * l) {
    Node * curr = l->head;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("NULL\n");
}

// Helper Functions

Node * create_node(Item item) {
    Node * new_node = malloc(sizeof(struct node));
    new_node->data = item;
    new_node->next = NULL;
    return new_node;
}

Node * do_reverse_list(Node * start) {
    // Empty list or single node list
    if (start == NULL || start->next == NULL) {
        return start;
    }
    // More than one node in list
    Node * rest_of_list = do_reverse_list(start->next);
    Node * curr = rest_of_list;
    while (curr->next != NULL) {
        curr = curr->next;
    }
    curr->next = start;
    start->next = NULL;
    return rest_of_list;
}