--[[ ---------------------------------------------------------------------------
Created:		8/6/2010 4:11:28 AM
Last Modified:	2011-04-29T08:44:39Z
Author:			orgevo
Version:		v1.3a

Options:	Contains all static options data for the addon.

AtlasLootAdvancedSearch is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation, either version 3 of the License, or
(at your option) any later version.

AtlasLootAdvancedSearch is distributed WITHOUT ANY WARRANTY; without even the 
implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with AtlasLootAdvancedSearch.	If not, see <http://www.gnu.org/licenses/>.

----------------------------------------------------------------------------- ]]

local ADDON_TAG					= "AtlasLootAdvancedSearch"
local AtlasLootAdvancedSearch	= LibStub("AceAddon-3.0"):GetAddon(ADDON_TAG);
local alas_addon				= AtlasLootAdvancedSearch;
local al_addon					= AtlasLoot;
local SEARCHPARSER_DEBUG		= false
local ENABLE_LOGGING			= alas_addon.ENABLE_LOGGING and SEARCHPARSER_DEBUG

-- localization
local L							= LibStub("AceLocale-3.0"):GetLocale(ADDON_TAG, true)
local AL						= LibStub("AceLocale-3.0"):GetLocale("AtlasLoot");
local ADDON_NAME				= L["ADDON_NAME"]
local BabbleInventory			= AtlasLoot_GetLocaleLibBabble("LibBabble-Inventory-3.0")

-- globals => locals, faster access
local tinsert, tremove, tconcat, tsort, twipe = table.insert, table.remove, table.concat, table.sort, table.wipe
local strlen,	strmatch,	strfind,	strsub,		strformat,	strlower,		strupper,	strtrim =
	string.len, string.match, string.find, string.sub, string.format, string.lower, string.upper, strtrim
local pairs, next, type = pairs, next, type
local tostring, strgmatch, gsub = tostring, string.gmatch, gsub
local RED_FONT_COLOR_CODE, GREEN_FONT_COLOR_CODE = RED_FONT_COLOR_CODE, GREEN_FONT_COLOR_CODE
local searchParms, newclass = alas_addon.SearchParameters, newclass

-- slightly modified version of strsplit that returns nil if the source string doesn't contain any of the delimiter characters
local strsplit = function(delim, source, count, return_null_set)
	if return_null_set then return strsplit(delim, source, count); end
	local result_tbl = { strsplit(delim, source, count) };
	if #result_tbl == 1 and result_tbl[1] == source then
		return nil;
	end
	return unpack(result_tbl);
end

-- print wrappers
-- t_print (testing): what I use while developing....most of these will be commented out in the repository versions
-- dev_print (development): outputs only when AtlasLootAdvancedSearch.dev_mode is true
local function r_print(str) alas_addon:Print(str); end
local function r_printf(str,...) alas_addon:Print(strformat(str,...)); end

local dbgProxy = alas_addon.DebugProxy;
local function isDevMode()			return dbgProxy and dbgProxy:isDevMode() end
local function isInternal()			return dbgProxy and dbgProxy:isInternal() end
local function t_print(str)			if dbgProxy and ENABLE_LOGGING then dbgProxy:t_print(str) end end
local function t_printf(str,...)	if dbgProxy and ENABLE_LOGGING then dbgProxy:t_printf(str, ...) end end
local function dev_print(str)		if dbgProxy and ENABLE_LOGGING then dbgProxy:dev_print(str) end end
local function dev_printf(str, ...)	if dbgProxy and ENABLE_LOGGING then dbgProxy:dev_printf(str,...) end end
local function d_print(str)			if dbgProxy and ENABLE_LOGGING then dbgProxy:d_print(str) end end
local function d_printf(str,...)	if dbgProxy and ENABLE_LOGGING then dbgProxy:d_printf(str,...) end end
local function funcEnter(obj, funcName, formatStr, ...)
	if alas_addon.DebugProxy.isEnabled and ENABLE_LOGGING then
		if formatStr then alas_addon.DebugProxy:TraceEnter(obj,funcName,strformat(formatStr,...));
		else alas_addon.DebugProxy:TraceEnter(obj,funcName); end
	end
end
local function funcExit(obj, funcName, formatStr, ...)
	if alas_addon.DebugProxy.isEnabled and ENABLE_LOGGING then
		if formatStr then alas_addon.DebugProxy:TraceExit(obj,funcName,strformat(formatStr,...));
		else alas_addon.DebugProxy:TraceExit(obj,funcName); end
	end
end
local function t_printSlow(str)			if alas_addon.ALLOW_SLOW_LOGS then t_print(str)		end end
local function t_printfSlow(str,...)	if alas_addon.ALLOW_SLOW_LOGS then t_printf(str,...)	end end

--[[
local _G = _G;	-- save a reference to the global environment
setfenv(1, setmetatable( {}, {
	__index = function(t, k)
		local v = _G[k]
		_G.print("Accessing global variable " .. k .. "; current value: " .. _G.tostring(v))
		return v;
	end,
	__newindex = function(t, k, v)
		local oldValue = _G[k];
		print("Setting variable in global environment " .. k .. " to " .. _G.tostring(v) .. "; old value: " .. _G.tostring(oldvalue));
		_G[k] = v;
	end
}))
--]]

local function truefalse(cond)
	if cond then return GREEN_FONT_COLOR_CODE .. "true" .. FONT_COLOR_CODE_CLOSE
	else return RED_FONT_COLOR_CODE .. "false" .. FONT_COLOR_CODE_CLOSE; end
end

function toggledebug_searchparser()
	SEARCHPARSER_DEBUG = not SEARCHPARSER_DEBUG;
end


--[[	ParseDelimitedString
 *
 * This is a wrapper function for the strsplit method.  Its sole purpose is to concatenate the output from successive strsplit operations
 * into a single table (safely).
 *
 * @param	text		the source string that will be parsed and separated
 * @param	delim		any string which is a valid input value for the delimiter parameter of the default strsplit function.
 * @param	destTable	[optional] a table for storing the individual parts produced from calling strsplit.  This table is not
 *						cleared before processing, in order to successive calls to send all results to the same location.
 *
 * @return	if a valid table value is specified for the destTable parameter, this function has no return value.  otherwise, returns the result
 *			of calling the strsplit function.
--]]
local function ParseDelimitedString(text, delim, destTable)
	if text and type(text) == "string" and delim and type(delim) == "string" then
		if destTable then
			local chunks = { strsplit(delim, text, nil, true) }
			for idx = 1, #chunks do
				-- add the next delimited portion to the array
				local nextChunk = strtrim(chunks[idx]);
				if strlen(nextChunk) > 0 then
					destTable[#destTable + 1] = nextChunk;
				end
			end
		else
			return strsplit(delim, text, nil, true);
		end
	end
end


-- Class declarations
local SearchTokenBase = newclass("SearchTokenBase");
local SearchToken = newclass("SearchToken", SearchTokenBase);
local SearchTerm = newclass("SearchTerm", SearchTokenBase);
SearchPhrase = newclass("SearchPhrase", SearchTokenBase);
local SearchPhrase = SearchPhrase;
--[[
Glossary:
	- SearchToken:
		a single word or number contained in a SearchTerm.
	
	- SearchTerm:
		a grouping of words which have an "AND" relationship with each other, with regards to matching against the list of items.
		For example - ("blue" "feet") is a SearchTerm which matches only items that have both words ("blue and "feet") somewhere
		in the data that is checked by the search modules.
		
		SearchTerm cannot contain an OR relationship.

	- SearchPhrase:
		a grouping of SearchTerms which have an OR relationship between them.
		
		
	-- need one more class: the class which holds the collection of search phrases

"blue feet"
SearchPhrase = 
	node[1] {SearchTerm}: blue
	node[2] {SearchTerm}: feet
	


SearchPhrase = "(Sanctified and (legs or chest)) or ((head or (hands and gloves)) and Zabra) or waist"
	SearchTerm[1]: (Sanctified and (legs or chest))
		token[1]: Sanctified
		token[2]: {Search Phrase}
			token[1]: legs
			token[2]: chest
			
	SearchTerm[2]: ((head or (hands and gloves)) and Zabra)
		token[1]: {Search Phrase: head or (hands and gloves)}
			token[1]: head
			token[2]: {Search Term}
				token[1]: hands
				token[2]: gloves
				
		token[2]: Zabra
	
	SearchTerm[3]: waist
		token[1]: {Search Token}: waist

--]]

--[[	SearchTokenBase
 * Base class for all search nodes 
 *
 *
--]]
function SearchTokenBase:init()
	self.super:init();
end
function SearchTokenBase.__len()
	return 6969;
end

function SearchTokenBase:GetClassName()
	return self:class():name();
end
SearchTokenBase:virtual("GetClassName");

function SearchTokenBase:AddSearchPhrase( searchTermText )
	local newSearchPhrase = nil;
	if searchTermText and type(searchTermText) == "string" then
		searchTermText = strtrim(searchTermText);
		if strlen(searchTermText) > 0 then
			newSearchPhrase = SearchPhrase:new(searchTermText);
			self:AppendSearchNode(newSearchPhrase);
		end
	end

	return newSearchPhrase;
end
SearchTokenBase:virtual("AddSearchPhrase");


-- pure virtuals, sort of
SearchTokenBase:virtual("GetValue");
SearchTokenBase:virtual("IsMatch")
SearchTokenBase:virtual("AppendSearchNode");
SearchTokenBase:virtual("DumpPhrase");
SearchTokenBase:virtual("Copy");
SearchTokenBase:virtual("CountTokens");
SearchTokenBase:virtual("CountNodes");

--[[============================================================================================================================================
	- SearchToken:
		a single word or number contained in a SearchTerm.  (quoted phrases are considered a single token)
    ========================================================================================================================================--]]
function SearchToken:init( text )
	self.super:init();

	-- text of this token
	if text and type(text) == "string" then
		self.value = text;
	else
		self.value = false;
	end
	
	-- this is the table of additional words that were sent to this SearchToken.  If it does not contain quotes, we'll
	-- consider the entire thing to be the intended expression.  If it contains a substring delimited with quotes, then
	-- the quoted portion becomes the new value of self.value, and the rest gets put into extraWords
	self.extraWords = false;
	self:ProcessQuotedText();
end

function SearchToken:Copy()
	local myCopy = SearchToken:new(self.value);
	
	--@TODO handle the extra words and quoted text...
	return myCopy;
end

function SearchToken:__tostring()
	return "{"  .. self:class():name() .. "  " .. tostring(self.value) .. "}";
end
function SearchToken:__len()
t_printfSlow("SearchToken.__len is being called");
	if self.value then return strlen(self.value) end
	return 0;
end

function SearchToken:ProcessQuotedText()
	if self.value and type(self.value) == "string" and strlen(self.value) > 0 then
		local oldValue = self.value;
		self.value = "";
		
		-- walk through the string, seperating words using space as a delimiter; if a phrase
		-- in quotes is encountered, treat it as a single "word"
		for before, quoted, after in strgmatch(oldValue, '([^"]*)(%b"")([^"]*)') do
			-- we found *something*, so go ahead and create the table now.
			if self.extraWords == false then self.extraWords = {} end
			ParseDelimitedString(before, " ", self.extraWords);
				-- if we found a quoted string, that goes next
				if strlen(quoted) > 2 then
					-- strip the actual quotation marks
					quoted = strsub(quoted, 2, strlen(quoted) - 1);

					-- strip leading/trailing whitespace
					quoted = strtrim(quoted);

					-- make sure it wasn't all whitespace
					if strlen(quoted) > 0 then
						if self.value == "" then
							-- replace the current value of self.value with the first quoted substring we encountered
							self.value = quoted;
						else
							-- for any additional (seperate) quoted substrings, consider them a single "word" but they also go into extra words
							self.extraWords[#self.extraWords + 1] = quoted;
						end
					end
				end
			ParseDelimitedString(after, " ", self.extraWords);
		end
		
		if self.extraWords == false or self.value == "" then
			-- this means that self.value didn't contain any substrings surrounded by quotes; assume the user intended for the whole thing to considered one term
			self.value = oldValue;
		else
			-- nothing to do here, so far...
		end
	end
end

function SearchToken:GetValue()
	return self.value;
end

function SearchToken:CountTokens()
	return 1;
end

function SearchToken:CountNodes()
	return 1;
end

function SearchToken:IsMatch( searchString )
	local isMatch = false;
	if searchString and self.value then
		local partial = true;					-- @TODO: perhaps one day we add support for non-partial matching
		if partial then
			local pos = strfind(searchString, gsub(self.value, "%-", "%%-"));
			if pos and pos > 0 then
				isMatch = true;
			else
				isMatch = false;
			end
		else
			isMatch = (self.value == searchString);
		end
	end
--print(self:class():name() .. ":IsMatch - searchString:" .. tostring(searchString) .. "    value:" .. self.value .. "   ismatch:" .. tostring(isMatch));
	return isMatch;
end

function SearchToken:DumpPhrase(indent_string)
	if indent_string == nil then indent_string = "" end
	t_print(indent_string .. "SearchToken (" .. tostring(self.value) .. ")");
end

--[[============================================================================================================================================
	- SearchTerm:
		a grouping of words which have an "AND" relationship with each other, with regards to matching against the list of items.
		For example - ("blue" "feet") is a SearchTerm which matches only items that have both words ("blue and "feet") somewhere
		in the data that is checked by the search modules.
		
		SearchTerm cannot contain an OR relationship.
    ========================================================================================================================================--]]

function SearchTerm:init( text )
	self.super:init();
	
	-- one or more search tokens, each of which might be a SearchToken, SearchPhrase or SearchTerm
	self.SearchTokens = {}

	if text and type(text) == "string" then
		self.value = text;
	else
		self.value = false;
	end
end
function SearchTerm:Copy()
	myCopy = SearchTerm:new();
	myCopy.value = self.value;
	
	for tokenIdx = 1, #self.SearchTokens do
		token = self.SearchTokens[tokenIdx];
		myCopy:AppendSearchNode(token:Copy());
	end
	
	return myCopy;
end

function SearchTerm:__tostring()
	return "{" .. self:GetClassName() .. "  " .. tostring(self.value) .. "}  Tokens:" .. tostring(#self.SearchTokens);
end
function SearchTerm:__len()
	return #self.SearchTokens;
end

function SearchTerm:GetValue()
	return self.value;
end

function SearchTerm:CountTokens()
	local result = 0;
	for tokenIdx = 1, #self.SearchTokens do
		result = result + self.SearchTokens[tokenIdx]:CountTokens();
	end
	return result;
end

function SearchTerm:CountNodes()
	local result = 1;
	
	for tokenIdx = 1, #self.SearchTokens do
		result = result + self.SearchTokens[tokenIdx]:CountNodes();
	end
	
	return result;
end

--[[	SearchTerm:IsMatch
 *
 * Determines whether some arbitrary input string (usually an item name, item slot, zone name, etc.) contains anything
 * the user was searching for.
 *
 * SearchTerm specific: iterates through the list of SearchTokens contains in this SearchTerm, allowing each SearchToken
 *						the opportunity to check whether that SearchToken has a match in the input string.  SearchTokens
 *						have an inclusive relationship with each other (AND), thus SearchTerm will only indicate a successful
 *						match if all tokens contained in the SearchTerm indicate successful matches.
 *						If at least one member SearchToken indicates a match, SearchTerm will then package the remainder of
 *						the input string (that is, any portion that did not indicate a successful match) to be checked by other
 *						search modules.
 *
 *
 * @param	searchString	the input string to compare against this SearchTerm's tokens.  The source of the string is determined
 *							by the individual search modules, so its value might be the complete item name, complete zone name, etc.
 *			incompleteMatchesAllowed
 *							indicates whether the remainder from a partial match should be packaged for comparison with data from other search modules.
 *
 * @return	bool, bool, table{SearchToken}
 *			- true if the entire SearchTerm was successfully matched against the input string
 *			- true if at least one (but not all) SearchToken indicated a successful match
 *			- the table of SearchTokens which did NOT indicate successful matches.
--]]
--[[
"zabra and hand"
"zabra and feet"
"zabra and head and crusader"
	SearchToken[1]: Zabra
	SearchToken[2]: head
	SearchToken[3]: crusader


this item should match:
item:
"Zabra Hood" => "Zabra Hood"	++ 1
slot:
"Zabra Hood"   => "head"		++ 2
zone:
"Zabra Hook" > ToC				++ 3

this item should not:
item: Zabra Staff				++ 1
slot: MH						+X 2
zone: ToC						++ 3
--]]

function SearchTerm:IsMatch( searchString, incompleteMatchesAllowed, pendingMatches )
	local isCompleteMatch, isPartialMatch = false, false;
	local unmatchedTokens, unmatchedTerm = {}, nil;

	if searchString then
		local allTokensMatch = #self.SearchTokens > 0;
		local foundMatchingToken = false;

		for termIndex = 1, #self.SearchTokens do
			local nextToken = self.SearchTokens[termIndex];
			
			-- check to see if the next token (OR clause) matches anything in this target string
			local nextTokenMatches = nextToken:IsMatch(searchString);
			allTokensMatch = allTokensMatch and nextTokenMatches;

			if incompleteMatchesAllowed then
				if not nextTokenMatches then
					unmatchedTokens[#unmatchedTokens + 1] = nextToken;
				end
				foundMatchingToken = foundMatchingToken or nextTokenMatches;
			end
		end

		isCompleteMatch = allTokensMatch;
		
		-- no need to check incompleteMatchesAllowed here because foundMatchingToken can only ever be true
		-- if incompleteMatchesAllowed is true.
		if not isCompleteMatch and foundMatchingToken then
			isPartialMatch = true;
			if incompleteMatchesAllowed and #unmatchedTokens > 0 then
				local unmatchedTermText = unmatchedTokens[1]:GetValue();
				for idx = 2, #unmatchedTokens do
					unmatchedTermText = unmatchedTermText .. "+" .. unmatchedTokens[idx]:GetValue();
				end
				
				-- we do this to prevent creating hundreds of nodes unnecessarily, such as in cases where some
				-- portion of the search term is something common to a large number of items (for example, if
				-- the name of a zone were part of the search expression)
				local alreadyPendingMatch = false;
				if pendingMatches ~= nil then
					for idx = 1, #pendingMatches do
						if pendingMatches[idx]:GetValue() == unmatchedTermText then
							alreadyPendingMatch = true;
							break;
						end
					end
				end
				if not alreadyPendingMatch then
					if #unmatchedTokens > 1 then
						-- since this will be some subset of our own search term, we'll need to create a new search term to contain it.
						unmatchedTerm = SearchTerm:new(unmatchedTermText);
						for idx = 1, #unmatchedTokens do
							-- no need to make a copy, as nothing is going to modify these values
							unmatchedTerm:AppendSearchNode(unmatchedTokens[idx]);
						end
					else
						unmatchedTerm = unmatchedTokens[1];
					end
					if pendingMatches then
						pendingMatches[#pendingMatches + 1] = unmatchedTerm;
					end
				end
			end
		else
			unmatchedTerm = nil;
		end
	end
--[===[@debug@
--t_printf("%s%s:IsMatch|r(%s%s|r) [value:%s%s|r] => isCompleteMatch:%s   isPartialMatch:%s   unmatchedTerm:%s%s|r    Num Tokens:%s",
--	RED_FONT_COLOR_CODE, self:class():name(), GREEN_FONT_COLOR_CODE, tostring(searchString), YELLOW_FONT_COLOR_CODE, self.value, truefalse(isCompleteMatch), truefalse(isPartialMatch), GREEN_FONT_COLOR_CODE, tostring(unmatchedTerm), tostring(#self.SearchTokens));
--@end-debug@]===]
	return isCompleteMatch, isPartialMatch, unmatchedTerm;
end


--[[	SearchTerm:AppendSearchNode
 *
 * Simple wrappper for adding a new element to this SearchTerm's list of tokens.
 *
 * @param	SearchNode	an instance of SearchTermBase which should be added to this SearchTerm's list of tokens
 *
 * @notes:	primarily used internally by the search parsing system.  External code should almost always call
 *			SearchTerm:AddSearchToken() instead.
--]]
function SearchTerm:AppendSearchNode( SearchNode )
	if SearchNode ~= nil then
		self.SearchTokens[#self.SearchTokens + 1] = SearchNode;
	else
		t_print("Warning - " .. self:GetClassName() .. ":AppendSearchNode() called with invalid value for 'SearchNode'");
	end
end

--[[	SearchTerm:AddSearchToken
 *
 * Creates a new search token instance that will be associated with a discreet element of an AND operation in a search string.
 *
 * @param	tokenText	the text that the search token represents; this value would normally originate from user input.
 *
 * @return:	the SearchToken instance that was created and linked to the input string
--]]
function SearchTerm:AddSearchToken( tokenText )
	local newSearchToken = nil;

	if tokenText then
		tokenText = strtrim(tokenText);
		if strlen(tokenText) > 0 then
			newSearchToken = SearchToken:new(tokenText);
			self:AppendSearchNode(newSearchToken);
		end
	end

	return newSearchToken;
end

function SearchTerm:DumpPhrase(indent_string)
	if indent_string == nil then indent_string = "" end
	print(indent_string .. "SearchTerm (" .. tostring(self.value) .. ")   SearchTokens:" .. tostring(#self.SearchTokens));
	for i = 1, #self.SearchTokens do
		self.SearchTokens[i]:DumpPhrase(indent_string .. "  ");
	end
end

--[[============================================================================================================================================
	- SearchPhrase:
		a grouping of SearchTerms which have an OR relationship between them.
    ========================================================================================================================================--]]
function SearchPhrase:init( text )
	self.super:init();

	-- a collection of SearchTerms
	self.SearchTerms = {}
	
	if text and type(text) == "string" then
		self.value = text;
	else
		self.value = false;
	end
end
function SearchPhrase:Copy()
	local myCopy = SearchPhrase:new();
	myCopy.value = self.value;
	for termIdx = 1, #self.SearchTerms do
		myCopy:AppendSearchNode(self.SearchTerms[termIdx]:Copy());
	end
	return myCopy;
end

function SearchPhrase:__tostring()
	return "{" .. self:GetClassName() .. "  " .. tostring(self.value) .. "}   SearchTerms:" .. tostring(#self.SearchTerms);
end
function SearchPhrase:__len()
	return #self.SearchTerms;
end

function SearchPhrase:GetValue()
	return self.value;
end

function SearchPhrase:IsMatch( searchString, incompleteMatchesAllowed, pendingMatches )
	local isMatch, isPartialMatch = false, false;
	local unmatchedTerms, unmatchedPhrase = {}, nil;
	
	if searchString then
		searchString = strlower(searchString);
		for phraseIndex = 1, #self.SearchTerms do
			local nextTerm = self.SearchTerms[phraseIndex];
			local nextIsCompleteMatch, nextIsPartialMatch, nextUnmatchedTerm = nextTerm:IsMatch(searchString, incompleteMatchesAllowed, pendingMatches);
			isMatch = isMatch or nextIsCompleteMatch;

			-- can skip checking incompleteMatchesAllowed here because nextIsPartialMatch should always be false if
			-- incompleteMatchesAllowed is false.
			if nextIsPartialMatch then
				isPartialMatch = true;
				if incompleteMatchesAllowed then
					if nextUnmatchedTerm ~= nil then
						unmatchedTerms[#unmatchedTerms + 1] = nextUnmatchedTerm;
--[===[@debug@
--						t_printf("%sSearchPhrase:IsMatch|r(%s%s|r) - nextIsCompleteMatch:%s   nextIsPartialMatch:%s   unmatchedTerm:%s%s|r   unmatchedTerms(%i)",
--							RED_FONT_COLOR_CODE, GREEN_FONT_COLOR_CODE, searchString, truefalse(nextIsCompleteMatch), truefalse(nextIsPartialMatch), GREEN_FONT_COLOR_CODE, tostring(nextTerm), #unmatchedTerms);
					else
--						t_printf("%s ****** ENCOUNTERED A NIL VALUE FOR nextUnmatchedTerm in SearchPhrase:IsMatch(%s), came from SearchTerm:'%s'", RED_FONT_COLOR_CODE, searchString, tostring(nextTerm));
--						for i = 1, #nextTerm.SearchTokens do
--							t_printf("        SearchToken[%i]: %s", i, tostring(nextTerm.SearchTokens[i]));
--						end
--@end-debug@]===]
					end
--[===[@debug@
				else
--					t_printf("%sSearchPhrase:IsMatch|r(%s%s|r) COMPLETING MATCH   Term:%s%s|r     isCompleteMatch:%s     isPartialMatch:%s",
--						RED_FONT_COLOR_CODE, GREEN_FONT_COLOR_CODE, searchString, tostring(nextTerm), truefalse(nextIsCompleteMatch), truefalse(nextIsPartialMatch));
--@end-debug@]===]
				end
			end
		end
		
		if isPartialMatch and incompleteMatchesAllowed and #unmatchedTerms > 0 then
			local unmatchedPhraseText = unmatchedTerms[1]:GetValue();
			for idx = 2, #unmatchedTerms do
				unmatchedPhraseText = unmatchedPhraseText .. "|" .. unmatchedTerms[idx]:GetValue();
			end
			
			local alreadyPendingMatch = false;
			if pendingMatches ~= nil then
				for idx = 1, #pendingMatches do
--[===[@debug@
--				t_printf("    %sSearchPhrase:IsMatch|r(%s%s|r) - unmatchedPhraseText:'%s'    pendingMatches[%i]:'%s%s|r'", RED_FONT_COLOR_CODE, GREEN_FONT_COLOR_CODE, searchString, unmatchedPhraseText, idx, YELLOW_FONT_COLOR_CODE, tostring(pendingMatches[idx]));
--@end-debug@]===]
					if pendingMatches[idx]:class() == SearchPhrase and pendingMatches[idx]:GetValue() == unmatchedPhraseText then
						alreadyPendingMatch = true;
						break;
					end
				end
			end
			if not alreadyPendingMatch then
				if #unmatchedTerms > 1 then
					unmatchedPhrase = SearchPhrase:new(unmatchedPhraseText);
					for idx = 1, #unmatchedTerms do
						unmatchedPhrase:AppendSearchNode(unmatchedTerms[idx]);
					end
				else
					unmatchedPhrase = unmatchedTerms[1];
				end
				if pendingMatches then
					pendingMatches[#pendingMatches + 1] = unmatchedPhrase;
				end
			end
		end
	end
	return isMatch, isPartialMatch, unmatchedPhrase;
end

function SearchPhrase:AppendSearchNode( SearchNode )
	if SearchNode ~= nil then
		self.SearchTerms[#self.SearchTerms + 1] = SearchNode;
	else
		t_print("Warning: " .. self:GetClassName() .. ":AppendSearchNode called with invalid value for 'SearchNode'.");
	end
end

function SearchPhrase:AddSearchTerm( searchTermText )
	local newSearchTerm;

	if searchTermText and type(searchTermText) == "string" then
		searchTermText = strtrim(searchTermText);
		if strlen(searchTermText) > 0 then
			newSearchTerm = SearchTerm:new(searchTermText);
			self:AppendSearchNode(newSearchTerm);
		end
	end

	return newSearchTerm;
end

function SearchPhrase:CountTokens()
	local result = 0;
	for termIdx = 1, #self.SearchTerms do
		result = result + self.SearchTerms[termIdx]:CountTokens();
	end
	return result;
end

function SearchPhrase:CountNodes()
	local result = 1;
	for termIdx = 1, #self.SearchTerms do
		result = result + self.SearchTerms[termIdx]:CountNodes();
	end
	return result;
end

function SearchPhrase:DumpPhrase(indent_string)
	if indent_string == nil then indent_string = "" end
	print(indent_string .. "SearchPhrase (" .. tostring(self.value) .. ")   SearchTerms:" .. tostring(#self.SearchTerms));
	for i = 1, #self.SearchTerms do
		self.SearchTerms[i]:DumpPhrase(indent_string .. "  ");
	end
end


local function ParsePrefix(prefixText)
	local parsedPrefix, delimiter;

	if prefixText then
		prefixText = strtrim(prefixText);
		if strlen(prefixText) > 0 then
			delimiter = strsub(prefixText, strlen(prefixText));
			if delimiter == "+" or delimiter == "|" then
				-- prefixText should be a search term, and everything after prefix text will be part of the same search term
				parsedPrefix = strtrim(strsub(prefixText, 1, strlen(prefixText) - 1));
			end
		end
	end

	return parsedPrefix, delimiter;
end

local function ParseSuffix(suffixText)
	local parsedSuffix, delimiter;

	if suffixText then
		suffixText = strtrim(suffixText);
		if strlen(suffixText) > 0 then
			delimiter = strsub(suffixText, 1,1);
			if delimiter == '+' or delimiter == '|' then
				parsedSuffix = strtrim(strsub(suffixText,2));
			end
		end
	end

--t_printf("ParseSuffix - suffixText:'%s'   delimiter:'%s'    parsedSuffix:'%s'", tostring(suffixText), tostring(delimiter), tostring(parsedSuffix));
	return parsedSuffix, delimiter;
end

local function ParseToken(tokenText, ownerPhrase)
	local nextSearchTerm = nil;

	if tokenText then
		local terms = { strsplit("|", tokenText) };
		if #terms > 0 then
			for i = 1, #terms do
				nextSearchTerm = ownerPhrase:AddSearchTerm(terms[i]);
				if nextSearchTerm then
					nextSearchTerm:AddSearchToken(strtrim(terms[i]));
				end
			end
		elseif strlen(tokenText) > 0 then
			nextSearchTerm = ownerPhrase:AddSearchTerm(tokenText);
			if nextSearchTerm then
				terms = { strsplit('+', tokenText, nil, true) }
				for i = 1, #terms do
					nextSearchTerm:AddSearchToken(strtrim(terms[i]));
				end
			end
		end
	end

	return nextSearchTerm;
end

--[[============================================================================================================================================
	- SearchPhraseParser
		Prepares a string to be parsed into a search token tree.
    ========================================================================================================================================--]]
local SearchPhraseParser = newclass("SearchPhraseParser");
function SearchPhraseParser:init()
	self.super:init();
	
	self.inputString = false;
	self.SearchTreeRoot = false;
end
function SearchPhraseParser:__len()
	if self.SearchTreeRoot then
		return #self.SearchTreeRoot;
	end
	return 0;
end
function SearchPhraseParser:__tostring()
	return "{ SearchPhraseParser: '" .. self:GetInputString() .. "' }";
end

function SearchPhraseParser:GetInputString()
	if self.inputString == false then
		-- due to restrictions of the OOP implementation, instance values cannot be initalized to nil
		-- in the class's init() function or they won't be linked properly
		return "";
	end
	
	return self.inputString;
end

function SearchPhraseParser:GetSearchExpressionTree()
	if self.SearchTreeRoot == false then
		-- due to restrictions of the OOP implementation, instance values cannot be initalized to nil
		-- in the class's init() function or they won't be linked properly
		return nil;
	end
	
	return self.SearchTreeRoot;
end

function SearchPhraseParser:IsMatch( text, incompleteMatchesAllowed, pendingMatches )
	searchParms = _G.searchParms;
	local foundMatch, foundPartialMatch, remainingMatchParser = false, false, nil;
	if text and type(text) == "string" then
		local searchRoot = self:GetSearchExpressionTree();
		if searchRoot then
			local remainingMatchPhrase;
			foundMatch, foundPartialMatch, remainingMatchPhrase = searchRoot:IsMatch(strlower(strtrim(text)), incompleteMatchesAllowed, pendingMatches);
			if foundPartialMatch and remainingMatchPhrase then
				local alreadyPendingMatch = false;
				for idx = 1, #pendingMatches do
					if pendingMatches[idx]:class() == SearchPhraseParser then
						alreadyPendingMatch = true;
						break;
					end
				end
				if not alreadyPendingMatch then
					remainingMatchParser = SearchPhraseParser:new();
					remainingMatchParser.inputString = remainingMatchPhrase:GetValue();
					remainingMatchParser.SearchTreeRoot = remainingMatchPhrase;
				end
			end
		end
	end
	return foundMatch, foundPartialMatch, remainingMatchParser;
end

function SearchPhraseParser:CountTokens()
	local result = 0;
	
	local RootPhrase = self:GetSearchExpressionTree();
	if RootPhrase ~= nil then
		result = result + RootPhrase:CountTokens();
	end
	
	return result;
end

function SearchPhraseParser:CountNodes()
	local result = 0;
	local RootPhrase = self:GetSearchExpressionTree();
	if RootPhrase ~= nil then
		result = result + RootPhrase:CountNodes();
	end
	return result;
end

function SearchPhraseParser:ParseText( text )
	if (not text) or (type(text) ~= "string") then
		error("Received call to SearchPhraseParser:ParseText with invalid value for Text! loc me");
	elseif strlen(text) == 0 then
		error("Received call to SearchPhraseParser:ParseText with empty string! loc me");
	else
		-- replace any occurrences of 'AND' or 'OR' with symbolic representations, to simplify the parsing code
		-- the following line replaces the word 'and' with the symbol '+' and the word 'or' with the symbol '|'
		self.inputString = gsub(strlower(text), "(%a+)", {["or"]="|",["and"]="+"});
		
		-- create the search expression tree
		self.SearchTreeRoot = SearchPhrase:new(strlower(text));
		self:tokenize("(" .. self.inputString .. ")", self.SearchTreeRoot);
	end
end

function SearchPhraseParser:tokenize(str, ownerPhrase)
	str = strtrim(str);
	local containsComplexExpression = false;

	for prefix, token, suffix in strgmatch(str, "([^(]*)(%b())([^(]*)") do
		containsComplexExpression = true;

		-- strip leading/trailing whitespace from each portion of the string (before the first parenthesis, after the last parenthesis, and text between the two)
		prefix = strtrim(prefix);
		suffix = strtrim(suffix);
		-- also strip off the outside-most parenthesis so we can start processing that string chunk
		token = strtrim( strsub(token, 2, strlen(token)-1) );

		local nextSearchTerm = nil;
		local parsedPrefix, pre_delimiter = ParsePrefix(prefix);
		local parsedSuffix, post_delimiter = ParseSuffix(suffix);
--t_printf("SearchPhrase:tokenize - prefix:%s   token:%s    suffix:%s    parsedPrefix:'%s'    pre_delimiter:'%s'    parsedSuffix:'%s'    post_delimiter:'%s'",
--	tostring(prefix), tostring(token), tostring(suffix), tostring(parsedPrefix), tostring(pre_delimiter), tostring(parsedSuffix), tostring(post_delimiter));
		if parsedPrefix then
			if pre_delimiter == '+' then
				-- prefix and token will need to be part of the same SearchTerm
				local searchTermText = parsedPrefix .. pre_delimiter .. token;

				-- create the search term that will match the entire AND expression
				local terms = { strsplit("|", parsedPrefix, nil, true) };
				if #terms > 1 then
					for i = 1, #terms - 1 do
						nextSearchTerm = ownerPhrase:AddSearchTerm(terms[i]);
						if nextSearchTerm then
							nextSearchTerm:AddSearchToken(terms[i]);
						end
					end

					-- update these variables to reflect the fact that only the last token is part of the upcoming search term
					parsedPrefix = terms[#terms - 1];
					searchTermText = parsedPrefix .. pre_delimiter .. token;
				end

				-- now, create a search token for text that came before the +
				nextSearchTerm = ownerPhrase:AddSearchTerm(searchTermText);
				if nextSearchTerm then
					nextSearchTerm:AddSearchToken(parsedPrefix);
				end

				-- for the part that was in parenthesis, we need to create another SearchPhrase
				local nestedSearchPhrase = nextSearchTerm:AddSearchPhrase(token);

				-- at this point, nextSearchTerm is still empty of search terms - we'll do that now
				if not self:tokenize(token, nestedSearchPhrase) then
					-- token didn't contain any further nested expressions, so we can just handle it here
					nextSearchTerm = ParseToken(token, nestedSearchPhrase);
				end
			elseif pre_delimiter == '|' then
				-- prefix and token will be different SearchTerms
				nextSearchTerm = ownerPhrase:AddSearchTerm(parsedPrefix);
				if nextSearchTerm then
					nextSearchTerm:AddSearchToken(parsedPrefix);
				end

				nextSearchTerm = ownerPhrase:AddSearchTerm(token);
				if nextSearchTerm then
					local tokens = { strsplit("+", token, nil, true) }
					for i = 1, #tokens do
						local tokenText = strtrim(tokens[i]);
						nextSearchTerm:AddSearchToken(tokenText);
					end
				end
			end
		elseif parsedSuffix then
			--t_printf("parsedSuffix detected - token:'%s'   parsedSuffix:'%s'   post_suffix:'%s'", tostring(token), tostring(parsedSuffix), tostring(post_delimiter));
			if post_delimiter == '+' then
				-- token and suffix will need to be part of the same SearchTerm
				local searchTermText = token .. post_delimiter .. parsedSuffix;
				local parsedSuffix_firstChunk = parsedSuffix;

				-- check the suffix for additional search tokens, and save them off for later so that we can make the search term containing the token
				local terms = { strsplit("|", parsedSuffix, nil, true) };
				if #terms > 1 then
					parsedSuffix_firstChunk = terms[0];
					searchTermText = token .. post_delimiter .. parsedSuffix_firstChunk;
				end

				-- create the search term that will cover the token and suffix
				nextSearchTerm = ownerPhrase:AddSearchTerm(searchTermText);

				if nextSearchTerm then
					-- for the part in parenthesis, we need to create a new SearchPhrase
					local nestedSearchPhrase = nextSearchTerm:AddSearchPhrase(token);

					-- now add a token for the first chunk of the suffix
					nextSearchTerm:AddSearchToken(parsedSuffix_firstChunk);

					-- now we can process the stuff that was inside the parenthesis
					if not self:tokenize(token, nestedSearchPhrase) then
						-- token didn't contain any further nested expressions, so we can just handle it here
						ParseToken(token, nestedSearchPhrase);
					end
				end

				-- finally, add additional parts of suffix that are not part of the previous search term
				for i = 2, #terms do
					nextSearchTerm = ownerPhrase:AddSearchTerm(terms[i]);
					if nextSearchTerm then
						nextSearchTerm:AddSearchToken(terms[i]);
					end
				end
			elseif post_delimiter == '|' then
				-- token and suffix will be different search terms
				if not self:tokenize(token, ownerPhrase) then
					ParseToken(token, ownerPhrase);
				end
				if strlen(parsedSuffix) > 0 then
					nextSearchTerm = ownerPhrase:AddSearchTerm(parsedSuffix);
					if nextSearchTerm then
						nextSearchTerm:AddSearchToken(parsedSuffix);
					end
				end
			end
		elseif not self:tokenize(token, ownerPhrase) then
			-- the part that was in parenthesis didn't contain any nested expressions, so we need to evaluate this part
			ParseToken(token, ownerPhrase);
		end
	end
	return containsComplexExpression;
end

--[[	AtlasLootAdvancedSearch:TokenizeSearchString
 *
 * Public entry point for processing a search string.  The entire process entails splitting the string into one or more
 * parts, delimited by special operator keywords 'AND' & 'OR' (these keywords can optionally be replaced with the symbolic
 * representations '+' & '|', respectively, as these symbols are what the operator keywords are converted to internally.
 * Anything else is considered a literal string, treated as though it were a single token, with only the leading/trailing
 * whitespace characters stripped.
 *
 * @param	Text	the complete string to be processed and parsed down into sub-tokens.
 *
 * @return	a SearchPhraseParser instance which holds a reference to the root of the table that stores the token structure
 *			for the processed input value.
--]]
function AtlasLootAdvancedSearch:TokenizeSearchString(Text)
	local parser = SearchPhraseParser:new();
	parser:ParseText(Text);
	
	return parser;
end


--[[	ExampleFunc
 *
 * This is a utility function for encapsulating the process of parsing a item data table or tokenized item name string (such as =ds=Name of Item).
 * The primary purpose of this method is to extract the bare item name (minus formatting markup) from the rest of the information provided, but it
 * will also attempt to parse fields 4 & 5 of the item data, if passed an item data table as the value for ID, instead of a number.
 *
 * @param	ID		should be either a number (item ID) or the entire item data table.  If passing the item ID value, you should also specify a value
 *					for encodedName.  If passing an item data table for the value of ID, the value of encodedName is irrelevant because it will be
 *					overwritten with the value of the 4th field of the table you passed in for the value of ID.
 *
 * @return	string, string, string
 *			- the name of the item, stripped of any formatting marks.
 *			- the name of the item, including all formatting markup needed to display the item correctly in WoW
 *			- an additional piece of information about the item; ideally the most important thing about the item
 *
--]]



--[[===========================================================================================================================================
	TESTING
===========================================================================================================================================--]]

--local testString = "head or (hands and gloves)";
--local testString = "Zabra and (head or (hands and gloves))";
--local testString = "(head or (hands and gloves)) and Zabra";
--local testString = "(Sanctified and legs) or waist"
--local testString = "(Sanctified and (legs or chest)) or ((head or (hands and gloves)) and Zabra) or waist or BLUE";

--[[
SearchPhrase = (Sanctified and legs) or waist
	SearchTerm[1]: (Sanctified and legs)
		token[1]: Sanctified
		token[2]:legs
	SearchTerm[2]: waist
		token[1]: waist

--]]
--local testString = "(Sanctified and (legs or chest)) or ((head or (hands and gloves)) and Zabra) or waist or BLUE";
--local testString = "legs or chest";
--[[
SearchPhrase = "Zabra and (head or (hands and gloves))"
	SearchTerm[1]: (Zabra and (head or (hands and gloves))
		token[1]: {SearchToken:zabra}
		token[2]: {SearchPhrase: head or (hands and gloves)}
			SearchTerm[1]: {SearchToken}
				token[1]: head
			SearchTerm[2]: {SearchTerm: hands or gloves}
				token[1]: hands
				token[2]: gloves


SearchPhrase = "(head or (hands and gloves)) and Zabra"
	SearchTerm[1]: (Zabra and (head or (hands and gloves))
		token[1]: {SearchPhrase: head or (hands and gloves)}
			SearchTerm[1]: {SearchToken}
				token[1]: head
			SearchTerm[2]: {SearchTerm: hands or gloves}
				token[1]: hands
				token[2]: gloves
		token[2]: {SearchToken:zabra}



	SearchTerm[1]: (Sanctified and (legs or chest))
		token[1]: Sanctified
		token[2]: {Search Phrase: legs or chest}
			token[1]: legs
			token[2]: chest

	SearchTerm[2]: ((head or (hands and gloves)) and Zabra)
		token[1]: {Search Phrase: head or (hands and gloves)}
			token[1]: head
			token[2]: {Search Term: hands and gloves}
				token[1]: hands
				token[2]: gloves

		token[2]: Zabra

	SearchTerm[3]: waist
		token[1]: {Search Token}: waist
--]]

