/* pattern_match.cc */

#include "pattern_match.h"

bool pmatch( cstring , int, int, cstring , int, int );
int next_pos( cstring , cstring , const int, const int );

bool pattern_match( cstring s, cstring pattern ) {
  int left_spos = 0;
  int right_spos = s.length() - 1;
  int left_ppos = 0;
  int right_ppos = pattern.length() - 1;
  return pmatch( s, left_spos, right_spos, pattern, left_ppos, right_ppos );
}

bool pmatch( cstring s, int left_spos, int right_spos,
	     cstring pattern, int left_ppos, int right_ppos ) {
  /*  cerr << "TRYING TO MATCH \"" << s( left_spos, right_spos ) << "\" to \""
       << pattern( left_ppos, right_ppos ) << "\"\n"; */

  while( left_ppos <= right_ppos ) {
    /* SCAN FROM LEFT */
    do {
      char c = pattern[left_ppos];
      if( c == '*' ) break;
      if( c == '?' ) { left_ppos++; left_spos++; }
      else if( pattern[left_ppos++] != s[left_spos++] ) return false;
    }  while( left_ppos <= right_ppos );
    
    /* SCAN FROM RIGHT */
    do {
      char c = pattern[right_ppos];
      if( c == '*' ) if( left_ppos >= right_ppos ) return true; else break;
      if( c == '?' ) { right_ppos--; right_spos--; }
      else if( pattern[right_ppos--] != s[right_spos--] ) return false;
    } while( left_ppos >= 0 && right_ppos >=0 && left_ppos <= right_ppos );

    if( left_ppos < right_ppos ) {
      /* recurse to handle multiple '*'s */
      /* move over leftmost '*'s */
      while( pattern[left_ppos] == '*' ) left_ppos++;
      
      int rss = left_ppos; /* right limit of substring between 
			      left_ppos and next asterisk */
      while( pattern[rss + 1] != '*' ) rss++;
      const string sub_str = pattern(left_ppos, rss );
      int ss_lenmin1 = rss - left_ppos; /* substring length - 1 */
      
      /* for each occurence of substring in s */
      int lscan = next_pos( s, sub_str, left_spos, right_spos );
      while( lscan >= 0 ) {
	if( pmatch( s, lscan + ss_lenmin1, right_spos,
		    pattern, rss + 1, right_ppos ) ) return true;
	lscan = next_pos( s, sub_str, lscan + 1, right_spos );
      }
      return false;
    }
  }
  return left_spos >= right_spos;
}

int next_pos( cstring s, cstring sub_pat, 
	      const int start, const int end ) {
  /* cerr << "sub_pat = \"" << sub_pat << "\", string = \"" << s 
          << "\", substring = \"" << s( start, end ) << "\"\n"; */
       

  int len = sub_pat.length();
  for( int i = 0 ; i < end - start + 1; i++ ) {
    // cerr << "substring = \"" << s( i + start, end ) << "\n";
    if( sub_pat[0] == '?' || sub_pat[0] == s[start + i] ) {
     int j;
      for( j = 1 ; j < len ; j++ ) {
	// cerr << "checking = \"" << s( i + start, i + j + start ) << "\n";
	if( sub_pat[j] != '?' && sub_pat[j] != s[start + i + j] ) break;
      }
      if( j == len ) return start + i;
    }
  }
  return -1;
}
