Tuesday, November 30, 2010

[Javascript] Wildcard string matching / globbing

Most Javascript programmers are more than happy with regular expressions. However, there are times when something like wildcards ('?' for one character and '*' for many) would be helpful.

Jack Handy's first and last (it seems) article on CodeProject implemented a wildcard string compare (also known as 'globbing') function in C. Below I present my port of that function to Javascript.

As a newbie Javascript programmer (4 weeks in as of 2010-11-30), I've pleasantly surprised by the expressive power of Javascript. What has caught my eye recently is the power of .prototype., so this implementation of matchesWild() is declared as a prototype extending the String class.

Here's the code, with some commentary:
Apart from the comments, notice the way Javascript adds a method to an object, defining an anonymous function with, in this case, one parameter, and assigning it as a prototype.
The C version did all kinds of interesting things with pointers. Javascript doesn't have that kind of stuff (AFAICT), so I had to do the equivalent with numeric offsets and substr().

Perhaps there are better ways of doing this. I have tried to do this kind of thing before, but this code seems to do a pretty good job of it and hasn't failed thus far.

What should be noted, and perhaps dealt with, is that there is no explicit check for calling the method without a parameter. If one does this, an error is raised. Chrome's V8 raises "TypeError: Cannot call method 'substr' of undefined".
And now some examples (evaluated using macports's JavaScript-C 1.7.0 2007-10-03)
Outputs:
More Javascript coming soon. In the meantime, enjoy.

© Bruce M. Axtens, 2010

3 comments:

Anonymous said...

Bruce, this can be done using a regex, with . representing a single character, and .* representing one or more. Your example here is equivalent to the regex /^.o.*$/ which can be simplified to /^.o/ (starting at the front, we want any char, then an 'o', and we don't care what comes after that.

Here it is in action (not sure how to format comments here for code)

a = ['kangaroo', 'koala', 'goanna', 'quoll', 'bunyip', 'yowie', 'bandicoot', 'numbat'];

a.filter(function(x){return /^.o/.test(x)})
// returns ["koala", "goanna", "yowie"]

// find words with o as the second letter that end in a
a.filter(function(x){return /^.o.*a$/.test(x)})
// returns ["koala", "goanna"]

Brooke said...

If you are interested in looking at a full blown implementation of wildcard string matching in JavaScript, I would look at jPaq's wild card string functions. jPaq extends JavaScript's String class by adding the findPattern, indexOfPattern and replacePattern functions. I personally love jPaq because it makes it so that the library you download for your site only contains the functions that you need, not the other stuff you wont use.

Bruce M. Axtens said...

Now that's what I call a comment. Thanks, Brooke, very helpful indeed!