// FILE:    bSearch.cpp
// PURPOSE: Implement binary search algorithm
// INSTRUCTIONS: Complete both binary search functions as specified
//-----------------------------------------------------------------
// COMPILATION INSTRUCTIONS: g++ and gxx 
// 1. FILES: apvector.h and apvector.cpp
// 2. COMMAND LINE: g++ (or gxx) bSearch.cpp 
//-----------------------------------------------------------------
#include <iomanip.h>
#include <string>
#include "apvector.h"

//------------------------------------------------
//  Recursive version of binary search
//------------------------------------------------
int bSearch2(const apvector<string> &v, int lo, int hi, const string &item) {
  // precond: v's elements arranged in ascending order, index positions
  //          in [lo, hi] need to be searched for item
  //postcond: if item is found, its index position is returned;
  //          otherwise, -1 is returned
  return -1;
}

//------------------------------------------------
//  Recursive version of sequential search
//------------------------------------------------
int seqSearch(const apvector<string> &v, const string &item, int pos) {
  // precond: v's elements arranged in no order, original call
  //          is seqSearch(V, name, 0)
  //postcond: if item is found, its index position is returned;
  //          otherwise, -1 is returned
    return -1;
}

//------------------------------------------------
//  Iterative version of binary search
//------------------------------------------------
int bSearch1(const apvector<string> &v, const string &item) {
  // precond: v's elements arranged in ascending order
  //postcond: if item is found, its index position is returned;
  //          otherwise, -1 is returned
  return -1;
}


void loadVec(apvector<string> &);
void printVec(const apvector<string> &);
void sortVec(apvector<string> &);
void testEmpty(void);
void wait(void); 
void cls(void);

int main() {
  const string title("Testing iterative and recursive binary searches");
  apvector<string> V;

  loadVec(V);
  sortVec(V);
  for (;;) {
    cls();
    cout << setw(39 + title.length()/2) << title.c_str() << endl << endl;
    printVec(V);
    cout << "Enter name to search for (<ENTER> to quit): ";
    string name;
    getline(cin, name);
    if ( name.length() == 0 ) break;

    cout << "\nRecursive binary search index was: " << flush;
    const int index2 = bSearch2(V, 0, V.length() - 1, name);
    cout << index2 << endl;
    if ( index2 >= 0 && name == V[index2] ) {
      cout << name << " found: ";
      cout << "V[" << index2 << "] = " << V[index2] << endl;
    }
    else
      cout << name << " not found." << endl;

    cout << "\nRecursive sequential search index is: " << flush;
  const int SSindex = seqSearch(V, name, 0);
  cout << SSindex << endl;
  if ( SSindex >= 0 && name == V[SSindex] ) {
    cout << name << " found: ";
    cout << "V[" << SSindex << "] = " << V[SSindex] << endl;
  }
  else
    cout << name << " not found." << endl;

  cout << "\nIterative binary search index is: " << flush; 
  const int index = bSearch1(V, name);
  cout << index << endl;
  if ( index >= 0 && name == V[index] ) {
    cout << name << " found: ";
    cout << "V[" << index << "] = " << V[index] << endl;
  }
  else
    cout << name << " not found." << endl << endl;
    wait();
  }
  testEmpty();
  cout << endl;
  return 0;
}


void loadVec(apvector<string> &v) {
  string A[] = {"Ed", "Mo Jo", "Eva", "Ava", "Pat", "Lesley", "Bo",
		"Zazu", "Helga", "Bobo", "Fred", "Ned", "Bea"};
  const int SIZE = sizeof(A)/sizeof(string);
  v.resize(SIZE);
  for (int k = 0; k < SIZE; k++)
    v[k] = A[k];
}

void printVec(const apvector<string> &v) {
  const int SIZE = v.length();
  for (int k = 0; k < SIZE; k++)
    cout << setw(2) << k << ".    " << v[k] << endl;;
  cout << endl;
}

void sortVec(apvector<string> &v) {
  // postcondition: elements of v (if any) are arranged in ascending order
  //================================================================
  // Implement selection sort on v
  const int SIZE = v.length();
  for (int position = 0; position < SIZE - 1; ++position) {
    int p = position;
    for (int k = position + 1; k < SIZE; k++)
      if ( v[k] < v[p] ) p = k;
    string tmp = v[position];
    v[position] = v[p];
    v[p] = tmp;
  } //==for position
}

void cls(void) {
  for (int k = 1; k <= 55; k++)
    cout.put('\n');
}


void testEmpty(void) {
  string title("Testing case of empty vector");
  cls();
  cout << setw(39 + title.length()/2) << title.c_str() << endl << endl;
  apvector<string> A;
  string st("Robin");
  cout << "Testing recursive sequential search: " << flush;
  int p = seqSearch(A, st, 0);
  if ( p < 0 )
    cout << "It worked." << endl;
  else
    cout << "It failed." << endl;
  cout << "Testing iterative binary search: " << flush;
  p = bSearch1(A, st);  
  if ( p < 0 )
    cout << "It worked." << endl;
  else
    cout << "It failed." << endl;

  cout << "Testing recursive binary search: " << flush;
  p = bSearch2(A, 0, A.length()-1, st);
  if ( p < 0 )
    cout << "It worked." << endl;
  else
    cout << "It failed." << endl;
  cout << endl;
  wait();
}



void wait(void) {
   cout << "Press <ENTER> to continue..."; 
   cin.ignore(10, '\n');
}