/* Wildcard.c  by Frank J. Perricone
     Matches (recursively) wildcards * and ? (arbitrary number of them)

  This program was written solely to test my algorithm for wildcard matching.
  It is of no use in and of itself, so I release it as source code only to
  the public domain, unless someone has copyrighted this code before, in
  which case, my apologies, no offense intended.
*/

#include <stdio.h>
#include <stdlib.h>

#define TRUE  1
#define FALSE 0

/* Prototypes */
int wildcardmatch(char *, char *);
int wcm(char *,char *);

int main(int argc, char *argv[]) {
  if (argc!=3) { /* we need two params to compare */
      fprintf(stderr,"Usage: WILDCARD pattern string\n");
      return 20;
      }
  if (wildcardmatch(argv[1],argv[2]))
      printf("%s matches %s.\n",argv[1],argv[2]);
      else
      printf("%s does not match %s.\n",argv[1],argv[2]);
  return 0;
  }

int wildcardmatch(char *pattern, char *string) {
/* Strip doubled asterisks, then call wcm which is recursive
---- That is, this routine simply runs a preparation phase on the pattern,
---- stripping out double (or more) asterisks (which are really meaningless
---- and can be reduced to one asterisk) and then calls wcm, which does the
---- real work.
*/
  char newpat[256];   /* build the new stripped pattern in the buffer */
  int i=0;    /* counter in pattern */
  int j=0;    /* counter in newpat */
  while (pattern[i]!='\0') {  /* until we reach the end of the pattern */
    newpat[j]=pattern[i];     /* copy a character */
    if (pattern[i]=='*') {    /* if it was an asterisk, */
        i++;          /*   starting with the next character, */
        while (pattern[i]=='*')   /*   scan past all ensuing asterisks */
          i++;
        }
      else
        i++;          /*   else just go to the next character */
        j++;
        }
  newpat[j]='\0';         /* put end-string marker on newpat */
  return wcm(newpat,string);  /* now call wcm to do the real work */
  }

int wcm(char *pattern, char *string) {
/* Actually does matching; very recursive, especially if pattern[0]=='*'
---- The parameters are a pattern, which can contain an arbitrary number of
---- characters including wildcards, excepting that it has no doubled
---- asterisks.  The asterisk matches 0 or more characters.  The question mark
---- matches exactly one character.  wcm just returns TRUE or FALSE.
---- It does this by breaking up all possibilities into cases described below.
---- The order they are shown is important, as many of them assume (and
---- therefore don't test for) the fact that previous cases didn't apply.
*/
  if (pattern[0]=='\0' && string[0]=='\0')   /* both are null */
      return TRUE;
  if (pattern[0]=='\0')          /* pattern null but string isn't */
      return FALSE;
  if (pattern[0]=='*' && pattern[1]=='\0')   /* pattern just an asterisk */
      return TRUE;             /* (this is an optimization) */
  if (string[0]=='\0')           /* string null but pattern isn't */
      return FALSE;
  if (pattern[0]=='?')           /* pattern starts with ? */
      return wcm(&(pattern[1]),&(string[1]));  /* matches if the rest matches.. */
  if (pattern[0]=='*') {         /* the biggie: pattern begins with
                                    an asterisk but has more, and
                                    string isn't null... */
      while (string[0]!='\0') {        /* does it match if * matches 0 */
        if (wcm(&(pattern[1]),string)) /* chars of string?  If not, how */
            return TRUE;               /* about one?  Or two?  Keep */
          else                         /* trying until it does, or */
            string++;                  /* you run out of string... */
        }  /* if we get out, we tried all possibilities without success... */
      return FALSE;
      }
  if (pattern[0]==string[0])         /* normal, matching characters */
      return wcm(&(pattern[1]),&(string[1]));
  /* if we got this far -- normal, nonmatching characters */
  return FALSE;
  }