#include <dllist.h>

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

dllist *
dl_new(void (*delfunc)(void *))
{
    dllist *list = malloc(sizeof *list);

    if (list != NULL) {
        list->delfunc = delfunc;
        list->count = 0;
        list->first = NULL;
        list->last = NULL;
    }

    return list;
}

void
dl_clear(dllist *list)
{
    if (list == NULL)
        return;
    while (dl_count(list))
        dl_remove(list, dl_first(list));
}

void
dl_delete(dllist *list)
{
    dl_clear(list);
    free(list);
}

static dlnode *
dl_add_between(dllist *list, void *data, dlnode *prev, dlnode *next)
{
    dlnode *node;

    assert((prev == NULL || prev->next == next) &&
           (next == NULL || next->prev == prev));
    if ((node = malloc(sizeof *node)) == NULL)
        return NULL;
    node->data = data;

    node->prev = prev;
    node->next = next;
    if (prev)
        prev->next = node;
    else
        list->first = node;
    if (next)
        next->prev = node;
    else
        list->last = node;
    list->count++;

    return node;
}

dlnode *
dl_insert(dllist *list, void *data, dlnode *node)
{
    if (node)
        return dl_add_between(list, data, node->prev, node);
    else
        return dl_add_between(list, data, NULL, list->first);
}

dlnode *
dl_add(dllist *list, void *data, dlnode *node)
{
    if (node)
        return dl_add_between(list, data, node, node->next);
    else
        return dl_add_between(list, data, list->last, NULL);
}

dlnode *
dl_add_sorted(dllist *list, void *data, int (*cmpfunc)(void *, void *))
{
    dlnode *node;

    for (node = dl_first(list); node; node = dl_next(node))
        if (cmpfunc(dl_data(node), data) > 0)
            return dl_insert(list, data, node);

    return dl_append(list, data);
}

static dlnode *
dl_link(dllist *list, dlnode *link, dlnode *node)
{
    if (link) {
        node->prev = link;
        node->next = link->next;

        if (link->next)
            link->next->prev = node;
        else
            list->last = node;

        link->next = node;
    } else if (list->first) {
        node->prev = NULL;
        node->next = list->first;
        list->first->prev = node;
        list->first = node;
    } else {
        node->prev = NULL;
        node->next = NULL;
        list->first = node;
        list->last = node;
    }
    list->count++;
}

static dlnode *
dl_unlink(dllist *list, dlnode *node)
{
    if (node->prev)
        node->prev->next = node->next;
    else
        list->first = node->next;
    if (node->next)
        node->next->prev = node->prev;
    else
        list->last = node->prev;
    node->prev = NULL;
    node->next = NULL;
    list->count--;

    return node;
}

void *
dl_remove(dllist *list, dlnode *node)
{
    void *data = NULL;

    if (node == NULL)
        return NULL;

    dl_unlink(list, node);

    if (list->delfunc)
        list->delfunc(node->data);
    else
        data = node->data;

    free(node);

    return data;
}

dlnode *
dl_at(dllist *list, int i)
{
    dlnode *node;

    if (i < 0)
        i = dl_count(list) + i;

    if (i < 0 || i >= dl_count(list))
        return NULL;

    if (i < dl_count(list) / 2) {
        node = dl_first(list);
        while (node && i--)
            node = dl_next(node);
    } else {
        i = dl_count(list) - 1 - i;
        node = dl_last(list);
        while (node && i--)
            node = dl_prev(node);
    }

    return node;
}

dlnode *
dl_search(dllist *list, void *data, int (*cmpfunc)(void *, void *))
{
    dlnode *node;

    for (node = dl_first(list); node; node = dl_next(node))
        if (cmpfunc(dl_data(node), data) == 0)
            break;

    return node;
}

void
dl_sort(dllist *list, int (*cmpfunc)(void *, void *))
{
    dlnode *node = dl_first(list);

    while (node) {
        dlnode *next = dl_next(node);

        if (next && cmpfunc(dl_data(node), dl_data(next)) > 0) {
            dlnode *tmp = node;

            dl_unlink(list, next);

            do
                tmp = dl_prev(tmp);
            while (tmp && cmpfunc(dl_data(tmp), dl_data(next)) > 0);

            dl_link(list, tmp, next);
        } else {
            node = next;
        }
    }
}