#include "common.h"

typedef struct {
    int data;
    int next;
} NODE;

typedef struct {
    int head, free,
        length, size;
    NODE *elements;
} LIST;

LIST create_list(int n) {
    int i;
    LIST l;
    if (NULL == 
        (l.elements = Malloc(n, NODE))) {
        perror("out of memory");
        exit(1);
    }
    for (i = 0; i < n-1; i++)
        l.elements[i].next = i+1;
    l.elements[n-1].next = -1;
    l.size = n;
    l.free = 0;
    l.head = -1;
    l.length = 0;
    return l;
}

void insert(LIST *l, int d, int *node) 
{
    /* insert d in front of "node" */
    int position = l->free; /* d will be stored in first free node */
    int i;
    if (-1 == position) {
        /* array is full, need to realloc */
        l->size *= 2;
        if (NULL == Realloc(l->elements, l->size, NODE)) {
            perror("out of memory");
            return;
        }
        l->free = l->size/2; /* added part (2nd half) is free */
        for (i = l->free; i < l->size - 1; i++)
            l->elements[i].next = i+1;
        l->elements[l->size - 1].next = -1;
        position = l->free;
    }
    l->free = l->elements[l->free].next; /* remove first free node to hold d */
    l->elements[position].data = d;
    l->elements[position].next = *node;  /* insert d in front of "node" */
    *node = position; /* change pointer to "node" to point to new node */
    l->length++;
}

void delete(LIST *l, int node) {
    /* remove next node after "node" */
    int tmp;
    if (-1 != node) {
        tmp = l->elements[node].next; /* node to be removed */
        if (-1 != tmp) {
            l->elements[node].next = l->elements[tmp].next; /* skip node to be 
                                                             * removed */
            l->elements[tmp].next = l->free; /* add deleted node to front of */
            l->free = tmp;                   /* free list */
            l->length--;
        }
    }
}

void dump_list(LIST *l) { /* dump everything in the elements array */
    int i;

    printf("Size: %d Free: %d Head: %d Length: %d\n", l->size, l->free, l->head, l->length);
    for (i = 0; i < l->size; i++)
        printf("%5d %5d %5d\n", i, l->elements[i].data, l->elements[i].next);
}

void print_list(LIST *l) { /* print only the actual linked list */
    int i;

    for (i = l->head; i != -1; i = l->elements[i].next)
        printf("%d ", l->elements[i].data);
    putchar('\n');
    
}

int main(int ac, char *av[])
{
    int n, i;
    LIST l;

    if (ac < 2)
        ERR_MESG("Usage: linked-list <number>");
    n = atoi(av[1]);
    l = create_list(5);

    for (i = 0; i < n; i++)
        insert(&l, rand() % n, &(l.head));

    dump_list(&l);

    for (n = 0, i = l.head; l.elements[i].next != -1; n++, i = l.elements[i].next)
        if (n % 1 == 0)
            delete(&l, i);

    print_list(&l);
    return 0;
}