Dr. Dobb's Journal - September 2008 - (Page 38)

d09kraus_p2db 7/14/08 11:00 AM Page 38 State of the Art MATCHING WILDCARDS: AN ALGORITHM Listing One // This function compares text strings, one of which can // have wildcards ("*"). BOOL GeneralTextCompare( char * pTameText, // A string without wildcards char * pWildText, // A (potentially) corresponding string with wildcards BOOL bCaseSensitive = FALSE, // By default, match on "X" vs "x" char cAltTerminator = '\0' // For function names, for example, you can stop at the first "(" ) { BOOL bMatch = TRUE; char * pAfterLastWild = NULL; // Location after last "*", if we've encountered one char t, w; // Walk the text strings one character at a time. while (1) { t = *pTameText; w = *pWildText; // How do you match a unique text string? if (!t || t == cAltTerminator) { // Easy: unique up on it! if (!w || w == cAltTerminator) { break; // "x" matches "x" } else if (w == '*') { pWildText++; continue; // "x*" matches "x" or "xy" } bMatch = FALSE; break; // "x" doesn't match "xy" } else { if (!bCaseSensitive) { // Lowercase the characters to be compared. if (t >= 'A' && t = 'A' && w <= 'Z') { w += ('a' - 'A'); } } // How do you match a tame text string? if (t != w) { // The tame way: unique up on it! if (w == '*') { pAfterLastWild = ++pWildText; continue; // "*y" matches "xy" } else if (pAfterLastWild) { pWildText = pAfterLastWild; w = *pWildText; if (!w || w == cAltTerminator) { break; // "*" matches "x" } else if (t == w) { pWildText++; } pTameText++; continue; // "*sip*" matches "mississippi" } else { bMatch = FALSE; break; } } } pTameText++; pWildText++; } return bMatch; } // "x" doesn't match "y" nonmatching characters will be either a wildcard character, or it won’t. If it is, then a pointer to the next character after the wildcard is saved. Otherwise, the strings don’t match, unless such a pointer has already been saved during earlier processing, meaning the algorithm has encountered a wildcard character already. When that is the case, processing continues from the character after that previous wildcard character, which is compared with the instant character from the tame string. Then the following occurs: • The string termination condition is checked, this time for the wild string, to ensure that it actually has additional valid characters to compare at this point. • If there are no valid characters, then there is nothing more to do. • Otherwise, one of two things can happen: 1. If the instant characters from the tame and wild strings now match, the algorithm continues by comparing the next characters from each string; or 2. if those characters don’t match, the algorithm continues by comparing the same instant character from the wild string with the next character from the tame string. After the big else clause, if the core code has not already continued from the top of the loop, the algorithm moves on to select the next pair of characters from each string, then it returns to the top of the loop to compare them. If you use the debugger to check the algorithm’s ability to compare the text string Mississippi against *sip*, this is what you’ll see looking at the Watch window view associated with the tame and wild string pointers. The algorithm compares the left-most characters of each string, moving through each string one character at a time, such that the debugger shows this representation of the two string pointers as you’re stepping through: mississippi mississippi ississippi ssissippi sissippi sissippi issippi ssippi ssippi sippi sippi ippi ppi pi i *sip* sip* sip* sip* ip* sip* ip* p* sip* ip* sip* ip* p* * * 38 Dr. Dobb’s Journal l www.ddj.com l September 2008 http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - September 2008

Dr. Dobb's Journal - September 2008 Contents Friday Night Fish Fry Alia Vox Developer Diaries Developer’s Notebook A Conversation With Erik Demaine Application Lifecycle Management Meets Model-Driven Development Building a Robust Development Environment Real Users Really Matter Matching Wildcards: An Algorithm The Android Mobile Phone Platform Managing Application Thread Use Signalling Integer Overflows in Java .NET Development & the IBM WebSphere Portal Server The Agile Edge Effective Concurrency Swaine’s Flames

Dr. Dobb's Journal - September 2008

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.