/*
// Full copyright information is available in the file ../doc/CREDITS
*/

#define NATIVE_MODULE "$list"

#include "cdc.h"

NATIVE_METHOD(listlen)
{
    Int len;

    INIT_1_ARG(LIST);

    len = list_length(LIST1);

    CLEAN_RETURN_INTEGER(len);
}

NATIVE_METHOD(sublist)
{
    Int start, span, len;
    cList *list;

    INIT_2_OR_3_ARGS(LIST, INTEGER, INTEGER);
    len = list_length(LIST1);
    start = INT2 - 1;
    span = (argc == 3) ? INT3 : len - start;

    /* Make sure range is in bounds. */
    if (start < 0) {
        THROW((range_id, "Start (%d) less than one", start + 1));
    } else if (span < 0) {
        THROW((range_id, "Sublist length (%d) less than zero", span));
    } else if (start + span > len) {
        THROW((range_id, "Sublist extends to %d, past end of list (length %d)", start + span, len));
    }
    list = list_dup(LIST1);

    CLEAN_STACK();
    anticipate_assignment();

    list = list_sublist(list, start, span);

    RETURN_LIST(list);
}

NATIVE_METHOD(insert)
{
    Int pos, len;
    cList *list;
    cData data;
    DEF_args;

    INIT_ARGC(ARG_COUNT, 3, "three");
    INIT_ARG1(LIST);
    INIT_ARG2(INTEGER);
    pos = INT2 - 1;
    len = list_length(LIST1);

    if (pos < 0) {
        THROW((range_id, "Position (%d) less than one", pos + 1));
    } else if (pos > len) {
        THROW((range_id, "Position (%d) beyond end of list (length %d)", pos + 1, len));
    }
    data_dup(&data, &args[2]);
    list = list_dup(LIST1);

    CLEAN_STACK();
    anticipate_assignment();

    list = list_insert(list, pos, &data);
    data_discard(&data);

    RETURN_LIST(list);
}

NATIVE_METHOD(replace)
{
    Int pos, len;
    cList *list;
    cData data;
    DEF_args;

    INIT_ARGC(ARG_COUNT, 3, "three");
    INIT_ARG1(LIST) INIT_ARG2(INTEGER) len = list_length(LIST1);
    pos = INT2 - 1;

    if (pos < 0) {
        THROW((range_id, "Position (%d) less than one", pos + 1));
    } else if (pos > len - 1) {
        THROW((range_id, "Position (%d) greater than length of list (%d)", pos + 1, len));
    }
    data_dup(&data, &args[2]);
    list = list_dup(LIST1);
    CLEAN_STACK();
    anticipate_assignment();

    list = list_replace(list, pos, &data);
    data_discard(&data);

    RETURN_LIST(list);
}

NATIVE_METHOD(delete)
{
    Int pos, len;
    cList *list;

    INIT_2_ARGS(LIST, INTEGER);
    len = list_length(LIST1);
    pos = INT2 - 1;

    if (pos < 0) {
        THROW((range_id, "Position (%d) less than one", pos + 1));
    } else if (pos > len - 1) {
        THROW((range_id, "Position (%d) greater than length of list (%d)", pos + 1, len));
    }

    list = list_dup(LIST1);

    CLEAN_STACK();
    anticipate_assignment();

    RETURN_LIST(list_delete(list, pos));
}

NATIVE_METHOD(setadd)
{
    cList *list;
    cData data;
    DEF_args;

    INIT_ARGC(ARG_COUNT, 2, "two");
    INIT_ARG1(LIST);
    data_dup(&data, &args[1]);
    list = list_dup(LIST1);

    CLEAN_STACK();
    anticipate_assignment();

    list = list_setadd(list, &data);
    data_discard(&data);

    RETURN_LIST(list);
}

NATIVE_METHOD(setremove)
{
    cList *list;
    cData data;
    DEF_args;

    INIT_ARGC(ARG_COUNT, 2, "two");
    INIT_ARG1(LIST);
    data_dup(&data, &args[1]);
    list = list_dup(LIST1);

    CLEAN_STACK();
    anticipate_assignment();

    list = list_setremove(list, &data);
    data_discard(&data);

    RETURN_LIST(list);
}

NATIVE_METHOD(union)
{
    cList *list, *list2;

    INIT_2_ARGS(LIST, LIST);
    list = list_dup(LIST1);
    list2 = list_dup(LIST2);

    CLEAN_STACK();
    anticipate_assignment();

    list = list_union(list, list2);

    list_discard(list2);

    RETURN_LIST(list);
}

NATIVE_METHOD(join)
{
    Int discard_sep = NO;
    cStr *str, *sep;

    INIT_1_OR_2_ARGS(LIST, STRING);
    if (!LIST1->len) {
        str = string_new(0);
    } else {
        if (argc == 1) {
            sep = string_from_chars(" ", 1);
            discard_sep = YES;
        } else {
            sep = STR2;
        }
        str = list_join(LIST1, sep);
        if (discard_sep)
            string_discard(sep);
    }

    CLEAN_RETURN_STRING(str);
}

static void
merge_lists(cData * l, cData * key, Int start1, Int end1, Int start2, Int end2, cData * l_out, cData * key_out)
{
    Int i, j, k;

    i = start1;
    j = start2;
    k = start1;

    while (i <= end1 && j <= end2)
        if (data_cmp(key + j, key + i) >= 0)
            key_out[k] = key[i], l_out[k++] = l[i++];
        else
            key_out[k] = key[j], l_out[k++] = l[j++];
    while (i <= end1)
        key_out[k] = key[i], l_out[k++] = l[i++];
    while (j <= end2)
        key_out[k] = key[j], l_out[k++] = l[j++];
    memcpy(l + start1, l_out + start1, sizeof(cData) * (k - start1));
    memcpy(key + start1, key_out + start1, sizeof(cData) * (k - start1));
}

static void merge_sort(cData * l, cData * key, cData * l1, cData * key1, Int start, Int end)
{

    Int mid;

    if (start == end)
        return;

    mid = (start + end) / 2;
    merge_sort(l, key, l1, key1, start, mid);
    merge_sort(l, key, l1, key1, mid + 1, end);
    merge_lists(l, key, start, mid, mid + 1, end, l1, key1);
}

NATIVE_METHOD(sort)
{
    cData *d1, *d2, *key1, *key2;
    Int n, i;
    cList *data, *keys;
    cList *out;

    INIT_1_OR_2_ARGS(LIST, LIST);
    data = LIST1;
    if (argc == 1)
        keys = data;
    else
        keys = LIST2;

    n = list_length(data);
    if (!(list_length(keys) == n)) {
        THROW((range_id, "Key and data lists are not of the same length"));
    }

    if (!n) {
        out = list_dup(data);
        CLEAN_RETURN_LIST(out);
    }

    d1 = emalloc(sizeof(cData) * n);
    d2 = emalloc(sizeof(cData) * n);
    key1 = emalloc(sizeof(cData) * n);
    key2 = emalloc(sizeof(cData) * n);

    for (i = 0; i < n; i++) {
        data_dup(d1 + i, list_elem(data, i));
        data_dup(key1 + i, list_elem(keys, i));
    }
    merge_sort(d1, key1, d2, key2, 0, n - 1);

    out = list_new(n);
    out->len = n;
    for (i = 0; i < n; i++) {
        *list_elem(out, i) = d1[i];     /* We already did data_dup */
        data_discard(key1 + i);
    }

    efree(d1);
    efree(d2);
    efree(key1);
    efree(key2);

    CLEAN_RETURN_LIST(out);
}
