// ====================================================================
// BinarySearch
// In class assignment using file input, sorting and searching methods
// ====================================================================
#include <iostream>
#include <fstream>
using namespace std;

// ====================================================================
// Global Function Prototypes  (Global Function Declarations)
// ====================================================================
void InsertionSort(float* anArray, int size);
bool BinSearchFor(float findMe, float* theArray, int size);
void OutputArray(float *theArray, int size);


// ====================================================================
// main function - it all begins here
// argc = number of arguments on the command line when program was run
// argv = an array of strings, argv[0] = executable name
//                             argv[1] = first parameter to the program
//                             argv[2] = second parameter
//                                 :
//                             argv[argc-1] = last parameter
//
// argc = argument count, argv = argument vector (of strings)
// ====================================================================
int main(int argc, char * argv[])
{
   // ---------------------------------------------------------------
   // ---------------------------------------------------------------
   // Read in the Data from a File
   // ---------------------------------------------------------------
   // ---------------------------------------------------------------
   cout << "Reading data file...\n";

   // open the data.txt file for input
   std::fstream inputFile("./ICA201_data.txt", std::ios_base::in);

   // Read all the numbers... 
   //      keep count of how many 
   //      display them just so we can see what is happening
   int   numCount = 0;
   float number;
   while (inputFile >> number)
   {
      cout << number << " ";
      numCount++;
   }
   cout << endl;

   // Allocate enough memory to hold the entire file 
   // contents in an array of floats
   float *theData = new float[numCount];

   // Go back to beginning of the file
   inputFile.clear();
   inputFile.seekg(0, ios::beg);

   // Read in all the data into the daa array
   //      Display the data again to verify it was read
   int index = 0;
   while (inputFile >> theData[index])
   {
      cout << theData[index] << " ";
      index++;
   }
   cout << endl;
   cout << "...end reading data file\n\n";

   // ---------------------------------------------------------------
   // ---------------------------------------------------------------
   // Sort theData and output it to show it is sorted
   // ---------------------------------------------------------------
   // ---------------------------------------------------------------
   cout << "Sorting...\n";
   InsertionSort(theData, numCount);
   OutputArray(theData, numCount);
   cout << "... end sorting\n\n";


   // ---------------------------------------------------------------
   // ---------------------------------------------------------------
   // Search for a value in theData... use Binary Search
   // ---------------------------------------------------------------
   // ---------------------------------------------------------------
   cout << "Searching...\n";
   float valueToFind = 999.999;
   if (true == BinSearchFor(valueToFind, theData, numCount))
   {
      cout << "   Value = " << valueToFind << " was found.\n";
   }
   else
   {
      cout << "   Value = " << valueToFind << " NOT found.\n";
   }
   cout << "...end Searching\n\n";


   // ---------------------------------------------------------------
   // ---------------------------------------------------------------
   // Perform clean up operations
   // Free the allocated memory, close the input file
   // ---------------------------------------------------------------
   // ---------------------------------------------------------------
   cout << "\nCleaning up...\n";
   delete [] theData;
   theData = NULL;
   inputFile.close();
   cout << "\nProgram ends.\n";

   return 0;
}

// ====================================================================
// ====================================================================
void InsertionSort(float* anArray, int size)
{
   float key;
   int i;
   for(int j=1; j < size; j++)
   {
      key = anArray[j];
      i = j - 1;
      while ( (anArray[i] > key) && (i >= 0) )
      {
         anArray[i+1] = anArray[i];
         i--;
      }
      anArray[i+1] = key;
   }
}

// ====================================================================
// ====================================================================
bool BinSearchFor(float findMe, float* theArray, int size)
{
   int left = 0;
   int right = size - 1;

   bool found = false;
   int i;

   while ((!found) && (left != right))
   {
      i = left + (right - left)/2;       // truncates decimal part

      cout << "   checking index = " << i << endl;

      if(findMe == theArray[i])        { found = true;  }
      else if (findMe < theArray[i])   { right = i;	  }
      else                             { left  = i+1;   }
   }
   return found;
}

// ====================================================================
// ====================================================================
void OutputArray(float *theArray, int size)
{
   for (int i=0; i < size; i++)
   {
      cout << "\t" << theArray[i];
      if ((i+1) % 5 == 0) { cout << endl; }
   }
   cout << endl;
}

// ====================================================================
// ====================================================================
// end of file