/* $Header: C:\\UTILS\\CVS\\ROOT/programs\\lang\\thue/thue.c,v 1.4 2000/09/02 16:46:29 John Colagioia Exp $
 *
 * Recent Changes:
 *
 * $Log: thue.c,v $
 * Revision 1.5  2010/12/18           Chris Pressey
 * Fix off-by-one error in sort routine, reported by
 * Nathan Thern.  Fix another off-by-one error in
 * random number generation.  Modernize: use rand()
 * and rename getline() to avoid name conflict.
 *
 * Revision 1.4  2000/09/02 16:46:29  John Colagioia
 * Trivial bugfix.
 *
 * Revision 1.2  2000/02/29 21:51:24  John Colagioia
 *
 * Just added some basic header info in the comments.
 *
 *
 */

/* For want of a nail,
    the shoe was lost.
   For want of a shoe,
    the horse was lost.
   For want of a horse,
    the knight was lost.
   For want of a knight,
    the battle was lost.
   So it was a kingdom was lost,
    all for the want of a nail.
	-- George Herbert, Jacula Prudentum
	   (Colloqual Adaptation)
*/

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

#define	SEP	"::="

	char	* get_line	(FILE * infile);

struct rule
	{
	 char	lhs[64];
	 char	rhs[64];
	} rulebase[128];

int	ruleidx = 0,
	debug = 0;
char	*dataspace,
	*tempspace;

int main (int argc, char *argv[])
{
 char	*line,
	*c,
	*tmp,
	*target[64],
	 tempstr[64];
 int	 state,
	 flagstate,
	 i, j, k,
	 order,
	 temp,
	 rnum[64];
 FILE	*infile;

 srand(time(0));
 dataspace = malloc(16384);
 tempspace = malloc(16384);
 if (dataspace == NULL || tempspace == NULL) {
	fprintf (stderr, "Could not allocate sufficient working memory\n");
	exit(1);
 }
 target[0] = dataspace;
 memset (rulebase, 0, sizeof (rulebase));
 memset (dataspace, 0, sizeof (dataspace));
 if (argc > 1)
	infile = fopen (argv[1], "r");
 else
	infile = stdin;
 if (infile == NULL)
	return (-1);

 order = 0;
 if (argc > 2)
    switch (argv[2][0])
	{
	 case 'r':	/* Right-to-Left Processing */
		order = 2;
		break;
	 case 'l':	/* Left-to-Right */
		order = 1;
		break;
	 case 'd':
		debug = 1;
		break;
	}

 /* Get input file */
 state = 0;
 while (!feof (infile))
	{
	 line = get_line (infile);
	 if (state == 0)
		{
		 if (line != NULL && !strlen (line))
			continue;
		 c = strstr (line, SEP);
		 if (c == NULL)
			fprintf (stderr, "Malformed production: \"%s\"!\n", line);
		 else if (c == line)
			state = 1;
		 else	{
			 flagstate = 0;
			 for (tmp=line;tmp!=c;tmp++)
				if (!isspace (*tmp))
					 flagstate = 1;
			 if (flagstate)
				{
				 *c = '\000';
				 c += strlen (SEP);
				 strcpy (rulebase[ruleidx].lhs, line);
				 strcpy (rulebase[ruleidx].rhs, c);
				 ++ruleidx;
				}
			 else	state = 1;
			}
		}
	 else if (line != NULL)
			strcat (dataspace, line);
	}

 if (debug)
	printf ("Initial:  \"%s\"\n", dataspace);

 /* Apply rules */
 state = 1;
 while (state)
	{
	 /* Get all valid LHSs */
	 j = 1;
	 k = 0;
	 c = dataspace;
	 for (i=0;i<ruleidx;i++)
	    do
		{
		 k = j;
		 target[k] = strstr (c, rulebase[i].lhs);
		 rnum[k] = i;
		 if (target[k] != NULL)
			{
			 ++j;
			 c = target[k] + 1;
			}
		 else
			c = dataspace;
		}
	    while (target[k]);

	 if (j == 1)
		{
		 state = 0;
		 continue;
		}

	 /* Sort the LHS list - Just a bubble sort */
	 for (i=1;i<j;i++)
	    for (k=1;k<i;k++)
		if (target[i] < target[k])
			{
			 c = target[i];		temp = rnum[i];
			 target[i] = target[k];	rnum[i] = rnum[k];
			 target[k] = c;		rnum[k] = temp;
			}

	 /* Choose rule to apply */
	 switch (order)
		{
		 case 2:
			i = j - 1;
			break;
		 case 1:
			i = 1;
			break;
		 default:
			i = rand() % (j - 1) + 1;
			break;
		}
	 line = target[i];
	 temp = rnum[i];
	 c = line + strlen (rulebase[temp].lhs);
	 *line = '\000';

	 /* Check for I/O */
	 i = rulebase[temp].rhs[0] == '~';
	 if (i)
		{
		 puts (&rulebase[temp].rhs[1]);
		 memset (tempstr, 0, sizeof (tempstr));
		}
	 else
		{
 		 i = !strcmp (rulebase[temp].rhs, ":::");
		 if (i)
                     {
			fgets (tempstr, sizeof (tempstr), stdin);
                        tempstr[strlen (tempstr) - 1] = '\0';
                     }
		}

	 /* Apply the rule */
	 sprintf (tempspace, "%s%s%s", dataspace, i?tempstr:rulebase[temp].rhs, c);
	 strcpy (dataspace, tempspace);
	 if (debug)
		puts (dataspace);
	}

 if (debug)
	printf ("Final:  \"%s\"\n", dataspace);
 return (0);
}

char * get_line (FILE * infile)
{
 static	char	 buffer[256];
	char	*s;

 memset (buffer, 0, sizeof (buffer));
 /* Get next line from file */
 s = fgets (buffer, sizeof (buffer), infile);
 if (s == NULL)
	return (NULL);
 buffer[strlen (buffer) - 1] = '\0';
 /* Return pointer to string */
 return (buffer);
}