/*
  Travis Gadberry
  Patrick Hesser
  Chris Ladewig

  proj2.cpp
  21Mar05
*/

using namespace std;

/* ********************* */
/*       Includes        */
/* ********************* */

#include <string>
#include <iostream>
#include <fstream>
#include <vector>

#include "BalancedBinaryTree.cpp"
#include "BinarySearch.h"
#include "InputFile.h"
#include "HashTable.h"
#include "LinearSearch.h"
#include "UnbalancedBinaryTree.cpp"
#include "RandomArrayGen.h"
#include "ReportResults.h"


/* ********************** */
/*    Function Headers    */
/* ********************** */

bool testArrayConditions(vector<bool>);
void menuHeader(vector<string>, int);
void menuMain(vector< vector<int> >&, int&, ReportResults&, vector<bool>&, vector<string>&, vector<int>);
void menuInputData(vector< vector<int> >&, vector<string>&, vector<bool>&, vector<int>);
int menuSearchElement();

void LSearch(vector< vector<int> >&, int&, ReportResults&, vector<int>);
void BSearch(vector< vector<int> >&, int&, ReportResults&, vector<int>);
void UTree(vector< vector<int> >&, int&, ReportResults&, vector<int>);
void BTree(vector< vector<int> >&, int&, ReportResults&, vector<int>);
void HTable(vector< vector<int> >&, int&, ReportResults&, vector<int>);
void Report(ReportResults);

/* ************************ */
/*       CONSTANTS          */
/* ************************ */

const int NUM_TEST_SIZES = 3;
const int NUM_TEST_ALGOS = 5;

const string none = "none\t";
const string file = "from file";
const string generated = "generated";

const int LS_INT = 0;
const int BS_INT = 1;
const int UTREE_INT = 2;
const int BTREE_INT = 3;
const int HTABLE_INT = 4;

/* *********************** */
/*    Function Defs        */
/* *********************** */

int main(int argc, char* argv[]) {
  vector<int> array_sizes;
  array_sizes.push_back(10);
  array_sizes.push_back(1000);
  array_sizes.push_back(10000);

  vector< vector<int> > array;
  vector<string> array_condition;
  int search_element = 0;
  vector<bool> array_init;
  bool search_init;

  ReportResults report(NUM_TEST_SIZES*NUM_TEST_ALGOS);

  for(int i=0; i<NUM_TEST_SIZES; i++) {
    array_condition.push_back(none);
    array_init.push_back(false);
  }

  while(true) {
    bool array_init_condition = testArrayConditions(array_init);
    
    while(!array_init_condition) {
      menuHeader(array_condition, search_element);
      menuInputData(array, array_condition, array_init, array_sizes);
      array_init_condition = testArrayConditions(array_init);
    }

    if(search_init == false) {
      search_element = menuSearchElement();
      search_init = true;
    }

    menuHeader(array_condition, search_element);
    menuMain(array, search_element, report, array_init, array_condition, array_sizes);
  }
  return 1;
}

bool testArrayConditions(vector<bool> array_init) {
  for(int i=0; i < array_init.size(); i++) {
    if(array_init.at(i) == false)
      return false;
  }
  return true;
}

void menuHeader(vector<string> array_condition, int search_element) {
  cout << endl << endl << endl << endl << endl << endl << endl << endl << endl << endl;
  cout << "******Status of Arrays*********" << endl;

  for(int i=1; i<=NUM_TEST_SIZES; i++)
    cout << "***   Array"  << i << ":  " << array_condition.at(i-1) << endl;

  cout << "***   Search Int: " << search_element << endl;
  cout << "*******************************" << endl;
}

void menuMain(vector< vector<int> >& array, int& search_element, ReportResults& report, vector<bool>& array_init, vector<string>& array_condition, vector<int> array_sizes) {
  int user_input;
  cout << endl;
  cout << "   Main Menu: " << endl;
  cout << "1. Input Data" << endl;
  cout << "2. Select Search Element" << endl;
  cout << "3. Linear Search" << endl;
  cout << "4. Binary Search" << endl;
  cout << "5. Unbalanced Binary Sorted Tree" << endl;
  cout << "6. Balanaced Binary Sorted Tree" << endl;
  cout << "7. Hash Table" << endl;
  cout << "8. Run All Tests" << endl;
  cout << "9. Overall Report" << endl;
  cout << "10.Exit Program" << endl;
  cout << "   Please select an option: ";
  cin >> user_input;

  switch(user_input) {
    case 1  : menuInputData(array, array_condition, array_init, array_sizes);
              break;
    case 2  : search_element = menuSearchElement();
              break;
    case 3  : LSearch(array, search_element, report, array_sizes);
              break;
    case 4  : cout << endl << "Binary Search" << endl;
              BSearch(array, search_element, report, array_sizes);
              break;
    case 5  : UTree(array, search_element, report, array_sizes);
              break;
    case 6  : BTree(array, search_element, report, array_sizes);
              break;
    case 7  : HTable(array, search_element, report, array_sizes);
              break;
    case 8  : LSearch(array, search_element, report, array_sizes);
              BSearch(array, search_element, report, array_sizes);
              UTree(array, search_element, report, array_sizes);
              BTree(array, search_element, report, array_sizes);
              HTable(array, search_element, report, array_sizes);
              break;
    case 9  : Report(report);
              break;
    case 10 : exit(0);
  }
}

void menuInputData(vector< vector<int> >& array, vector<string>& array_condition, vector<bool>& array_init, vector<int> array_sizes) {
  int n, source;
  string filename;

  cout << endl << endl << endl << endl << endl << endl << endl << endl << endl << endl;
  cout << "   Input Data: " << endl;
  for(int i=1; i<=NUM_TEST_SIZES; i++)
    cout << i << ". Array " << i << endl;

  cout << "Please choose : ";
  cin >> n;
  n = n-1;

  cout << endl;
  cout << "1. From File" << endl;
  cout << "2. Generate" << endl;

  cout << "Please choose : ";
  cin >> source;

  InputFile f;
  if(source == 1) {
    cout << endl;
    cout << "Please type the name of the file : ";
    cin >> filename;
    f.setFileName(filename);
    f.readData();
    if(f.isValid() == true) {
      array.at(n) = f.getVector();
      array_init.at(n) = true;
      array_condition.at(n) = file;
    }
  }
  if(source == 2) {
    RandomArrayGen gen;
    gen.setType(2);
    gen.setN(array_sizes.at(n));
    gen.genArray();
    vector<int> V = gen.getVector();

    vector< vector<int> > array_holder;
    for(int i=0; i<n; i++)
      array_holder.push_back(array.at(i));
    array_holder.push_back(V);
    for(int i=n+1; i<array.size(); i++)
      array_holder.push_back(array.at(i));
    array.clear();
    for(int i=0; i<array_holder.size(); i++)
      array.push_back(array_holder.at(i));

    vector<string> array_condition_holder;
    for(int i=0; i<n; i++)
      array_condition_holder.push_back(array_condition.at(i));
    array_condition_holder.push_back(generated);
    for(int i=n+1; i<array_condition.size(); i++)
      array_condition_holder.push_back(array_condition.at(i));
    array_condition.clear();
    for(int i=0; i<array_condition_holder.size(); i++)
      array_condition.push_back(array_condition_holder.at(i));

    vector<bool> array_init_holder;
    for(int i=0; i<n; i++)
      array_init_holder.push_back(array_init.at(i));
    array_init_holder.push_back(true);
    for(int i=n+1; i<array_init.size(); i++)
      array_init_holder.push_back(array_init.at(i));
    array_init.clear();
    for(int i=0; i<array_init_holder.size(); i++)
      array_init.push_back(array_init_holder.at(i));

cout << "\nn= " << n << "   source = " << source << endl;
  }
}

int menuSearchElement() {
  int search;
  cout << endl << endl << endl << endl << endl << endl << endl << endl << endl << endl;
  cout << "   Please type the integer to search for : ";
  cin >> search;
  return search;
}

void LSearch(vector< vector<int> >& array, int& search_element, ReportResults& report, vector<int> array_sizes) {
  bool   search_found;
  double search_time;
  int    search_increments;
  double creation_time;
  int    creation_increments;

  int report_increment = LS_INT * NUM_TEST_SIZES;

  for(int i=0; i<NUM_TEST_SIZES; i++) {
    LinearSearch ls = LinearSearch(array.at(i));
    search_found = ls.search(search_element);
    search_time = ls.getSearchTime();
    search_increments = ls.getSearchIncrements();
    report.setFound(i+report_increment, search_found);
    report.setTime(i+report_increment, search_time);
    report.setIncrements(i+report_increment, search_increments);
  }
}

void BSearch(vector< vector<int> >& array, int& search_element, ReportResults& report, vector<int> array_sizes) {
  bool   search_found;
  double search_time;
  int    search_increments;
  double creation_time;
  int    creation_increments;

  int report_increment = BS_INT * NUM_TEST_SIZES;

  for(int i=0; i<NUM_TEST_SIZES; i++) {
    BinarySearch bs = BinarySearch(array.at(i));
    search_found = bs.search(search_element);
    search_time = bs.getSearchTime();
    search_increments = bs.getSearchIncrements();
    report.setFound(i+report_increment, search_found);
    report.setTime(i+report_increment, search_time);
    report.setIncrements(i+report_increment, search_increments);
  }
}

void UTree(vector< vector<int> >& array, int& search_element, ReportResults& report, vector<int> array_sizes) {
  bool   search_found;
  double search_time;
  int    search_increments;
  double creation_time;
  int    creation_increments;

  int report_increment = UTREE_INT * NUM_TEST_SIZES;

  for(int i=0; i<NUM_TEST_SIZES; i++) {
    UnbalancedBinaryTree<int> utree(-9999);
    utree.resetIncrements();
    utree.insertIntVector(array.at(i));

    if(search_element == utree.find(search_element))
      search_found = true;
    else
      search_found = false;    

    search_time = utree.getSearchTime();
    search_increments = utree.getIncrements();
    creation_time = utree.getCreationTime();
    creation_increments = 0;
    report.setFound(i+report_increment,search_found);
    report.setTime(i+report_increment, search_time);
    report.setIncrements(i+report_increment, search_increments);
    report.setCreationTime(i+report_increment,creation_time);
    report.setCreationIncrements(i+report_increment,creation_increments);
  }
}

void BTree(vector< vector<int> >& array, int& search_element, ReportResults& report, vector<int> array_sizes) {
  bool   search_found;
  double search_time;
  int    search_increments;
  double creation_time;
  int    creation_increments;
  int report_increments = BTREE_INT * NUM_TEST_SIZES;

  for(int i=0; i<NUM_TEST_SIZES; i++) {
    BalancedBinaryTree<int> btree(-9999);
    btree.resetIncrements();
    btree.insertIntVector(array.at(i));

    if(search_element == btree.find(search_element))
      search_found = true;
    else
      search_found = false;

    search_time = btree.getSearchTime();
    search_increments = btree.getIncrements();
    creation_time = btree.getCreationTime();
    creation_increments = 0;
    report.setFound(i+report_increments,search_found);
    report.setTime(i+report_increments, search_time);
    report.setIncrements(i+report_increments, search_increments);
    report.setCreationTime(i+report_increments,creation_time);
    report.setCreationIncrements(i+report_increments,creation_increments);
  }
}

void HTable(vector< vector<int> >& array, int& search_element, ReportResults& report, vector<int> array_sizes) {
  bool   search_found;
  double search_time;
  int    search_increments;
  double creation_time;
  int    creation_increments;

  int report_increment = HTABLE_INT * NUM_TEST_SIZES;

  for(int i=0; i<NUM_TEST_SIZES; i++) {
    HashTable hash(array.at(i));
    search_found = hash.search(search_element);
    search_time = hash.getSearchTime();
    search_increments = hash.getSearchIncrements();
    creation_time = hash.getCreationTime();
    creation_increments = hash.getCreationIncrements();
    report.setFound(i+report_increment, search_found);
    report.setTime(i+report_increment, search_time);
    report.setIncrements(i+report_increment, search_increments);
    report.setCreationTime(i+report_increment,creation_time);
    report.setCreationIncrements(i+report_increment,creation_increments);
  }
}

void Report(ReportResults report) {
  int j;

  cout << endl;
  cout << "********************************************" << endl;
  cout << "**              Test Results              **" << endl;
  cout << "********************************************" << endl << endl;

  cout << "*** Increments : ***" << endl;
  cout << "-----------------------" << endl;
  cout << "Linear Search:" << endl;
  j=1;
  for(int i=LS_INT*NUM_TEST_SIZES; i<(LS_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getIncrements(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;
  cout << "Binary Search :" << endl;
  j=1;
  for(int i=BS_INT*NUM_TEST_SIZES; i<(BS_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getIncrements(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;
  cout << "Unbalanced Search Tree :" << endl;
  j=1;
  for(int i=UTREE_INT*NUM_TEST_SIZES; i<(UTREE_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getIncrements(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;
  cout << "Balanced Search Tree :" << endl;
  j=1;
  for(int i=BTREE_INT*NUM_TEST_SIZES; i<(BTREE_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getIncrements(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;
  cout << "Hash Table :" << endl;
  j=1;
  for(int i=HTABLE_INT*NUM_TEST_SIZES; i<(HTABLE_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getIncrements(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;

  cout << endl << endl;

  cout << "*** Creation Increments : ***" << endl;
  cout << "-----------------------" << endl;
  cout << "Unbalanced Search Tree :" << endl;
  j=1;
  for(int i=UTREE_INT*NUM_TEST_SIZES; i<(UTREE_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getCreationIncrements(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;
  cout << "Balanced Search Tree :" << endl;
  j=1;
  for(int i=BTREE_INT*NUM_TEST_SIZES; i<(BTREE_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getCreationIncrements(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;
  cout << "Hash Table :" << endl;
  j=1;
  for(int i=HTABLE_INT*NUM_TEST_SIZES; i<(HTABLE_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getCreationIncrements(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;

  cout << endl << endl;

  cout << "*** Time : ***" << endl;
  cout << "-----------------------" << endl;
  cout << "Linear Search:" << endl;
  j=1;
  for(int i=LS_INT*NUM_TEST_SIZES; i<(LS_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getTime(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;
  cout << "Binary Search:" << endl;
  j=1;
  for(int i=BS_INT*NUM_TEST_SIZES; i<(BS_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getTime(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;
  cout << "Unbalanced Search Tree:" << endl;
  j=1;
  for(int i=UTREE_INT*NUM_TEST_SIZES; i<(UTREE_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getTime(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;
  cout << "Balanced Search Tree:" << endl;
  j=1;
  for(int i=BTREE_INT*NUM_TEST_SIZES; i<(BTREE_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getTime(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;
  cout << "Hash Table:" << endl;
  j=1;
  for(int i=HTABLE_INT*NUM_TEST_SIZES; i<(HTABLE_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getTime(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;

  cout << endl << endl;

  cout << "*** Creation Time : ***" << endl;
  cout << "-----------------------" << endl;
  cout << "Unbalanced Search Tree :" << endl;
  j=1;
  for(int i=UTREE_INT*NUM_TEST_SIZES; i<(UTREE_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getCreationTime(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;
  cout << "Balanced Search Tree :" << endl;
  j=1;
  for(int i=BTREE_INT*NUM_TEST_SIZES; i<(BTREE_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getCreationTime(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;
  cout << "Hash Table :" << endl;
  j=1;
  for(int i=HTABLE_INT*NUM_TEST_SIZES; i<(HTABLE_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getCreationTime(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;

  cout << endl << endl;

  cout << "*** Found : ***" << endl;
  cout << "-----------------------" << endl;
  cout << "Linear Search:" << endl;
  j=1;
  for(int i=LS_INT*NUM_TEST_SIZES; i<(LS_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getFound(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;
  cout << "Binary Search:" << endl;
  j=1;
  for(int i=BS_INT*NUM_TEST_SIZES; i<(BS_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getFound(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;
  cout << "Unbalanced Search Tree:" << endl;
  j=1;
  for(int i=UTREE_INT*NUM_TEST_SIZES; i<(UTREE_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getFound(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;
  cout << "Balanced Search Tree:" << endl;
  j=1;
  for(int i=BTREE_INT*NUM_TEST_SIZES; i<(BTREE_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getFound(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;
  cout << "Hash Table:" << endl;
  j=1;
  for(int i=HTABLE_INT*NUM_TEST_SIZES; i<(HTABLE_INT+1)*NUM_TEST_SIZES; i++) {
    cout << "     Array " << j << " : " << report.getFound(i) << endl;
    j++;
  }
  cout << "-----------------------" << endl;

  cout << endl << endl;

  cout << "********************************************" << endl;
  cout << "**          End of Test Results           **" << endl;
  cout << "********************************************" << endl << endl;
}