[Javascript] Wildcard string matching / globbing, Take 2.

Okay, I'm convinced: you just can't beat regular expressions. (Okay, SNOBOL4's pattern matching is streets ahead, but there's nothing out there like that for Javascript, AFAIK.)

I've reworked the matchesWild function, caling it grepWild. It takes the wildCard parameter as before but instead of all the substr stuff, it replaces '?' with '.', '*' with '.*' and wraps with '^' and '$'. Then it feeds that into match().

It's simpler, easier on the eyes, and faster too.

String.prototype.grepWild = function( wildCard ) {
        var pattern = '^';
        for (var i = 0; i < wildCard.length; i++ ) {
                var c = wildCard.charAt(i);
                switch (c) {
                        case '?':
                                pattern += '.';
                                break;
                        case '*':
                                pattern += '.*';
                                break;
                        default:
                                pattern += c;
                }
        }
        pattern += '$';
        return ( this.match( pattern ) != null );
}

© Bruce M. Axtens, 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:

String.prototype.matchesWild = function( wildCard ) {
        // Written by Jack Handy - jakkhandy@hotmail.com
        //  http://www.codeproject.com/KB/string/wildcmp.aspx
        // Made to work in javascript by Bruce M. Axtens - bruce@strapper.net

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.

        var nCp = 0;
        var nMp = 0;
        var nWild = 0;
        var nThis = 0;

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".

        while ( ( this.substr( nThis, 1 ) ) && ( wildCard.substr( nWild, 1 ) !== '*')) {
                if ( ( wildCard.substr( nWild, 1 ) !== this.substr( nThis, 1 ) ) && 
                        ( wildCard.substr( nWild, 1 ) !== '?') ) 
                                return false;
                nWild++;
                nThis++;
        }

        while ( this.substr( nThis, 1 ) ) {
                if ( wildCard.substr( nWild, 1 ) === '*' ) {
                        if ( !wildCard.substr( ++nWild, 1 ) ) 
                                return true;
                        nMp = nWild;
                        nCp = nThis+1;
                } else if ( ( wildCard.substr( nWild, 1 ) === this.substr( nThis, 1 ) ) || 
                        ( wildCard.substr( nWild, 1 ) === '?' ) ) {
                                nWild++;
                                nThis++;
                } else {
                        nWild = nMp;
                        nThis = nCp++;
                }
        }

        while ( wildCard.substr( nWild, 1 ) === '*' ) 
                nWild++;
        return !wildCard.substr( nWild, 1 );
}

And now some examples (evaluated using macports's JavaScript-C 1.7.0 2007-10-03)

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

        print('select everything with an \'o\' at the second character position');
        for ( i = 0; i < a.length; i++ ) {
                if ( a[ i ].matchesWild( '?o*' ) )  print( 'item(' + i + ')=' + a[i] );
        }
        print("--------------------");
        print('select everything ending with \'a\'');
        for ( i = 0; i < a.length; i++ ) {
                if ( a[ i ].matchesWild( '*a' ) )  print( 'item(' + i + ')=' + a[i] );
        }
        print("--------------------");
        print('select everything with at least two \'a\' characters');
        for ( i = 0; i < a.length; i++ ) {
                if ( a[ i ].matchesWild( '*a*a*' ) )  print( 'item(' + i + ')=' + a[i] );
        }
        print("--------------------");
        print('select everything with an \'oo\'' );
        for ( i = 0; i < a.length; i++ ) {
                if ( a[ i ].matchesWild( '*oo*' ) )  print( 'item(' + i + ')=' + a[i] );
        }
        print("--------------------");
        print('select everything with at least one \'z\' character');
        for ( i = 0; i < a.length; i++ ) {
                if ( a[ i ].matchesWild( '*z*' ) )  print( 'item(' + i + ')=' + a[i] );
        }
        print("--------------------");

Outputs:

select everything with an 'o' at the second character position
item(1)=koala
item(2)=goanna
item(5)=yowie
--------------------
select everything ending with 'a'
item(1)=koala
item(2)=goanna
--------------------
select everything with at least two 'a' characters
item(0)=kangaroo
item(1)=koala
item(2)=goanna
--------------------
select everything with an 'oo'
item(0)=kangaroo
item(6)=bandicoot
--------------------
select everything with at least one 'z' character
--------------------

More Javascript coming soon. In the meantime, enjoy.

© Bruce M. Axtens, 2010