// File: prg3_1.cpp
// the program compares the efficiency of the sequential
// and binary search by timing algorithm execution using the
// timer class. two integer arrays list1 and list2
// of size ARRAY_SIZE are initialized with the same random
// integers in the range 0 to 999,999. initialize the array
// targetList having TARGET_SIZE elements to contain other
// random numbers in the same range. time the selection sort
// as it sorts list2 and output the result. using the
// elements in array targetList as target values for the
// sequential and binary searches, time each algorithm and
// output the results

#include <iostream>

#include "d_search.h"    // generic sequential and binary searches
#include "d_sort.h"        // generic selection sort
#include "d_random.h"    // random number generation
#include "d_timer.h"        // time events

using namespace std;

int main()
{    const int ARRAY_SIZE = 100000, TARGET_SIZE = 50000;

    // arrays for the search
   int list1[ARRAY_SIZE], list2[ARRAY_SIZE], targetList[TARGET_SIZE];
    int i;

    // t used for timing the search algorithms
    timer t;
    // random number object
    randomNumber rnd;

    // initialize the arrays with random numbers in the
   // range 0 to 999,999
   for (i = 0; i < ARRAY_SIZE; i++)
        list1[i] = list2[i] = rnd.random(1000000);

    // initialize targetList with random numbers in the
   // same range 0 to 999,999
    for (i=0;i < TARGET_SIZE; i++)
        targetList[i] = rnd.random(1000000);

    // sort list2
   cout << "Timing the Selection Sort" << endl;
    t.start();        // start timer
    selectionSort(list2,ARRAY_SIZE);
    t.stop();        // stop timer
    cout << "Selection Sort takes " << t.time()
          << " seconds." << endl;

   cout << endl << "Timing the Sequential Search" << endl;
    t.start();        // start timer
    // perform sequential search with elements from list2
    for (i = 0; i < TARGET_SIZE; i++)
        seqSearch(list1,0,ARRAY_SIZE,targetList[i]);
    t.stop();        // stop timer
    cout << "Sequential Search takes " << t.time()
          << " seconds." << endl;

    cout << endl << "Timing the Binary Search" << endl;
    t.start();        // start timer
    // perform binary search with elements from list1
    for (i = 0; i < TARGET_SIZE; i++)
        binSearch(list2,0,ARRAY_SIZE,targetList[i]);
    t.stop();        // stop timer
    cout << "Binary Search takes " << t.time()
          << " seconds." << endl;

    return 0;
}

/*
Run:

Timing the Selection Sort
Selection Sort takes 126.912 seconds.

Timing the Sequential Search
Sequential Search takes 132.889 seconds.

Timing the Binary Search
Binary Search takes 0.08 seconds.
*/

#ifndef SEARCH_FUNCTIONS
#define SEARCH_FUNCTIONS

#include <vector>
#include <list>

using namespace std;

// perform a sequential search of an integer array for a target
// in the index range [first, last). return the index of a
// match or last if the target is not in arr
int seqSearch(const int arr[], int first, int last, int target);

// perform  asequential search for a target in the index range
// [first, last).  return the index of a match or last if the
// target is not in arr
template <typename T>
int seqSearch(const T arr[], int first, int last, const T& target);

// perform a binary search of an integer array for a target
// in the index range [first, last). return the index of a
// match or last if the target is not in arr
int binSearch(const int arr[], int first, int last, int target);

// perform a binary search of an array for a target
// in the index range [first, last). return the index of a
// match or last if the target is not in arr
template <typename T>
int binSearch(const T arr[], int first, int last, const T& target);

// vector version of the sequential search
template <typename T>
int seqSearch(const vector<T>& v, int first, int last, const T& target);

// vector version of the binary search
template <typename T>
int binSearch(const vector<T>& v, int first, int last, const T& target);

// perform the sequential search for target in the list
// iterator range [first, last). return an iterator pointing
// at the target in the list or last if target is not found
template <typename T>
list<T>::iterator seqSearch(list<T>::iterator first,
                                     list<T>::iterator last, const T& target);

// perform the sequential search for target in the container
// iterator range [first, last). return an iterator pointing
// at the target in the container or last if target is not
// found
template <typename Iterator, typename T>
Iterator find(Iterator first, Iterator last, const T& target);

// ***********************************************************
//      search function implementations
// ***********************************************************

int seqSearch(const int arr[], int first, int last, int target)
{
    int i;

   // scan indices in the range first <= i < last
    for(i=first; i < last; i++)
        if (arr[i] == target)
            return i;                // immediately return on a match

    return last;                    // return last if target not found
}

template <typename T>
int seqSearch(const T arr[], int first, int last, const T& target)
{
    int i;

   // scan indices in the range first <= i < last
    for(i=first; i < last; i++)
        if (arr[i] == target)    // assume T has the "==" operator
            return i;                // immediately return on a match

    return last;                    // return last if target not found
}

int binSearch(const int arr[], int first, int last, int target)
{
    int mid;                        // index of the midpoint
    int midValue;                // object that is assigned arr[mid]
    int origLast = last;        // save original value of last
    
    while (first < last)        // test for nonempty sublist
    {
        mid = (first+last)/2;
        midValue = arr[mid];
        if (target == midValue)
            return mid;            // have a match
      // determine which sublist to search
        else if (target < midValue)
            last = mid;            // search lower sublist. reset last
        else
            first = mid+1;        // search upper sublist. reset first
    }

    return origLast;            // target not found
}

template <typename T>
int binSearch(const T arr[], int first, int last, const T& target)
{
    int mid;                        // index of the midpoint
    T midValue;                    // object that is assigned arr[mid]
    int origLast = last;        // save original value of last
    
    while (first < last)        // test for nonempty sublist
    {
        mid = (first+last)/2;
        midValue = arr[mid];
        if (target == midValue)
            return mid;            // have a match
      // determine which sublist to search
        else if (target < midValue)
            last = mid;            // search lower sublist. reset last
        else
            first = mid+1;        // search upper sublist. reset first
    }

    return origLast;            // target not found
}

template <typename T>
int seqSearch(const vector<T>& v, int first, int last, const T& target)
{
    int i;

   // scan indices in the range first <= i < last
    for(i=first; i < last; i++)
        if (v[i] == target)        // assume T has the "==" operator
            return i;                // immediately return on a match

    return last;                    // otherwise return last
}

template <typename T>
int binSearch(const vector<T>& v, int first, int last, const T& target)
{
    int mid;                        // index of the midpoint
    T midvalue;                    // object that is assigned v[mid]
    int origLast = last;        // save original value of last
    
    while (first < last)        // test for nonempty sublist
    {
        mid = (first+last)/2;
        midvalue = v[mid];
        if (target == midvalue)
            return mid;            // have a match
      // determine which sublist to search
        else if (target < midvalue)
            last = mid;            // search lower sublist. reset last
        else
            first = mid+1;        // search upper sublist. reset first
    }

    return origLast;            // target not found
}

template <typename T>
list<T>::iterator seqSearch(list<T>::iterator first,
                                     list<T>::iterator last, const T& target)
{
    // start at location first
    list<T>::iterator iter = first;

    // compare list elements with item until either
    // we arrive at last or locate item
    while(iter != last && !(*iter == target))
        iter++;

    // iter either points at item or is last
    return iter;
}

template <typename Iterator, typename T>
Iterator find(Iterator first, Iterator last, const T& target)
{
    Iterator iter = first;

    // scan iterator range [first, last), stopping
    // if the loop locates target
    while (iter != last && *iter != target)
        iter++;

    // if target located, iter points at it; otherwise
    // is has value last
    return iter;
}

#endif   // SEARCH_FUNCTIONS