Author Topic: Wildcard string compare/search  (Read 1324 times)

Offline Kitty Hello

  • code monkey
  • Administrator
  • Prof. Inline
  • *******
  • Posts: 10661
  • here on my island the sea says 'hello'
    • View Profile
    • http://www.glbasic.com
Wildcard string compare/search
« on: 2016-Apr-22 »
Code: GLBasic [Select]

LOCAL pp% = WildcardTextCompare("abcdefg", "*d*g*") // returns "3" -> where the "d" is




// case sensitive!
IMPORT int WildcardTextCompare(const char*, const char*)


INLINE
// #NEED find first non* character match
//---------------------------------------------------------------//
// This function compares text strings, one of which can have wildcards ('*').
// http://www.drdobbs.com/architecture-and-design/matching-wildcards-an-algorithm/210200888
// GF: improved version
// returns 0..x -> position of first non wildcard character
//         -1   -> no match
//---------------------------------------------------------------//
int WildcardTextCompare(
        const char* pTameText,             // A string without wildcards
        const char* pWildText              // A (potentially) corresponding string with wildcards
        )
{
        const char* pOrigTame=pTameText;
        const char* pFirstMatch=NULL;
        int bMatch = TRUE;
        const char* pAfterLastWild = NULL; // The location after the last '*', if we’ve encountered one
        const char* pAfterLastTame = NULL; // The location in the tame string, from which we started after last wildcard
        char t, w;

        // Walk the text strings one character at a time.
        for(;;)
        {
                t = *pTameText;
                w = *pWildText;

                // How do you match a unique text string?
                if (!t)
                {
                        // Easy: unique up on it!
                        if (!w)
                        {
                                break;                                   // "x" matches "x"
                        }
                        else if (w == '*')
                        {
                                pWildText++;
                                continue;                           // "x*" matches "x" or "xy"
                        }
                        else if (pAfterLastTame)
                        {
                                if (!(*pAfterLastTame))
                                {
                                        bMatch = FALSE;
                                        break;
                                }
                                pTameText = pAfterLastTame++;
                                pWildText = pAfterLastWild;
                                continue;
                        }

                        bMatch = FALSE;
                        break;                                           // "x" doesn't match "xy"
                }
                else
                {
                        if(!pFirstMatch && w==t)
                                pFirstMatch = pTameText;
                        // How do you match a tame text string?
                        if (t != w)
                        {
                                // The tame way: unique up on it!
                                if (w == '*')
                                {
                                        pAfterLastWild = ++pWildText;
                                        pAfterLastTame = pTameText;
                                        w = *pWildText;

                                        if (!w )
                                        {
                                                break;                           // "*" matches "x"
                                        }
                                        continue;                           // "*y" matches "xy"
                                }
                                else if (pAfterLastWild)
                                {
                                        if (pAfterLastWild != pWildText)
                                        {
                                                pWildText = pAfterLastWild;


                                                w = *pWildText;

                                                if (t == w)
                                                {
                                                        pWildText++;
                                                }
                                        }
                                        pTameText++;
                                        continue;                           // "*sip*" matches "mississippi"
                                }
                                else
                                {
                                        bMatch = FALSE;
                                        break;                                   // "x" doesn't match "y"
                                }
                        }
                }

                pTameText++;
                pWildText++;
        }

        if(bMatch)
        {
                if(pFirstMatch)
                        return (int)(pFirstMatch-pOrigTame); // return position of first match
                return 0; // match at first character
        }
        return -1; // no match
}
ENDINLINE

 

Offline Ian Price

  • Administrator
  • Prof. Inline
  • *******
  • Posts: 4128
  • On the shoulders of giants.
    • View Profile
    • My Apps
Re: Wildcard string compare/search
« Reply #1 on: 2016-Apr-23 »
Very useful :)

Cheers Kitty
I came. I saw. I played.