// Assignment 4 Solution - Fall 2020

#include <iostream>
#include <fstream>
#include <cstdlib>
#include <string>
#include <cstring>
using namespace std;

const string KeywordsFilename = "c:/temp/unsorted_keywords.txt";
const string testInputFile = "c:/temp/oldass3.cpp";

int getKeywordsCount(const string& filename);
bool getKeywords(const string& filename, string* keywords, int numberOfKeywords);
void sort (string a[], int size);
void swap (string& a, string& b);
void searchFileForKeywords(const string& filename, string* keywords, int numberOfKeywords);
bool isA_keyword(const char* word, const string* keywords, int numberOfKeywords);

int main()
{
    int numberOfKeywords = getKeywordsCount(KeywordsFilename);
    string* keywords = new string[numberOfKeywords];
    getKeywords(KeywordsFilename,keywords,numberOfKeywords);
    sort(keywords, numberOfKeywords);
    searchFileForKeywords(testInputFile, keywords, numberOfKeywords);
    delete [] keywords;
}

int getKeywordsCount(const string& filename)
{
    ifstream fin(filename);
    if (!fin)
    {
        cerr << "Unable to open input file: " << filename << endl;
        exit(EXIT_FAILURE);
    }
    int countKeywords = 0;
    string temp;
    while (fin >> temp) countKeywords++;
    fin.clear();
    return countKeywords;
}

// Get keywords from file & store in string array
bool getKeywords(const string& filename, string* keywords, int numberOfKeywords)
{
    ifstream fin(filename.c_str());
    if (!fin)
    {
        cerr << "Unable to open input file: " << filename << endl;
        exit(EXIT_FAILURE);
    }

    for (int i = 0; i < numberOfKeywords; i++)
    {
        fin >> keywords[i];
        if (!fin) return false;
    }
    return true;
}

// Use a bubble sort for keywords
void sort(string a[], int size)
{
    bool swapOccurred;

    do
    {
        swapOccurred = false;
        for (int i = 0; i < size-1; i++)
        {
            if (a[i] > a[i+1])
            {
                swap(a[i],a[i+1]);
                swapOccurred = true;
            }
        }
    }
    while (swapOccurred);
}

void swap (string& a, string& b)
{
    string temp;
    temp = a;
    a = b;
    b = temp;
}

void searchFileForKeywords(const string& ass3Filename,string* keywords, int numberOfKeywords)
{
    ifstream fin(ass3Filename);
    if (!fin)
    {
        cerr << "Unable to open input file: " << ass3Filename << endl;
        exit(EXIT_FAILURE);
    }

    char line[256];     // buffer for each line in the file
    char* ptr;          // strtok pointer
    int lineCount = 0;
    int last0utputLine = 0;
    size_t keywordPos;
    int numKeywordsFound = 0;

    while (fin.getline(line,sizeof(line)))
    {
        lineCount++;

        // look for // in the line
        ptr = strstr(line,"//");
        if (ptr) *ptr = 0;      // terminate line if // found

        ptr = strtok(line," \r(),!&*;");

        while (ptr != NULL)
        {
            if (isA_keyword(ptr,keywords,numberOfKeywords))
            {
                // Start output for a new line?
                if (lineCount != last0utputLine)
                {
                    cout << endl << "Line " << lineCount << ":";
                    last0utputLine = lineCount;
                }

                // Determine keyword position in the line
                keywordPos = ptr - line;

                cout << ' ' << ptr << "(" << keywordPos << ")";
                numKeywordsFound++;
            }
            ptr = strtok(NULL," \r(),!&*;");
        }
    }
    cout << endl << "Number of keywords found = " << numKeywordsFound << endl;
}

// Binary search for word in array of keywords
bool isA_keyword(const char* word, const string* keywords, int numberOfKeywords)
{
    int low, high, middle;
    string word_string(word);
    low = 0;
    high = numberOfKeywords - 1;
    string middleWord;
    int compare;

    while (low <= high)
    {
        middle = (low + high) / 2;
        middleWord = keywords[middle];
        compare = strcmp(word,middleWord.c_str());
        if (compare < 0)
        {
            high = middle - 1;
        }
        else if (compare > 0)
        {
            low = middle + 1;
        }
        else
        {
            return true;
        }
    }
    return false;
}