#include <iostream>
#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
#include "prompt.h"
#include "tvector.h"

// read strings from file and then find them again
// rcd@cs.duke.edu


int SequentialSearchIter (const tvector<string>& list, const string& key)
// pre:  list.size() == # elements in list
// post: returns index of key in list, -1 if key not found
{
    for (int k = 0; k < list.size(); k++)
    {
        if (list[k] == key)         // found key, exit search
        {
            return k;
        }
    }

    return -1;                      // not in list
}

int SequentialSearchRec (const tvector<string>& list, const string& key,
                         int low, int high)
// pre:  key if it exists is between indices low and high , list sorted
// post: returns index of key in list, -1 if key not found
{
    if (low > high)            return -1;
    else if (list[low] == key) return low;
    else                       return SequentialSearchRec(list, key, low + 1, high);
}


int BinarySearchIter (const tvector<string>& list, const string& key)
// pre:  list.size() == # elements in list, list sorted
// post: returns index of key in list, -1 if key not found
{
    int low = 0;                   // leftmost possible entry
    int high = list.size()-1;      // rightmost possible entry

    while (low <= high)
    {
        int mid = (low + high) / 2; // middle of current range
        if (list[mid] == key)       // found key, exit search
        {
            return mid;
        }
        else if (list[mid] < key)   // key in upper half
        {
            low = mid + 1;
        }
        else                        // key in lower half
        {
            high = mid - 1;
        }
    }

    return -1;                      // not in list
}

int BinarySearchRec (const tvector<string>& list, const string& key,
                     int low, int high)
// pre:  key if it exists is between indices low and high , list sorted
// post: returns index of key in list, -1 if key not found
{
    int mid = (low + high) / 2;

    if (list[mid] == key)     return mid;
    else if (list[mid] < key) return BinarySearchRec(list, key, low, mid-1);
    else                      return BinarySearchRec(list, key, mid+1, high);
}


int Search (const tvector<string>& list, const string& key)
// pre:  list.size() == # elements in list, list sorted
// post: returns index of key in list, -1 if key not found
{
    return SequentialSearchIter(list, key);
    // return BinarySearchIter(list, toFind);
    // return SequentialSearchRec(list, toFind, 0, list.size() -1);
    // return BinarySearchRec(list, toFind, 0, list.size() - 1);
}

void Print (const tvector<string>& list)
// pre:  list.size() == # elements in list
// post: prints all elements in list
{
    for (int k = 0; k < list.size(); k++)
    {
        cout << list[k] << endl;
    }
    cout << endl;
}

int main()
{
    // prepare input
    string filename = PromptString("Enter file name: ");
    ifstream input(filename.c_str());

    // check to see if file opened correctly
    if (input.fail())
    {
        cout << "Unable to open file " << filename << endl;
        return -1;
    }

    tvector<string> list;

    // read words from file
    string word;
    while (input >> word)
    {
        list.push_back(word);
    }
    input.close();

    // sort the list
    Print(list);
    sort(list.begin(), list.end());
    Print(list);

    // search for words
    string toFind;
    while (cin >> toFind)
    {
        cout << Search(list, toFind) << endl;
    }

    return 0;
}