/*
** linked-list.h
*/ 

#ifndef _LINKED_LIST_H
#define _LINKED_LIST_H  /* to ensure we don't include it more than once */

#include "misc.h"

/*
** LinkedList routines: a smallest-at-top list.  You also supply a
** comparison function.  You allocate a LL using LinkedListAlloc, and
** LinkedListCmp is a pointer to a function to compare your entries.
** Entries are of type foint, which is as close to a general "object" 
** that you can get in C without doing major surgery.
*/
typedef struct _linkedListType LINKED_LIST;


/*
** LinkedListAlloc:  allocate a linked list and make it empty.  If the
** list is to be ordered, a then 'CmpFcn' must be specified,
** otherwise it may be set to NULL.  If the linked list is to contain
** dynamically allocated data (i.e., if the 'data' fields of the list
** nodes point to allocated memory), then 'dynamicData' must be set to
** true.  A pointer to the list is returned.
*/
LINKED_LIST *LinkedListAlloc( pCmpFcn CmpFcn, Boolean dynamicData );


/*
** LinkedListSize: return the number of items in a linked list.
*/
int LinkedListSize( LINKED_LIST *ll );


/*
** LinkedListReset: Free everything in the list except the LINKED_LIST
** struct itself.  It does not have to be empty.
*/
void LinkedListReset( LINKED_LIST *ll );


/*
** LinkedListFree: Free the list and everything in it.
** It does not have to be empty.
*/
void LinkedListFree( LINKED_LIST *ll );


/*
** LinkedListPeek: peek at the top of the list without removing it from
** the list.
*/
foint LinkedListPeek( LINKED_LIST *ll );


/*
** LinkedListNext:  delete the top entry and returns its value.  If the list is
** empty it will fail with an assertion.
*/
foint LinkedListNext( LINKED_LIST *ll );


/*
** LinkedListPrepend: insert a new element at the front of the list, ignoring
** the comparison function.  The new value is returned after inserting.
*/
foint LinkedListPrepend( LINKED_LIST *ll, foint newEntry );


/*
** LinkedListAppend:  insert something at the end of the list, igroning the 
** comparison function.  The new value is returned after inserting.
*/
foint LinkedListAppend( LINKED_LIST *ll, foint newEntry ); 


/*
** LinkedListInsert:  insert something in the list, using the comparison
** function.  The element should be inserted *after* any elements that
** compare equally; that way, even if two events have the same time, they
** get executed in the order in which they were inserted.  This is
** sometimes important.  The new value is returned after inserting.
*/
foint LinkedListInsert( LINKED_LIST *ll, foint newEntry );


/*
** LinkedListFind:  find something in the list, using the comparison
** function.  The new entry is passed as the first argument to the
** comparison function.  Note you can use a function different from
** the one that's global to the list.
*/
foint LinkedListFind( LINKED_LIST *ll, pCmpFcn CmpFcn, foint entry );


/*
** LinkedListDelete: find, delete and return an arbitrary element from the
** list, using the given comparison function.
*/
foint LinkedListDelete( LINKED_LIST *ll, pCmpFcn CmpFcn, foint entry );


/*
** LinkedListSanityCheck:  checks a linked list for "sanity".  "ordered"
** should be true or false, and tells us whether we should check that
** elements are in order using the comparison function.  This function is
** provided for you.
*/
void LinkedListSanityCheck( LINKED_LIST *ll, Boolean ordered );

#endif  /* _LINKED_LIST_H */
