//Flexie Muirhead   #: 26075046
//Assignment #2
 
#include <iostream>//allows program to output data to the screen
using namespace std;
 
//searching class definition
class Searching
{
      public:
             //member funtions
             void insertionSort(int *list, int last);
             void hashSearching(int *list, int last);
             void sequentialSearch(int list[], int last);
             void binarySearch(int list[], int last);
 
      private:
};
 
//funtion sorts a list
void Searching::insertionSort(int *list, int last)
{
     int current;
     int hold;
     int walker;
 
     for (current = 1; current <= last; current++)
     {
         hold=list[current];
 
         for(walker = current -1; walker >= 0 && hold < list[walker]; walker--)
         {
                    list[walker + 1 ] = list[walker];
         }
 
         list[walker + 1] = hold;
     }
 
}//end of funtion insertion sort
 
 
//searches a list using hash search
void Searching::hashSearching(int *list, int last)
{
    //declarations 
    int hashList[last];
	int num;
    int address;
 
    //rearrange list by determine location with the modulo-division
    //method
    for(int x=0; x<10; x++)
    {
            address = list[x]%last;
 
            hashList[address]= list[x];
    }
 
    //accept target
    cout<<"Enter The Number You Want To Find: ";
	cin>>num;
 
	//finds loction by modulo-division method
	address = num%last;
 
	//check if location correct
	if (num == hashList[address])
		cout<<"Loaction Found!!! "<<endl;
	else
		cout<<"Location Not Found!!! "<<endl;
}
 
 
//search list using sequential search    
void Searching::sequentialSearch(int *list, int last)
{
     int target;
     int flag=0;
 
     //accpet target
     cout<<"Enter The Number You Want To Find: ";
     cin>>target;
 
     //check to see if target is in list
     for(int cntr = 0; cntr < last; cntr++)
     {
             if(list[cntr] == target)
             {
             cout << "Target Found!!" << cntr << "."<< endl;
             flag += 1;
             }
 
     }
 
      //if flag has not be incrimented them location not found
      if(flag < 1)
      {
             cout << "Target Not Found!!" << endl;
      } 
 
}//end of sequential search
 
 
//searches a lsit using binaery search
void Searching::binarySearch(int list[], int last)
{
 
          //declarations 
          int target;
          int first = 0;
          int mid;
 
          //accept the target 
          cout << "Enter a target to be found: ";
          cin >> target;
 
          //loops until program reaches the end of the list
          while(first < last)
          {
              mid = (first + last)/2;
 
              if(target > list[mid])
              {
                    first = mid + 1;
              }
 
          else 
              if(target < list[mid])
              {
                    last = mid + 1;
              } 
          else
              {
                    first = last + 1;
              }
          }
 
          //check to see if location found
          if(target == list[mid])
            cout << "Target Found." << endl;
          else
            cout << "Target Not Found." << endl; 
}//end of funtion binary search

//Flexie Muirhead   #: 26075046
//Assignment #2
 
//include directives
#include <iostream>//allows program to output data to the screen
#include <iomanip>
#include "plpl.h"//include definition of class Search 
 
using namespace std;
 
//funtion prototype, menu
void menu(char *option);
 
//************INT MAIN*****************
int main()
{
    //array size. number of elements in the list
    const int arraySize = 10;
    //assign elements to list
    int array[arraySize] = {45, 67, 98, 12, 34, 53, 20, 01, 9, 56};
 
    //create an object of the class
    Search searchOption;
 
    char option;
    menuu:
 
    //call menu funtion
    menu(option);
    //change opyion to caps
    option = toupper(option);
 
    switch(option)
    {
                  case 'A':
                       system("cls");
                       searchOption.sequentialSearch(array, arraySize);
                  break;
 
                  case 'B':
                       system("cls");
                       searchOpyion.binarySearch(array, arraySize);
                  break;
 
                  case 'C':
                       system("cls");
                       searchOption.hashSorting(array, arraySize);
                  break;
 
                  case 'X':
                       system("cls");
                       cout<<"THANK YOU FOR USING THIS PROGRAM; SEE YOU NEXT TIME!\n\n";
                       cout<<"\tThis Prgram was Created by:\n\n"<<"\t\tFlexie Muirhead\n\n";
                       system("pause");
                       exit(0);
                  break;
 
                  default:
                          system("cls");	
                          cout<< "Please Enter One of the Stated Options!"<<endl;	
     }
 
system("pause");
system("cls");
 
//goto statment acts a loop to loop back to the star of the program
goto menuu;
 
system("pause");
return 0;	
}//end of main funtions  
 
//function header; this funtion accept option for the type of 
//search the user wants
void menu(char *option)
{
      cout<<"\n\t\tFlexie Muirhead Type Test Search Software\n";
      cout<<"\n\t\t"<<"_____________________________________________\n\n";
 
      cout<<"\t\t\t"<<"MENU OPTIONS\n\n\n";
      cout<<"\t\t"<<"Press [A] For Sequential Searc Test\n";
      cout<<"\t\t"<<"Press [B] For Binary Search Test\n";
      cout<<"\t\t"<<"Press [C] For Hash Searche Tes\n";
      cout<<"\t\t"<<"Press [X] To Exit\n\n";
      cout<<"\t\t"<<"Select Option -->"<<endl;
 
     cout<<"Enter Option ";
     cin>>option;
}//end of menu funtion