|
This strikes me as an obvious place to use recursion. So here goes...
public class MString
{
public static bool CompareWWc(string strA, string strB, bool ignoreCase)
{
if (ignoreCase)
return CompareWWc(strA.ToLower(), strB.ToLower());
else
return CompareWWc(strA, strB);
}
public static bool CompareWWc(string strA, string strB)
{
for (int i = 0; i < strA.Length; i++)
{
if (strA[i] == '*')
{
if (i == strA.Length - 1)
return true;
strA = strA.Substring(i + 1);
for (int j = i; j < strB.Length; j++)
if (CompareWWc(strA, strB.Substring(j)))
return true;
return false;
}
if (i >= strB.Length || (strA[i] != strB[i] && strA[i] != '?'))
return false;
}
return strA.Length == strB.Length;
}
}
And here's a little test sequence:
if (!MString.CompareWWc("", ""))
Console.WriteLine("Something wrong!");
if (!MString.CompareWWc("something", "something"))
Console.WriteLine("Something wrong!");
if (MString.CompareWWc("something", "zomething"))
Console.WriteLine("Something wrong!");
if (MString.CompareWWc("something", "some"))
Console.WriteLine("Something wrong!");
if (MString.CompareWWc("something", "something else"))
Console.WriteLine("Something wrong!");
if (!MString.CompareWWc("s?m?th???", "something"))
Console.WriteLine("Something wrong!");
if (MString.CompareWWc("s?m?th???", "somethin"))
Console.WriteLine("Something wrong!");
if (!MString.CompareWWc("*", ""))
Console.WriteLine("Something wrong!");
if (!MString.CompareWWc("*", "nonsense"))
Console.WriteLine("Something wrong!");
if (!MString.CompareWWc("non*", "nonsense"))
Console.WriteLine("Something wrong!");
if (!MString.CompareWWc("*nonsense", "nonsense"))
Console.WriteLine("Something wrong!");
if (!MString.CompareWWc("non*nse", "nonsense"))
Console.WriteLine("Something wrong!");
if (MString.CompareWWc("non*nse", "nonsenze"))
Console.WriteLine("Something wrong!");
if (!MString.CompareWWc("non*n?e", "nonsense"))
Console.WriteLine("Something wrong!");
if (!MString.CompareWWc("n*on*nse", "nonsense"))
Console.WriteLine("Something wrong!");
if (!MString.CompareWWc("n*n*nse", "nonsense"))
Console.WriteLine("Something wrong!");
if (MString.CompareWWc("*non*nse", "nonsenze"))
Console.WriteLine("Something wrong!");
if (!MString.CompareWWc("n*n*n?e", "nonsense"))
Console.WriteLine("Something wrong!");
}
By the way, the name CompareWWc means Compare With Wildcards.
|
|
|
|
|
Actually, the recursive function together with substring will make this slow.
I'm using this at the moment:
public static class StringExtensions
{
public static bool WildcardMatch(this string str, string compare, bool ignoreCase)
{
if (ignoreCase)
return str.ToLower().WildcardMatch(compare.ToLower());
else
return str.WildcardMatch(compare);
}
public static bool WildcardMatch(this string str, string compare)
{
if (string.IsNullOrEmpty(compare))
return str.Length == 0;
int pS = 0;
int pW = 0;
int lS = str.Length;
int lW = compare.Length;
while (pS < lS && pW < lW && compare[pW] != '*')
{
char wild = compare[pW];
if (wild != '?' && wild != str[pS])
return false;
pW++;
pS++;
}
int pSm = 0;
int pWm = 0;
while (pS < lS && pW < lW)
{
char wild = compare[pW];
if (wild == '*')
{
pW++;
if (pW == lW)
return true;
pWm = pW;
pSm = pS + 1;
}
else if (wild == '?' || wild == str[pS])
{
pW++;
pS++;
}
else
{
pW = pWm;
pS = pSm;
pSm++;
}
}
while (pW < lW && compare[pW] == '*')
pW++;
return pW == lW && pS == lS;
}
}
|
|
|
|
|
Hi Erwin,
Thanks for your posting. It did make me decide to investigate the situation.
I still really think this is a situation that begs for recursion. But maybe you were right that substring is not a good idea. So I made this version:
public class MString2
{
public static bool CompareWWc(string strA, string strB, bool ignoreCase)
{
if (ignoreCase)
return CompareWWc(strA.ToLower(), 0, strB.ToLower(), 0);
else
return CompareWWc(strA, 0, strB, 0);
}
public static bool CompareWWc(string strA, string strB)
{
return CompareWWc(strA, 0, strB, 0);
}
private static bool CompareWWc(string strA, int indexA, string strB, int indexB)
{
for (int i = 0; indexA + i < strA.Length; i++)
{
if (strA[indexA + i] == '*')
{
if (indexA + i == strA.Length - 1)
return true;
for (int j = indexB + i; j < strB.Length; j++)
if (CompareWWc(strA, indexA + i + 1, strB, j))
return true;
return false;
}
if (indexB + i >= strB.Length || (strA[indexA + i] != strB[indexB + i] && strA[indexA + i] != '?'))
return false;
}
return strA.Length - indexA == strB.Length - indexB;
}
}
Then I ran some timing tests, using System.Diagnostics.Stopwatch. I put my test case with 19 calls to the function in a loop and executed it 10,000 times. I did this for my original version, your version, and my new version. I compiled the programs in Release mode.
Assuming I haven't made a mistake somewhere, here are my results for a single function call:
My original version: 342 nonoseconds
Your version: 237 nanoseconds
My second version: 279 nanoseconds
Now to tell you the truth, I find it very difficult to get excited about saving 100 nanoseconds at the expense of having two and a half times as many lines of code. Especially since my expected use of this function in my application will probably never exceed a couple hundred calls per day.
Anyway, thanks for getting me to think things over again and make the tests. Personally, at least in this particular case, I prefer programmer understandability to execution efficiency. I've decided to stick with my original version, since I think my second version is more difficult to understand, and the improved efficiency not worth that disadvantage.
|
|
|
|
|
Hi Erwin,
Sorry - my previous numbers are not correct. I was running the programs under the Visual Studio debugger, and that was apparently not good for timing tests.
Here's what I get now:
My original version: 243 nonoseconds
Your version: 76 nanoseconds
My second version: 111 nanoseconds
Assuming these timings are valid, your version is three times faster than my original version, and that is pretty significant, at least in a situation were the function may be used millions times a day.
Sorry for the incorrect timings in my previous posting.
|
|
|
|
|
Yes, the recursive function makes it more understandable for sure. In my case I actually call it several thousands of times after certain user actions, so I'm even considering using unsafe code I also thought of a special case where your function will get a performance hit: SearchString = "--ABC-----ABC-----ABC-----lots of text (without 'at') goes here" , wildcardString = "*ABC*@" . In this case my function (based on Jack's) will search for the '@' character once starting from position 5 (but won't find it, because it's not there). With your function it would search for the '@' character 3 times (once starting from position 5 until the end, once from 13 and once from 21). The longer the text at the end or the more occurances of 'ABC' at the start, the greater the performance hit.
|
|
|
|
|
If at first you don't succeed...
Here's my third version, where I say to hell with minimizing lines of code and try to optimize the speed. No "unsafe" code though, unless you consider "goto" to be unsafe coding.
public class MString
{
public static bool CompareWWc(string strA, string strB, bool ignoreCase)
{
if (ignoreCase)
return CompareWWc(strA.ToLower(), strB.ToLower());
else
return CompareWWc(strA, strB);
}
public static bool CompareWWc(string strA, string strB)
{
int starPtr = 0;
if (strB.Length >= strA.Length)
{
for (;; starPtr++)
{
if (starPtr == strA.Length)
return strA.Length == strB.Length;
if (strA[starPtr] == '*')
goto firstSegmentMatches;
if (strA[starPtr] != strB[starPtr] && strA[starPtr] != '?')
return false;
}
}
else
{
for (;; starPtr++)
{
if (strA[starPtr] == '*')
goto firstSegmentMatches;
if (starPtr == strB.Length)
return false;
if (strA[starPtr] != strB[starPtr] && strA[starPtr] != '?')
return false;
}
}
firstSegmentMatches:
int indexA;
int indexB = starPtr;
while (true)
{
indexA = ++starPtr;
if (indexA == strA.Length)
return true;
for (;; starPtr++)
if (starPtr == strA.Length || strA[starPtr] == '*')
break;
for (;; indexB++)
{
if (starPtr - indexA > strB.Length - indexB)
return false;
for (int i = indexA, j = indexB; i < starPtr; i++, j++)
if (strA[i] != strB[j] && strA[i] != '?')
goto tryStringBAgain;
goto findNextSegment;
tryStringBAgain:
continue;
}
findNextSegment:
indexB += starPtr - indexA;
if (starPtr == strA.Length)
return indexB == strB.Length;
}
}
}
And here are my timing results (which I'm not totally sure of, I'm not used to timing code):
My original version: 243 nanoseconds 17 lines of code
Erwin's version: 76 nanoseconds 42 lines of code
My second version: 111 nanoseconds 16 lines of code
My third version: 56 nanoseconds 52 lines of code
I'd appreciate it if someone would check this out and let me know if they find any bugs or anything.
|
|
|
|
|
I found small bug, if compare "*a" and "babbba" function return false.
|
|
|
|
|