// SearchMethod.cpp: implementation of the CSearchMethod class.
//采用通配符匹配字符竄的方法類接口
//語法說明:本類實現的通配符號有兩個"?"and"*"
//   '?'----------可以代替一個字符
//   '*'----------可以代替任意長度的字符竄
//example: "3*6?8"與"345678"兩個字符竄是可以匹配的
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "qq.h"
#include "SearchMethod.h"

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
static LPCTSTR STRINGS[]=
{
	"!","@","#","$","%","^","&",
		"-","+","~",":","<", ">"," ","(",")","=","==",
		"\\","//","|","||","&&","/*","*/",
		"{","}","{}","[","]","[]",";","'",".",
		"`","$$","!=",
		NULL
};
CSearchMethod::CSearchMethod()
{
	for(int i=0;i<50;i++)
	{
		serial[i]=0;//賦初值
		serialchar[i]=' ';
	}
}

CSearchMethod::~CSearchMethod()
{

}
//////////////////////////////////////////////////////////////////////////
/*             檢查輸入的字符是否合乎語法規則               */
//////////////////////////////////////////////////////////////////////////
bool CSearchMethod::CheckString(CString str)
{
	CString strText=str;
	int i=0;
	while (i<strText.GetLength()&&strText[i]!=NULL)
	{
		int j=0;
		while(STRINGS[j]!=NULL)
		{
			CString str1=strText[i];
			if(str1==STRINGS[j])
			{
				return false;
			}
			j++;
		}
		i++;
	}
	//因為通配符*可以代替任何長度，所以不能有連續兩個**符號
	int k=0;
    while(k+1<strText.GetLength()&&strText[k]!=NULL&&strText[k+1]!=NULL)
	{
		if(strText[k]=='*'&&strText[k+1]=='*')
		{
			return false;
		}
		k++;
	}
    return true;
}
/*@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
                   str1:需要匹配的字符竄
                   str2:源字符竄
         說明：若str1中的部分或者全部字符與str2相同則稱為匹配
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@*/
bool CSearchMethod::IsMatchString(CString str1, CString str2)
{
       //先清空
	for(int m=0;m<50;m++)
	{
		serial[m]=0;
		serialchar[m]=' ';
	}
    //循環str1查找非特殊字符
	int i=0,j=0;
	while (i<str1.GetLength()&&str1[i]!=NULL)
	{//search the serial and serialchar
		if(str1[i]!='?'&&str1[i]!='*')
		{
            serial[j]=i;//保存序號
			serialchar[j]=str1[i];//保存字符
			j++;
		}
		i++;
	}
	bool bAllZero=true;//判斷得出的結果是否全為0
	for(i=0;i<50;i++)
	{
		if(serial[i]==0)
		{
			bAllZero=bAllZero&true;
		}
		else
		{
			bAllZero=bAllZero&false;
		}
	}
	bool bEnableMates=true;
	if(bAllZero)
	{//若輸入的字符全為0
		if(str1.GetLength()==1)
		{
            if(str1[0]=='*')
			{
				bEnableMates=true;
			}
			else if(str1[0]=='?')
			{
				if(str2.GetLength()>1)
				{
					bEnableMates=false;
				}
				else
				{
					bEnableMates=true;
				}
			}
			else
			{
				if(str2.GetLength()==1&&str1[0]==str2[0])
				{
					bEnableMates=true;
				}
				else
				{
					bEnableMates=false;
				}
			}
		}
		else
		{//不是只有一位，有多位的特殊符號
			BOOL bAllSame=true;//是否全為?
			for(int i=0;i<str1.GetLength();i++)
			{
                if(str1[i]=='?')
				{
					bAllSame=bAllSame&true;
				}
				else{bAllSame=bAllSame&false;}
			}
			if(bAllSame)
			{//全為?
				if(str1.GetLength()==str2.GetLength())
				{
					bEnableMates=true;
				}
				else{bEnableMates=false;}
			}
			else
			{
				if(str1[0]!=str2[0])
				{
					bEnableMates=false;
				}
				else
				{bEnableMates=true;}
			}
		}
	}
	else
	{
		i=0;
		while(serial[i+1]!=0)
		{
			//得到分段的字符竄
			CString s1=str1.Mid(serial[i],serial[i+1]-serial[i]+1);
			int k=0,pre=0,next=0;
			while(k<str2.GetLength()&&str2[k]!=NULL)
			{
				if(str2[k]==serialchar[i])
				{
					pre=k;//前一個字符
				}
				if(str2[k]==serialchar[i+1])
				{
					next=k;//后一個字符
					break;
				}
				k++;
			}
			CString s2=str2.Mid(pre,next-pre+1);
			bEnableMates=bEnableMates&EnableMatches(s1,s2);
			i++;
		}
		//分析字符的前面一部分
		bool bsuceess=false;
		if(serial[0]!=0)
		{
			BOOL bAllSame=true;//是否全為'?'
			for(int i=0;i<serial[0];i++)
			{
				if(str1[i]=='?')
				{
					bAllSame=bAllSame&true;
				}
				else
				{
					bAllSame=bAllSame&false;
				}
			}
			if(bAllSame)
			{//若全為'?'
                int nCount=0;
				for(int i=0;i<str2.GetLength();i++)
				{
					if(str2[i]==serialchar[0])
					{
						nCount=i;
						break;
					}
				}
				if(nCount==serial[0])
				{//若兩個字符竄的前面一部分的字符個數相同
                    bEnableMates=bEnableMates&true;
				}
				else{bEnableMates=bEnableMates&false;}
			}
			else
			{
				bEnableMates=bEnableMates&true;
			}
		}
		else
		{
			if(str1[0]==str2[0])
			{
				bsuceess=true;
			}
			else{bsuceess=false;}
            bEnableMates=bEnableMates&bsuceess;
		}
		//分析后面一部分
		bsuceess=false;
		int nFirstZero=0;
		for(i=0;i<50;i++)
		{
			if(serial[i]==0&&serial[i+1]==0)
			{
				nFirstZero=i;
				break;
			}
		}
            if(serial[nFirstZero-1]==str1.GetLength()-1)
			{//不存在通配符號
                 if(serialchar[nFirstZero-1]==str2[str2.GetLength()-1])
				 {
					 bsuceess=true;
				 }
				 else{bsuceess=false;}
				 bEnableMates=bEnableMates&bsuceess;//將后部分的結果并入總結果中
			}
			else
			{
				if(serialchar[nFirstZero-1]==str2[str2.GetLength()-1])
				{
					bEnableMates=bEnableMates&false;
				}
				else
				{
					BOOL bAllSame=true;
					for(int i=serial[nFirstZero-1]+1;i<str1.GetLength();i++)
					{
						if(str1[i]=='?')
						{
							bAllSame=bAllSame&true;
						}
						else{bAllSame=bAllSame&false;}
					}
					if(bAllSame)
					{
                        int nCount=0;
						for(int i=0;i<str2.GetLength();i++)
						{
							if(str2[i]==serialchar[nFirstZero-1])
							{
								nCount=i;
								break;
							}
						}
						int nLong1=str1.GetLength()-serial[nFirstZero-1]-1;
						int nLong2=str2.GetLength()-nCount-1;
						if(nLong1==nLong2)
						{
							bEnableMates=bEnableMates&true;
						}
						else{bEnableMates=bEnableMates&false;}
					}
					else{bEnableMates=bEnableMates&true;}
				}

			}
	}
	return bEnableMates;
}

bool CSearchMethod::EnableMatches(CString str1, CString str2)
{//判斷兩個首尾字符相同的字符竄是否匹配 str1="a*b",str2="acdfeb"
    if(str1.GetLength()>str2.GetLength())
	{
		return false;
	}
	else
	{
		if(str1.GetLength()<=2&&str2.GetLength()>2)
		{
			return false;
		}
		else 
		{
			BOOL bAllSame=true;
			
			for (int i=1;i<str1.GetLength()-1;i++)
			{
				if(str1[i]=='?')
				{
					bAllSame=bAllSame&true;
				}
				else{bAllSame=bAllSame&false;}
			}
			if(bAllSame)
			{
				if(str1.GetLength()==str2.GetLength())
				{
					return true;
				}
				else{return false;}
			}
            else{return true;}
		}
	}
}

int CSearchMethod::FindingString(const char *lpszSour, const char *lpszFind, int nStart)
{
    if(lpszSour == NULL || lpszFind == NULL || nStart < 0)
		return -1;
	
	int m = strlen(lpszSour);
	int n = strlen(lpszFind);
	
	if( nStart+n > m )
		return -1;
	
	if(n == 0)
		return nStart;
	
	//KMP算法
	int* next = new int[n];
	//得到查找字符串的next數組
	{	n--;
	
	int j, k;
	j = 0;
	k = -1;
	next[0] = -1;
	
	while(j < n)
	{	if(k == -1 || lpszFind[k] == '?' || lpszFind[j] == lpszFind[k])
	{	j++;
				k++;
				next[j] = k;
	}
	else
		k = next[k];
	}
	
	n++;
	}
	
	int i = nStart, j = 0;
	while(i < m && j < n)
	{
		if(j == -1 || lpszFind[j] == '?' || lpszSour[i] == lpszFind[j])
		{	i++;
		j++;
		}
		else
			j = next[j];
	}
	
	delete []next;
	
	if(j >= n)
		return i-n;
	else
		return -1;
}
//功	  能：帶通配符的字符串匹配
//參	  數：lpszSour是一個普通字符串；
//			  lpszMatch是一可以包含通配符的字符串；
//			  bMatchCase為0，不區分大小寫，否則區分大小寫。
//返  回  值：匹配，返回1；否則返回0。
//通配符意義：
//		‘*’	代表任意字符串，包括空字符串；
//		‘?’	代表任意一個字符，不能為空；
bool CSearchMethod::MatchingString(const char *lpszSour, const char *lpszMatch, bool bMatchCase)
{
   	if(lpszSour == NULL || lpszMatch == NULL)
		return false;

	if(lpszMatch[0] == 0)//Is a empty string
	{
		if(lpszSour[0] == 0)
			return true;
		else
			return false;
	}

	int i = 0, j = 0;

	//生成比較用臨時源字符串'szSource'
	char* szSource =
		new char[ (j = strlen(lpszSour)+1) ];

	if( bMatchCase )
	{	//memcpy(szSource, lpszSour, j);
		while( *(szSource+i) = *(lpszSour+i++) );
	}
	else
	{	//Lowercase 'lpszSour' to 'szSource'
		i = 0;
		while(lpszSour[i])
		{	if(lpszSour[i] >= 'A' && lpszSour[i] <= 'Z')
				szSource[i] = lpszSour[i] - 'A' + 'a';
			else
				szSource[i] = lpszSour[i];

			i++;
		}
		szSource[i] = 0;
	}

	//生成比較用臨時匹配字符串'szMatcher'
	char* szMatcher = new char[strlen(lpszMatch)+1];

	//把lpszMatch里面連續的“*”并成一個“*”后復制到szMatcher中
	i = j = 0;
	while(lpszMatch[i])
	{
		szMatcher[j++] = (!bMatchCase) ?
								( (lpszMatch[i] >= 'A' && lpszMatch[i] <= 'Z') ?//Lowercase lpszMatch[i] to szMatcher[j]
										lpszMatch[i] - 'A' + 'a' :
										lpszMatch[i]
								) :
								lpszMatch[i];		 //Copy lpszMatch[i] to szMatcher[j]
		//Merge '*'
		if(lpszMatch[i] == '*')
			while(lpszMatch[++i] == '*');
		else
			i++;
	}
	szMatcher[j] = 0;

	//開始進行匹配檢查

	int nMatchOffset, nSourOffset;

	bool bIsMatched = true;
	nMatchOffset = nSourOffset = 0;
	while(szMatcher[nMatchOffset])
	{
		if(szMatcher[nMatchOffset] == '*')
		{
			if(szMatcher[nMatchOffset+1] == 0)
			{	//szMatcher[nMatchOffset]是最后一個字符

				bIsMatched = true;
				break;
			}
			else
			{	//szMatcher[nMatchOffset+1]只能是'?'或普通字符

				int nSubOffset = nMatchOffset+1;

				while(szMatcher[nSubOffset])
				{	if(szMatcher[nSubOffset] == '*')
						break;
					nSubOffset++;
				}

				if( strlen(szSource+nSourOffset) <
						size_t(nSubOffset-nMatchOffset-1) )
				{	//源字符串剩下的長度小于匹配串剩下要求長度
					bIsMatched = false; //判定不匹配
					break;			//退出
				}

				if(!szMatcher[nSubOffset])//nSubOffset is point to ender of 'szMatcher'
				{	//檢查剩下部分字符是否一一匹配

					nSubOffset--;
					int nTempSourOffset = strlen(szSource)-1;
					//從后向前進行匹配
					while(szMatcher[nSubOffset] != '*')
					{
						if(szMatcher[nSubOffset] == '?')
							;
						else
						{	if(szMatcher[nSubOffset] != szSource[nTempSourOffset])
							{	bIsMatched = false;
								break;
							}
						}
						nSubOffset--;
						nTempSourOffset--;
					}
					break;
				}
				else//szMatcher[nSubOffset] == '*'
				{	nSubOffset -= nMatchOffset;

					char* szTempFinder = new char[nSubOffset];
					nSubOffset--;
					memcpy(szTempFinder, szMatcher+nMatchOffset+1, nSubOffset);
					szTempFinder[nSubOffset] = 0;

					int nPos = FindingString(szSource+nSourOffset, szTempFinder, 0);
					delete []szTempFinder;

					if(nPos != -1)//在'szSource+nSourOffset'中找到szTempFinder
					{	nMatchOffset += nSubOffset;
						nSourOffset += (nPos+nSubOffset-1);
					}
					else
					{	bIsMatched = false;
						break;
					}
				}
			}
		}		//end of "if(szMatcher[nMatchOffset] == '*')"
		else if(szMatcher[nMatchOffset] == '?')
		{
			if(!szSource[nSourOffset])
			{	bIsMatched = false;
				break;
			}
			if(!szMatcher[nMatchOffset+1] && szSource[nSourOffset+1])
			{	//如果szMatcher[nMatchOffset]是最后一個字符，
				//且szSource[nSourOffset]不是最后一個字符
				bIsMatched = false;
				break;
			}
			nMatchOffset++;
			nSourOffset++;
		}
		else//szMatcher[nMatchOffset]為常規字符
		{
			if(szSource[nSourOffset] != szMatcher[nMatchOffset])
			{	bIsMatched = false;
				break;
			}
			if(!szMatcher[nMatchOffset+1] && szSource[nSourOffset+1])
			{	bIsMatched = false;
				break;
			}
			bool b=bIsMatched;
			nMatchOffset++;
			nSourOffset++;
		}
	}

	delete []szSource;
	delete []szMatcher;
	return bIsMatched;
}