/*	File:	pattern.cpp





			Christer Karlsson



This code implements pattern search of text files.

It uses both the Brute-force- and Boyer-Moore-

search algorithms.



    Allowed inputs are all printable characters.



*********************************************************************************

*************************** Print out of test cases *****************************

*********************************************************************************



Search of the ab-pattern



Brute-Force search Algorithm.

2402006 Comparisons were done.

The pattern was found at: 1199809

Boyer-Moore search Algorithm.

1315727 Comparisons were done.

The pattern was found at: 1199809

ImprovedBoyer-Moore search Algorithm.

850367 Comparisons were done.

The pattern was found at: 1199809



Search of the letter-pattern



Brute-Force search Algorithm.

1181177 Comparisons were done.

The pattern was found at: 1159856

Boyer-Moore search Algorithm.

182139 Comparisons were done.

The pattern was found at: 1159856

ImprovedBoyer-Moore search Algorithm.

177690 Comparisons were done.

The pattern was found at: 1159856



*********************************************************************************/



#include <iostream>

#include <fstream>

#include <vector>

#include <cstdlib>



using namespace std;





// User defined functions

void error (char* s, int s2)

{

    cerr << s << " " << s2 << "\n";

    exit(1);

}



void error (char* s, const char* s2 = "")

{

    cerr << s << " " << s2 << "\n";

    exit(1);

}

/* Had to define two different readFile

   functions as the first one does not

   take whitespaces.  */

void readFile1(vector<char>& v, const char* fname)

{/* A file of charcters WITHOUT whitespaces

    is open. The characters are stored in

    a vector that is passed back to main

    by reference */

 	v.clear();

    ifstream fin(fname);



    if (fin == NULL)

    {

        error("Could not open pattern file", fname);

    }



    char text;

    fin >> text;

    int l = 1;

    while (!fin.fail())

    {

        v.push_back(text);

        fin >> text;

        l++;

    }



    if (!fin.eof())

        error("Something strange reading the file line ", l);



    fin.close();

}



void readFile2(vector<char>& v, const char* fname)

{/* A file of charcters INCLUDING whitespaces

    is open. The characters are stored in

    a vector that is passed back to main

    by reference */

 	v.clear();

    ifstream fin(fname);



    if (fin == NULL)

    {

        error("Could not open pattern file", fname);

    }



    char buffer[100];

    fin.getline(buffer, 100);

    int l = 1;

    while (!fin.fail())

    {

        int i = 0;

        while (buffer[i]>31 && buffer[i]<127)

        {

            v.push_back(buffer[i]);

            i++;

        }

        fin.getline(buffer, 100);

        l++;

    }



    if (!fin.eof())

        error("Something strange reading the file line ", l);



    fin.close();

}

// Brute-Force search Algorithm

int BruteForce(const vector<char>& T, const vector<char>& P)

{/* The text vector is matched from left to right

    when a missmatch occurs the pattern moves

    one step towards the end of the text */

    int n = T.size();

    int m = P.size();

    int count=0;



    cout << "Brute-Force search Algorithm.\n";

    for (int i = 0; i <=(n-m); i++)

    {

        int j=0;

        while(j<m && T[i+j]==P[j])

        {

            count++;

            j++;

        }

        if(j==m)

        {

            cout << count << " Comparisons were done.\n";

            return(i);

        }

        count++;

    }

    cout << count << " Comparisons were done.\n";

    return (-1);

}



// Last function;

void Last(const vector<char>& P, int last[])

{

    for (int i=0; i<P.size(); i++)

        last[int(P[i])]=i;

}



// Boyer-Moore search Algorithm.

int BoyerMoore(const vector<char>& T, const vector<char>& P)

{/* The text vector is matched from left to right

    when a missmatch occurs the pattern moves

    one or more steps towards the end of the text */

    int n = T.size();

    int m = P.size();

    int i = m-1;

    int j = m-1;

    int last[127]={-1};

    int count=0;



    /* Call the Last-function to

       set the last-array */

    Last(P, last);



    cout << "Boyer-Moore search Algorithm.\n";

    while (i < n)

    {

        if (T[i]==P[j])

        {

            count++;

            if (j==0)

            {

                cout << count << " Comparisons were done.\n";

                return(i);

            }

            else

            {

                i--;

                j--;

            }

        }

        else

        {

            count++;

            i=i+m-min(j,1+last[int(T[i])]);

            j=m-1;

        }

    }

    cout << count << " Comparisons were done.\n";

    return (-1);

}



// Next function;

void Next(const vector<char>& P, int last[], int next[])

{

    for (int i=0; i<P.size(); i++)

    {

        if (i<last[int(P[i])])

            next[int(P[i])]=i;

    }

}



/* ImprovedBoyer-Moore search Algorithm.

   I have trouble with this one between compilers,

   so it might not work properly.  */



int ImprovedBoyerMoore(const vector<char>& T, const vector<char>& P)

{/* The text vector is matched from left to right

    when a missmatch occurs the pattern moves

    one or more steps towards the end of the text */

    int n = T.size();

    int m = P.size();

    int i = m-1;

    int j = m-1;

    int last[127]={-1};

    int next[127];	// I have trouble here between the g++ and

    int count=0;	// the microsoft-compiler. g++ works if I

			// don't initilize the array.  Microsoft

			// is unable to find the pattern if I don't

			// give this array the right value.



    /* Call the Last-function to

       set the last-array */

    Last(P, last);

    Next(P, last, next);



    cout << "ImprovedBoyer-Moore search Algorithm.\n";

    while (i < n)

    {

        if (T[i]==P[j])

        {

            count++;

            if (j==0)

            {

                cout << count << " Comparisons were done.\n";

                return(i);

            }

            else

            {

                i--;

                j--;

            }

        }

        else

        {

            count++;

            i=i+m-min( min(j,1+last[int(T[i])]) , min(j,1+next[int(T[i])]) );

            j=m-1;

        }

    }

    cout << count << " Comparisons were done.\n";

    return (-1);

}



// Main program

int main(int argc, char *argv[])

{

    vector<char> pattern;

    vector<char> text;



    char abPatternFile[]="ab.pattern";

    char abTextFile[]="ab.txt";

    char PatternFile[]="letter.pattern";

    char TextFile[]="letter.txt";

    int Index;



    /*  Read in the pattern and

        the text file into the

        two vectors        */

    readFile1(pattern, abPatternFile);

    readFile1(text, abTextFile);

    cout << "Search of the ab-pattern\n\n";

  	// Bruteforce search of the ab text

   	Index = BruteForce(text, pattern);

   	if (Index != -1)

        cout << "The pattern was found at: "

        <<  Index << endl;

    else

        cout << "Pattern was not found\n";

    //Boyer-Moore search of the ab text

   	Index = BoyerMoore(text, pattern);

   	if (Index != -1)

        cout << "The pattern was found at: "

        <<  Index << endl;

    else

        cout << "Pattern was not found\n";

    //ImprovedBoyer-Moore search of the ab text

   	Index = ImprovedBoyerMoore(text, pattern);

   	if (Index != -1)

        cout << "The pattern was found at: "

        <<  Index << endl;

    else

        cout << "Pattern was not found\n";



   /*  Read in the pattern and

        the text file into the

        two vectors        */

    readFile2(pattern, PatternFile);

    readFile2(text, TextFile);

    cout << "\nSearch of the letter-pattern\n\n";

  	// Bruteforce search of the letter text

  	Index = BruteForce(text, pattern);

   	if (Index != -1)

        cout << "The pattern was found at: "

        <<  Index << endl;

    else

        cout << "Pattern was not found\n";

    // Boyer-Moore search of the letter text

   	Index = BoyerMoore(text, pattern);

   	if (Index != -1)

        cout << "The pattern was found at: "

        <<  Index << endl;

    else

        cout << "Pattern was not found\n";

     //ImprovedBoyer-Moore search of the ab text

   	Index = ImprovedBoyerMoore(text, pattern);

   	if (Index != -1)

        cout << "The pattern was found at: "

        <<  Index << endl;

    else

        cout << "Pattern was not found\n";



    system("PAUSE");

    return 0;

}