// Name: John H. Hacker
// Assg: Lab #4
// Date: June 27, 2006
// Desc: This program demonstrates the use of binary and sequential
//       search methods on an array of strings.
#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;


const int MAX_NAMES = 5000; 

// Prototypes for functions used in searching
void display(string names[], int size);
int input(string filename, string names[]);

int sequentialSearch(const string names[], int numberNames,
		     string searchName);
int binarySearch(const string names[], int numberNames,
		 string searchName);


int main()
{
  string names[MAX_NAMES];
  int numNames;

  numNames = input("sortednames.dat", names);

  cout << "The names that are in our database: " << endl;
  display(names, numNames);
  cout << endl << endl;

  string searchName;
  int searchIndex;
  // keep asking the user for names to search for, forever, or at least
  // until they enter quit at which point we break out and are done
  while (true)
  {
    // get a name to search for
    cout << "Enter a name to search for or 'quit' to stop: ";
    getline(cin, searchName);

    // check if the user is fed up with the program yet
    if (searchName == "quit")
      break;


    // perform a binary search for the name the user entered in the
    // names database
    cout << "Using binary search to search for name: " << searchName
         << endl;

    searchIndex = binarySearch(names, numNames, searchName);

    if (searchIndex == -1)
      cout << "Unable to find name using binary search" 
	   << endl << endl;
    else
      cout << "Found the name at index " << searchIndex
	   << " in the names database" << endl << endl;


    // CODE: your task, implement the books sequential search 
    //       down below and call it here.  Compare and see if you
    //       get the same answer as the binary search
  }

  cout << "Goodbye!" << endl;
}



// display
//
// A simple function to display the values in an array of strings
// We format the values onto standard output in a nice readable way
//
// Params:
//    names   an array of strings whose values are to be displayed
//    size    the number of values in the array
void display(string names[], int size)
{
  for (int i=0; i<size; i++)
  {
    cout << "[" << setw(2) << i << "] "
	 << names[i] << endl;
  }
}



// input
//
// Input names from a file.  Each line of the file contains a single
// name, so we need to read in a whole line (with possible spaces) to
// get a single name.  The user supplies the name of the file
// to read from, and an array to fill up with the integers.  This 
// function returns the number of items that were read from the file.
//
// Params:
//    filename  a string that is the name of the file 
//              to be open for input
//    names    an array of strings, upon return this array
//              is filled with the strings from the input file
// Result:
//    size      returns the number of strings read in from 
//              the input file and placed in the names array
int input(string filename, string names[])
{
  int size = 0;  // keeps track of number of items we read in
  ifstream infile;
  string name;

  // open the file and check that it opened properly
  infile.open(filename.c_str());
  if (!infile)
  {
    cerr << "Error, could not open file: " << filename << endl
         << "   Perhaps the file is not in your build directory?" 
	 << endl;
    exit(0);
  }

  // now, we keep on reading in values from the file until 
  // we reach the end of file.  infile will become false once
  // the input file has reach the end of the file, which is how
  // the test in this while loop works.
  while (infile)
  {
    getline(infile, name);
    names[size] = name;
    size++;
  }

  // always good to explicitly close a file when we are done with it
  infile.close();

  return size;
}



// binarySearch
//
// Implement the books binary search function (Malik Ch #10, pg. 519
// but use an array of strings to search within.
//
// Params:
//    names  an array of strings which contains the names we are to
//             to search within
//    numberNames the number of names in the names database we are
//                   searching
//    searchName a string containing the name we are searching for
//
// Result:
//    index  the search returns a -1 if the searchName is not found
//             in the names database, otherwise it returns the index
//             of the location of the searchName in the database
int binarySearch(const string names[], int numberNames,
		 string searchName)
{
  int first = 0;
  int last = numberNames - 1;
  int mid;

  int searchCounter = 1;

  bool found = false;
  
  while (first <= last && !found)
  {
    // calculate mid from the current  focus of the binary search
    mid = (first + last) / 2;

    // display progress of the binary search
    cout << "     In binarySearch, comparison: " 
	 << searchCounter 
	 << " first=" << first << " mid=" << mid << " last=" << last
	 << endl;
    searchCounter++;

    // see if we have found the item we are searching for, if not
    // change the lower or upper bounds (first or last) appropriately
    // to reconcentrate search on smaller region
    if (names[mid] == searchName)
      found = true;
    else
      if (names[mid] > searchName)
	last = mid - 1;
      else
	first = mid + 1;
  }

  if (found)
    return mid;
  else
    return -1;
}