/*
 *	togglesort: read in lines and sort them; if you encounter a duplicate,
 *	throw it away and remove the original. This means you only get lines
 *	which occur an odd number of times.
 *
 *	The program is pointless, but means we have to insert and delete things
 *	at interesting places in a linked list.
 *
 *	This is a hairier exercise in linked list manipulation.
 *	The problem if you try to trace the list with a simple pointer to cell
 *	is that you only find out what you want to do with
 *	the current cell when you get to it, and deleting it involves patching
 *	the link pointer of the previous cell, which you aren't pointing at any
 *	more.  Methods using two pointers, one to the current and one to the
 *	previous cell need special cases for the head of the list, the tail of
 *	the list, the empty list, or all three.
 *
 *	Here's how: instead of maintaining a pointer to the current cell,
 *	you access the current cell through a pointer to the link field of
 *	the previous structure.  This pointer is initialised to the address
 *	of the head pointer, and the routines are all blissfully unaware that
 *	it isn't the link pointer of a full structure.
 *
 *		------
 *		|head|
 *		------
 *		  |
 *		  V
 *		------	  ------------------------
 *		|line| -> |F|i|r|s|t| |l|i|n|e|\0|
 *		------	  ------------------------
 *	lcpp -> |link|
 *		------
 *		  |
 *		  V
 *		------	  --------------------------
 *	Current |line| -> |S|e|c|o|n|d| |l|i|n|e|\0|
 *	Cell	------	  --------------------------
 *		|link|
 *		------
 *		  |
 *		  V
 *
 *	Martin Guy, University of Kent, February 1988
 */

#include <stdio.h>

extern char *malloc();
extern char *strcpy();

/* A structure to hold each item, in alphabetical order. */
struct linecell {
	char *line;		/* pointer to a mallocked copy of the line */
	struct linecell *link;
};

/* define for end-of-list marker and for checking return values from malloc */
#define NULLLINECELL (struct linecell *) 0

/* pointer to first cell in the list */
struct linecell *head = NULLLINECELL;

/* forward declarations */
struct linecell *createcell();
char *strsave();

main()
{
	char inputline[256];		/* what they just typed in */

	while (fgets(inputline, sizeof(inputline), stdin) != NULL) {
		process(inputline);
	}

	regurgitate();

	exit(0);
}

/*
 *	Insert-sort the new line into the linked list, with frills.
 */
process(line)
char *line;
{
	/* Trip down the list of lines we have so far until either
	 * - we get to the end of the list, in which case tack it on to the end.
	 * - we find another line which is lexically after the line we
	 *   are trying to insert, in which case insert the current line
	 *   before it.
	 * - we find a line which is identical to the current, in which case
	 *   delete the matching entry.
	 *
	 * Extract from manual: int strcmp(s1, s2) char *s1, *s2;
	 * Strcmp compares its arguments and returns an integer greater than,
	 * equal to, or less than 0, according as s1 is lexicographically
	 * greater than, equal to, or less than s2.
	 */

	struct linecell **lcpp;		/* see header commentary */

	for (lcpp = &head; *lcpp != NULLLINECELL; lcpp = &((*lcpp)->link)) {

		int newafterold;	/* cache return from strcmp for
					 * 3-way switch */

		newafterold = strcmp(line, (*lcpp)->line);
		
		if (newafterold > 0) {
			/* The new line comes after the old. Carry on down. */
			continue;
		} else
		if (newafterold < 0) {
			/* 
			 * The new line comes before the old.
			 * Grab some space and fit it in.
			 */
			struct linecell *newlc;
			
			newlc = createcell(line);

			/* insert-um */
			newlc->link = *lcpp;
			*lcpp = newlc;
			return;
		} else {
			/*
			 * newafterold == 0 : an exact match.
			 * Remove the duplicate
			 */
			char *tofree;	/* remember what we must free */

			tofree = (char *) *lcpp; /* address of current cell */

			/* link over the current cell */
			*lcpp = (*lcpp)->link;

			free(tofree);

			return;
		}
	}

	/* We got to the end of the list, so append.
	 * Lpcc has been left pointing at the final NULL pointer.
	 */
	*lcpp = createcell(line);
	(*lcpp)->link = NULL;
}

/*
 *	Get memory for a new cell, make a copy of the line and point the
 *	cell's line pointer at the copy.
 *
 *	This routine either succeeds or exits, so no error checking need
 *	be done by the caller.
 */
struct linecell *
createcell(line)
char *line;
{
	struct linecell *new;

	new = (struct linecell *) malloc(sizeof(struct linecell));
	if (new == NULLLINECELL) {
		fputs("togglesort: Out of memory\n", stderr);
		exit(1);
	}

	new->line = strsave(line);
	if (new->line == (char *) 0) {
		fputs("togglesort: Out of memory\n", stderr);
		exit(1);
	}

	return(new);
}

/*
 *	Return a pointer to a mallocked copy of a string
 *	or a null character pointer on failure.
 */
char *
strsave(str)
char *str;
{
	char *copy;		/* pointer to the copy of the string */

	copy = malloc(strlen(str) + 1);		/* + 1 for the NUL */
	if (copy == NULL) return((char *)0);

	(void) strcpy(copy, str);

	return(copy);
}

/*
 *	Write the list of lines to stdout.
 */
regurgitate()
{
	struct linecell *lcp;		/* nothing clever required */

	for (lcp = head; lcp != NULL; lcp = lcp->link) {
		fputs(lcp->line, stdout);
	}
}