/*************************************************************************/
/*    Copyright (C) 2015 Wizardry and Steamworks - License: GNU GPLv3    */
/*************************************************************************/
/*                                                                       */
/*  doubleLinkedList                                                     */
/*                                                                       */
/*  An implementation of linked lists for Amiga OS.                      */
/*                                                                       */
/*  Implemented functions:                                               */
/*      - append                                                         */
/*      - insert after                                                   */
/*      - insert before                                                  */
/*      - insert at index                                                */
/*      - element at index                                               */
/*      - remove                                                         */
/*      - remove at index                                                */
/*      - size                                                           */
/*      - is empty                                                       */
/*      - print                                                          */
/*                                                                       */
/*  Compile on Amiga OS using SAS/C: sc link doubleLinkedList.c          */
/*                                                                       */
/*************************************************************************/

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

#include <proto/exec.h>
#include <proto/dos.h>

/* The linked list element structure with storage containing pointers to
 * the next, respectively the previous element.
 */
typedef struct doubleLinkedListElement doubleLinkedListElement;
typedef struct doubleLinkedListElement {
    UBYTE *store;
    doubleLinkedListElement *nextElement;
    doubleLinkedListElement *prevElement;
};

/* The double linked list structure holding the size of the linked list
 * with pointers to both the head and the tail of the linked list.
 */
typedef struct {
    ULONG size;
    doubleLinkedListElement *head;
    doubleLinkedListElement *tail;
} doubleLinkedList;

/* Creates a double linked list. */
doubleLinkedList *doubleLinkedListCreate(void) {
    doubleLinkedList *l = (doubleLinkedList *)AllocMem(
        sizeof(doubleLinkedList),
        MEMF_ANY|MEMF_CLEAR
    );
    l->head = NULL;
    l->tail = NULL;
    l->size = 0;
    return l;
}

/* Creates a double linked list. */
doubleLinkedListElement *doubleLinkedListElementCreate(UBYTE *data) {
    doubleLinkedListElement *e = (doubleLinkedListElement *)AllocMem(
        sizeof(doubleLinkedListElement),
        MEMF_ANY|MEMF_CLEAR
    );
    e->store = (UBYTE *)AllocMem(
        strlen(data) * sizeof(UBYTE *) + 1,
        MEMF_ANY|MEMF_CLEAR
    );
    CopyMem(data, e->store, strlen(data) * sizeof(UBYTE *) + 1);
    e->prevElement = NULL;
    e->nextElement = NULL;
    return e;
}

/* Appends an element to the end of the double linked list. */
doubleLinkedListElement *doubleLinkedListAppend(doubleLinkedList *l, doubleLinkedListElement *e) {
    /* Update the element. */
    e->prevElement = l->tail != NULL ? l->tail : NULL;
    e->nextElement = NULL;
    /* Update head and tail list pointers. */
    switch(l->head != NULL) {
        case FALSE:
            l->head = e;
            break;
    }
    switch(l->tail != NULL) {
        case TRUE:
            l->tail->nextElement = e;
        default:
            l->tail = e;
            break;
    }
    ++l->size;
    return e;
}

/* Inserts a double linked list element after an element. */
doubleLinkedListElement *doubleLinkedListInsertNext(
    doubleLinkedList *l, doubleLinkedListElement *e, doubleLinkedListElement *a) {
    a->nextElement = e->nextElement;
    if(a->nextElement != NULL)
        a->nextElement->prevElement = a;
    a->prevElement = e;
    e->nextElement = a;
    if(a->nextElement == NULL)
        l->tail = a;
    ++l->size;
    return a;
}

/* Inserts a double linked list element before an element. */
doubleLinkedListElement *doubleLinkedListInsertPrev(
    doubleLinkedList *l, doubleLinkedListElement *e, doubleLinkedListElement *a) {
    a->nextElement = e;
    a->prevElement = e->prevElement;
    if(e->prevElement != NULL)
        e->prevElement->nextElement = a;
    e->prevElement = a;
    if(a->prevElement == NULL)
        l->head = a;
    ++l->size;
    return a;
}

/* Returns the element at a given index. */
doubleLinkedListElement *doubleLinkedListElementAtIndex(doubleLinkedList *l, ULONG i) {
    doubleLinkedListElement *e = l->head;
    while(i > 0) {
        e = e->nextElement;
        --i;
    }
    return e;
}

/* Inserts a double linked list element at a given index. */
doubleLinkedListElement *doubleLinkedListInsertAt(
    doubleLinkedList *l, doubleLinkedListElement *a, ULONG i) {
    return doubleLinkedListInsertPrev(l, doubleLinkedListElementAtIndex(l, i), a);
}

/* Removes a double linked list element. */
void doubleLinkedListRemove(doubleLinkedList *l, doubleLinkedListElement *e) {
    if(e->prevElement != NULL)
        e->prevElement->nextElement = e->nextElement;
    if(e->nextElement != NULL)
        e->nextElement->prevElement = e->prevElement;
    if(l->head == e)
        l->head = e->nextElement;
    if(l->tail == e)
        l->tail = e->prevElement;
    --l->size;
}

/* Removes a double linked list element at a given index. */
void doubleLinkedListRemoveAt(doubleLinkedList *l, ULONG i) {
    doubleLinkedListRemove(l, doubleLinkedListElementAtIndex(l, i));
}

/* Returns true if the double linked list is empty. */
BOOL doubleLinkedListIsEmpty(doubleLinkedList *l) {
    return (BOOL)(l->head == l->tail);
}

/* Returns the number of elements in the double-linked list. */
ULONG doubleLinkedListSize(doubleLinkedList *l) {
    return l->size;
}

/* Prints the double linked list. */
void doubleLinkedListPrint(doubleLinkedList *l) {
    doubleLinkedListElement *e;
    if(doubleLinkedListIsEmpty(l)) {
        Printf("List is empty.\n");
        return;
    }
    Printf("Elements in the linked list: ");
    e = l->head;
    do {
        Printf("%s ", e->store);
        e = e->nextElement;
    } while(e != NULL);
    Printf("\n");
}

int main(void) {
    doubleLinkedList *l = doubleLinkedListCreate();
    doubleLinkedListElement *s, *e;
    s = doubleLinkedListElementCreate("Good day!");
    doubleLinkedListAppend(l, s);
    doubleLinkedListAppend(l, doubleLinkedListElementCreate("Hello there!"));
    e = doubleLinkedListElementCreate("hi...");
    doubleLinkedListAppend(l, e);
    Printf("Head: %s\n", l->head->store);
    Printf("Tail: %s\n", l->tail->store);
    Printf("nnp: %s\n", s->nextElement->nextElement->prevElement->store);
    doubleLinkedListInsertNext(l, l->head, doubleLinkedListElementCreate("STOP"));
    Printf("Head: %s\n", l->head->store);
    doubleLinkedListPrint(l);
    doubleLinkedListRemove(l, l->head);
    Printf("Head: %s\n", l->head->store);
    doubleLinkedListPrint(l);
    Printf("Count: %ld\n", doubleLinkedListSize(l));
    doubleLinkedListInsertPrev(l, l->tail, doubleLinkedListElementCreate("START"));
    doubleLinkedListPrint(l);
    doubleLinkedListRemoveAt(l, 0);
    doubleLinkedListPrint(l);
    doubleLinkedListInsertAt(l, doubleLinkedListElementCreate("TEST"), 1);
    doubleLinkedListPrint(l);
}