/*
** linked-list.c
*/

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

#include "misc.h"
#include "mem-debug.h"
#include "linked-list.h"

typedef struct _linkedListNode
{
    struct _linkedListNode *next; /* pointer to the next node in the list */
    foint data;		/* data (of unknown type) stored in this node */
} LINKED_LIST_NODE;


struct _linkedListType
{
    int n;                          /* number of elments in the list */
    Boolean dynamicData;            /* true if the node 'data' field
		                    ** points to dynamically allocated memory,
				    ** false otherwise */
    pCmpFcn comparisonFunction;
    LINKED_LIST_NODE *first;
    LINKED_LIST_NODE *last;
};

LINKED_LIST *LinkedListAlloc( pCmpFcn comparisonFunction,
    Boolean dynamicData )
{
    LINKED_LIST *ll = MALLOC( sizeof(LINKED_LIST) );

    ll->first = ll->last = NULL;
    ll->n = 0;
    ll->comparisonFunction = comparisonFunction;
    ll->dynamicData = dynamicData;

    return ll;
}


void LinkedListReset( LINKED_LIST *ll )
{
    LINKED_LIST_NODE *node = ll->first;

    while( node != NULL )
    {
        LINKED_LIST_NODE *prev = node;
        node = node->next;
        if( ll->dynamicData && prev->data.v != NULL )
            FREE( prev->data.v );
        FREE( prev );
    }

    ll->first = ll->last = NULL;
    ll->n = 0;
}


int LinkedListSize( LINKED_LIST *ll )
{
    return ll->n;
}


void LinkedListFree( LINKED_LIST *ll )
{
    LinkedListReset( ll );
    FREE( ll );
}


foint LinkedListPrepend( LINKED_LIST *ll, foint newEntry )
{
    LINKED_LIST_NODE *newNode = MALLOC( sizeof(LINKED_LIST_NODE) );

    newNode->data = newEntry;

    newNode->next = ll->first;
    ll->first = newNode;
    if( ll->last == NULL )
        ll->last = newNode;

    ll->n++;

    return newEntry;
}


foint LinkedListAppend( LINKED_LIST *ll, foint newEntry )
{
    LINKED_LIST_NODE *newNode = MALLOC( sizeof(LINKED_LIST_NODE) );

    newNode->data = newEntry;
    newNode->next = NULL;

    if( ll->first == NULL )
    {
        assert( ll->n == 0 && ll->last == NULL );
        ll->first = newNode;
    } else {
        assert( ll->n > 0 );
        ll->last->next = newNode;
    }
    ll->last = newNode;

    ll->n++;

    return newEntry;
}


foint LinkedListInsert( LINKED_LIST *ll, foint newEntry )
{
    LINKED_LIST_NODE *prev = NULL;
    LINKED_LIST_NODE *curr = ll->first;

    assert( ll->comparisonFunction != NULL );

    /* if we're first... */
    if(ll->first == NULL ||
	ll->comparisonFunction(newEntry, ll->first->data) < 0 )
        return LinkedListPrepend( ll, newEntry );

    /* we could be last */
    if( ll->comparisonFunction(newEntry, ll->last->data) >= 0 )
        return LinkedListAppend( ll, newEntry );

    /* else ... */
    while( curr != NULL && ll->comparisonFunction(newEntry, curr->data) >= 0 )
    {
        prev = curr;
        curr = curr->next;
    }

    assert( curr != NULL ); /* if we're last, it should've been done above! */
    assert( prev->next == curr );

    prev->next = MALLOC( sizeof(LINKED_LIST_NODE) );
    prev->next->data = newEntry;
    prev->next->next = curr;

    ll->n++;

    return newEntry;
}


foint LinkedListFind( LINKED_LIST *ll, pCmpFcn CmpFcn, foint entry )
{
    LINKED_LIST_NODE *prev = NULL;
    LINKED_LIST_NODE *curr = ll->first;

    assert( CmpFcn != NULL );

    while( curr != NULL && CmpFcn(entry, curr->data) != 0 )
    {
        prev = curr;
        curr = curr->next;
    }

    if( curr == NULL )	/* not found */
	return ABSTRACT_ERROR;

    assert( ll->first == curr || prev->next == curr );

    return curr->data;
}


foint LinkedListDelete( LINKED_LIST *ll, pCmpFcn CmpFcn, foint entry )
{
    LINKED_LIST_NODE *prev = NULL;
    LINKED_LIST_NODE *curr = ll->first;

    assert( CmpFcn != NULL );

    while( curr != NULL && CmpFcn(entry, curr->data) != 0 )
    {
        prev = curr;
        curr = curr->next;
    }

    if( curr == NULL ) /* Nothing to delete! */
	return ABSTRACT_ERROR;

    if(curr == ll->first)
	ll->first = curr->next;
    else
	prev->next = curr->next;

    /* last is tricky, especilally if ll->n == 1 */
    if(curr == ll->last)
    {
	ll->last = prev;
	if(prev == NULL)
	    assert(ll->n == 1);
    }

    --ll->n;

    entry = curr->data;
    Free(curr);

    return entry;
}


foint LinkedListPeek( LINKED_LIST *ll )
{
    if( ll->n == 0 )
    {
        assert( ll->first == NULL && ll->last == NULL );
        FATAL( "LinkedListPeek: the list is empty" );
        return (foint )0;        /* too keep gcc quiet */
    }
    return ll->first->data;
}


foint LinkedListNext( LINKED_LIST *ll )
{
    foint data;
    LINKED_LIST_NODE *newFirst;
    if( ll->n == 0 )
    {
        assert( ll->first == NULL && ll->last == NULL );
        FATAL( "LinkedListNext: nothing to return!" );
    }

    data = ll->first->data;

    newFirst = ll->first->next;
    FREE( ll->first );
    ll->first = newFirst;
    if( ll->first == NULL )
	ll->last = NULL;

    ll->n--;

    return data;
}


void LinkedListSanityCheck( LINKED_LIST *ll, Boolean ordered )
{
    LINKED_LIST_NODE *prev, *curr;
    assert( ll );
    assert( ll->n >= 0 );

    if( ordered )
        assert( ll->comparisonFunction != NULL );

    if( ll->n == 0 )
        assert( ll->first == NULL && ll->last == NULL );
    else if( ll->n == 1 )
        assert( ll->first == ll->last && ll->first->next == NULL );
    else { /* n >= 2 */
        int i;
        prev = NULL;
        curr = ll->first;
        for( i = 0; i < ll->n - 1; i++ )
        {
            assert( curr != NULL );
            assert( curr->next != NULL );
            if( ordered )
                assert(ll->comparisonFunction(curr->data, curr->next->data)<=0);
            prev = curr;
            curr = curr->next;
        }
        assert( curr == ll->last );
        assert( ll->last->next == NULL );
    }
}
