/******** Problem 3--Wild Cards ***************************************
 The ACM coaches guide said that this would be the program that
 separates those who get six from those who get five, indicating that
 they think this is the hardest one.  I disagree with them; I think
 problems 2 and 5 were both harder than this one.  What could really
 throw you on this one was if you didn't see how to do it right away
 and tried some really nasty search method through the patterns and
 the files.  This is a simple recursion problem; do the first characters
 match?  If so, then try matching the rest of the strings.
 The other thing to watch out for is that while the limit on the string
 length was 20, there was no limit given on either the number of files
 or the number of patterns.  So, this program reads these things into
 a linked list with no hardcoded maximum size.
 **********************************************************************/

#include <fstream>
#include <cstdlib>
#include <cstring>
using namespace std;

class list21;

class list21 {  // linked list of strings
 public:
  char str[21]; // 20 chars for the string; 1 for the null
  list21 *next;
  list21 (char *s);
  ~list21 ();
};

int main (int argc, char **argv);
int match (char *F, char *P);
list21 * readlist ();
void freelist (list21 *l);
void printmatches (list21 *Files, list21 *Patterns);

ifstream in ("prob3.in");
ofstream out ("prob3.out");

/**** list21 constructor **********************************************/

list21::list21 (char *s) {
 strcpy (str,s);
 next = NULL;
}

/**** list21 destructor ***********************************************/
list21::~list21 () {
 if (next != NULL) delete next;
}

/****** main **********************************************************
 This program reads a list of filenames into a linked list, then a list
 of patterns into another linked list, and prints out which files match
 which patterns.
 *********************************************************************/

int main (int argc, char **argv) {

  list21 *Files, *Patterns;  // linked lists

 Files = readlist ();       // read in the information
 Patterns = readlist ();
 printmatches (Files,Patterns); // print the matches
 delete Files;
 delete Patterns;
 return EXIT_SUCCESS;
}

/**** match ***********************************************************
 match accepts a filename string and a pattern string and returns a
 boolean value indicating whether the file matches that pattern.  It
 tries matching the first character of the pattern.  If it succeeds, it
 uses recursion to match the rest of the pattern.
 **********************************************************************/

int match (char *F, char *P) {

 if (P[0]==0)     // if the pattern is the empty string,
  return F[0]==0;    // it can only match the empty string.
 if (P[0]=='?')  {// if the first character of the pattern is ?
  if (F[0]==0)   // it can't match the empty string,
   return 0;        // but it can match every other character,
              // so that we only need check if the rest of the
  return match (&F[1],&P[1]);  // strings match.
 }
 if (P[0]=='*') {  // if the first character of the pattern is *
  for (int i=0;;i++) { // matching the * with 0, 1, 2, ... characters
   if (match (&F[i],&P[1])) return 1;
                   // and try matching the rest of the
   if (F[i]==0) break;
  }
  return 0;         // pattern with the rest of the file
 }                  // stopping when we get a match, or when we've
                  // tried matching the whole string to the *
 if (P[0]==F[0])   // if the first character is not a wild card,
  return match (&F[1],&P[1]); // it has to match the first character
                // of the filename for us to check if the rest
 return 0;           // of the patterns match
}

/******* readlist *****************************************************
 readlist reads a bunch of strings into a linked list and returns a
 pointer to that linked list.  The function stops reading when it
 encounters a $.
 **********************************************************************/

list21 * readlist () {

  list21 *l,     //the linked list to be returned
         *p, *q; // temporary variables for building the list
  char s[21];  // temporary storage for reading in the string

 for (l=q=NULL;;) {
  in.getline(s,sizeof s);
  if (strcmp (s,"$")==0) break;   /* read strings until $ is found */
  p = new list21 (s);
  if (l==NULL)                   /* add it to the appropriate place */
   l = p;                        /* in the list */
  else
   q->next = p;
  q = p;
 }
 return l;
}


/****** printmatches **************************************************
 printmatches goes through the linked lists of filenames and patterns
 and prints which files match which patterns in the format specified in
 the problem description.  This is done simply with nested loops.
 **********************************************************************/

void printmatches (list21 *Files, list21 *Patterns) {

  list21 *F; // loop variable for filenames

 for (int cs=0;Patterns != NULL;Patterns=Patterns->next) {
                          // loop through patterns
  out << "Case " << ++cs << ". Pattern " << Patterns->str
      << " matches..." <<endl;
  for (F=Files;F != NULL;F=F->next)    // loop through files
   if (match (F->str,Patterns->str))   // if they match, print it
    out << "   " << F->str << endl;
  out << endl;
 }
}