[ANN] Wildcard string matching / globbing
axtens
wildcard-string-matching.html> is a prototype extension to the String
class which provides for ? and * globbing. Yes, I know that "everyone"
uses regular expressions but it's there if you need it.
Kind regards,
Bruce.
Evertjan.
No reason to multipost.
--
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)
Scott Sauyet
Congratulations on starting to learn Javascript. It's a very
interesting language.
I posted a version of your code at
<http://scott.sauyet.com/Javascript/Test/2010-11-30a/>
It uses a unit test framework rather than logging results.
Several points:
- There is significant controversy over updating the prototypes of
built-in objects. If you haven't done so already, you should
investigate that arguments for and against it before deciding to do
so. Note that enhancing the prototype of String is less of an issue
for many than enhancing the prototype of Object or Array.
- The code somehow *looks* as if it were ported from C. There is
nothing exactly wrong with that, but JS has its own idioms, and is
often much more expressive than its syntactic cousins.
- An alternate approach you might consider for the same problem is
generating a regular expression from the pattern and then using that
for testing. I knocked one off that is probably incomplete, but
demonstrates the idea and passes the same set of tests. You can see
it at
<http://scott.sauyet.com/Javascript/Test/2010-11-30b/>
This is the basic concept, though:
var specialChars = "\\{}+.():-|^$";
var makeRegex = function(pattern) {
pattern = pattern.split("");
var i, len = pattern.length;
for (i = 0; i < len; i++) {
var character = pattern[i];
if(specialChars.indexOf(character) > -1) {
pattern[i] = "\\" + character;
} else if (character === "?") {
pattern[i] = ".";
} else if (character === "*") {
pattern[i] = ".*";
}
}
return new RegExp("^" + pattern.join("") + "$");
};
(I'm not sure what Evertjan meant. FWIW, to me it seems fine to blog
about something and then post a link to that blog post here.)
Cheers,
--
Scott
Thomas 'PointedEars' Lahn
> Just posted on <http://codeaholic.blogspot.com/2010/11/javascript-
> wildcard-string-matching.html> is a prototype extension to the String
> class
There is no String class; you are dealing with programming languages here
that support only prototype-based inheritance.
> which provides for ? and * globbing. Yes, I know that "everyone"
> uses regular expressions but it's there if you need it.
You should have posted your source code as well. Here it is, verbatim:
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 );
}
I have read that you are new to the languages, and that you wondered whether
there were better ways to do it. Consider this:
String.prototype.matchesWild = (function() {
var
map = {
"*": ".*",
"?": "."
},
fEscape = function(m, paren1) {
if (paren1)
{
return map[paren1];
}
return "\\" + m;
},
wildcardEscape = function(pattern) {
return pattern.replace(/([*?])|[\]\\^$+.(){}[]/g, fEscape);
};
return function(wildcard) {
return (new RegExp(wildcardEscape(wildcard))).test(this);
};
}());
/* true */
"foobar".matchesWild("*ba*");
/* false */
"foobar".matchesWild("*az*");
BTW, do not use the proprietary String.prototype.substr() method; use the
standards-compliant String.prototype.substring() instead.
PointedEars
--
realism: HTML 4.01 Strict
evangelism: XHTML 1.0 Strict
madness: XHTML 1.1 as application/xhtml+xml
-- Bjoern Hoehrmann
Thomas 'PointedEars' Lahn
> On Nov 29, 10:44 pm, axtens <bruce.axt...@gmail.com> wrote:
>> Just posted on <http://codeaholic.blogspot.com/2010/11/javascript-
>> wildcard-string-matching.html> is a prototype extension to the String
>> class which provides for ? and * globbing. Yes, I know that "everyone"
>> uses regular expressions but it's there if you need it.
>
> Congratulations on starting to learn Javascript. It's a very
> interesting language.
OP: There is no(t one) language named "Javascript". There is one named
(Netscape/Mozilla.org) JavaScript, another named (Microsoft) JScript, aso.,
all of which are very similar because they are implementations of the same
ECMAScript Language Specification. Some people do not know any better, or
choose to be ignorant about this.
<http://PointedEars.de/es-matrix>
PointedEars
--
Prototype.js was written by people who don't know javascript for people
who don't know javascript. People who don't know javascript are not
the best source of advice on designing systems that use javascript.
-- Richard Cornford, cljs, <f806at$ail$1$8300...@news.demon.co.uk>
John G Harris
What on earth is globbing?
One dictionary says that a glob is 'a round mass of a thick liquid or a
sticky substance'. Sounds like javascript all right.
John
--
John Harris
Stefan Weiss
> On Mon, 29 Nov 2010 at 19:44:37, in comp.lang.javascript, axtens wrote:
>>Just posted on <http://codeaholic.blogspot.com/2010/11/javascript-
>>wildcard-string-matching.html> is a prototype extension to the String
>>class which provides for ? and * globbing. Yes, I know that "everyone"
>>uses regular expressions but it's there if you need it.
>
> What on earth is globbing?
http://www.science.uva.nl/~mes/jargon/g/glob.html
http://en.wikipedia.org/wiki/Glob_(programming)
(not to be confused with the <http://kingtet.com/images/blob.jpg>)
The "globbing" type of pattern matching is usually used in connection
with file names and paths (as in "ls *.txt"). Some languages have
support for globbing built in, for example Perl via the "glob" function
and the "<*.c>" operator. Now that JS is beginning to become relevant as
a general scripting language, a method to support globbing could come in
handy.
--
stefan
Tim Down
wrote:
> BTW, do not use the proprietary String.prototype.substr() method; use the
> standards-compliant String.prototype.substring() instead.
Or String.prototype.slice(), which is more flexible.
Tim
Thomas 'PointedEars' Lahn
> Thomas 'PointedEars' Lahn wrote:
>> BTW, do not use the proprietary String.prototype.substr() method; use the
>> standards-compliant String.prototype.substring() instead.
>
> Or String.prototype.slice(), which is more flexible.
Unfortunately, the additional flexibility that slice() provides per
Specification is not interoperable. In particular, JScript is buggy with
negative values.
PointedEars
--
Anyone who slaps a 'this page is best viewed with Browser X' label on
a Web page appears to be yearning for the bad old days, before the Web,
when you had very little chance of reading a document written on another
computer, another word processor, or another network. -- Tim Berners-Lee
Tim Down
wrote:
> Tim Down wrote:
> > Thomas 'PointedEars' Lahn wrote:
> >> BTW, do not use the proprietary String.prototype.substr() method; use the
> >> standards-compliant String.prototype.substring() instead.
>
> > Or String.prototype.slice(), which is more flexible.
>
> Unfortunately, the additional flexibility that slice() provides per
> Specification is not interoperable. In particular, JScript is buggy with
> negative values.
It is? Which version, and what is/are the bug(s)?
Tim
John G Harris
wrote:
So several languages have a function called glob. That doesn't say what
the OP's function does in javascript; neither does the OP, nor does the
web page it links to.
I suppose it's standard practice for API's to have no documentation :-(
John
--
John Harris
Scott Sauyet
> On Tue, 30 Nov 2010 at 21:50:43, in comp.lang.javascript, Stefan Weiss
> wrote:
>
>> On 30/11/10 21:00, John G Harris wrote:
>>> What on earth is globbing?
>
>> http://www.science.uva.nl/~mes/jargon/g/glob.html
>> http://en.wikipedia.org/wiki/Glob_(programming)
> So several languages have a function called glob. That doesn't say what
> the OP's function does in javascript; neither does the OP, nor does the
> web page it links to.
>
> I suppose it's standard practice for API's to have no documentation :-(
The first two paragraphs of the blog entry linked to by the OP read
| 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.
Granted, it might be a transgression of Netiquette rules to not repeat
that information when posting to USENET, but I think it's a minor
one. Was it really not clear what the OP was presenting?
> I suppose it's standard practice for API's to have no documentation :-(
The OP also mentioned in the blog entry that he was quite new to JS.
I thought about this as more of a learning exercise than a fully-
developed public API.
-- Scott
Thomas 'PointedEars' Lahn
> Thomas 'PointedEars' Lahn wrote:
>> Tim Down wrote:
>> > Thomas 'PointedEars' Lahn wrote:
>> >> BTW, do not use the proprietary String.prototype.substr() method; use
>> >> the standards-compliant String.prototype.substring() instead.
>>
>> > Or String.prototype.slice(), which is more flexible.
>>
>> Unfortunately, the additional flexibility that slice() provides per
>> Specification is not interoperable. In particular, JScript is buggy with
>> negative values.
>
> It is? Which version, and what is/are the bug(s)?
Apparently I was wrong. The next revision of the ECMAScript Support Matrix
(which now contains information about such differences as determined by
tests, and which I hope to release soon¹) says that it is
String.prototype.substr() which does not support negative values in JScript
(any version from 3.0 to 5.8.x). Example:
/*
* "X";
* should be "V" per ES, as in V8, JavaScript, JSCore, Opera, and KJS
*/
"XV".substr(-1, 1)
This is not a bug but only implementation-specific behavior, because the
corresponding section in the ECMAScript Specification are informative, not
normative (hence my calling this method "proprietary" for short).
I can confirm this for IE 8.0 on Windows 7 (at the office) and IE 6 on Wine
98 (at home, now). I could not produce a problem with
String.prototype.slice() there.
_____
¹ see <http://PointedEars.de/es-matrix>
John G Harris
wrote:
>John G Harris wrote:
>> On Tue, 30 Nov 2010 at 21:50:43, in comp.lang.javascript, Stefan Weiss
>> wrote:
>>
>>> On 30/11/10 21:00, John G Harris wrote:
>>>> What on earth is globbing?
>>
>>> http://www.science.uva.nl/~mes/jargon/g/glob.html
>>> http://en.wikipedia.org/wiki/Glob_(programming)
>> [ extra elucidation elided :-) ]
>> So several languages have a function called glob. That doesn't say what
>> the OP's function does in javascript; neither does the OP, nor does the
>> web page it links to.
>>
>> I suppose it's standard practice for API's to have no documentation :-(
>
>The first two paragraphs of the blog entry linked to by the OP read
>
>| 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.
That's not a description. Can the parameter be an object; what if it is
null; what wildcard characters can be used; is there a limit on string
length; is it executed in linear time; etc, etc ?
And Jack Handy's write-up was no better.
>Granted, it might be a transgression of Netiquette rules to not repeat
>that information when posting to USENET, but I think it's a minor
>one.
Some people use news readers. Articles can be downloaded then read
offline, e.g while on the train. Links are not helpful.
>Was it really not clear what the OP was presenting?
It was really not clear.
>> I suppose it's standard practice for API's to have no documentation :-(
>
>The OP also mentioned in the blog entry that he was quite new to JS.
>I thought about this as more of a learning exercise than a fully-
>developed public API.
He is a full time programmer, so should know better.
Notice also that his subject started with [ANN].
John
--
John Harris
Scott Sauyet
> On Wed, 1 Dec 2010 at 11:59:25, in comp.lang.javascript, Scott Sauyet
> wrote:
>> John G Harris wrote:
>>> I suppose it's standard practice for API's to have no documentation :-(
>
>> The first two paragraphs of the blog entry linked to by the OP read
>
> That's not a description. Can the parameter be an object; what if it is
> null; what wildcard characters can be used; is there a limit on string
> length; is it executed in linear time; etc, etc ?
No, it's not a description. I was not expecting such, though.
Obviously you were, and perhaps, since the subject was prefixed with
"ANN:", I should have expected it too. (At work, I'm stuck with
Google Groups, which ever-so-helpfully removes this prefix -- uggh!)
> And Jack Handy's write-up was no better.
I never got that far, as it was immediately clear to me what he was
discussing. I looked superficially at his code, noted that he was a
newbie, and thought about what might make a cleaner implementation.
>> Granted, it might be a transgression of Netiquette rules to not repeat
>> that information when posting to USENET, but I think it's a minor
>> one.
>
> Some people use news readers. Articles can be downloaded then read
> offline, e.g while on the train. Links are not helpful.
That's why I called it a transgression. I'm guessing that the number
of people reading news without simultaneous access to a browser has
fallen sharply in the last ten years, though. We have to balance
that guideline against the one regarding wastes of bandwidth.
>> Was it really not clear what the OP was presenting?
>
> It was really not clear.
Okay. I'm surprised. It seems to me that event the most junior
developers I work with and even most web designers naturally
understand globbing. But maybe my experience is limited by having
worked over my career mostly with people familiar with Unix
conventions.
>>> I suppose it's standard practice for API's to have no documentation :-(
>
>> The OP also mentioned in the blog entry that he was quite new to JS.
>> I thought about this as more of a learning exercise than a fully-
>> developed public API.
>
> He is a full time programmer, so should know better.
I don't agree. I think there is a significant difference between
announcing an implementation of an algorithm and announcing a fully-
developed public library that employs said algorithm. This seems much
more of the former to me.
> Notice also that his subject started with [ANN].
I had missed that, and it does put a different spin on things. The
biggest issue it raises for me, though, is that he started a
discussion and didn't seem to stick around for the followup. I don't
know if that is listed in any Netiquette guidelines, but it raises a
red flag for me.
-- Scott
Scott Sauyet
> Okay. I'm surprised. It seems to me that event the most junior
s/event/even