/* pattern.c
 * Program to demonstrate pattern searching.
 * Written by : Vikram R. Bhat <vrb1001@yahoo.co.in>
 *
 * Program to demonstrate pattern-searching of strings.
 * This program interactively builds a list of words and
 * searches for words in the list that match a specified pattern.
 * The pattern can include wildcard chars * and ?.
 * Eg : The query s* gives the words in the list which start with s.
 * The program uses a command-interpreter style interface for interaction
 * with the user. Usage of the program is shown in the Usage() function.
 * The PatternSearch() function is the heart of the program. It returns 1 
 * if a string pattern matches another in input.
 * The function has quite a few bugs I've not been able to put right. If
 * somebody can, please let me know.
*/
 
#include <stdio.h>
#include <string.h>
 
#define INPUT 1
#define QUERY 2
#define MAXSIZE 20
#define MAXCOL 30
 
void Usage( void );
int PatternSearch( char *str1, char *str2 );
char* StrUpper( const char *str );
 
int main()
{
 	char str[MAXSIZE][MAXCOL],input[MAXCOL];
 	int mode = INPUT;
 	int count = -1,i, m_count;
 
 	Usage();
 
 	while(1)
 	{
		if( mode == INPUT )
		{
			printf("\n%d %s in list", count+1, count == 0 ? "item":"items" );
			printf("\n\nINPUT >");
		}
		else
			printf("\n\nQUERY > ");
 
		fgets( input, MAXCOL, stdin );
			// fgets retains the newline entered. Replace it with null char.
		input[ strlen(input) - 1 ] = '\0';
 
		if( !strcmp( StrUpper( input ), "$INPUT" ))
		{
			mode = INPUT;
			printf("\n[ Enter words to add to list ]");
		}
		else if( !strcmp( StrUpper( input ), "$QUERY" ))
		{
   			mode = QUERY;
   			printf("\n[ Enter pattern ( may contain wildcards * and ? ) to search in list. ]");
   		}
   		else if( !strcmp( StrUpper( input ), "$CLS" ))
   			system("CLS");
   		else if( !strcmp( StrUpper( input ), "$HELP" ))
   			Usage();
		else if( !strcmp( StrUpper( input ), "$LIST" ))
		{
			for( i = 0; i<=count; i++ )
				printf("\n%s", str[i] );
		}
 
		else if( !strcmp( StrUpper( input ), "$EXIT" ))
			break;
 
		else
		{
			if( mode == INPUT )
			{
				if( count < MAXSIZE - 1 )
					strcpy( str[++count], input );
				else
					printf("\nSorry, cannot add.List Full");
			}
			else
			{
				m_count = 0;
				for( i=0; i<=count; i++ )
				{
     				if( PatternSearch( str[i], input ))
     				{
     					m_count++;
     					printf("\n%s", str[i] );
     				}
				}
				printf("\n%d %s found.", m_count, m_count == 1 ? "match": "matches" );
			}
		}
 	}
 
	return 0;
} // End of main
 
	// How to use the program
void Usage( void )
{
	printf("Valid commands are ( case-insensitive ):");
 	printf("\n\n $INPUT : Switch to input mode. Any input word\
  			\n\texcept commands will be added to list");
  	printf("\n\n $QUERY : Switch to query mode. The input word\
   		\n\tis searched for pattern-match in the built list. Input\
     	\n\tword can include the wildcards ? and *");
   	printf("\n\n $LIST  : List current words in list");
    printf("\n\n $CLS   : Clear Screen");
    printf("\n\n $HELP  : Display this message");
    printf("\n\n $EXIT  : Exit this program\n");
}
 
	// Searches for pattern match of str2( can contain wildcards * and ? )
 	// within str1
int PatternSearch( char *str1, char *str2 )
{
	int i,j, flag, asterisk_flag;
	i = j = asterisk_flag = 0;
	flag = 1;
 
	while( str1[i] != '\0')
	{
 
		if(str2[j] == '\0')		// if str2 has ended, check
		{						// for last char match
			if( str2[j-1] == '*' )
				break;			// correct matching
			else if( str2[j-1] != str1[i-1] )
			{
				flag = 0;
				break;
			}
		}
		if( asterisk_flag )		// '*' found in str2, search for
		{						// next char of str2 in str1
			flag = 0;			// Assume no match
   			if( str1[i] == str2[j] )
   			{
   				j++;			// Move str2 char
       			asterisk_flag = 0;
       			flag = 1;		// Match found
			}
			i++;
		}
 
		else
		{
			if( str2[j] == '?' )	// Don't compare current chars
			{
				i++;
				j++;
			}
			else if( str2[j] == '*' )	// Search next char of str2
			{							// in str1 ignoring anything
				j++;					// in between
				asterisk_flag = 1;
			}
			else if( str2[j] == str1[i] )
			{
				i++;
				j++;
			}
			else				// Matching failed
				return 0;
 
    	}	// End of main 'else'
 
    }	// End of while
 
    if( flag )
    	return 1;
    else			// str1 ended before a matching char following *
    	return 0;	// in str2 was found
}	// End of patternsearch
 
	// Returns string in upper case
char* StrUpper( const char *str )
{
	int i;
	char *str2;
	str2 = ( char* ) malloc( sizeof( char)* strlen(str) + 1);
 
	strcpy( str2, str );
 
	for( i = 0; str[i] != '\0'; i++ )
	{
		if( islower( str2[i] ))
   			str2[i]=  toupper( str2[i] );
   	}
   	return str2;
}