/*
	The fuzzy string matching concept provide a powerful way for comparing strings.
	This code provide a simple implementation of the fuzzy string matching technique.
	The function "fuzzymatch" included in this program perform a fuzzy comparaison 
	(fault tolerant comparaison) of two strings,the returned value is a percentage 
	that tells how closed are the strings that have been compared.

	Fuzzy strings comparaison can be useful in many applications.
	One of them is a string matching algorythm for a Chatbot.

	Also,the "fuzzymatch" algorythm implemented in this code is very quick and 
	precise as well.If you like this code,please vote for it or you can just 
	let me know what do you think of it.

	this code is copyrighted and has limited warranties.
	author: Gonzales Cenelia.
*/

#include  <windows.h>
#include  <iostream>
#include  <ctime>

#define NEON_GREEN 10
#define LIGHT_BLUE 11
#define LIGHT_RED 12
#define WHITE 15

#define WAIT(x) Sleep((long)(x));
#define SECOND 1000
using std::cout;
using std::endl;

float fuzzymatch( char *str, char *str2 );
int srchstr( const char *str, char c, int pos );
void sswap( char **str1, char **str2 );
void print_text( const char *text );
void select_color( void );
BOOL settextcolor( WORD color );
int TEXT_COLOR;


void main()
{
	/*
	   Testing the current fuzzy string matching algorithm
	   by using different strings. The algorithm used in the current code is particularly
	   suitable for usage in a spellchecker program, althought it can perfectly be use 
	   for other purpose.
	*/
	select_color();
	print_text("\n======================================================================\n");
	cout << "  This is a test of the current string matching algorithm,this test\n"
		 << "  will be performed by using all types of different strings.";
	print_text("\n======================================================================\n");
	WAIT( 0.6 * SECOND );
	print_text("\n\ntest started...\n");
	
	WAIT( 0.9 * SECOND );
	print_text("\ncorrect name: "); 
	cout << "John" << endl;
	print_text("misspelled name: "); 
	cout << "Jon" << endl;
	print_text("comparaison value: ");
	cout << fuzzymatch("John", "Jon") << endl;

	WAIT( 0.9 * SECOND );
	print_text("\nname1: ");
	cout << "Albert Einstein" << endl;
	print_text("name2: ");
	cout << "Isaac Newton" << endl;
	print_text("comparaison value: ");
	cout << fuzzymatch("Albert Einstein", "Isaac Newton") << endl;
	
	WAIT( 0.9 * SECOND );
	print_text("\nname3: ");
	cout << "Mariah" << endl;
	print_text("name4: ");
	cout << "Maria" << endl;
	print_text("comparaison value: ");
	cout << fuzzymatch("Mariah", "Maria") << endl;
	
	WAIT( 0.9 * SECOND );
	print_text("\nword1: ");
	cout << "New York" << endl;
	print_text("word2: ");
	cout << "New Jersey" << endl;
	print_text("comparaison value: ");
	cout << fuzzymatch("New York", "New Jersey") << endl;
	
	WAIT( 0.9 * SECOND );
	print_text("\nstr1: ");
	cout << "how do you do?" << endl;
	print_text("str2: ");
	cout << "how are you?" << endl;
	print_text("comparaison value: ");
	cout << fuzzymatch( "how do you do?", "how are you?" ) << endl;

	// testing the search function with longer strings
	WAIT( 0.9 * SECOND );
	print_text("\n\nstr3: ");
	cout << "The winter will be there pretty soon and at that moment" << endl
		 << "there will be snow outside and the tempature will get colder." << endl;
	print_text("\nstr4: ");
	cout << "When the winter comes,there will be snow outside"
		 << "\nand the tempature will eventualy get colder." << endl;
	print_text("comparaison value: ");
	cout << fuzzymatch( "The winter will be there pretty soon and at that moment" 
		                "there will be snow outside and the tempature will get colder.",
						"When the winter comes,there will be snow outside"
					    "and the tempature will eventualy get colder." ) << " ";
	
	settextcolor(TEXT_COLOR);
}

// search a character inside a string
int srchstr( const char *str, char c, int pos )
{
	for( int i = pos, cur; ( cur = str[i] ) != 0; i++ )
	{
		if( cur == c ) return i;
	}
	return -1;
}

// template function for 
// swaping two variables
template
void swap( T &a, T &b )
{
	T temp = a;
	a = b;
	b = temp;
}

// search for a number inside an array
// if that number is found,the function
// returns true otherwise it returns false
bool is_in( int *array, int index, int val )
{
	for(int i=0; i <= index; i++)
	{
		if(array[i] == val) return true;
	}
	return false;
}

////////////////////////////////////////////////////////////////////////////////////////
// Performs a fuzzy comparaison of two strings. Actualy,this comparaison is based only
// on the syntaxe of the two strings. The returned value for that function is a value
// between zero and one,the closer the returned value is to 1,the closer
// are the strings syntacticaly. Notice: because most words can be usualy separated
// into different parts (prefix, suffix and roots) therefore, words that are closed
// syntacticaly might in some cases share some morphological relationship.
///////////////////////////////////////////////////////////////////////////////////////
float fuzzymatch( char *str, char *str2 )
{
	int len = strlen(str), len2 = strlen(str2);
	// if the length of the strings are not the same
	// then we might need to swap them to make sure that 
	// the first string is the longest one
	if( len2 > len ) 
	{
		swap( str, str2 );
		swap( len, len2 );
	}

	// variable for holding the total penalty
	// for a given charcater search
	float cost = 0.0f;

	// variable for holding the total number
	// of chacters found during the fuzzy search
	// that variable is incremented with a value
	// between 0 and 1 each time a character is found
	float hit = 0.0f;

	// this variable will be use for holding the position
	// of the current character search
	int pos = 0;

	// when a character is not found at the expected position
	// there should be a penalty and the penalty value will be 
	// directly proportional to the distance to which 
	// that character was found.
	// This distance is simply calculated by using the following formula.
	// distance = abs(found_position - expected_position)
	
	// seting the minimum value for a penalty
	float min_cost = (float)1/len;

	// declaring the "hit_pos" array
	// that array will be use to avoid
	// duplication during the search
	int *hit_pos = new int[len];

	// looping over the first string: "str"
	for( int i = 0; i < len; i++ )
	{
		// search for the current character
		// belonging to the first string
		// inside the second string
		pos = srchstr( str2, str[i], 0 );

		// if the current character was already found 
		// at that same position makes a new search 
		// by starting at a new postion
		if( is_in( hit_pos, i, pos ))
		{
			int j = pos + 1;
			// continues the search till we found
			// a chacaracter that is not already
			// in the hit_pos array
			while( j < len2 )
			{
				pos = srchstr( str2, str[i], ++j );
				if( pos != -1 && !is_in( hit_pos, i, j )) break;
			}
		}

		// if a character was found during the previous character search,
		// then we need to make some variable updating. Otherwise,the search will 
		// continue with the next character of the first string: "str"
		if( pos != -1 )
		{
			// saving the current position to the hit_pos array
			// so that we do not reuse characters found in this position
			// later while performing the search
			hit_pos[i] = pos;

			// calculating distance
			// expected position: i
			// found position: pos
			int distance = abs(pos - i);

			// calculating penalty value
			cost = distance * min_cost;

			// updating the number of characters found
			hit += 1 - cost;
		}
	}
	delete hit_pos;
	return hit/len;
}

// sets the text color
BOOL settextcolor( WORD color )
{
	HANDLE hStdout = GetStdHandle(STD_OUTPUT_HANDLE); 
	BOOL rt = SetConsoleTextAttribute( hStdout, color );
	return rt;
}

// prints a text on the screen
// the text color will be the color 
// previously selected with the function
// "select_color"
void print_text( const char *text ) {
	settextcolor(TEXT_COLOR);
	cout << text;
	settextcolor(WHITE);
}

// selects a color randomly and 
// saves the colors value into the 
// "TEXT_COLOR" variable
void select_color( void ) {
	srand( ( unsigned )time( NULL ) );
	int selection = rand() % 3;
	switch(selection) {
	case 0:
		TEXT_COLOR = NEON_GREEN;
		break;
	case 1:
		TEXT_COLOR = LIGHT_BLUE;
		break;
	case 2:
		TEXT_COLOR = LIGHT_RED;
		break;
	}
}