/*
 * frost_list.c
 *
 *  Created on: Jul 1, 2012
 *      Author: ergino
 */

#include "frost_list.h"

#include <stdio.h>

FROST_List*
frost_list_alloc ()
{
    return frost_new0 (FROST_List, 1);
}

static inline FROST_List*
new_node (FROST_List *prev, frost_pointer data, FROST_List *next)
{
    FROST_List *node = frost_list_alloc ();
    node->data = data;
    node->prev = prev;
    node->next = next;
    if (prev)
        prev->next = node;
    if (next)
        next->prev = node;
    return node;
}

static inline FROST_List*
disconnect_node (FROST_List *node)
{
    if (node->next)
        node->next->prev = node->prev;
    if (node->prev)
        node->prev->next = node->next;
    return node;
}

FROST_List *
frost_list_prepend (FROST_List *list, frost_pointer data)
{
    return new_node (list ? list->prev : NULL, data, list);
}

void
frost_list_free_1 (FROST_List *list)
{
    frost_free (list);
}

void
frost_list_free (FROST_List *list)
{
    while (list){
        FROST_List *next = list->next;
        frost_list_free_1 (list);
        list = next;
    }
}

FROST_List*
frost_list_append (FROST_List *list, frost_pointer data)
{
    FROST_List *node = new_node (frost_list_last (list), data, NULL);
    return list ? list : node;
}

FROST_List *
frost_list_concat (FROST_List *list1, FROST_List *list2)
{
    if (list1 && list2) {
        list2->prev = frost_list_last (list1);
        list2->prev->next = list2;
    }
    return list1 ? list1 : list2;
}

frost_uint
frost_list_length (FROST_List *list)
{
    frost_uint length = 0;

    while (list) {
        length ++;
        list = list->next;
    }

    return length;
}

FROST_List*
frost_list_remove (FROST_List *list, frost_constpointer data)
{
    FROST_List *current = frost_list_find (list, data);
    if (!current)
        return list;

    if (current == list)
        list = list->next;
    frost_list_free_1 (disconnect_node (current));

    return list;
}

FROST_List*
frost_list_remove_all (FROST_List *list, frost_constpointer data)
{
    FROST_List *current = frost_list_find (list, data);

    if (!current)
        return list;

    while (current) {
        if (current == list)
            list = list->next;
        frost_list_free_1 (disconnect_node (current));

        current = frost_list_find (list, data);
    }

    return list;
}

FROST_List*
frost_list_remove_link (FROST_List *list, FROST_List *link)
{
    if (list == link)
        list = list->next;

    disconnect_node (link);
    link->next = NULL;
    link->prev = NULL;

    return list;
}

FROST_List*
frost_list_delete_link (FROST_List *list, FROST_List *link)
{
    list = frost_list_remove_link (list, link);
    frost_list_free_1 (link);

    return list;
}

FROST_List*
frost_list_find (FROST_List *list, frost_constpointer data)
{
    while (list){
        if (list->data == data)
            return list;

        list = list->next;
    }

    return NULL;
}

FROST_List*
frost_list_find_custom (FROST_List *list, frost_constpointer data, FROSTCompareFunc func)
{
    if (!func)
        return NULL;

    while (list) {
        if (func (list->data, data) == 0)
            return list;

        list = list->next;
    }

    return NULL;
}

FROST_List*
frost_list_reverse (FROST_List *list)
{
    FROST_List *reverse = NULL;

    while (list) {
        reverse = list;
        list = reverse->next;

        reverse->next = reverse->prev;
        reverse->prev = list;
    }

    return reverse;
}

FROST_List*
frost_list_first (FROST_List *list)
{
    if (!list)
        return NULL;

    while (list->prev)
        list = list->prev;

    return list;
}

FROST_List*
frost_list_last (FROST_List *list)
{
    if (!list)
        return NULL;

    while (list->next)
        list = list->next;

    return list;
}

FROST_List*
frost_list_insert_sorted (FROST_List *list, frost_pointer data, FROSTCompareFunc func)
{
    FROST_List *prev = NULL;
    FROST_List *current;
    FROST_List *node;

    if (!func)
        return list;

    /* Invariant: !prev || func (prev->data, data) <= 0) */
    for (current = list; current; current = current->next) {
        if (func (current->data, data) > 0)
            break;
        prev = current;
    }

    node = new_node (prev, data, current);
    return list == current ? node : list;
}

FROST_List*
frost_list_insert_before (FROST_List *list, FROST_List *sibling, frost_pointer data)
{
    if (sibling) {
        FROST_List *node = new_node (sibling->prev, data, sibling);
        return list == sibling ? node : list;
    }
    return frost_list_append (list, data);
}

void
frost_list_foreach (FROST_List *list, FROSTFunc func, frost_pointer user_data)
{
    while (list){
        (*func) (list->data, user_data);
        list = list->next;
    }
}

frost_int
frost_list_index (FROST_List *list, frost_constpointer data)
{
    frost_int index = 0;

    while (list){
        if (list->data == data)
            return index;

        index ++;
        list = list->next;
    }

    return -1;
}

FROST_List*
frost_list_nth (FROST_List *list, frost_uint n)
{
    for (; list; list = list->next) {
        if (n == 0)
            break;
        n--;
    }
    return list;
}

frost_pointer
frost_list_nth_data (FROST_List *list, frost_uint n)
{
    FROST_List *node = frost_list_nth (list, n);
    return node ? node->data : NULL;
}

FROST_List*
frost_list_copy (FROST_List *list)
{
    FROST_List *copy = NULL;

    if (list) {
        FROST_List *tmp = new_node (NULL, list->data, NULL);
        copy = tmp;

        for (list = list->next; list; list = list->next)
            tmp = new_node (tmp, list->data, NULL);
    }

    return copy;
}

typedef FROST_List list_node;
#include "sort.frag.h"

FROST_List*
frost_list_sort (FROST_List *list, FROSTCompareFunc func)
{
    FROST_List *current;
    if (!list || !list->next)
        return list;
    list = do_sort (list, func);

    /* Fixup: do_sort doesn't update 'prev' pointers */
    list->prev = NULL;
    for (current = list; current->next; current = current->next)
        current->next->prev = current;

    return list;
}
