/*
 * llist.c	Matt Bishop
 *
 * This is a library of linked list functions:
 * insert	-- inserts a value into the linked list
 * delete	-- deletes a value from the linked list
 * prforw	-- prints the values in the list in order
 * prback	-- prints the values in the list in reverse order
 */

#include "llist.h"

/*
 * insert: insert a value into a linked list
 *
 * arguments:   	LLIST **head	address of pointer to head of
 *						linked list
 *			int value		value to be inserted
 *
 * return:     	 1	insertion succeeded; on return, head points
 *				to the address of the (possibly new) head of
 *				the linked list
 *			0	insertion failed
 *
 * output:      none
 *
 * exceptions:  memory cannot be allocated (returns 0)
 */
int insert(LLIST **head, int value)
{
	register LLIST *p, *q;	/* pointers to walk linked list */
	/*
	 * you can argue whether or not this next line had a bug,
	 * but it certainly was poor style, since lalloc is
	 * called below!
	 */
	register LLIST *temp;		/* points to new node */

	/*
	 * construct new node for the linked list
	 */
	if ((temp = lalloc()) == NULL)
		return(0);
	temp->val = value;
	temp->next = L_NULL;

	/*
	 * if an empty list, make this node the head
	 */
	if (*head == NULL){
		*head = temp;
		return(1);
	}
	/*
	 * walk the linked list; after this loop,
	 * you'll need to insert the new node between
	 * p and q
	 */
	for(p = *head; p != NULL && p->val < value; p = p->next)
		q = p;
	/*
	 * insert the new node and return success
	 */
	q->next = temp;
	temp->next = p;
	return(1);
}

/*
 * delete: delete a value from a linked list
 *
 * arguments:   	LLIST **head	address of pointer to head of
 *						linked list
 *			int value		value to be inserted
 *
 * return:     	1	deletion succeeded; on return, head points
 *				to the address of the (possibly new) head of
 *				the linked list
 *			0	deletion failed
 *
 * output:      	none
 *
 * exceptions:  	pointer to ptr to head of list is NULL (return 0)
 *			no node in the list contains value (return 0)
 */
int delete(LLIST **head, int value)
{
	register LLIST *p, *q;		/* used to locate node in list */

	/*
	 * if an empty list, nothing to delete
	 */
	if (*head == NULL)
		return(0);
 	/*
	 * value is at the head of linked list
	 */
	if ((*head)->val == value){
		/* make head point to next one */
		p = *head;
		*head = (*head)->next;
		/* free it and return success */
		(void) free(p);
		return(1);
	}
	/*
	 * figure out where the node to be deleted is
	 * after this loop, if there is a node with the given
	 * value in the linked list, p points to it, and
	 * q points to its predecessor
	 */
	for(p = *head; p != NULL && p->val < value; p = p->next)
		q = p;
	/* see if the value is in the list */
	if (p->val != value)
		return(0);
	/*
	 * release the deleted node and return success
	 */
	(void) free(p);
	return(1);
}
 /*
 * prforw -- print list
 *
 * arguments:   LLIST *head	pointer to head of linked list
 *
 * return:      nothing
 *
 * output:      list of values in linked list, one per line
 *
 * exceptions:  none
 */
void prforw(LLIST *head)
{
	register LLIST *p;		/* pointer in a for loop */

	/*
	 * walk the list, printing as you go
	 */
	for(p = head; p != NULL; p = p->next)
		printf("%d\n", p->val);
}

/*
 * prback -- print list backwards
 *
 * arguments:   LLIST *head	pointer to head of linked list
 *
 * return:      nothing
 *
 * output:      list of values in linked list (in reverse), one per line
 *
 * exceptions:  none
 */
void prback(LLIST *head)
{
	/* if list is empty, print nothing */
	if (head == NULL)
		return;
	/* print rest of list */
	(void) prback(head->next);
	/* print this node */
	printf("%d\n", head->val);
	
}