// APS105 Lab6 11/05/06
// Geoffrey Lang
// 995155772
// langgeof@ecf.utoronto.ca

#include <iostream>
#include <fstream>

using namespace std;

const int MAX_WORDS = 10000;
const int MAX_WORD_LENGTH = 25;
const int WORD_NOT_FOUND = -1;

bool goodLetter(char a);
void printArray(char words[][MAX_WORD_LENGTH], int n);
void selectionSort(char words[][MAX_WORD_LENGTH], int n);
void deleteDuplicates(char words[][MAX_WORD_LENGTH], int& n);
int binarySearch(char words[][MAX_WORD_LENGTH], int n, char key[]);

int main (int argc, char *argv[])
{
        char current, currentkey;
        int i = 0, j = 0, k = 0, totalwords = 0, uniquewords = 0, foundloc;
        bool twolines = 0, keydone = 0, exit = 0;

        char words[MAX_WORDS][MAX_WORD_LENGTH];
        char key[MAX_WORD_LENGTH];


        ifstream in_stream;                                     // Opens the file written after the
        in_stream.open(argv[1]);                                // name of this program when it is run

        while(!in_stream.eof())
        {
                in_stream.get(current);
                current = tolower(current);

                if((current == ' ' || current == '\n') && twolines == 1)// Move to next line if there is
                {                                                       // a space in the input
                        while(!goodLetter(words[i][strlen(words[i])-1]))
                        {
                                words[i][strlen(words[i])-1] = '\0';
                        }
                        i++;
                        j = 0;
                        twolines = 0;
                }

                if(j == 0 && goodLetter(current) || j != 0)     // Check that the first letter isn't punctuation
                {                                               // before putting the word into the array and
                        words[i][j] = current;                  // if its not the first letter, put it in anyway
                        j++;
                        twolines = 1;
                }
        }

        selectionSort(words,i);                                 // Apply selection sort to the array
                                                                // and then print it (for testing
        totalwords = i;                                         // purposes only)
        deleteDuplicates(words,i);                              // Delete the duplicates in the array
        uniquewords = i;                                        // and print it to check that they are
        printArray(words,i);                                    // all deleted
        cout << "Total words: " << totalwords << ".\n";
        cout << "Unique words: " << uniquewords << ".\n";

        while(exit == 0)                                                // Continues to ask the user for a
        {                                                               // Key to search the words array for.
                cout << "\nEnter a word to search for: ";               // If the first non-punctuation
                                                                        // character is a number, the program
                while(keydone == 0)                                     // will quit, also deletes punctuation
                {                                                       // leading or following the search key
                        cin.get(currentkey);
                        currentkey = tolower(currentkey);

                        if(currentkey == ' ' || currentkey == '\n')
                        {
                                while(!goodLetter(key[strlen(key)])-1)
                                {
                                        key[strlen(key)] = '\0';
                                }
                                keydone = 1;
                                k = 0;
                        }
                        if (k == 0 && goodLetter(currentkey) || k != 0)
                        {
                                key[k] = currentkey;
                                k++;
                        }
                }
                keydone = 0;
                if (key[0] >= '0' && key[0] <= '9')
                {
                        exit = 1;
                        cout << "... Quitting ...\n";
                }
                else
                {
                        cout << "... Searching ...\n";
                        foundloc = binarySearch(words, i, key);

                        if(foundloc >= 0)
                        {
                                cout << "\"" << key << "\" FOUND at location: " << foundloc << ".\n";
                        }
                        else
                        {
                                cout << "\"" << key << "\" NOT FOUND.\n";
                        }
                }
                for (int t = 0; t <= MAX_WORD_LENGTH; t++)      // Clears the key array after the
                {                                               // search is complete
                        key[t] = '\0';
                }
        }
        return 0;
}

bool goodLetter(char a)                                         // Function to check if a character is
{                                                               // a character that can start or end
        if((a >= 'a' && a <= 'z') || (a >= '0' && a <= '9'))    // a word--must be a letter or a
        {                                                       // number. Returns 1 if the character
                return 1;                                       // is a letter or number, 0 if not
        }
        else
        {
                return 0;
        }
}

void printArray(char words[][MAX_WORD_LENGTH], int n)           // Function to print an array, one
{                                                               // word per line
        for(int x = 0; x < n; x++)
        {
                for (int y = 0; words[x][y] != '\0'; y++)
                {
                        cout << words[x][y];
                }
                cout << endl;
        }
        return;
}

void selectionSort(char words[][MAX_WORD_LENGTH], int n)        // Function to sort an array of
{                                                               // c-strings in alphabetical
        for(int i = 0; i < n - 1; i++)                          // order
        {
                int smallest = i;
                for(int j = i + 1; j < n; j++)
                {
                        if(strncmp(words[j],words[smallest],MAX_WORD_LENGTH) < 0)
                        {
                                smallest = j;
                        }
                }
                char temp[1][MAX_WORD_LENGTH];
                strncpy(temp[0],words[i],MAX_WORD_LENGTH);
                strncpy(words[i],words[smallest],MAX_WORD_LENGTH);
                strncpy(words[smallest],temp[0],MAX_WORD_LENGTH);
        }
        return;
}

void deleteDuplicates(char words[][MAX_WORD_LENGTH], int& n)            // Function to delete all duplicate
{                                                                       // enteries in an array of sorted
        int i = 0, j = 0, k = 0;                                        // c-strings
        while(i < n - 1)
        {
                while (strncmp(words[i-j],words[i+1],MAX_WORD_LENGTH) == 0)
                {
                        j++;
                        i++;
                }

                if (j > 0)
                {
                        strncpy(words[i-j+1],words[i+1],MAX_WORD_LENGTH);
                        j--;
                }
                else
                {
                        i++;
                }
                k++;
        }
        n = k;
        return;
}

int binarySearch(char words[][MAX_WORD_LENGTH], int n, char key[])      // Function to search the words array
                                                                        // for the key array and return the
{                                                                       // index of the words array that the
        int left = 0, right = n - 1, middle, result;                    // that the key is in
        while(left < right)
        {
                middle = (left + right)/2;
                if(strncmp(key,words[middle],MAX_WORD_LENGTH) > 0)
                {
                        left = middle + 1;
                }
                else
                {
                        right = middle;
                }
        }
        if(strncmp(key,words[left],MAX_WORD_LENGTH) == 0)
        {
                result = left;
        }
        else
        {
                result = WORD_NOT_FOUND;
        }
        return result;
}