/*******************************************************************************************
* NumberOccurrence
* This program reads in two large data sets; one sorted, and one unsorted.
* The program will allow the user to search the data sets for numbers
* using various searching algorithms. The program will report:
* How many instances of the number there are?
* How many comparisons were made?
*
* Interface:
* (0) exit
* (1) Linear Search
* (2) Binary Search
* (3) Hash
*
* Grading Considerations Include:
* The program is written in C++. It is error-free and has been thoroughly
* unit-tested by multiple people.
* The program has a refined user-interface in which the user’s expectations
* are met.
* The program adheres to the StyleGuide (comments, clean code, and
* functions).
* The program is submitted on-time and according to the Submission
* Instructions
*
* Author: Abigail Mott
* Date: 3/3/2025
* Time Spent: about 3 hours ish
*******************************************************************************************/
#include <iostream>
#include <string>
#include <vector>
#include <fstream>

using namespace std;

ifstream sortedFile;
ifstream unsortedFile;

// the user input
int userInput = 0;
// loop the program
bool loop = true;
// instances of the number
int instances = 0;
// number of times the key was compared with the number in file
int comparisons = 0;
// spot in the file
int i = 0;
// store unsorted file into a vector
vector<int> unsortedVec;
// store sorted file into a vector
vector<int> sortedVec;
// high of the vec
int high;
// mid of vec
int mid;
//check if userInput is a double
double doubleCheck;


/*******************************************************************************************
* tryCatch()
* checks user input and lets user pass on if its right
*******************************************************************************************/
void tryCatch() {
    bool validInput = true;
    do {
        //accepts userinput as a double
        std::cin >> doubleCheck;
        //checks to see if it fails or is double
        if (cin.fail() || doubleCheck != static_cast<int>(doubleCheck)) {
            validInput = false;
            //ask user for the correct input
            cout << "\n";
            cout << "Invalid input!\n";
            cout << "Please give me a number: ";
            //clears cin and gets ready for another input
            cin.clear();
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
        }
        //lets user pass through rest of program
        else {
            validInput = true;
            //turn input back into a int
            userInput = static_cast<int>(doubleCheck);
        }
    } while (!validInput);
}

/*******************************************************************************************
* linearSearch()
* checks file one by one for the key
*******************************************************************************************/
void linearSearch() {
    //recets the comparisons and instances variables back to 0
    instances = 0;
    comparisons = 0;
    //accepts users input
    cout << "\n";
    cout << "What int do you want me to look for?\n";
    cout << "Please give me a number: ";
    tryCatch();
    //checks one by one for the desired number to be found
    while (unsortedFile >> i) {
        if (i == userInput) {
            instances++;
        }
        comparisons++;
    }
    //tell user the instances and comparisons
    cout << "There were " << instances << " instances of " << userInput << " in the file";
    cout << " with " << comparisons << " comparisons made\n";
    userInput = 10;
}

/*******************************************************************************************
* binarySearch()
* searches for the key by dividing the unsorted numbers down
*******************************************************************************************/
void binarySearch() {
    //resets the comparisons and instances variables back to 0
    instances = 0;
    comparisons = 0;
    cout << "\n";
    cout << "What int do you want me to look for?\n";
    cout << "Please give me a number: ";
    tryCatch();
    int key = userInput;
    int add;
    // Read sorted file
    while (sortedFile >> add) {
        sortedVec.push_back(add);
    }

    // begin of binary search
    int low = 0;
    high = sortedVec.size() - 1;

    while (low <= high) {
        mid = (low + high) / 2;
        //adds more comparisons
        comparisons++;

        if (sortedVec[mid] == key) {
            instances++;
            // Check both sides to ensure all instances are counted
            int left = mid - 1;
            while (left >= low && sortedVec[left] == key) {
                //adding up more instances as it checks for them
                instances++;
                left--;
            }

            int right = mid + 1;
            while (right <= high && sortedVec[right] == key) {
                //adding up more instances as it checks for them
                instances++;
                right++;
            }
            //ends the loop because it is now done and checked
            high = low;
        }
        //continues the search since function above indicated its not done
        else if (sortedVec[mid] > key) {
            high = mid - 1;
        }
        else {
            low = mid + 1;
        }
    }
    //tell user the instances and comparisons
    cout << "There were " << instances << " instances of " << userInput << " in the file";
    cout << " with " << comparisons << " comparisons made\n";
}

/*******************************************************************************************
* hashSearch()
* - in maintence -
*******************************************************************************************/
void hashSearch() {
    cout << "in maintenance, sorry!\n";
}

/*******************************************************************************************
* main()
* runs the entire program
*******************************************************************************************/
int main() {
    //tells user about program
    cout << "Hello user! Welcome to the program.  This program will search for a needle in the haystack for you!\n";
    cout << "Loading up the unsorted file and sorted file\n";
    //attempts to open both sorted and unsorted files
    unsortedFile.open("numbers.txt");
    sortedFile.open("sortedNumbers.txt");
    //if it doesn't work, it tells the user
    if (!unsortedFile) cerr << "Can't open unsorted file!\n";
    if (!sortedFile) cerr << "Can't open sorted file!\n";
    //but if it does open the files, it tells the user it does
    else if (unsortedFile && sortedFile) {
        cout << "Files opened successfully!\n";
    }
    //loops main menu
    do {
        //main menu
        cout << "\n";
        cout << "    Main Menu\n";
        cout << "(1) Linear Search\n(2) Binary Search\n(3) Hash Search\n(0) exit\n";
        cout << "Please give me a number 1 - 3: ";
        tryCatch();
        //sends user to linear search
        if (userInput == 1) {
            linearSearch();
        }
        //sends user to binary search
        if (userInput == 2) {
            binarySearch();
        }
        //sends user to hash search
        if (userInput == 3) {
            hashSearch();
        }
        //ends the program
        if (userInput == 0) {
            loop = false;
        }
    } while (loop);
    //closes the files
    unsortedFile.close();
    sortedFile.close();
}
