#ifndef DOUBLY_LINKED_LIST_H
#define DOUBLY_LINKED_LIST_H

#include <stdlib.h>
#include <assert.h>

/* When reading through this code, you may encounter functions not being
 * strictly const-correct. This is because I wanted to make const-correctness
 * to depict the CONCEPTUAL const-ness, not const-ness due to some random
 * implementation-detail.
 */

/* From this implementation's perspective, this is not a pointer to the data
 * but really the data itsself.
 */
typedef void* data_t;

/* I second that the name "dll" for "doubly-linked list" is ambiguous
 * with the Windows DLL (Dynamic Link Library) but I don't think this'll
 * lead to any serious confusion.
 */

typedef struct dll_node {
    struct dll_node* prev;
    struct dll_node* next;

    data_t data;
} dll_node_t;

typedef int (*cleanup_op_t)(dll_node_t* node);

typedef struct dll {
    dll_node_t* head;
    dll_node_t* tail;

    cleanup_op_t cleanup_op;

    size_t size;
} dll_t;

/* Initializes a list with zero nodes.
 * `list' - The list to initialize
 * `cleanup_op' - The operation to apply to every datum when it is
 *                removed from the list. This includes the destruction of
 *                the list using `dll_destroy'.
 */
void dll_init(dll_t* list, cleanup_op_t cleanup_op);

/* Data definition with macros - Linux kernel style. C ain't got no
 * constructors - we use ugly macros to make up for that. AFAIK, GCC does
 * offer aping constructors using the attribute "constructor" but that's
 * compiler-specific and therefore not eligible for usage.
 * Use it if you find it useful. The big fat drawback is that the actually
 * hidden stuff going on in this macro needs to be exposed for further
 * operations. Or, when assigning dll_t*'s, you need to know the type too.
 * That completely defeats the purpose of this macro.
 * NOTE: LACK OF DO-WHILE LOOP IS ON PURPOSE TO MAKE THE VARIABLE VISIBLE
 * IN THE OUTER SCOPE!
 */
#define DEFINE_DLL(identifier, cleanup_op)
    dll_t identifier;
    dll_init(&identifier, (cleanup_op));

/* Destructs the list, that is, all its nodes and the data they contain.
 * Complexity: O(n)
 * `list' - The list to destruct
 */
void dll_destroy(dll_t* list);

/* The return value indicates whether the traversing function should continue
 * or if the required condition has been met. This enables searching for
 * items in the list and other, crazy stuff the user of this API can think of.
 */
typedef int (*dll_traverse_op_t)(dll_node_t* node);

/* Traverses through a list, starting at the head and going forward to the next
 * nodes, and performs an operation on every node.
 * Complexity: O(n)
 * `list' - The list to traverse through
 * `op' - The operation to perform
 */
void dll_traverse(dll_t* list, dll_traverse_op_t op);

/* Traverses through a list, starting at the tail and going backward to the
 * previous nodes, and performs an operation on every node.
 * Complexity: O(n)
 * `list' - The list to traverse through
 * `op' - The operation to perform
 */
void dll_traverse_rev(dll_t* list, const dll_traverse_op_t op);

/* TODO: is it reasonable to return the created node from the dll_add_* and
 * dll_insert_* functions? Think about that!
 */

/* TODO: THE BELOW COMMENT SERVES AS A TEMPLATE FOR ALL DOCUMENTING COMMENTS
 * IN THIS IMPLEMENTATION. FORM THE OTHER ONES WITH THIS ONE HERE IN MIND!
 */
/* Inserts a node right before another one.
 * Complexity: O(1)
 * `list' - The list to insert into
 * `node' - The node before which to insert the new node
 * `data' - The data stored by the new node
 * Notes:
 * If the list doesn't contain any nodes, a new node is created and added to
 * the list, INDEPENDENT OF THE VALUE OF `node'.
 */
dll_node_t* dll_insert_before(dll_t* list, dll_node_t* node, data_t data);

/* TODO: THE BELOW COMMENT SERVES AS A TEMPLATE FOR ALL DOCUMENTING COMMENTS
 * IN THIS IMPLEMENTATION. FORM THE OTHER ONES WITH THIS ONE HERE IN MIND!
 */
/* Inserts a node right after another one.
 * Complexity: O(1)
 * `list' - The list to insert into
 * `node' - The node after which to insert the new node
 * `data' - The data stored by the new node
 * Notes:
 * If the list doesn't contain any nodes, a new node is created and added to
 * the list, INDEPENDENT OF THE VALUE OF `node'.
 */
dll_node_t* dll_insert_after(dll_t* list, dll_node_t* node, data_t data);

/* The dll_add_* and dll_insert_* functions are very similar, so I wrote the
 * actual, generic implementation in the dll_insert_* functions and built
 * the dll_add_* ones on top of them.
 * Similarly done with the dll_rm and dll_rm_* functions.
 */

/* Add a node to the head of the list.
 * Complexity: O(1)
 * `list' - The list to prepend the node to
 * `data' - The data to be stored in the new node
 */
dll_node_t* dll_add_front(dll_t* list, data_t data);

/* Add a node to the tail of the list.
 * Complexity: O(1)
 * `list' - The list to append the node to
 * `data' - The data to be stored in the new node
 */
dll_node_t* dll_add_back(dll_t* list, data_t data);

/* Removes a node.
 * Complexity: O(1)
 * `list' - The list to remove the node from
 * `node' - The node to remove
 */
void dll_rm(dll_t* list, const dll_node_t* node);

/* Remove the node at the head of the list.
 * Complexity: O(1)
 * `list' - The list to remove the node from
 */
void dll_rm_front(dll_t* list);

/* Remove the node at the tail of the list.
 * Complexity: O(1)
 * `list' - The list to remove the node from
 */
void dll_rm_back(dll_t* list);

#endif

#include <dll.h>

void dll_init(dll_t* list, cleanup_op_t cleanup_op) {
    assert(list);

    list->head = list->tail = NULL;
    list->cleanup_op = cleanup_op;
    list->size = 0;
}

void dll_destroy(dll_t* list) {
    assert(list);

    if (list->size == 0)
        return;

    dll_node_t* it = list->head;

    while (it) {
        if (list->cleanup_op)   /* fare well, branch predictor */
            list->cleanup_op(it->data);

        dll_node_t* tmp = it;
        it = it->next;
        free(tmp);
    }
}

void dll_traverse(dll_t* list, dll_traverse_op_t op) {
    assert(list);

    if (list->size == 0)
        return;

    dll_node_t* it = list->head;

    while (it) {
        op(it);
        it = it->next;
    }
}

void dll_traverse_rev(dll_t* list, const dll_traverse_op_t op) {
    if (list->size == 0)
        return;

    dll_node_t* it = list->tail;

    while (it) {
        op(it);
        it = it->prev;
    }
}

dll_node_t* dll_insert_before(dll_t* list, dll_node_t* node, data_t data) {
    assert(list);

    if (list->size == 0)
        assert(node);

    dll_node_t* prev_node = list->size == 0 ? NULL : node->prev;

    dll_node_t* new_node = malloc(sizeof(dll_node_t));
    assert(new_node);
    new_node->data = data;
    new_node->next = list->size == 0 ? NULL : node;
    new_node->prev = prev_node;

    if (list->size == 0)
        list->head = list->tail = new_node;
    else {
        if (node->prev)
            prev_node->next = new_node;
        else {
            assert(node == list->head);
            list->head = new_node;
        }
        node->prev = new_node;
    }

    ++(list->size);

    return new_node;
}

dll_node_t* dll_insert_after(dll_t* list, dll_node_t* node, data_t data) {
    assert(list);

    if (list->size != 0)
        assert(node);

    dll_node_t* next_node = list->size == 0 ? NULL : node->next;

    dll_node_t* new_node = malloc(sizeof(dll_node_t));
    assert(new_node);
    new_node->data = data;
    new_node->next = next_node;
    new_node->prev = list->size == 0 ? NULL : node;

    if (list->size == 0)
        list->head = list->tail = new_node;
    else {
        if (node->next)
            next_node->prev = new_node;
        else {
            assert(node == list->tail);
            list->tail = new_node;
        }
        node->next = new_node;
    }

    ++(list->size);

    return new_node;
}

dll_node_t* dll_add_front(dll_t* list, data_t data) {
    return dll_insert_before(list, list->head, data);
}

dll_node_t* dll_add_back(dll_t* list, data_t data) {
    return dll_insert_after(list, list->tail, data);
}

void dll_rm(dll_t* list, const dll_node_t* node) {
    assert(list);
    assert(node);
    assert(list->size != 0);

    if (list->cleanup_op)
        list->cleanup_op(node->data);

    if (node->prev)
        node->prev->next = node->next;
    else {
        assert(node == list->head);
        list->head = node->next;
    }
    if (node->next)
        node->next->prev = node->prev;
    else {
        assert(node == list->tail);
        list->tail = node->prev;
    }

    /* Casting away const-ness is bad but it's just a necessary
     * implementation detail here. I hope it's not undefined behavior...
     * in C++, it is, if the object the casted pointer is pointing to is
     * const, AFAIK. Only if it is non-const but pointed to by a const
     * pointer casting away const-ness is well-defined.
     * But I think the rules differ in C. (C != C++!)
     */
    free((dll_node_t*) node);

    --(list->size);
}

void dll_rm_front(dll_t* list) {
    dll_rm(list, list->head);
}

void dll_rm_back(dll_t* list) {
    dll_rm(list, list->tail);
}

/* When reading through this code, you may encounter functions not being
  * strictly const-correct. This is because I wanted to make const-correctness
  * to depict the CONCEPTUAL const-ness, not const-ness due to some random
  * implementation-detail. */