typedef struct node
{
    void* data;
    struct node* prev;
    struct node* next;
} node_t;


typedef struct list
{
    struct node* first;
    struct node* last;
    long length;
} list_t;


// Create and free list
list_t* list_new();
void list_free(list_t *l);

// Create and free nodes
node_t* node_new(void* data);
// WARNING: free does free the node data by default
// to prevent freeing of the data set data to 0 before removing from the list
void node_free(node_t* n);

// List operations
void list_insert(list_t *l, node_t* n);
void list_append(list_t *l, node_t* n);
void list_remove(list_t *l, node_t *n);
void list_clear(list_t *l);


// Default implementation of specal list modes

// Queue
void list_queue_push(list_t *l, void* data);
void* list_queue_pop(list_t *l);

// Stack
void list_stack_push(list_t *l, void* data);
void* list_stack_pop(list_t *l);

#include "linkedlist.h"

#include 

list_t* list_new()
{
    list_t *l = malloc(sizeof(list_t));
    l->first = 0;
    l->last = 0;
    l->length = 0;
    return l;
}

node_t* node_new(void* data)
{
    node_t *n = malloc(sizeof(node_t));
    n->prev = 0;
    n->next = 0;
    n->data = data;
    return n;
}

void node_free(node_t* n)
{
    free(n->data);
    free(n);
}

void list_insert(list_t *l, node_t* n)
{
    if (l->first != 0)
    {
        n->next = l->first;
        l->first->prev = n;
        l->first = n;
    }
    else
    { // assuming list is empty
        l->first = n;
        l->last = n;
    }

    l->length += 1;
}

void list_append(list_t *l, node_t* n)
{
    if (l->last != 0)
    {
        n->prev = l->last;
        l->last->next = n;
        l->last = n;
    }
    else
    { // assuming list is empty
        l->first = n;
        l->last = n;
    }

    l->length += 1;
}

void list_remove(list_t *l, node_t *n)
{
    if (n->prev != 0 && n->next != 0)
    {
        // We are dealing with a middle node
        n->prev->next = n->next;
        n->next->prev = n->prev;
    }
    else if (n->prev != 0 && n->next == 0)
    {
        // We are dealing with a last node
        n->prev->next = 0;
        l->last = n->prev;
    }
    else if (n->prev == 0 && n->next != 0)
    {
        // We are dealing with a first node
        n->next->prev = 0;
        l->first = n->next;
    }
    else if (n->prev == 0 && n->next == 0)
    {
        // We are dealing with a single node
        l->first = 0;
        l->last = 0;
    }

    l->length -= 1;
}

void list_clear(list_t *l)
{
    while(l->first != 0)
    {
        list_remove(l, l->first);
    }
}

void list_free(list_t *l)
{
    if (l->length > 0)
    {
        list_clear(l);
    }
    free(l);
}

// Queue (FIFO)
void list_queue_push(list_t *l, void* data)
{
    list_append(l, node_new(data));
}

void* list_queue_pop(list_t *l)
{
    void* data = 0;
    if (l->first != 0)
    {
        data = l->first->data;
        l->first->data = 0;
        list_remove(l, l->first);
    }
    return data;
}

// Stack (FILO)
void list_stack_push(list_t *l, void* data)
{
    list_append(l, node_new(data));
}

void* list_stack_pop(list_t *l)
{
    void* data = 0;
    if (l->last != 0)
    {
        data = l->last->data;
        l->last->data = 0;
        list_remove(l, l->last);
    }
    return data;
}

#include 
#include 

#include "linkedlist.h"


void list_test1()
{
    printf("start\n");

    list_t *l;

    l = list_new();

    printf("list count: %ld\n", l->length);

    list_append(l, node_new("Hello 1"));
    list_append(l, node_new("Hello 2"));
    list_append(l, node_new("Hello 3"));
    list_append(l, node_new("Hello 4"));
    list_append(l, node_new("Hello 5"));

    printf("list count: %ld\n", l->length);

    list_insert(l, node_new("Hello 1"));
    list_insert(l, node_new("Hello 2"));
    list_insert(l, node_new("Hello 3"));
    list_insert(l, node_new("Hello 4"));
    list_insert(l, node_new("Hello 5"));

    printf("list count: %ld\n", l->length);

    node_t *n = l->first;
    while(n != 0)
    {
        printf("item: %s\n", (char*) n->data);
        n = n->next;
    }

    list_remove(l, l->last);

    printf("list count: %ld\n", l->length);

    list_clear(l);

    printf("list count: %ld\n", l->length);

    list_free(l);

    printf("end\n");
}

void list_test2()
{
    printf("start\n");

    list_t *l;

    l = list_new();

    list_queue_push(l, "Hello 1");
    list_queue_push(l, "Hello 2");
    list_queue_push(l, "Hello 3");
    list_queue_push(l, "Hello 4");
    list_queue_push(l, "Hello 5");
    printf("list count: %ld\n", l->length);

    char *data = 0;

    data = (char*)list_queue_pop(l);
    //printf("list count: %ld\n", l->length);
    while(data != 0)
    {
        printf("item: %s\n", data);
        data = (char*)list_queue_pop(l);
        //printf("list count: %ld\n", l->length);
    }

    printf("list count: %ld\n", l->length);
    list_clear(l);

    printf("\n");

    list_stack_push(l, "Hello 1");
    list_stack_push(l, "Hello 2");
    list_stack_push(l, "Hello 3");
    list_stack_push(l, "Hello 4");
    list_stack_push(l, "Hello 5");
    printf("list count: %ld\n", l->length);

    data = (char*)list_stack_pop(l);
    //printf("list count: %ld\n", l->length);
    while(data != 0)
    {
        printf("item: %s\n", data);
        data = (char*)list_stack_pop(l);
        //printf("list count: %ld\n", l->length);
    }

    printf("list count: %ld\n", l->length);

    list_free(l);

    printf("end\n");
}

void list_test3()
{
    list_t *l = list_new();

    int i = 0;
    for(i=0; i<1000000; i++)
    {
        int *d = malloc(sizeof(int));
        *d = i;
        list_stack_push(l, d);
    }

    int *data = (int*)list_stack_pop(l);

    while(data != 0)
    {
        printf("%i\n", *data);
        data = (int*)list_stack_pop(l);
    }

    list_free(l);
}

int main(int argc, char *argv[])
{
    list_test1();

    list_test2();

    //list_test3();

    return 0;
}