/*
 *
 * insort.c
 *
 * Sorts list of input words by insertion sort into linked list.
 *
 * MODULES:	main, insert
 *
 * AUTHOR: Lisa Amini
 *
 * $Id$
 *
 */


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

#define ERROR		-1
#define SUCCESS		0

struct element {
	struct element	*next;
	char		*text;
};

int insert(struct element *newItem, struct element **itemList);

/*
 * insert
 *
 * walk the list to find the appropriate insertion point, and insert
 *
 */
int insert(struct element *newItem, struct element **itemList)
{
	struct element *eCurr;		/* current item in list */
	struct element *ePrev;		/* previous item in list */

	if (!newItem)
		return ERROR;

	if (!(*itemList)) {
		*itemList = newItem;
		return SUCCESS;
	}

	eCurr = ePrev = *itemList;
	while (eCurr) {
		if (strcmp(newItem->text, eCurr->text) < 0) {
			/* insert before current */
			if (eCurr==ePrev) { 
				*itemList = newItem;	/* new list head */
			} else {
				ePrev->next = newItem;		
			}
			newItem->next = eCurr;
			return SUCCESS;
		} else {
			/* keep searching */
			ePrev = eCurr;
			eCurr = eCurr->next;
		}

	}

	/* tack onto end */
	ePrev->next = newItem;
	return SUCCESS;
} /* end insert */


/*
 *
 * main
 *
 * accept list of input words, sort and print
 *
 */
int main()
{
	struct element	*eWordList;	/* input list */
	struct element	*eNext;		/* next element in list */
	int		eCount=0;	/* num elements in list */
	char		input[100];	/* input word */
	int		rc;

	eWordList = NULL;		/* start with empty list */

	printf("Welcome to Buggy Sort!\n\n");
	printf("You will be prompted for a list of words to be sorted.\n");
	printf("To terminate input, enter # and then press Enter.\n");

	rc=1;
	while (rc) {
		printf("Enter word to be added to list: ");
		
		rc=scanf("%s", input);

		if (rc && (strlen(input)>0)) {
			if (input[0] == '#')
				break;
			eNext = (struct element *) malloc(sizeof(struct element));
			eNext->next=0;
			eNext->text = (char *) malloc(strlen(input));
			strcpy(eNext->text, input);
			if (insert(eNext, &eWordList)==ERROR) {
				printf("Fatal Error, exiting...\n");
				break;
			}
			eCount++;
		} else {
			break;
		}
	}

	/* done, cleanup the list */
	eNext = eWordList;		/* start at head of list */
	printf("\n\nResults:\n");
	while (eNext) {
		printf("%s\n", eNext->text);
		free(eNext);
		eNext = eNext->next;
	}

	return 0;
}