/* gf RandMap Random Name Generator
 * version 2
 * Written by ME when I was very BORED
 * This script is free for non-profit use
 * see gfhiryuu.tripod.com/random/index.html for more info
 */

/* // Here's an example of how to use a generator
   var map_string = "<root>uga\n<root>oog";
   var gen = new Generator();
   var success = gen.buildMap(map_string); //this might take a second or so and cause a noticeable delay for user
   
   if(success == true)
  	{
 		var random_string = gen.generate(); //each time you'll get a randomly generated string
 		alert(random_string);
 		// if you want to, you can call gen.buildMap again
  	}
   else
   {
     alert("Problem with map_string !");
     alert(gen.strError);
   }
*/


//BEGIN Utility Functions
function push_back(arr, val)
{
	arr[arr.length] = val;
}


//This is used instead of RegExp's because they are buggy in some browsers
//there are two forms of repl()
//if 3 arguments are passed, repl() searches str for each occurance of
//strFind and replaces it with the string rep
//if 4 arguments are given, replace searches str for each occurance of str and
//replaces it with the result of the function rep.
//for each occurance of strFind, the function rep is passed the first nChars characters
//of str which follow the found substring. nChars must be greater than 0
function repl(str, strFind, rep, nChars) //return string
{
	if(arguments.length < 4) nChars = 0;
	var iStart = 0;
	var newStr = "";
	var i;

	if((i = str.indexOf(strFind, iStart)) >= 0)
	{
		do
		{
			newStr += str.substring(iStart, i);

			if(nChars)
			{
				i += strFind.length;
							
				if(i >= str.length)
				{
					newStr += rep("");
					break;
				}
				
				iStart = i + nChars;
				newStr += rep(str.substring(i, Math.min(str.length, iStart)));
			}
			else
			{
				newStr += rep;
				iStart = i + strFind.length;
			}

			if(iStart >= str.length)	break;
		}while((i = str.indexOf(strFind, iStart)) >= 0 );

		if(iStart < str.length)
			newStr += str.substring(iStart, str.length);

		return newStr;
	}

	return str;
}


//pass a string containing a symbol map and it returns a string that, when enclosed in " or ' 
//and used as a javascript literal, represents an equivalent symbol map
function toJSLiteral(strMap) //return string
{
	var s = repl(strMap, "\r\n", "\n");
	s = jsEscape(s);
	s = repl(s, "</script", "<\\/script");
	return s;
}


//pass a character code like 65 (65 indicates letter "A"),
//and it returns unicode escape sequence like "\u0041"
function uniEscape(cc) //return string
{
	var n;
	return "\\u"
	 + ((n = cc >> 16 & 0xF) < 10 ? n : String.fromCharCode(55+n))
	 + ((n = cc >> 8  & 0xF) < 10 ? n : String.fromCharCode(55+n))
	 + ((n = cc >> 4  & 0xF) < 10 ? n : String.fromCharCode(55+n))
	 + ((n = cc       & 0xF) < 10 ? n : String.fromCharCode(55+n));
}



//returns a string which is equivalent to s when used as a JavaScript literal enclosed by " or '
function jsEscape(s) //return string
{
	var cc;
	var sNew = "";
	var i=0;
	var j=0;
	
	while(j < s.length)
	{
		cc = s.charCodeAt(j);
		switch(cc)
		{
		case 13:
			if(j+1 < s.length && s.charCodeAt(j+1) == 10)
			{
				sNew += s.substring(i, j);
				sNew += "\\n";
				j += 2;
				i = j;
				break;
			}
			
			sNew += s.substring(i, j);
			i = ++j;
			break;

		case 10:
			sNew += s.substring(i, j);
			sNew += "\\n";
			i = ++j;
			break;
		
		case 92:
			sNew += s.substring(i, j);
			sNew += "\\\\";
			i = ++j;
			break;
		
		case 34:
			sNew += s.substring(i, j);
			sNew += '\\"';
			i = ++j;
			break;
			
		case 39:
			sNew += s.substring(i, j);
			sNew += "\\'";
			i = ++j;
			break;
			
		case 9:
			sNew += s.substring(i, j);
			sNew += '\\t';
			i = ++j;
			break;
			
		case 12:
			sNew += s.substring(i, j);
			sNew += '\\f';
			i = ++j;
			break;
			
		case 8:
			sNew += s.substring(i, j);
			sNew += '\\b';
			i = ++j;
			break;
			
		default:
			if(cc < 32 || cc > 126)
			{
				sNew += s.substring(i, j);
				sNew += uniEscape(cc);
				i = ++j;
			}
			else
			{ ++j; }
			break;
		}
	}
	
	if(i == 0)
		return s;

	if(i < j)
		sNew += s.substring(i, j);
	
	return sNew;
}

//END Utility functions



//CLASS Tokenize
var Tokenize_UNDEFINED = 0;
var Tokenize_SYMBOL  = 1;
var Tokenize_LITERAL = 2;
var Tokenize_NUMBER  = 3;
var Tokenize_ENDDOC  = 4;
var Tokenize_ENDLINE = 5;
var Tokenize_ATTRIBUTE = 6;


function Tokenize() //ctor if passed 1 argument calls newDoc with that argument
{
	if(arguments.length == 1)
		this.newDoc(arguments[0]);
}


function Tokenize_translateEscaped(ch) //return string
{
	switch(ch.charCodeAt(0))
	{
		case 110: return "\n";
		case 116: return "\t";
		case 114: return "\r";
		case 102: return "\f";
	}
	
	return ch;
}


function Tokenize_newDoc(strMap)
{
	this.doc = strMap;
	this.data = "";
	this.i = 0;
	this.line_num = 1;
	this.currentType = Tokenize_UNDEFINED;
}
Tokenize.prototype.newDoc = Tokenize_newDoc;


//true if a recognizable token is found, false if a syntax error. You can read error message from this.strError
function Tokenize_findToken() //return boolean
{
	findTokenLoop:
	for(;;)
	{
		if(this.i >= this.doc.length)
		{
			this.currentType = Tokenize_ENDDOC;
			return true;
		}

		this.currentType = Tokenize_UNDEFINED;
		var c; //holds char code.

		//skip white space
		while( ((c=this.doc.charCodeAt(this.i)) == 32) || c == 9) //32==' ' 9=='\t'
		{
			if(++this.i == this.doc.length)
			{
				this.currentType = Tokenize_ENDDOC;
				return true;
			}
		}

		//check for "\n" newline
		if(c == 10) //10=='\n'
		{
			++this.i;
			++this.line_num;
			this.currentType = Tokenize_ENDLINE;
			return true;
		}

		//check for "\r" or "\r\n" newline
		if(c == 13) //13=='\r'
		{
			if(this.i+1 < this.doc.length && this.doc.charCodeAt(this.i+1) == 10) //10=='\n'
				this.i += 2;
			else
				++this.i;

			++this.line_num;
			this.currentType = Tokenize_ENDLINE;
			return true;
		}

		//check for comments
		if(c == 47 && this.i+1 < this.doc.length) //47=='/'
		{
			if(this.doc.charCodeAt(this.i+1) == 47) //found  "//" single-line comments
			{
				++this.i; //skip the "/"

				while(++this.i < this.doc.length && 
						(c=this.doc.charCodeAt(this.i)) != 10 && c != 13)//10=='\n' 13=='\r'
				{}
				
				continue findTokenLoop;
			}

			if(this.doc.charCodeAt(this.i+1) == 42) //42=='*' found "/*" comment
			{
				var nCommentStart = this.line_num;
				this.i += 2;

				for(;;)
				{
					if(this.i == this.doc.length) //found end of document inside comment
					{
						this.line_num = nCommentStart;
						this.strError = "unterminated comment";
						return false;
					}

					switch(this.doc.charCodeAt(this.i))
					{
					case 10: //10=='\n'
						++this.line_num;
						break;
							
					case 13: //13=='\r'
						++this.line_num;
							
						if(this.i+1 < this.doc.length && this.doc.charCodeAt(this.i+1) == 10)
						{
							this.i += 2;
							continue;
						}
						break;
						
					case 42: //42=='*'
						if(this.i+1 < this.doc.length && this.doc.charCodeAt(this.i+1) == 47) //47=='/'
						{
							this.i += 2;
							continue findTokenLoop; //found end of comment, look for another token
						}
						break;
					}
					
					++this.i;
				}
			}
		}//END if comments 

		//check for symbols		
		switch(this.findBoundedToken(60, 62, 0)) 
		{
			case 1:
				if( this.data.length < 1 )
				{
					this.strError = "symbol name of 0 characters";
					return false;
				}
			
				this.currentType = Tokenize_SYMBOL;
				return true;
				
			case 2:
				return false;
		}

		//check for bare characters
		if(c >= 97 && c <= 122 || c >= 65 && c <= 90 ) //97=='a' 122='z' 65=='A'  90=='Z'
		{
			var iData = this.i;
			this.currentType = Tokenize_LITERAL;

			while(++this.i < this.doc.length && 
				  ((c=this.doc.charCodeAt(this.i)) >= 97 && c <= 122 || c >= 65 && c <= 90 ))
			{}

			this.data = this.doc.substring(iData, this.i);
			return true;
		}

		//check for numbers	
		if(c >= 48 && c <= 57)//48=='0'  57=='9'
		{
			var iData = this.i;
			this.currentType = Tokenize_NUMBER;

			while( ++this.i < this.doc.length && (c=this.doc.charCodeAt(this.i)) >= 48 && c <= 57 )
			{}

			this.data = this.doc.substring(iData, this.i);
			return true;
		}

		//check for strings
		switch(this.findBoundedToken(34, 34, 92)) //34=='\"' 92=='\\'
		{
			case 1:
				this.data = repl(this.data, "\\", Tokenize_translateEscaped, 1);						
				this.currentType = Tokenize_LITERAL;
				return true;
				
			case 2:
				return false;
		}
		
		//check for attributes
		switch(this.findBoundedToken(40, 41, 0)) //40=='(' 41==')'
		{
			case 1:
				this.currentType = Tokenize_ATTRIBUTE;
				return true;
				
			case 2:
				return false;
		}
		
		//character is not allowed here
		var chr = this.doc.charAt(this.i);
		this.strError = "unexpected character ";

		if(chr >= " " && chr <= "~")
		{	this.strError += "'" + chr + "'";  }
		else
		{	this.strError += "code: " + c;  }
		
		return false;
	}//end findTokenLoop
}
Tokenize.prototype.findToken = Tokenize_findToken;


//looks for string beginning with beginCode and ending with an endCode not preceeded by escapeCode
//return value: 1 indicates bounded token was found,
//              0 indicates no token was found,
//              2 indicates the document is invalid (has a syntax error or other error)
function Tokenize_findBoundedToken(beginCode, endCode, escapeCode)
{
	if(this.i >= this.doc.length)
	{
		//end of document
		return 2;
	}
	
	if( this.doc.charCodeAt(this.i) == beginCode )
	{
		var i = this.i + 1;
		var c;
		
		for(;;)
		{
			if(i >= this.doc.length)
			{
				this.strError = "unexpected end of document following " + String.fromCharCode(beginCode);
				return 2;
			}
			
			c = this.doc.charCodeAt(i);
			
			if(c == 10 || c == 13) //10=='\n'  13=='\r'
			{
				this.strError = "unexpected end of line following " + String.fromCharCode(beginCode);
				return 2;
			}
			
			if(c == escapeCode) //found escape char "\" so skip next char
			{
				i += 2;
				continue;
			}
			
			if(c == endCode)
			{
				// found token
				this.data = this.doc.substring(this.i+1, i);
				this.i = i+1;
				return 1;
			}
			
			++i;
		}
	}

	return 0;
}
Tokenize.prototype.findBoundedToken = Tokenize_findBoundedToken;

//END CLASS Tokenize



//CLASS Generator

//this is the initial symbol evaluated when generating. this symbol must be defined in the map
var Generator_strRootSymbol = "root";

//this default weight is assigned if a line has no specified weight
var Generator_nDefaultWeight = 10;

//since symbol names are used as property names of an Object, an extra char is appended to
//all symbol names to prevent name collisions with predefined javascript property names like 'toString'
var Generator_strSymPostfix = "_";
var Generator_strRootSymbolInternal = Generator_strRootSymbol + Generator_strSymPostfix;

//used to cut off recursion
var Generator_nSymbols = 0;     //during generation, counts how many symbols have been evaluated
var Generator_nMaxSymbols = 50; //maximum number of symbols to eval before stopping


function ProdRule(strData, isSymbolRef) //ctor "production rule"
{
	this.str = strData;      
	this.bSymbol = isSymbolRef; // is this a symbol reference (true) or a literal (false)
}


function ReplaceRule() //ctor
{
	this.nWeight = 0;
	this.arrProdRules = new Array();
};


function Symbol() //ctor
{
	this.nTotalWeight = 0;
	this.arrReplaceRules = new Array();
	this.bConstant = false; // is this symbol to have constant value?
};


function Generator() //ctor
{
	this.sym_map   = null; 
	this.strError  = null;
	this.genString = "";
}


//tries to compile a string into a symbol map. must return success before generate can be used
function Generator_buildMap(strMap) //return boolean success/fail
{
	this.sym_map = new Object();
	var parser = new Tokenize(strMap);

	this.strError = null;

	var strSrcSymbol;
	var symbol;
	var replRule;
	
	for(;;)
	{
		if(!parser.findToken())
		{ //an error occured
			this.strError = "line " + parser.line_num + ": " + parser.strError;
			this.sym_map = null;
			return false;
		}

		if(parser.currentType == Tokenize_ENDLINE) continue;
		if(parser.currentType == Tokenize_ENDDOC ) break;
		
		if(parser.currentType != Tokenize_SYMBOL)
		{
			this.strError = "source symbol expected on line " + parser.line_num;
			this.sym_map = null;
			return false;
		}
		
		//found symbol
		strSrcSymbol = parser.data + Generator_strSymPostfix;
	
		if(this.sym_map[strSrcSymbol] == null)
			symbol = this.sym_map[strSrcSymbol] = new Symbol();
		else
			symbol = this.sym_map[strSrcSymbol];
		

		if(!parser.findToken())
		{
			this.strError = "line " + parser.line_num + ": " + parser.strError;
			this.sym_map = null;
			return false;
		}
		
		switch(parser.currentType)
		{
			case Tokenize_LITERAL:
			case Tokenize_SYMBOL:
				replRule = symbol.arrReplaceRules[symbol.arrReplaceRules.length] = new ReplaceRule();
			
				prodRuleLoop:
				for(;;)//get production rules for this replacement rule
				{
					switch(parser.currentType)
					{
					case Tokenize_LITERAL:
						push_back(replRule.arrProdRules, new ProdRule(parser.data, false));
						break;
						
						
					case Tokenize_SYMBOL:
						push_back(replRule.arrProdRules, new ProdRule(parser.data + Generator_strSymPostfix, true));
						break;
					
						
					case Tokenize_ENDLINE:
					case Tokenize_ENDDOC:
							replRule.nWeight = Generator_nDefaultWeight; //no weight present so assign default weight
							break prodRuleLoop;
						
					case Tokenize_NUMBER:
							replRule.nWeight = parseInt(parser.data, 10);
					
							if(!parser.findToken())
							{
								this.strError = "line " + parser.line_num + ": " + parser.strError;
								this.sym_map = null;
								return false;
							}
								
							//only ENDLINE or ENDDOC is a valid token at this point
							if(parser.currentType == Tokenize_ENDLINE || parser.currentType == Tokenize_ENDDOC)
								break prodRuleLoop;
							//else go to default
								
					default:
						this.strError = "unexpected token on line " + parser.line_num;
						this.sym_map = null;
						return false;
					}
			
					if(!parser.findToken())
					{
						this.strError = "line " + parser.line_num + ": " + parser.strError;
						this.sym_map = null;
						return false;
					}
				}						
				break;
				
			case Tokenize_ATTRIBUTE:
				attributeLoop:
				for(;;) //get 1 or more attributes
				{
					switch(parser.currentType)
					{
					case Tokenize_ATTRIBUTE:
						switch(parser.data)
						{
							case "const":
								symbol.bConstant = true;
								symbol.strConstant = null;
								break;
							
							default:
								this.strError = "unrecognized attribute on line " + parser.line_num;
								this.sym_map = null;
								return false;						
						}
						break;
						
					case Tokenize_ENDLINE:
					case Tokenize_ENDDOC:
						break attributeLoop;
						
					default:
						this.strError = "unexpected token on line " + parser.line_num;
						this.sym_map = null;
						return false;
					}
					
					if(!parser.findToken())
					{
						this.strError = "line " + parser.line_num + ": " + parser.strError;
						this.sym_map = null;
						return false;
					}
				}
				break;
				
			case Tokenize_ENDLINE:
			case Tokenize_ENDDOC:
				this.strError = "token expected on line " + (parser.line_num - 1);
				this.sym_map = null;
				return false;				
				break;
				
			default:
				this.strError = "unexpected token on line " + parser.line_num;
				this.sym_map = null;
				return false;
		}
	}


	buildLoop:
	for(var key in this.sym_map)
	{
		symbol = this.sym_map[key];

		for(var i=0; i < symbol.arrReplaceRules.length; ++i)
		{
			symbol.nTotalWeight += symbol.arrReplaceRules[i].nWeight; //weights are added to produce cutoff values
			symbol.arrReplaceRules[i].nWeight = symbol.nTotalWeight;

			var arrProdRules = symbol.arrReplaceRules[i].arrProdRules;

			//check that all symbols used by production rules are actually defined
			for(var j=0; j < arrProdRules.length; ++j) 
			{
				if(arrProdRules[j].bSymbol && this.sym_map[arrProdRules[j].str] == null)
				{
					this.strError = "symbol <" + 
						arrProdRules[j].str.substring(0, arrProdRules[j].str.length - Generator_strSymPostfix.length) 
						+ "> is undefined";
					break buildLoop;
				}
			}
		}

		if(symbol.nTotalWeight == 0)
		{
			this.strError = "replacement rules for symbol <" + 
				key.substring(0, key.length - Generator_strSymPostfix.length) + "> have 0 total weight";
			break;
		}
	}

	if(this.sym_map[Generator_strRootSymbolInternal] == null)
		this.strError = "root symbol <" + Generator_strRootSymbol + "> is undefined";

	if(this.strError != null) //if there was an error
	{
		this.sym_map = null;
		return false;
	}

	return true; 
}
Generator.prototype.buildMap = Generator_buildMap;




//returns a randomly generated string. buildMap must return true before this can be used
function Generator_generate() 
{
	this.nSymbols = 0;
	this.genString = "";

	//reset all constant symbol values
	for(var symName in this.sym_map)
	{
		if(this.sym_map[symName].bConstant)
			this.sym_map[symName].strConstant = null;
	}

	this.recurseGenerate(Generator_strRootSymbolInternal);
	return this.genString;
}
Generator.prototype.generate = Generator_generate;


function Generator_recurseGenerate(strSymbol)
{
	if(++this.nSymbols > Generator_nMaxSymbols) return;

	var symbol = this.sym_map[strSymbol];

	if(symbol.bConstant && symbol.strConstant != null)
	{
			this.genString += symbol.strConstant;
			return;
	}
	
	var oldLength = this.genString.length;
	

	
	var r = Math.floor(Math.random()*symbol.nTotalWeight);
	var arrProdRules;

	for(var i=0; i < symbol.arrReplaceRules.length; ++i)
	{
		if(r < symbol.arrReplaceRules[i].nWeight)
		{
			arrProdRules = symbol.arrReplaceRules[i].arrProdRules;
			break;
		}
	}

	for(var i=0; i < arrProdRules.length; ++i)
	{
		if(arrProdRules[i].bSymbol)
			this.recurseGenerate(arrProdRules[i].str);
		else
			this.genString += arrProdRules[i].str;
	}

	//if(symbol.bCap)
	
	if(symbol.bConstant && symbol.strConst == null)
		symbol.strConstant = this.genString.substring(oldLength, this.genString.length);
}
Generator.prototype.recurseGenerate = Generator_recurseGenerate;
//END CLASS Generator