#include "misc.h"
#include "linked-list.h"
#include <stdio.h>
#include <assert.h>

typedef struct { int i; char s[10]; } DATA;

static int CmpInt(foint a, foint b)
{
    DATA *A=(DATA*)a.v, *B=(DATA*)b.v;
    return A->i - B->i;
}

#define NUM 10

int main(void)
{
    LINKED_LIST *ll = LinkedListAlloc( CmpInt, false );
    DATA *D = Malloc(NUM * sizeof(DATA));
    int i;

    srand48(time(NULL)+getpid());
    for(i=0; i<NUM; i++)
    {
	int j;
	assert(i == LinkedListSize( ll ));
	D[i].i = i;
	sprintf(D[i].s, "%d", i);

	LinkedListSanityCheck( ll, false );

	/* Insert it at the beginning and ensure everything is still there */
	LinkedListPrepend(ll, (foint)(void*)(D+i));
	LinkedListSanityCheck( ll, false );
	assert(i+1 == LinkedListSize( ll ));
	assert((DATA*)LinkedListPeek( ll ).v == D+i);
	LinkedListSanityCheck( ll, false );
	for(j=0; j<=i; j++)
	{
	    LinkedListSanityCheck( ll, false );
	    assert((DATA*)LinkedListFind(ll, CmpInt, (foint)(void*)(D+j)).v == D+j);
	    LinkedListSanityCheck( ll, false );
	}

	/* delete it and ensure everything else still remains */
	assert((DATA*)LinkedListDelete(ll, CmpInt, (foint)(void*)(D+i)).v == D+i);
	LinkedListSanityCheck( ll, false );
	assert(i == LinkedListSize( ll ));
	for(j=0; j<i; j++)
	{
	    LinkedListSanityCheck( ll, false );
	    assert((DATA*)LinkedListFind(ll, CmpInt, (foint)(void*)(D+j)).v == D+j);
	    LinkedListSanityCheck( ll, false );
	}

	/* Append it at the end and ensure everything is there again */
	LinkedListAppend(ll, (foint)(void*)(D+i));
	LinkedListSanityCheck( ll, false );
	assert(i+1 == LinkedListSize( ll ));
	for(j=0; j<=i; j++)
	{
	    LinkedListSanityCheck( ll, false );
	    assert((DATA*)LinkedListFind(ll, CmpInt, (foint)(void*)(D+j)).v == D+j);
	    LinkedListSanityCheck( ll, false );
	}
    }

    /* Now delete them in random order */
    i = NUM;
    while(i > 0)
    {
	extern double drand48(void);
	int del;

	assert(i == LinkedListSize( ll ));

	/* Find one to delete */
	do {
	    del = NUM*drand48();
	    printf("D[%d].i = %d\n", del, D[del].i);
	} while (D[del].i == -1);
	printf("deleting element %d\n", del);

	LinkedListSanityCheck( ll, false );
	assert((DATA*)LinkedListDelete(ll, CmpInt, (foint)(void*)(D+del)).v == D+del);
	LinkedListSanityCheck( ll, false );
	assert(i-1 == LinkedListSize( ll ));
	D[del].i = -1;
	i--;
    }

    assert(LinkedListSize( ll ) == 0);

    LinkedListFree( ll );
    return 0;
}
