#include <iostream>
#include <fstream>
#include <string>
#include <chrono>  //has stuff to time code
using namespace std;

//Topics:
//Linear search
//Binary search

//Goal: Read words from a dictionary into an array.
//Make a "search" function that figures out the location of a given word
//int the array.


//load words from a dictionary file into given array
void loadWords(ifstream &infile, string bigArray[], int n)
{
	for (int i = 0; i < n; i++)
	{
		infile >> bigArray[i];
	}
}


//Return index position of key in given array, in given range from start to end.
//Return -1 if item is not present in given range.
//Let n = e - s + 1   (the number of items in the search range)
//Run time:  O(n)
int linearSearch(string key, string words[], int start, int end)
{
	for (int i = start; i <= end; i++)
	{
		if (key == words[i])
		{
			return i;
		}
	}
	return -1;  //Item is not there!
}


//run time O(log n)
//Whoa!!!! The CHOPPING NUMBER of n!?!?!
//That is super super super fast....
int binarySearch(string key, string words[], int start, int end)
{
	int s = start;
	int e = end;

	while (s <= e)
	{
		int m = (s + e) / 2;

		if (key == words[m])
		{
			return m;
		}
		else if (key < words[m])
		{
			e = m - 1;
		}
		else // key > words[m]
		{
			s = m + 1;
		}
	}
	return -1; //Item not present in given range.
}

int main()
{
	//file variables
	ifstream infile;
	infile.open("largedictionary.txt");

	//Read words from dictionary file into a giant array
	int numWords = 202412;
	string* bigArray = new string[numWords];
	loadWords(infile, bigArray, numWords);

	//Search for some target word
	string coolWord = "hinderance";
	int location;
	
	//Let's time the searches
	int runs = 100000;

	auto start1 = chrono::high_resolution_clock::now();
	//for(int i=0; i<runs; i++)
	//	location = linearSearch(coolWord, bigArray, 0, numWords - 1);
	auto end1 = chrono::high_resolution_clock::now();
	
	chrono::duration<double> elapsed1 = end1 - start1;
	cout << "Linear search took " << elapsed1.count() << endl;
	
	auto start2 = chrono::high_resolution_clock::now();
	for(int i=0; i<runs; i++)
		location = binarySearch(coolWord, bigArray, 0, numWords - 1);
	auto end2 = chrono::high_resolution_clock::now();

	chrono::duration<double> elapsed2 = end2 - start2;
	cout << "Binary search took " << elapsed2.count() << endl;

	//Report location to user
	cout << coolWord << " is located at position/index " << location << endl;


	return 0;
}






















//Code to time stuff:
//auto start = chrono::high_resolution_clock::now();
//auto finish = chrono::high_resolution_clock::now();
//chrono::duration<double> elapsed = finish - start;

//elapsed.count()