// Assignment 2
// Fall 2020

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

const int DictionarySize = 15000;
const int gettysburgWordsSize = 271;

void getFile(const string& filename,string*, int filesize);
bool find(const string& searchValue, const string dictionary[]);
void sort( string* list, int size);
void swap( string&,  string&);

int main()
{
    const string wordFile = "c:/temp/ass2words.txt";
    const string gettysburgFile = "c:/temp/gettysburg.txt";
    const string outputFile = "c:/temp/ass2output.txt";

    int notfoundWords = 0;

    string dictionary[DictionarySize];
    string gettysburgWords[gettysburgWordsSize];

    getFile(wordFile, dictionary, DictionarySize);
    getFile(gettysburgFile, gettysburgWords, gettysburgWordsSize);

    cout << "Sorting Dictionary data ... ";
    sort(dictionary, DictionarySize);
    cout << "done" << endl;

    cout << "Sorting gettysburg data ... ";
    sort(gettysburgWords,gettysburgWordsSize);
    cout << "done" << endl << endl;

    ofstream fout(outputFile);
    fout << "Words not found in the dictionary" << endl;
    cout << "Words not found in the dictionary" << endl;
    if (fout)
    {
        for (int i= 0; i < gettysburgWordsSize; i++)
        {
            if (!find(gettysburgWords[i],dictionary))
            {
                fout << gettysburgWords[i]<< endl;
                cout << gettysburgWords[i]<< endl;
                notfoundWords++;
            }
        }
        cout << "Number of Gettysburg Words not found = " << notfoundWords << endl;
    }
    else
    {
        cerr << "Unable to open output file " << outputFile << endl;
    }
}

void getFile(const string& filename, string* array, int size)
{
    ifstream fin(filename.c_str());
    if (!fin)
    {
        cerr << "Unable to open word file " << filename << endl;
        exit(1);
    }

    cout << "Reading file: " << filename << endl;

    for (int i = 0; i < size; i++)
    {
        fin >> array[i];
    }
    fin.close();
}

bool find(const string& searchValue, const string dictionary[])
{
    int low, high, middle;
    low = 0;
    high = DictionarySize-1;

    while (low <= high)
    {
        middle = (low + high) / 2;
        if (searchValue < dictionary[middle])
        {
            high = middle - 1;
        }
        else if (searchValue > dictionary[middle])
        {
            low = middle + 1;
        }
        else
        {
            return true;
        }
    }

    return false;
}

void sort( string a[], int size)
{
    // minIndex is the position in the unsorted part containing the minimum
    int minIndex;
    for (int i = 0; i < size - 1; i++)
    {
        // find the position of the minimum in the unsorted part
        minIndex = i;
        for (int j = i+1; j < size; j++)
        {
            if (a[j] < a[minIndex])
            {
                minIndex = j;
            }
        }

        // swap the value of the minimum in the unsorted part with the next
        // value in the sorted part

        if(minIndex != i)    // don't swap if the minimum is already in place
        {
            swap(a[i],a[minIndex]);
        }
    }
}

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