/**		insert.c		**/

/** For CES 490A - one solution to HW#1 problem 3 **/

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

struct node { int          data;
              struct node *next;
	    };

struct node *root = NULL;

/* Print out the linked list to stdout */
void printList( struct node * head ) {
    printf("List contains:\n");
    while (head != NULL) {
        printf("  %i\n", head->data);
	head= head->next;
    }
}

/* Insert a node into the correct spot in the linked list. */
void insert( struct node **pHead, struct node *element ) {
    struct node *curr;
    struct node *prev;
    curr= *pHead;
    prev= NULL;

    /* Find the correct spot. Loop ends when prev points to the node to
       insert after. If prev is NULL, insert at the beginning of the list */
    while (curr != NULL) {
        if (curr->data < element->data) {
	    /* wrong spot, try the next one */
	    prev= curr;
	    curr= curr->next;
	}
	else {
	    /* correct spot, leave the loop */
	    curr= NULL;
	}
    }

    if (prev == NULL) {
        /* Special case to insert at the start of the list */
        element->next= *pHead;
	*pHead= element;
    }
    else {
        /* Normal case to insert after "prev" */
        element->next= prev->next;
        prev->next= element;
    }
}

/* main program is to test the insert() routine */
/* start with an empty list, add elements, printing the list between. */
int main(int argc, char *argv[])
{
    struct node *newNode;

    printList(root);

    newNode= (struct node *)malloc( sizeof(struct node) );
    if (newNode == NULL)
	printf("malloc failed at line #%i\n",__LINE__);
    newNode->data = 13;
    newNode->next = NULL;
    insert(&root, newNode);
    printList(root);

    newNode= (struct node *)malloc( sizeof(struct node) );
    if (newNode == NULL)
	printf("malloc failed at line #%i\n",__LINE__);
    newNode->data = 34;
    newNode->next = NULL;
    insert(&root, newNode);
    printList(root);

    newNode= (struct node *)malloc( sizeof(struct node) );
    if (newNode == NULL)
	printf("malloc failed at line #%i\n",__LINE__);
    newNode->data = 27;
    newNode->next = NULL;
    insert(&root, newNode);
    printList(root);

    newNode= (struct node *)malloc( sizeof(struct node) );
    if (newNode == NULL)
	printf("malloc failed at line #%i\n",__LINE__);
    newNode->data = 5;
    newNode->next = NULL;
    insert(&root, newNode);
    printList(root);

    newNode= (struct node *)malloc( sizeof(struct node) );
    if (newNode == NULL)
	printf("malloc failed at line #%i\n",__LINE__);
    newNode->data = 7;
    newNode->next = NULL;
    insert(&root, newNode);
    printList(root);

    newNode= (struct node *)malloc( sizeof(struct node) );
    if (newNode == NULL)
	printf("malloc failed at line #%i\n",__LINE__);
    newNode->data = 31;
    newNode->next = NULL;
    insert(&root, newNode);
    printList(root);

    newNode= (struct node *)malloc( sizeof(struct node) );
    if (newNode == NULL)
	printf("malloc failed at line #%i\n",__LINE__);
    newNode->data = 99;
    newNode->next = NULL;
    insert(&root, newNode);
    printList(root);

    return 0;
}