//terina burr
//section one
//assign two
//due 10/11/15
#include <iostream>
#include <vector>
#include <cstdlib>
#include <algorithm>
#include <iomanip>
using namespace std; 

const int TOBE_SEARCHED = 5000;
const int HIGH = 10000;
const int LOW = 1;
void genRndNums( vector<int>& v, int vec_size, int seed );

bool linearSearch( const vector<int>& v, int x) ;

bool binarySearch( const vector<int>& v, int x) ;
int search( const vector<int>& container, const vector<int>& searchNums,
            bool (*p)( const vector<int>&, int) ) ;
void sortVec (vector<int>& v) ;

void printStat (int totalSucCnt, int vec_size);


int main() {
    vector<int> container, tobeSearched;
    genRndNums(container, 10000, 9);
    genRndNums(tobeSearched, TOBE_SEARCHED, 3);

    cout << "\nConducting linear search ..." << endl;
    int linear_search_count = search( container, tobeSearched, linearSearch );
    printStat ( linear_search_count, TOBE_SEARCHED );

    cout << "\nConducting binary search on unsorted container ..." << endl;
    int binary_search_count = search( container, tobeSearched, binarySearch );
    printStat ( binary_search_count, TOBE_SEARCHED );

    sortVec( container );

    cout << "\nConducting binary search on sorted container ..." << endl;
    binary_search_count = search( container, tobeSearched, binarySearch );
    printStat ( binary_search_count, TOBE_SEARCHED );

    return 0;
}



/***************************************************************
Function: genRndNums

Use:      it generates random number

Arguments: 1. V: the vector that it puts the random numbers in
           2. vec_size: the size of the vector you want to have
           3. seed: 

Returns:   nothing
***************************************************************/

void genRndNums( vector<int>& v, int vec_size, int seed ) {

        srand(seed);
        int x;
        for(int i = 0; i<vec_size; i++)
//this loop goes through a vector and inserts the random numbers         
	{
                x = rand() % HIGH + LOW;
                v.push_back(x);
        }

}

/***************************************************************
Function: linearSearch

Use:      it starts searching for x at the beginning of the vector v

Arguments: 1. V: the vector that it searches
           2. x: is the item that it searches


Returns:   true or false whether the item x is in the vector v or not returns true if the item x is in the vector v returns false if the item x is not in the vector v
***************************************************************/


bool linearSearch( const vector<int>& v, int x) {
	if(std::find(v.begin(), v.end(), x) !=v. end())
	{
//if they find the correct value and it is not equal to the last one it returns true
		return true;
	}

	else 
		return false;
//otherwise it returns false
}

/***************************************************************
Function: binarySearch

Use:      it uses the algorithm binary search to find the value x in the array v

Arguments: 1. V: the vector that it searches
           2. x: is the item that it searches


Returns:   true or false whether the item x is in the vector v or not returns true if the item x is in the vector v returns false if the item x is not in the vector v
***************************************************************/



bool binarySearch( const vector<int>& v, int x) {
	if ( binary_search( v.begin(), v.end(), x ) )
		return true;
//if they find the correct value return true
	else
		return false;
//else return false
}
/***************************************************************
Function: search

Use:    it is used to compute the total number of successful searches 
Arguments: 1. container: the vector that it searches from
           2. searchNums: the numbers its suppose to search
           3. p: a pointer to a search routine


Returns:   the total number of successful searches
***************************************************************/

int search( const vector<int>& container, const vector<int>& searchNums,
            bool (*p)( const vector<int>&, int) ) {
int x = 0;
	for(unsigned int i = 0; i<searchNums.size(); i++)
	{
//goes through the second vector and stops when it reaches its size
		if(p(container,searchNums.at(i))==true)
		{
//it points to a search function and if that search function goes through as true then it adds one to the total it says going through vector one
			x++;
		}
	}
	return x;

}
/***************************************************************
Function: sortVec

Use:    it is used to sort a vector from smallest to largest using the algorithm sort 
Arguments: 1. v: the vector that it is going to sort


Returns:   nothing
***************************************************************/


void sortVec (vector<int>& v) {
//sorts a vector from smallest to largest 
	sort(v.begin(), v.end() );
}
/***************************************************************
Function: printStat

Use:    it is used to print out the percentage of successful searches
Arguments: 1. totalSucCnt: total number of successful searches
           2. vec_size: the size of the vector 

Returns:   nothing
***************************************************************/


void printStat (int totalSucCnt, int vec_size) {
	float x =( float(totalSucCnt)/vec_size)*100;
//gives the percentage number of successes as a float
	std::cout.width(6); std::cout << std::right <<"Percent of successful searches = "<<setw(4)<< x<<"%"<<'\n';

}