#include <iostream>
#include <fstream>
#include "WordT.h"
#include <string>

using namespace std;

void ReadWord(WordT & newWord, ifstream & inFile);
void PrintWords(const WordT words[],  size_t size);
void ReadFile(WordT dictionary[], size_t & size, string fileName);

void AddWordToDictionary(WordT dictionary[], size_t & size, WordT word);

size_t Find(const WordT array[], size_t size, WordT word ); 
size_t BinarySearch(const WordT ary[], size_t size, WordT key);

void Sort(WordT array[], size_t size);
void InsertionSort(WordT array[], size_t size);

const size_t MAX_WORDS{1000};
const size_t NO_POS {MAX_WORDS+1};

int main() {
    WordT dictionary[MAX_WORDS];
    size_t dictionarySize{0};

    //ReadFile(dictionary, dictionarySize, "main.cpp");
    ReadFile(dictionary, dictionarySize, "ocap.txt");

    PrintWords(dictionary, dictionarySize);

    cout << endl << endl;
    InsertionSort(dictionary, dictionarySize);

    PrintWords(dictionary, dictionarySize);

    return 0;
}

void AddWordToDictionary(WordT dictionary[], size_t & size, WordT word) {
    size_t pos;
    size_t checkPos;

    // pos = Find(dictionary,size, word);
    pos = BinarySearch(dictionary,size, word);
   // cout << endl << endl;

    if (pos ==  NO_POS) {
        // cout << "Inserting " << word.word << endl;
        if (size < MAX_WORDS) {
          //  dictionary[size] = word;
          //  ++size was here.
          checkPos = size;
          while ( checkPos > 0 and dictionary[checkPos-1].word > word.word) {
              // cout << "Moving " << dictionary[checkPos -1].word << " up"<< endl;
              dictionary[checkPos] = dictionary[checkPos - 1];
              --checkPos;
          }
          //cout << "Storing word at " << checkPos << endl;
          dictionary[checkPos] = word;
        } else {
            cout << "Out of space in the dictionary " << endl;
        }

        // bug moved this because we should not increment, size points at the
        // next empty space
        ++size;
       // PrintWords(dictionary, size);
    } else {
      ++dictionary[pos].count;
    }

    //cout << endl << endl;

    return;
}

void ReadFile(WordT dictionary[], size_t & size, string fileName){
    ifstream inFile{fileName};
    WordT newWord;

    if (!inFile) {
        cout << "Failed to open file " << endl;
    } else {
        ReadWord(newWord, inFile);
        while (inFile) {
            if(newWord.word != "") {
               AddWordToDictionary(dictionary, size, newWord);
            }
            ReadWord(newWord, inFile);
        }

        inFile.close();
    }
}

size_t Find(const WordT array[], size_t size, WordT word ){
    size_t pos{NO_POS};
    size_t i{0};

    while (i < size) {
       if (array[i].word == word.word) {
          pos = i;
          i = NO_POS;
       } else {
          ++i;
       }
    }

    return pos;
}

void ReadWord(WordT & newWord, ifstream & inFile){
    string inWord;

    inFile >> inWord;
    newWord = MakeWordT(inWord);

    return;
}

void PrintWords(const WordT words[],  size_t size){
    size_t i;
//    size_t j;

    for(i = 0; i < size; ++i) {
       PrintWordT(words[i]);
/*
       for(j = 0; j < words[i].word.size(); ++j) { 
          cout << words[i].word.at(j);
       }
       cout << ", " << words[i].count << endl;
*/
    }

    return;
}

void Swap(WordT & a, WordT & b) {
    WordT tmp{a};
    a = b;
    b = tmp;
}

void Sort(WordT array[], size_t size){
    size_t current;
    size_t small;
    size_t compare;

    for(current = 0; current < size; ++ current) {
        small = current;

        for(compare = current + 1; compare < size; ++compare) {
            if (array[small].count == array[compare].count) {
                // the counts are the same
                if (array[small].word > array[compare].word) {
                   // sort by word 
                   small = compare;
                   
                }
            } else if (array[small].count < array[compare].count)  {
                   small = compare;
            }
/*
            if (array[small].count < array[compare].count) {
               small = compare;
            }
*/
        }

        if (small != current) {
           Swap(array[small], array[current]);
        }
    }
    return;
}

size_t BinarySearch(const WordT ary[], size_t size, WordT key){
    int low{0};
    int high{static_cast<int>(size)-1};
    int mid;
    size_t rv{NO_POS};

    bool found{false};

    while (not found and low <= high) {
        mid = (low + high) / 2;
/*
        cout << "Searching for " << key.word;
        cout << " low = " << low << " high = " << high << " mid = " 
             << mid << endl;

        cout << "\t\t ary[mid] - " << ary[mid].word << endl;
        cout << endl;
*/
        if (ary[mid].word == key.word) {
            //cout << "\t\t found " << endl;
            found = true;
       // note this comparison was wrong
        } else if (ary[mid].word > key.word) {
            //cout << "\t\t search low " << endl;
            high = mid - 1;
        } else {
            //cout << "\t\t search high " << endl;
            low = mid + 1;
        }
    }

    if( found) {
        rv = static_cast<size_t>(mid);
    }

    return rv;
}


void InsertionSort(WordT array[], size_t size){
    WordT hold;

    size_t current;
    size_t insertPos;

    for(current = 1; current < size; current++) {
         hold = array[current];
         insertPos = current;

         while (insertPos > 0 and array[insertPos-1].word > hold.word) {
              array[insertPos] = array[insertPos-1];
              --insertPos;
         }
         array[insertPos] = hold;

    }


}