//
//	silly sentence generation
//

# include <iostream.h>
# include <string>
# include <map>
# include <list>
# include <vector>
# include <fstream.h>

class randomInteger {
	public:
		unsigned int operator () (unsigned int);
} randomizer;

unsigned int randomInteger::operator () (unsigned int max)
{
		// rand return random integer
		// convert to unsigned to make positive
		// take remainder to put in range
	unsigned int rval = rand();
	return rval % max;
}

unsigned int randBetween(int low, int high) {
	return low + randomizer(high - low);
}

void split (string & text, string & separators, list<string> & words)
	// split a string into a list of words
	// text and separators are input,
	// list of words is output
{
	int textLen = text.length();

		// find first non-separator character
	int start = text.find_first_not_of(separators, 0);
		// loop as long as we have a non-separator character
	while ((start >= 0) && (start < textLen)) {
			// find end of current word
		int stop = text.find_first_of(separators, start);
		if ((stop < 0) || (stop > textLen)) stop = textLen;
			// add word to list of words
		words.push_back (text.substr(start, stop - start));
			// find start of next word
		start = text.find_first_not_of (separators, stop+1);
		}	
}

typedef map<string, vector< list<string> >, less<string> > grammarType;

void readGrammar (istream & ifile, grammarType & grammar)
	// read a silly sentence grammar into the given structure
{
	string line;
	while (getline(ifile, line)) {
		list<string> words;
		string separators = " ";
		split (line, separators, words);
		string category = words.front();
		words.pop_front();
			// add a new grammar rule
		grammar[category].push_back(words);
		}
}

string generateSentence (string & start, grammarType & grammar)
	// generate silly sentence from given start string
{
	if (grammar.count(start) != 0) {
		vector< list<string> > & rules = grammar[start]; // see box
		int n = rules.size();
		list<string> & rule = rules[randBetween(0, n-1)];
		list<string>::iterator start, stop;
		stop = rule.end();
		string result;
		for (start = rule.begin(); start != stop; ++start)
			result += generateSentence (*start, grammar);
		return result;
		}
	else		// not a category, simply return string
		return start;
}

void main () {
	ifstream gfile ("grammar");
	grammarType grammar;
	readGrammar (gfile, grammar);
	string start = "SENTENCE";
	for (int i = 0; i < 10; i++)
		cout << generateSentence(start, grammar) << "\n";
}