/*
 * Markov Chain Random Sequence Generator
 */

/* Copyright (c) 1999 Blossom Associates West */
/* Copyright (C) 1999 Lucent Technologies */
/* Adapted from 'The Practice of Programming' */
/* by Brian W. Kernighan and Rob Pike */

#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>
#include <unistd.h>
#include "eprintf.h"

enum {
	NPREF	= 3,	/* number of prefix words */
	NHASH	= 4093,	/* size of state hash table array */
	MAXGEN	= 10000	/* maximum words generated */
};

typedef struct State State;
typedef struct Suffix Suffix;

struct State {	/* prefix + suffix list */
	char	pref[NPREF];	/* prefix letters */
	Suffix	*suf;		/* list of suffixes */
	State	*next;		/* next in hash table */
};

struct Suffix {	/* list of suffixes */
	char	residue;		/* suffix */
	Suffix	*next;			/* next in list of suffixes */
};

State	*lookup(char prefix[], int create);
void	build(char prefix[], FILE*);
void	generate(int nletters);
void	add(char prefix[], char residue);

State	*statetab[NHASH];	/* hash table of states */

char NONWORD = '\n';  /* cannot appear as real word */

/* usage: print usage message and exit */
void usage(void)
{
	fprintf(stderr, "usage: %s [-d] [-n residues]"
		" [-s seed] [files ...]\n", progname());
	exit(2);
}

/* markov main: markov-chain random text generation */
int main(int argc, char *argv[])
{
	int i, nwords = MAXGEN;
	char prefix[NPREF];		/* current input prefix */

	int c, dflag;
	long seed;

	setourprogname("markov");
	seed = time(NULL);
	dflag = 0;

        while ((c = getopt(argc, argv, "dn:s:")) != EOF)
                switch (c) {
                case 'd':
                        dflag = 1;
                        break;
                case 's':
                        seed = atoi(optarg);
                        break;
                case 'n':
                        nwords = atoi(optarg);
                        break;
                default:
                        usage();
                }

	srand(seed);
	if (dflag)
		fprintf(stderr, "%s -s 0x%lx\n", progname(), seed);
	for (i = 0; i < NPREF; i++)	/* set up initial prefix */
		prefix[i] = NONWORD;
	build(prefix, stdin);
	/*add(prefix, NONWORD);*/
	generate(nwords);
	return 0;
}   

const int MULTIPLIER = 31;  /* for hash() */

/* hash: compute hash value for array of NPREF characters */
unsigned int hash(char s[NPREF])
{
	unsigned int h;
	int i;

	h = 0;
	for (i = 0; i < NPREF; i++)
		h = MULTIPLIER * h + s[i];
	return h % NHASH;
}

/* lookup: search for prefix; create if requested. */
/*  returns pointer if present or created; NULL if not. */
/*  creation doesn't strdup so strings mustn't change later. */
State* lookup(char prefix[NPREF], int create)
{
	int i, h;
	State *sp;

	h = hash(prefix);
	for (sp = statetab[h]; sp != NULL; sp = sp->next) {
		for (i = 0; i < NPREF; i++)
			if (prefix[i] != sp->pref[i])
				break;
		if (i == NPREF)		/* found it */
			return sp;
	}
	if (create) {
		sp = (State *) emalloc(sizeof(State));
		for (i = 0; i < NPREF; i++)
			sp->pref[i] = prefix[i];
		sp->suf = NULL;
		sp->next = statetab[h];
		statetab[h] = sp;
	}
	return sp;
}

/* addsuffix: add to state. suffix must not change later */
void addsuffix(State *sp, char suffix)
{
	Suffix *suf;

	suf = (Suffix *) emalloc(sizeof(Suffix));
	suf->residue = suffix;
	suf->next = sp->suf;
	sp->suf = suf;
}

/* add: add residue to suffix list, update prefix */
void add(char prefix[NPREF], char suffix)
{
	State *sp;

	sp = lookup(prefix, 1);  /* create if not found */
	addsuffix(sp, suffix);
	/* move the words down the prefix */
	memmove(prefix, prefix+1, (NPREF-1)*sizeof(prefix[0]));
	prefix[NPREF-1] = suffix;
}

/* build: read input, build prefix table */
void build(char prefix[NPREF], FILE *f)
{
	int c;

	while ( EOF != ( c = fgetc(f) ) ) {
		if ( ' ' <= c )
			add(prefix, c);
	}
}

/* generate: produce output */
void generate(int nwords)
{
	State *sp;
	Suffix *suf;
	char prefix[NPREF], w;
	int i, nmatch;
	int pos = 0;

	for (i = 0; i < NPREF; i++)	/* reset initial prefix */
		prefix[i] = NONWORD;

	for (i = 0; i < nwords; i++) {

		sp = lookup(prefix, 0);
		if (sp == NULL)
			eprintf("internal error: lookup failed");
		nmatch = 0;
		for (suf = sp->suf; suf != NULL; suf = suf->next)
			if (rand() % ++nmatch == 0) /* prob = 1/nmatch */
				w = suf->residue;
		if (nmatch == 0)
			eprintf("internal error: no suffix %d %s", i, prefix[0]);
		if (NONWORD == w)
			break;
		putchar(w);

		memmove(prefix, prefix+1, (NPREF-1)*sizeof(prefix[0]));
		prefix[NPREF-1] = w;
	}

}