//<script>
function ParseError(errorCode, message, term, charPos, fieldName, data)
{
	this.errorCode = errorCode;
	this.message = message;
	this.term = term;
	this.charPos = charPos;
	this.fieldName = fieldName;
	this.data = data;
}

ParseError.prototype.toString = function()
{
	var n = this.charPos;
	var t = this.term;
	var s = "";
	for (var i = 0; i < t.length + 1; ++i)
		s += (i == n) ? "^" : " ";
	return "Error in field \"" + this.fieldName + "\": " + this.message + "\n\n" + t + "\n" + s;
}

ParseError.PROXIMITY = 1;			// invalid proximity definition [data = the invalid string]
ParseError.NUMERIC = 2;				// invalid numeric search [data = null]
ParseError.DATE    = 3;				// invalid date search [data = the invalid string; may be null]
ParseError.INVALID_DAY = 4;			// day out of range [data = the invalid value]
ParseError.INVALID_MONTH = 5;		// month out of range [data = the invalid value]
ParseError.WILDCARD = 6;			// wildcards not allowed [data = term with wildcard]
ParseError.MISMATCHED_QUOTE = 7;	// end quote not found [data = begin quote char]
ParseError.SEARCH_EXPECTED = 8		// search expression expected [data = actual next token]
ParseError.SUBSEARCH_EXPECTED = 9;	// expected '(' [data = actual next token]
ParseError.SUBSEARCH_BEGIN = 10;	// mismatched '(' [data = actual next token; most likely Token.End]
ParseError.SUBSEARCH_END = 11;		// mismatched ')' [data = actual next token; most likely Token.EndSubsearch]
ParseError.EMPTY_SUBSEARCH = 12;	// empty subsearch [data = null]
ParseError.TOO_WILD = 13;			// search term must contain at least 2 non-wildcard characters [data = search term]
ParseError.EMPTY_TERM = 14;			// missing search expression in quotes

function QueryParser(fieldName, fieldFlags)
{
	this.fieldName  = fieldName;
	this.fieldFlags = fieldFlags;
	// "newline" and "tab" properties affect formatting of the returned XML string.
	// For a nicely formatted tree, use:  this.newline = "\n"; this.tab = "   ";
	// Use empty strings for most compact XML.
	this.newline = "";
	this.tab = "";
    this.defaultOperator = Token.And;
}

QueryParser.prototype.checkSpecialToken = function(s)
{
	switch (s.toLowerCase()) {
		case OP_AND: return Token.And;
		case OP_OR: return Token.Or;
		case OP_NOT: return Token.Not;
	}
}

function Operator(precedence, tagName)
{
	this.precedence = precedence;
	this.tagName    = tagName;
}

var OpNot = new Operator(1, "not");
var OpOr = new Operator(2, "or");
var OpAnd = new Operator(3, "and");
var OpProx = new Operator(4, "prox");
var OpAdj = new Operator(5, "adj");

var TokenType =
{
	BeginSubsearch: 1,
	EndSubsearch: 2,
	InfixOperator: 3,
	PrefixOperator: 4,
	SearchTerm: 5,
	ParseTree: 6,
	End: 7
}

// Possible ways to call this constructor:
//     new Token(operator, operatorType)
//     new Token(searchTerm, termType)
//     new Token(tokenType)
function Token(arg1, arg2)
{
	if (arg1.constructor == Operator)
	{
		this.op = arg1;
		this.type = arg2;
	}
	else if (arg1.constructor == String)
	{
		this.type = TokenType.SearchTerm;
		this.term = arg1;
		this.termType = arg2;
	}
	else if (arg1.constructor == ParseTree)
	{
		this.type = TokenType.ParseTree;
		this.tree = arg1;
	}
	else {
		this.type = arg1;
	}
}

// Predefined tokens
Token.And = new Token(OpAnd, TokenType.InfixOperator);
Token.Or = new Token(OpOr, TokenType.InfixOperator);
Token.Not = new Token(OpNot, TokenType.InfixOperator);
Token.Adjacent = new Token(OpAdj, TokenType.InfixOperator);
Token.BeginSubsearch = new Token(TokenType.BeginSubsearch);
Token.EndSubsearch = new Token(TokenType.EndSubsearch);
Token.End = new Token(TokenType.End);

function ParseTree(op)
{
	this.op = op;
	this.arSubSearches = new Array();
	this.opAllowed = false;
	this.push = function(oSubSearch) { this.arSubSearches.push(oSubSearch); }
	this.pop  = function() { return this.arSubSearches.pop(); }
}

// add all properties from objProps to obj; return obj
function addProps(obj, objProps)
{
	for (var prop in objProps)
		obj[prop] = objProps[prop];
	return obj;
}

QueryParser.prototype.getXMLhelper = function(oSearch, level, prefix)
{
	var oAttrs = { };
	if (level == 0)
		oAttrs.f = this.fieldName;

	if (oSearch.constructor == Token)
	{
		addProps(oAttrs, { type: oSearch.termType, v: oSearch.term });
		return prefix + Compat.makeTag("t", oAttrs, null);
	}
	if (oSearch.constructor == ParseTree)
	{
		var arSubs = oSearch.arSubSearches;
		var n = arSubs.length;
		if (n == 0)
			return "";
		if (n == 1)
			return this.getXMLhelper(arSubs[0], level, prefix);

		var ar = new Array("");
		for (var i in arSubs)
			ar.push(this.getXMLhelper(arSubs[i], level+1, prefix + this.tab));
		ar.push(prefix);

		var op = oSearch.op;
		if (op == null)
			op = OpAnd;
		return prefix + Compat.makeTag(op.tagName, addProps(oAttrs, op.attrs), ar.join(this.newline));
	}
}

QueryParser.prototype.getXML = function(oParseTree)
{
	return this.getXMLhelper(oParseTree, 0, "");
}

QueryParser.prototype.createParseError = function(errorCode, message, data, charPos)
{
	if (charPos == null) charPos = this.charPos;
	return new ParseError(errorCode, message, this.term, charPos, this.fieldName, data);
}

QueryParser.prototype.parseProx = function()
{
	var s = this.term.substr(this.charPos);
	var ar = s.match(/^([wsp])(\+?)(\d+)/);
	if (ar == null)
		throw this.createParseError(ParseError.PROXIMITY, "invalid proximity definition", s);

	this.charPos += ar[0].length;
	var op = new Operator(OpProx.precedence, OpProx.tagName);
	op.attrs = {
		type: ar[1],
		order: (ar[2] == "+") ? "true" : "false",
		dist: ar[3]
	};
	return op;
}

QueryParser.prototype.makeNumericTerm = function(vMin, vMax)
{
	var oAttrs = { f: this.fieldName, type: "num" };
	if (vMin == vMax)
		addProps(oAttrs, { v: vMin });
	else
		addProps(oAttrs, { min: vMin, max: vMax });
	return Compat.makeTag("t", oAttrs);
}

QueryParser.prototype.parseNumber = function(v, bAllowFloat)
{
	if (v == null || v == "")
		return v;
	if (bAllowFloat)
	{
		v = v.replace(/,/g, ".");
		if (!v.match(/\d*(\.\d*)?/))
			throw this.createParseError(ParseError.NUMERIC, "invalid numeric search");
		var f = parseFloat(v);
		if (isNaN(f))
			throw this.createParseError(ParseError.NUMERIC, "invalid numeric search");
		return Math.floor(f * 100);
	}
	else
	{
		if (!v.match(/\d+/))
			throw this.createParseError(ParseError.NUMERIC, "invalid numeric search");
		var n = parseInt(v);
		if (isNaN(n))
			throw this.createParseError(ParseError.NUMERIC, "invalid numeric search");
		return n;
	}
}

QueryParser.prototype.parseNumeric = function(bAllowFloat)
{
	var re = /^\s*([0-9.,]+)?\s*(-\s*([0-9.,]+)?\s*)?$/;
	var ar = this.term.match(re);
	if (ar == null)
		throw this.createParseError(ParseError.NUMERIC, "invalid numeric search");
	var vMin = ar[1];
	var vMax = (ar[2] != null && ar[2].length) ? ar[3] : vMin;
	if (vMin == "" && vMax == "")
		throw this.createParseError(ParseError.NUMERIC, "invalid numeric search");
	vMin = this.parseNumber(vMin, bAllowFloat);
	vMax = this.parseNumber(vMax, bAllowFloat);
	return this.makeNumericTerm(vMin, vMax);
}

QueryParser.prototype.parseSingleDate = function(s)
{
	if (s.length == 0)
		return "";
	var re = /^(\d{1,2})\/(\d{1,2})\/(\d{1,4})$/;
	var ar = s.match(re);
	if (ar == null)
		throw this.createParseError(ParseError.DATE, "invalid date search", s);
	var day = parseInt(ar[1]), month = parseInt(ar[2]), year = parseInt(ar[3]);
	if (day < 1 || day > 31)
		throw this.createParseError(ParseError.INVALID_DAY, "day out of range", day);
	if (month < 1 || month > 12)
		throw this.createParseError(ParseError.INVALID_MONTH, "month out of range", month);
	// Count years since 1900.
	if (year > 1900)
		year -= 1900;
	else if (year < 28)
		year += 100;	// assume XXI century
	return day + month*(1 << 5) + year*(1 << 9);
}

QueryParser.prototype.parseDate = function()
{
	var re = /^\s*([0-9\/]+)?\s*(-\s*([0-9\/]+)?\s*)?$/;
	var ar = this.term.match(re);
	if (ar == null)
		throw this.createParseError(ParseError.DATE, "invalid date search");
	var vMin = this.parseSingleDate(ar[1]);
	var vMax = (ar[2] != null && ar[2].length) ? this.parseSingleDate(ar[3]) : vMin;
	if (vMin == "" && vMax == "")
		throw this.createParseError(ParseError.DATE, "invalid date search");
	return this.makeNumericTerm(vMin, vMax);
}

QueryParser.prototype.cleanTerm = function(s)
{
	s = s.replace(/[()\[\],\/\\]/g, " ");
	s = s.replace(/\s\./g, " ");
	s = s.replace(/\.\s/g, " ");
	return s;
}

QueryParser.prototype.checkTerm = function(s, bCleanTerm)
{
	if (s.match(/^\s*$/))
		throw this.createParseError(ParseError.EMPTY_TERM, "empty search expression");
	return s;
}

QueryParser.prototype.createToken = function(s)
{
	var t = this.checkSpecialToken(s);
	if (t != null)
		return t;

	var first = s.charAt(0), last = s.charAt(s.length - 1);

	if (first == "\"" && last == "\"")
	{
		var p = new QueryParser(this.fieldName, this.fieldFlags);
		var t = this.cleanTerm(s.substr(1, s.length - 2));
		p.term = this.checkTerm(t);
		p.charPos = 0;
		p.checkSpecialToken = function(s) { return null; }	// ignore "and", "or", "not" inside quotes
		var oParseTree = p.doParse(new ParseTree());
		oParseTree.op = OpAdj;
		return new Token(oParseTree);
	}

	if (first == "[" && last == "]")
		return new Token(this.checkTerm(s.substr(1, s.length - 2)), "expr");		// [ ] - expression

	if (first == "'" && last == "'")
		return new Token(this.checkTerm(s.substr(1, s.length - 2)), "word");		// single quotes - literal

	// Remove funny characters at the beginning or end ("C.D.I." -> "C.D.I")
	s = s.replace(/^[.,]+|[.,]+$/, "");

	// Count wildcard characters
	var wildCount = 0;
	s.replace(/[*!?]/g, function() { ++wildCount; });
	if (wildCount > 0)
	{
		if ((this.fieldFlags & FieldFlags.WILDCARD) == 0)
			throw this.createParseError(ParseError.WILDCARD, "wildcards not allowed", s);
		if (s.length - wildCount < 2)
			throw this.createParseError(ParseError.TOO_WILD, "search term must contain at least 2 non-wildcard characters", s);
		return new Token(this.checkTerm(s), "wild");
	}

	return new Token(this.checkTerm(s), "word");
}

QueryParser.prototype.getToken = function()
{
	if (this.lookahead != null)
	{
		var ret = this.lookahead;
		this.lookahead = null;
		return ret;
	}
	
	var startPos = null;		// character position in this.term where current token starts
	var stopChars = " \t()";	// token-breaking characters
	if (this.fieldFlags & FieldFlags.PROXIMITY)
		stopChars += "^/|";
	var s, sBeginQuote, sEndQuote;
	var openCount = 0;
	var bAdvance = true;
	
	// Main tokenizer loop - check characters one by one
	while (true)
	{
		if (bAdvance)
			s = this.term.charAt(this.charPos++);
		else
			bAdvance = true;
		if (s.length == 0)
			break;

		if (startPos != null)		// token already started
		{
			if (s == sBeginQuote)
				++openCount;

			if (s == sEndQuote)		// matching quote found
			{
				if (openCount > 0)
					--openCount;
				// Ignore closing quote inside a word
				if (openCount == 0)
				{
					var nextChar = this.term.charAt(this.charPos);	// will be "" at the end of string
					if (nextChar == "" || nextChar == " ") 
						break;
				}
			}

			if (sEndQuote == null && stopChars.indexOf(s) >= 0)
			{
				// one of the stop chars found (if token is quoted, stop chars don't count)
				--this.charPos;
				break;
			}
			continue;	// keep adding characters to current token
		}

		// token not started yet
		switch (s)
		{
			case " ":
			case "\t":
				// ignore spaces before token
				continue;
				
			case "'":
			case "\"":
				sBeginQuote = sEndQuote = s;	// quote closing character is the same as opening
				break;

			case "[":
				sBeginQuote = s;
				sEndQuote = "]";
				openCount = 1;
				break;

			case "(": return Token.BeginSubsearch;

			case ")": return Token.EndSubsearch;

			case "^": return Token.Adjacent;

			// If the term is not a valid proximity token (e.g. "foo/bar"),
			// parse as if there was a space instead ("foo bar")
			case "/": try { return new Token(this.parseProx(), TokenType.InfixOperator); }
					catch (e) { s = " "; bAdvance = false; continue; }

			case "|": try { return new Token(this.parseProx(), TokenType.PrefixOperator); }
					catch (e) { s = " "; bAdvance = false; continue; }
		}

		// real char! token starts here
		startPos = this.charPos - 1;
	}

	if (startPos == null)
		return Token.End;

	if (sEndQuote != null && s != sEndQuote)
		throw this.createParseError(ParseError.MISMATCHED_QUOTE, "mismatched " + sBeginQuote, sBeginQuote, startPos);
	
	return this.createToken(this.term.substr(startPos, this.charPos - startPos));
}

QueryParser.prototype.ungetToken = function(token)
{
	this.lookahead = token;
}

QueryParser.prototype.parseSubSearch = function()
{
	var startPos = this.charPos;
	var subSearch = this.doParse(new ParseTree());
	if (subSearch.arSubSearches.length == 0)
		throw this.createParseError(ParseError.EMPTY_SUBSEARCH, "search expression expected", null, startPos);
	var nextToken = this.getToken();
	if (nextToken.type != TokenType.EndSubsearch)
		throw this.createParseError(ParseError.SUBSEARCH_BEGIN, "mismatched '('", nextToken, startPos);

	return subSearch;
}

QueryParser.prototype.doParse = function(oParseTree)
{
	while (true)
	{
		var token = this.getToken();

		// If there's no operator between two consecutive search expressions, insert an implicit "and".
		if (oParseTree.opAllowed && token.type != TokenType.InfixOperator)
		{
			this.ungetToken(token);
			token = this.defaultOperator;
			//token = Token.And;
		}

		switch (token.type)
		{
			case TokenType.SearchTerm:
				oParseTree.push(token);
				break;
				
			case TokenType.BeginSubsearch:
				var subSearch = this.parseSubSearch();
				oParseTree.push(subSearch);
				break;
			
			case TokenType.EndSubsearch:
			case TokenType.End:
				this.ungetToken(token);
				return oParseTree;

			case TokenType.PrefixOperator:
				var nextToken = this.getToken();
				if (nextToken.type != TokenType.BeginSubsearch)
					throw this.createParseError(ParseError.SUBSEARCH_EXPECTED, "expected '('", nextToken);
				var subSearch = this.parseSubSearch();
				subSearch.op = token.op;
				oParseTree.push(subSearch);
				break;
				
			case TokenType.InfixOperator:
				if (!oParseTree.opAllowed)
					throw this.createParseError(ParseError.SEARCH_EXPECTED, "search expression expected", token);

				var currOp = oParseTree.op;
				var op = token.op;
				if (currOp == null)
					currOp = oParseTree.op = op;
				
				// if same operator as the current, keep adding subsearches.
				if (op == currOp)
					break;

				if (op.precedence < currOp.precedence)
				{
					var newTree = new ParseTree(op);
					newTree.push(oParseTree);
					oParseTree = this.doParse(newTree);
				}
				else
				{
					var newTree = new ParseTree(op);
					newTree.push(oParseTree.pop());
					var oSubsearch = this.doParse(newTree);
					oParseTree.push(oSubsearch);
				}
				break;

			case TokenType.ParseTree:
				oParseTree.push(token.tree);
				break;
		}
		// Can't have two consecutive infix operators.
		oParseTree.opAllowed = (token.type != TokenType.InfixOperator);
	}
}

QueryParser.prototype.parseTerm = function(sTerm)
{
	this.term = sTerm;
	this.charPos = 0;
	
	if (this.fieldFlags & FieldFlags.NUMERIC)
		return this.parseNumeric(this.fieldFlags & FieldFlags.FLOAT);

	if (this.fieldFlags & FieldFlags.DATE)
		return this.parseDate();

	var oParseTree = this.doParse(new ParseTree());
	var checkToken = this.getToken();
	if (checkToken.type != TokenType.End)
		throw this.createParseError(ParseError.SUBSEARCH_END, "mismatched ')'", checkToken);

	return this.getXML(oParseTree);
}