/*
// Full copyright information is available in the file ../doc/CREDITS
//
// Routines for list manipulation.
//
// This code is not ANSI-conformant, because it allocates memory at the end
// of List structure and references it with a one-element array.
*/

#include "defs.h"
#include "quickhash.h"

/* Note that we number list elements [0..(len - 1)] internally, while the
 * user sees list elements as numbered [1..len]. */

/* We use MALLOC_DELTA to keep our blocks about 32 bytes less than a power of
 * two.  We also have to account for the size of a List (16 bytes) which gets
 * added in before we allocate.  This works if a Data is sixteen bytes. */
  
#define MALLOC_DELTA    3
#define STARTING_SIZE   (16 - MALLOC_DELTA)

/* Input to this routine should be a list you want to modify, a start, and a
 * length.  The start gives the offset from list->el at which you start being
 * interested in data; the length is the amount of data there will be in the
 * list after that point after you finish modifying it.
 *
 * The return value of this routine is a list whose contents can be freely
 * modified, containing at least the information you claimed was interesting.
 * list->start will be set to the beginning of the interesting data; list->len
 * will be set to len, even though this will make some data invalid if
 * len > list->len upon input.  Also, the returned string may not be null-
 * terminated.
 *
 * If start is increased or len is decreased by this function, and list->refs
 * is 1, the uninteresting data will be discarded by this function.
 *
 * In general, modifying start and len is the responsibility of this routine;
 * modifying the contents is the responsibility of the calling routine. */

cList * list_prep(cList *list, Int start, Int len) {
    cList * cnew;
    Int      i,
             resize,
             size;

    /* Figure out if we need to resize the list or move its contents.  Moving
     * contents takes precedence. */
#if DISABLED
    resize = (len - start) * 4 < list->size;
    resize = resize && list->size > STARTING_SIZE;
    resize = resize || (list->size < len);
#endif
    resize = list->size < len + start;


    /* Move the list contents into a new list. */
    if ((list->refs > 1) || (resize && start > 0)) {
        cnew = list_new(len);
        cnew->len = len;
        len = (list->len < len) ? list->len : len;
        for (i = 0; i < len; i++)
            data_dup(&cnew->el[i], &list->el[start + i]);
        list_discard(list);
        return cnew;
    }

    /* Resize the list.  We can assume that list->start == start == 0. */
    else if (resize) {
        for (; list->len > len; list->len--)
            data_discard(&list->el[list->len - 1]);
        list->len = len;
        size = len;
        list = (cList *) erealloc(list,
                                   sizeof(cList) + (size * sizeof(cData)));
        list->size = size;
        return list;
    }

    else {
        for (; list->start < start; list->start++, list->len--)
            data_discard(&list->el[list->start]);
        for (; list->len > len; list->len--)
            data_discard(&list->el[list->start + list->len - 1]);
        list->start = start;
        list->len = len;
        return list;
    }
}


cList *list_new(Int len) {
    cList * cnew;
    cnew = (cList *) emalloc(sizeof(cList) + (len * sizeof(cData)));
    cnew->len = 0;
    cnew->start = 0;
    cnew->size = len;
    cnew->refs = 1;
    return cnew;
}

cList *list_dup(cList *list) {
    list->refs++;
    return list;
}

Int list_length(cList *list) {
    return list->len;
}

cData *list_first(cList *list) {
    return (list->len) ? list->el + list->start : NULL;
}

cData *list_next(cList *list, cData *d) {
    return (d < list->el + list->start + list->len - 1) ? d + 1 : NULL;
}

cData *list_last(cList *list) {
    return (list->len) ? list->el + list->start + list->len - 1 : NULL;
}

cData *list_prev(cList *list, cData *d) {
    return (d > list->el + list->start) ? d - 1 : NULL;
}

cData *list_elem(cList *list, Int i) {
    return list->el + list->start + i;
}

/* This is a horrible abstraction-breaking function.  Call it just after you
 * make a list with list_new(<spaces>).  Then fill in the data slots yourself.
 * Don't manipulate <list> until you're done. */
cData * list_empty_spaces(cList *list, Int spaces) {
    list->len += spaces;
    return list->el + list->start + list->len - spaces;
}

Int list_search(cList *list, cData *data) {
    cData *d, *start, *end;

    start = list->el + list->start;
    end = start + list->len;
    for (d = start; d < end; d++) {
        if (data_cmp(data, d) == 0)
            return d - start;
    }
    return -1;
}

/* Effects: Returns 0 if the lists l1 and l2 are equivalent, or 1 if not. */
Int list_cmp(cList *l1, cList *l2) {
    Int i, k;

    /* They're obviously the same if they're the same list. */
    if (l1 == l2)
        return 0;

    /* Lists can only be equal if they're of the same length. */
    if (l1->len != l2->len)
        return 1;

    /* See if any elements differ. */
    for (i = 0; i < l1->len; i++) {
        if ((k=data_cmp(&l1->el[l1->start + i], &l2->el[l2->start + i])) != 0)
            return k;
    }

    /* No elements differ, so the lists are the same. */
    return 0;
}

/* Error-checking on pos is the job of the calling function. */
cList *list_insert(cList *list, Int pos, cData *elem) {
    list = list_prep(list, list->start, list->len + 1);
    pos += list->start;
    MEMMOVE(list->el + pos + 1, list->el + pos, list->len - 1 - pos);
    data_dup(&list->el[pos], elem);
    return list;
}

cList *list_add(cList *list, cData *elem) {
    list = list_prep(list, list->start, list->len + 1);
    data_dup(&list->el[list->start + list->len - 1], elem);
    return list;
}

/* Error-checking on pos is the job of the calling function. */
cList *list_replace(cList *list, Int pos, cData *elem) {
    /* list_prep needed here only for multiply referenced lists */
    if (list->refs > 1)
      list = list_prep(list, list->start, list->len);
    pos += list->start;
    data_discard(&list->el[pos]);
    data_dup(&list->el[pos], elem);
    return list;
}

/* Error-checking on pos is the job of the calling function. */
cList *list_delete(cList *list, Int pos) {
    /* Special-case deletion of last element. */
    if (pos == list->len - 1)
        return list_prep(list, list->start, list->len - 1);

    /* list_prep needed here only for multiply referenced lists */
    if (list->refs > 1)
        list = list_prep(list, list->start, list->len);

    pos += list->start;
    data_discard(&list->el[pos]);
    MEMMOVE(list->el + pos, list->el + pos + 1, list->len - pos);
    list->len--;

    /* list_prep needed here only if list has shrunk */
    if (((list->len - list->start) * 4 < list->size)
        && (list->size > STARTING_SIZE))
        list = list_prep(list, list->start, list->len);

    return list;
}

/* This routine will crash if elem is not in list. */
cList *list_delete_element(cList *list, cData *elem) {
    return list_delete(list, list_search(list, elem));
}

cList *list_append(cList *list1, cList *list2) {
    Int i;
    cData *p, *q;

    list1 = list_prep(list1, list1->start, list1->len + list2->len);
    p = list1->el + list1->start + list1->len - list2->len;
    q = list2->el + list2->start;
    for (i = 0; i < list2->len; i++)
        data_dup(&p[i], &q[i]);
    return list1;
}

cList *list_reverse(cList *list) {
    cData *d, tmp;
    Int i;

    /* list_prep needed here only for multiply referenced lists */
    if (list->refs > 1)
        list = list_prep(list, list->start, list->len);

    d = list->el + list->start;
    for (i = 0; i < list->len / 2; i++) {
        tmp = d[i];
        d[i] = d[list->len - i - 1];
        d[list->len - i - 1] = tmp;
    }
    return list;
}

cList *list_setadd(cList *list, cData *d) {
    if (list_search(list, d) != -1)
        return list;
    return list_add(list, d);
}

cList *list_setremove(cList *list, cData *d) {
    Int pos = list_search(list, d);
    if (pos == -1)
        return list;
    return list_delete(list, pos);
}

cList *list_union(cList *list1, cList *list2) {
    cData *start, *end, *d;

    start = list2->el + list2->start;
    end = start + list2->len;
    if (list1->len + list2->len < 12) {
        for (d = start; d < end; d++) {
            if (list_search(list1, d) == -1)
                list1 = list_add(list1, d);
        }
    } else {
        Hash * tmp;
        
        tmp = hash_new_with(list1);
        list_discard(list1);
        for (d = start; d < end; d++) {
            tmp = hash_add(tmp, d);
        }
        list1 = list_dup(tmp->keys);
        hash_discard(tmp);
    }
    return list1;
}

cList *list_sublist(cList *list, Int start, Int len) {
    return list_prep(list, list->start + start, len);
}

/* Warning: do not discard a list before initializing its data elements. */
void list_discard(cList *list) {
    Int i;

    if (!--list->refs) {
        for (i = list->start; i < list->start + list->len; i++)
            data_discard(&list->el[i]);
        efree(list);
    }
}

/* 'list' must ALWAYS have at least one element, it does not check */
#define ADD_TOSTR() \
    switch (d->type) { \
        case STRING: \
            s = string_add(s, d->u.str); \
            break; \
        case SYMBOL: \
            sp = ident_name(d->u.symbol); \
            s = string_add_chars(s, sp, strlen(sp)); \
            break; \
        default: \
            s = data_add_literal_to_str(s, d, TRUE); \
            break; \
    }

cStr * list_join(cList * list, cStr * sep) {
    Int size;
    cData * d;
    cStr * s;
    char * sp;
    
    /* figure up the size of the resulting string */
    size = sep->len * (list->len - 1);
    for (d=list_first(list); d; d = list_next(list, d)) {
        /* just guess on its resulting size, magic numbers, whee */
        if (d->type != STRING)
            size += 5;
        else
            size += d->u.str->len;
    }

    s = string_new(size);

    d = list_first(list);
    ADD_TOSTR() 
    for (d=list_next(list, d); d; d = list_next(list, d)) {
        s = string_add(s, sep);
        ADD_TOSTR()
    }   
    
    return s;
}

int list_index(cList * list, cData * search, int origin) {
    int     len;
    Bool    reverse = NO;
    cData * d,
          * start,
          * end;

    len = list_length(list);
    
    if (origin < 0) {
        reverse = YES;
        origin = -origin;
    }

    if (origin > len || !origin)
        return F_FAILURE;

    if (origin == len)
        return 0;

    origin--;
    start = list->el + list->start;
    end = start + list->len;

    if (reverse) {
        end -= (origin + 1);
        for (d = end; d >= start; d--) {
            if (data_cmp(search, d) == 0)
                return (d - start) + 1;
        }
    } else {
        start += origin;
        for (d = start; d < end; d++) {
            if (data_cmp(search, d) == 0)
                return (d - start) + 1;
        }
    }
    return 0;
}