#include <stdlib.h>
/*	Linked List Abstract Data Type

	Written by: G & F
	Modified by Peter Brusilovsky
*/

/*	List ADT Type Defintions */

	typedef struct 
        {
         int         data;
         struct node   *link;
        } NODE;

	typedef struct
        {
           int    count; 
           NODE  *pos;
           NODE  *head; 
           NODE  *rear;
        } LIST;
        
/*	Prototype Declarations */
	LIST *createList ();
	
	LIST *destroyList (LIST *list);

	int addNode (LIST *pList, int newdata);

	int removeNode(LIST *pList, int d_data);

	static int retrieveNode(LIST  *pList, int key);

	int traverse (LIST  *pList, int fromWhere, int *t_data);

	int listCount (LIST *pList);
	int emptyList (LIST *pList);
	int fullList  (LIST *pList); 

	static int _insert (LIST *pList, NODE *pPre, int newdata);

	void _delete (LIST *pList, NODE  *pPre, NODE  *pLoc);

	static int _search  (LIST  *pList, NODE **pPre, NODE **pLoc, int s_data);
/*	End of List ADT Definitions */

/*	=============== createList ==============	*/
/*	Allocates dynamic memory for a linked list head
	node and returns its address to caller
	Pre		compare is address of compare function used 
			whenever two nodes need to be compared.
	Post		head has allocated or error returned
	Return		head node pointer or null if memory overflow 
*/
LIST *createList()
{
/*	Local Declarations */
	LIST *list;

/*	Statements */
	list = (LIST *) malloc (sizeof (LIST));
	if (list)
		{
		 list->head     = NULL;
		 list->pos      = NULL;
		 list->rear     = NULL;
		 list->count    = 0;
		} /* if */

	return list;
}	/* createList */

/*	=============== addNode ============== */
/*	Inserts data into linked list.
	Pre		pList is a pointer to a valid list
			dataInPtr is a pointer to data to be inserted
	Post		data inserted unless dupe key or overflow
	Return		-1 if overflow, 0 if successful, 1 if dupe key
*/
int addNode	(LIST *pList, int newdata )
{
/*	Local Declarations */
	int found;
	int success;
	
	NODE *pPre;
	NODE *pLoc;
	
/*	Statements */
	found = _search (pList, &pPre, &pLoc, newdata);
	if (found == 1)
		/* Duplicate keys not allowed */
		return (+1);
		
	success = _insert (pList, pPre, newdata);
	if (!success)
		/* Overflow */
		return (-1);
	return (0);
}	/* addNode */

/*	=============== _insert ============== */
/*	Inserts data pointer into a new node in the linked list.
		Pre		pList is a pointer to a valid list
				pPre is a pointer to the data's predecessor
				dataInPtr contains data pointer to be inserted
		Post		data have been inserted in sequence
		Return		 boolean,			true if successful, 
							false if memory overflow. 
*/
static int _insert (LIST *pList, NODE *pPre, int newdata)
{
/*	Local Declarations */
	NODE *pNew;

/*	Statements */
	if (!(pNew = (NODE *) malloc(sizeof(NODE))))
		return 0;
		
	pNew->data = newdata; 
	pNew->link = NULL; 
		 
	if (pPre == NULL) {
		 /* Adding before first node or to empty list. */
		 pNew->link = pList->head;
		 pList->head = pNew;
		 if (pList->count == 0)
		 	/* Adding to empty list. Set rear */
		 	pList->rear = pNew;
	} else {
		 /* Adding in middle or at end */
		 pNew->link  = pPre->link;
		 pPre->link  = pNew;
		 
		 /* Now check for add at end of list */
		 if (pNew->link == NULL)
			pList->rear = pNew;
	} /* if else */ 
		
	(pList->count)++;
	return 1;
}	/* _insert */

/*	=============== removeNode ============== */
/*	Removes data from linked list. 
		Pre		pList      is a pointer to a valid list
				d_data     is key to be deleted
		Post		Node deleted or error returned.
		Return		false (0) if not found; true (1) if deleted
*/
	int removeNode(LIST *pList, int d_data)
{
/*	Local Declarations */
	int found;
	
	NODE *pPre;
	NODE *pLoc;
	
/*	Statements */
	found = _search (pList, &pPre, &pLoc, d_data);
	if (found)
		 _delete (pList, pPre, pLoc);
	
	return found;
}	/* removeNode */

/*	=============== _delete ============== */
/*	Deletes data from a linked list and returns 
	pointer to data to calling module.
		Pre		pList is a pointer to a valid list.
				pPre is a pointer to predecessor node
				pLoc is a pointer to target node
		Post		Data have been deleted
					Data memory has been freed
*/
void _delete (LIST *pList, NODE  *pPre, NODE  *pLoc) 
{
/*	Statements */
	if (pPre == NULL)
		/* Deleting first node */
		pList->head = pLoc->link;
	else
		/* Deleting any other node */
		pPre->link = pLoc->link;
	 
	/* Test for deleting last node */
	if (pLoc->link == NULL)
	    pList->rear = pPre;

	(pList->count)--;
	free (pLoc);

	return;
}	/* _delete */

/*  =============== searchList ============== */
/*	Interface to search function. 
	Pre    pList is a pointer to an initialized list.
	       pArgu is pointer to key being sought
	Post   pDataOut contains pointer to found data
			 -or- NULL if not found
	Return boolean true if successful, false if not found. 
*/


/*	=============== _search ============== */
/*	Searches list and passes back address of node containing 
	target and its logical predecessor.
	Pre		pList is a pointer to an initialized list.
			pPre is pointer variable to receive predecessor
			pLoc is pointer variable to receive node
			pArgu is pointer to key being sought
	Post		pLoc points to first node equal/greater key 
			 -or- null if target > key of last node
			pPre points to largest node smaller than key
			 -or- null if target < key of first node
	Return		boolean true if successful, false if not found. 

*/
int _search	(LIST  *pList, NODE **pPre,  NODE **pLoc, int s_data)
{
/*	Statements */
	*pPre  = NULL;
	*pLoc  = pList->head;
	if (pList->count == 0)
	    return 0;
	
	/* Test for argument > last node in list */
	if ( s_data > pList->rear->data) 
		{
		 *pPre = pList->rear;
		 *pLoc = NULL;
		 return 0;
		} /* if */

	while ( s_data > (*pLoc)->data )
		{
		 /* Have not found search argument location */
		 *pPre = *pLoc;
		 *pLoc = (*pLoc)->link;
		} /* while */
	
	if (s_data == (*pLoc)->data)
		/* argument found--success */
		return 1;
	else /* i.e., s_data < (*pLoc)->data */
		return 0;
}	/* _search */

/*	=============== retrieveNode ============== */
/*	This algorithm retrieves data in the list without
	changing the list contents. 
		Pre		pList is a pointer to an initialized list.
				pArgu is a pointer to key of data to be retrieved
		Return		boolean true if successful, 
				false if underflow. 
*/
static int retrieveNode(LIST  *pList, int key)
{
/*	Local Declarations */
	NODE  *pPre;
	NODE  *pLoc;
	
/*	Statements */
	return _search (pList, &pPre, &pLoc, key);
}	/* retrieveNode */


/*	=============== emptyList ============== */
/*	Returns boolean indicating whether or not the
	list is empty
	Pre		pList is a pointer to a valid list 
	Return		boolean true if empty, false if list has data 
*/
int emptyList (LIST *pList) 
{
/*	Statements */

	return (pList->count == 0);

}	/* emptyList */

/*	=============== fullList ============== */
/* 	Returns boolean indicating no room for more data. The list
	is full if memory cannot be allocated for another node. 
	Pre		pList is a pointer to a valid list 
	Return		boolean true if full, 
			false if room for another node.
*/
int fullList (LIST *pList) 
{
/*	Local Declarations */ 
NODE *temp;

/*	Statements */
	if ((temp = (NODE *)malloc (sizeof (NODE))))
		{
		 free (temp);
		 return 0;
		}

	/* Dynamic memory full */
	return 1;

}	/* fullList */

/*	=============== listCount =============== */
/*	Returns integer representing number of nodes in list.
	Pre		pList is a pointer to a valid list
	Return		count for number of nodes in list
*/
int listCount(LIST *pList) 
{
/*	Statements */

	return pList->count;
	
}	/* listCount */

/*	=============== traverse ============== */
/*	Traverses a linked list. Each call either starts at 
	the beginning of list or returns the location of the 
	element in the list that was last returned.
	Pre		pList       is a pointer to a valid list
			fromWhere   is 0 to start at the first element
			dataPtrOut is address of a pointer to data
	Post		if another element, address placed in dataPtr
	Return		true if another element located, 
			false if end of list
*/
int traverse (LIST  *pList, int fromWhere, int *t_data)
{
/*	Local Declarations */
	int success;

/*	Statements */
	if (fromWhere == 0) {
		 /*Start from first node */
		 if (pList->count == 0)
		 	success = 0;
		 else {
		 	 pList->pos	= pList->head;
		 	 *t_data = pList->pos->data;
		 	 success = 1;
		 } /* if else */
	} else {
		 /* Start from current position */
		 if (pList->pos->link == NULL)
		 	success = 0;
		 else {
		 	 pList->pos	= pList->pos->link;
		 	 *t_data = pList->pos->data;
		 	 success = 1;
		 } /* if else */
	} /* if fromwhere else */
	
	return success;
} /* traverse */
/*	=============== destroyList ============== */
/* 	Deletes all data in list and recycles memory
	Pre		List is a pointer to a valid list.
	Post		All data and head structure have been deleted.
	Return		null head pointer
*/
LIST *destroyList (LIST *pList) 
{
/*	Local Declarations */
	NODE  *deletePtr;

/*	Statements */
	if (pList) {
		 while (pList->count > 0) {
			 /* Delete node */
			  deletePtr = pList->head;
			  pList->head = pList->head->link; 
			  pList->count--;
			  free (deletePtr); 
		}
		free (pList);
	} /* if */

	return NULL;
}	/* destroyList */