///////////////////////////////////////////////////////////////////////////
//    Copyright (C) 2015 Wizardry and Steamworks - License: GNU GPLv3    //
///////////////////////////////////////////////////////////////////////////
//                                                                       //
//   stringDoubleLinkedList                                              //
//                                                                       //
//   An implementation of a double linked list of strings.               //
//   Implemented functions:                                              //
//       - insert after                                                  //
//       - insert before                                                 //
//       - is empty                                                      //
//       - count                                                         //
//       - size                                                          //
//       - print                                                         //
//                                                                       //
///////////////////////////////////////////////////////////////////////////

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

/* The stringDoubleLinkedList node structure with prior pointing to the
 * previous element in the double linked list and later pointing to the
 * next element in the double linked list.
 */
typedef struct node {
    char *store;
    struct node *prior, *later;
} stringDoubleLinkedListNode;

/*
 * The stringDoubleLinkedList structure with head poiting to the first
 * element in the double linked list and tail pointing to the last element
 * in the doublelinked list.
 */
typedef struct {
    stringDoubleLinkedListNode *head, *tail;
} stringDoubleLinkedList;

/*
 * Creates a new stringDoubleLinkedList.
 */
stringDoubleLinkedList* stringDoubleLinkedListCreate(void) {
    stringDoubleLinkedList *l = (stringDoubleLinkedList*)calloc(1, sizeof(stringDoubleLinkedList));
    l->head = (stringDoubleLinkedListNode*)calloc(3, sizeof(stringDoubleLinkedListNode *));
    l->tail = l->head;
    l->tail->prior = NULL;
    l->tail->later = NULL;
    return l;
}

/*
 * Returns 1 in case the stringDoubleLinkedList is empty or 0 otherwise.
 */
int stringDoubleLinkedListIsEmpty(stringDoubleLinkedList *l) {
    return l->head->later == l->head->prior && l->head->store == NULL;
}

/*
 * Returns the number of elements in stringDoubleLinkedList.
 */
int stringDoubleLinkedListCount(stringDoubleLinkedList *l) {
    int count = 0;
    stringDoubleLinkedListNode *root = l->head;
    while (root != NULL)
        ++count;
    return count;
}

/*
 * Prints out the current stringDoubleLinkedList.
 */
void stringDoubleLinkedListPrint(stringDoubleLinkedList *l) {
    stringDoubleLinkedListNode *root;
    if (stringDoubleLinkedListIsEmpty(l)) {
        printf("Linked list is empty.\n");
        return;
    }
    root = l->head;
    printf("Elements in linked list: ");
    while (root != NULL) {
        printf("%s ", root->store);
        root = root->later;
    }
    printf("\n");
}

/*
 * Inserts a new element e in the stringDoubleLinkedList l before node n.
 */
void stringDoubleLinkedListInsertBefore(stringDoubleLinkedList *l, stringDoubleLinkedListNode *n, char *e) {
    stringDoubleLinkedListNode *root = l->head;
    stringDoubleLinkedListNode *node;

    while (root != NULL && root != n)
        root = root->later;

    node = (stringDoubleLinkedListNode*)calloc(3, sizeof(stringDoubleLinkedListNode *));
    node->store = (char*)calloc(strlen(e) + 1, sizeof(char *));
    memcpy(node->store, e, strlen(e) + 1);

    if (stringDoubleLinkedListIsEmpty(l)) {
        node->prior = NULL;
        node->later = NULL;
        l->head = node;
        l->tail = node;
        return;
    }

    node->later = n;
    if (n->prior != NULL) {
        node->prior = n->prior;
        (n->prior)->later = node;
    }
    n->prior = node;

    if (l->head->prior != NULL)
        l->head = l->head->prior;
    if (l->tail->later != NULL)
        l->tail = l->tail->later;
}

/*
 * Inserts a new element e in the stringDoubleLinkedList l after node n.
 */
void stringDoubleLinkedListInsertAfter(stringDoubleLinkedList *l, stringDoubleLinkedListNode *n, char *e) {
    stringDoubleLinkedListNode *root = l->head;
    stringDoubleLinkedListNode *node;

    while (root != NULL && root != n)
        root = root->later;

    node = (stringDoubleLinkedListNode*)calloc(3, sizeof(stringDoubleLinkedListNode *));
    node->store = (char*)calloc(strlen(e) + 1, sizeof(char *));
    memcpy(node->store, e, strlen(e) + 1);

    if (stringDoubleLinkedListIsEmpty(l)) {
        node->prior = NULL;
        node->later = NULL;
        l->head = node;
        l->tail = node;
        return;
    }

    node->prior = n;
    if (n->later != NULL) {
        node->later = n->later;
        (n->later)->prior = node;
    }
    n->later = node;

    if (l->head->prior != NULL)
        l->head = l->head->prior;
    if (l->tail->later != NULL)
        l->tail = l->tail->later;
}

/*
 * Deletes node n from the stringDoubleLinkedList l.
 */
void stringDoubleLinkedListDelete(stringDoubleLinkedList *l, stringDoubleLinkedListNode *n) {
    stringDoubleLinkedListNode *root = l->head;

    while (root != NULL && root != n)
        root = root->later;

    if (root == NULL || root != n)
        return;

    if (n->prior == NULL && n->later == NULL) {
        n->store = NULL;
        free(n);
        return;
    }

    if (n->prior == NULL) {
        (n->later)->prior = NULL;
        l->head = l->head->later;
        free(n);
        return;
    }

    if (n->later == NULL) {
        (n->prior)->later = NULL;
        l->tail = l->tail->prior;
        free(n);
        return;
    }

    (n->prior)->later = n->later;
    (n->later)->prior = n->prior;
    free(n);
}

int main(void) {
    stringDoubleLinkedList *l = stringDoubleLinkedListCreate();
    //printf("Linked list is empty: %d\n", stringDoubleLinkedListIsEmpty(l));

    stringDoubleLinkedListPrint(l);
    stringDoubleLinkedListInsertAfter(l, l->head, "Hello");
    stringDoubleLinkedListPrint(l);
    stringDoubleLinkedListInsertAfter(l, l->head, "World");
    stringDoubleLinkedListPrint(l);
    //printf("head later: %s\n", l->head->later->store);
    stringDoubleLinkedListInsertAfter(l, l->head->later, "DAY");
    stringDoubleLinkedListPrint(l);
    stringDoubleLinkedListInsertAfter(l, l->tail->prior, "final");
    stringDoubleLinkedListPrint(l);

    stringDoubleLinkedListDelete(l, l->head);
    stringDoubleLinkedListPrint(l);

    stringDoubleLinkedListPrint(l);
    stringDoubleLinkedListInsertBefore(l, l->head, "Hello");
    stringDoubleLinkedListPrint(l);
    stringDoubleLinkedListInsertBefore(l, l->head, "World");
    stringDoubleLinkedListPrint(l);
    //printf("head later: %s\n", l->head->later->store);
    stringDoubleLinkedListInsertBefore(l, l->head->later, "DAY");
    stringDoubleLinkedListPrint(l);
    stringDoubleLinkedListInsertBefore(l, l->tail->prior, "final");
    stringDoubleLinkedListPrint(l);
    return 0;
}