9
\$\begingroup\$

I have the following function to compare a string with a wildcard string (containing ? and *), as C# doesn't seem to have a builtin function to do it.

    /// <summary>
    /// Compares wildcard to string
    /// </summary>
    /// <param name="WildString">String to compare</param>
    /// <param name="Mask">Wildcard mask (ex: *.jpg)</param>
    /// <returns>True if match found</returns>
    public static bool CompareWildcard(string WildString, string Mask, bool IgnoreCase = true)
    {
        int i = 0, k = 0;

        // Cannot continue with Mask empty
        if (string.IsNullOrEmpty(Mask))
            return false;

        // If WildString is null -> make it an empty string
        if (WildString == null)
            WildString = string.Empty;

        // If Mask is * and WildString isn't empty -> return true
        if (string.Compare(Mask, "*") == 0 && !string.IsNullOrEmpty(WildString))
            return true;

        // If Mask is ? and WildString length is 1 -> return true
        if (string.Compare(Mask, "?") == 0 && WildString.Length == 1)
            return true;

        // If WildString and Mask match -> no need to go any further
        if (string.Compare(WildString, Mask, IgnoreCase) == 0)
            return true;

        while (k != WildString.Length)
        {
            switch (Mask[i])
            {
                case '*':

                    if ((i + 1) == Mask.Length)
                        return true;

                    while (k != WildString.Length)
                    {
                        if (CompareWildcard(WildString.Substring(k + 1), Mask.Substring(i + 1), IgnoreCase))
                            return true;

                        k += 1;
                    }

                    return false;

                case '?':

                    break;

                default:

                    if (IgnoreCase == false && WildString[k] != Mask[i])
                        return false;

                    if (IgnoreCase && Char.ToLower(WildString[k]) != Char.ToLower(Mask[i]))
                        return false;

                    break;
            }

            i += 1;
            k += 1;
        }

        if (k == WildString.Length)
        {
            if (i == Mask.Length || Mask[i] == '*')
                return true;
        }

        return false;
    }

I added the check to make sure Mask isn't null/empty because if it is then switch (Mask[i]) will throw a IndexOutOfRangeException. I'm wondering if there are any other checks I should make or change (specifically during the while loop)?

\$\endgroup\$
  • 1
    \$\begingroup\$ why dont you use Regex and you save yourself this hassle codeproject.com/Articles/11556/Converting-Wildcards-to-Regexes \$\endgroup\$ – Sleiman Jneidi Jun 26 '14 at 21:21
  • \$\begingroup\$ @SleimanJneidi I want a foolproof method rather then something that has unknown problems with it \$\endgroup\$ – ub3rst4r Jun 26 '14 at 21:54
  • \$\begingroup\$ Why do you think that the $Regex$ method "has unknown problems"? What would satisfy you that any solution was "foolproof"? \$\endgroup\$ – Snowbody Jun 30 '14 at 14:39
7
\$\begingroup\$

What you want to do is called "globbing". It's actually quite easy to do with a Regex.

There are a few code smells here. The recursion is the obvious one. The other is the special-cases. When you special-case the single-character wildcard, it suggests that you're thinking about the problem wrong. There's no reason why they would need to -- or even should -- be specialcased.

If you really want to reinvent the wheel, the "right way" is to build a state machine and backtrack. I combined @NotPro's answer and @svick's hint to get http://ideone.com/VUDFIw but that uses backtracking. Check out http://swtch.com/~rsc/regexp/regexp1.html to see why backtracking is a bad idea, and how we can get an O(n) state machine.

\$\endgroup\$
7
\$\begingroup\$

Another option, as outlined in this blog is to not re-invent the wheel and use the VB.net LikeString method:

Add a reference to Microsoft.VisualBasic first.

using Microsoft.VisualBasic;
using Microsoft.VisualBasic.CompilerServices;

if(Operators.LikeString("This is just a test", "*just*", CompareMethod.Text))
{
  Console.WriteLine("This matched!");
}
\$\endgroup\$
  • 3
    \$\begingroup\$ using Microsoft.VisualBasic in a C# project? o.O \$\endgroup\$ – Mathieu Guindon Jul 1 '14 at 4:36
1
\$\begingroup\$

You still have bug for wildString = "xyzz", mask = "?" .

The best idea is to use Regex but if you want implement your own solution I would use Linq. I think it's make solution much shorter and easier to understand.

static bool CompareWildcard(IEnumerable<char> input, string mask)
{
    for (int i = 0; i < mask.Length; i++)
    {
        switch (mask[i])
        {
            case '?':
                if (!input.Any())
                    return false;

                input = input.Skip(1);
                break;
            case '*':
                while (input.Any() && !CompareWildcard(input, mask.Substring(i + 1)))
                    input = input.Skip(1);
                break;
            default:
                if (!input.Any() || input.First() != mask[i])
                    return false;

                input = input.Skip(1);
                break;
        }
    }

    return ! input.Any(); 
}
\$\endgroup\$
  • 1
    \$\begingroup\$ @Snowbody You're right that using Skip() this way is a bad idea (it leads to \$\mathcal{O}(n^2)\$ code), but how exactly do you clone Enumerator? A better way to do this might be to use ImmutableStack or FSharpList. \$\endgroup\$ – svick Jun 28 '14 at 14:26
  • \$\begingroup\$ @svick Yikes! I committed the cardinal sin of C#, assuming that it worked the same as C++. Thanks for setting me straight. \$\endgroup\$ – Snowbody Jun 30 '14 at 19:48
  • 1
    \$\begingroup\$ @Snowbody Now that I think about it, if input was string, then its enumerator is CharEnumerator, which can be cloned. But you can't do that with a general IEnumerator<char>. \$\endgroup\$ – svick Jun 30 '14 at 19:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.