//----------------------------------------------------------
// File: sortetc.cxx
// This file shows how to do a selection sort and some other
// manipulations of arrays.
//----------------------------------------------------------

//----------------------------------------------------------
// Directives:
#include <cstdlib>
#include <iostream>
#include <graphics.h>
#include <cassert>
using namespace std;
//----------------------------------------------------------

//----------------------------------------------------------
// Prototypes:
// Return the biggest number in an array of size n:
int biggest(int data[], size_t n);

// Return true if an array of size n contains at least one
// copy of a specified target.
bool has_specified_target(int data[], size_t n, int target);

// Return the index of the biggest number in an array of
// size n. If there are several locations that contain the
// biggest item, then this function returns the index of
// the first time the biggest item appears.
size_t index_of_biggest(int data[], size_t n);

// Return the index of the location of a speecified target in
// an array of size n. If there are several locations that
// contain the target, then this function could return the
// index of any of those occurrences. If the target is not
// in the array, then this function returns n.
// Precondition: The data array is sorted from smallest
// to largest.
size_t index_via_binary_search(int data[], size_t n, int target);

// Return the index of the location of a speecified target in
// an array of size n. If there are several locations that
// contain the target, then this function returns the index of
// the first time it appears. If the target is not in the array,
// then this function returns n.
size_t index_via_serial_search(int data[], size_t n, int target);

// Print all the elements of an array of size n on one
// line of output with spaces in between.
void print_array(int data[], size_t n);

// Sort an array of size n from smallest (at index 0) to
// largest (at index n-1):
void selection_sort(int data[], size_t n);
//----------------------------------------------------------


// Function definitions:
//----------------------------------------------------------
int main()
{
    int a[12] = {5, 0, 6, 6, 7, 4, 3, 9, 7, 3, -4, 2};

    // Test the simple functions:
    cout << "Array a: ";
    print_array(a,12);
    cout << "The biggest number is at index: "
	 << index_of_biggest(a, 12) << endl;
    cout << "Result of searching for 6: "
	 << index_via_serial_search(a, 12, 6) << endl;
    cout << "Result of searching for 42: "
	 << index_via_serial_search(a, 12, 42) << endl;

    // Sort the array:
    selection_sort(a, 12);
    cout << "Array a: ";
    print_array(a,12);
    cout << "Result of searching for 6: "
	 << index_via_binary_search(a, 12, 6) << endl;
    cout << "Result of searching for 42: "
	 << index_via_binary_search(a, 12, 42) << endl;

    // Test the binary search:
    
    return EXIT_SUCCESS;
}
//----------------------------------------------------------

//----------------------------------------------------------
int biggest(int data[], size_t n)
{
    assert(n > 0);
    size_t i;
    int ans = data[0];
    for (i = 1; i < n; ++i)
    {
	if (data[i] > ans)
	{
	    ans = data[i];
	}
    }
    return ans;
}
//----------------------------------------------------------

//----------------------------------------------------------
bool has_specified_target(int data[], size_t n, int target)
{
    size_t i;
    for (i = 0; i < n; ++i)
    {
	if (data[i] == target)
	{
	    return true;
	}
    }
    return false;
}
//----------------------------------------------------------

//----------------------------------------------------------
size_t index_of_biggest(int data[], size_t n)
{
    assert(n > 0);
    size_t i;
    size_t ans = 0; // The index of the biggest target
    
    for (i = 1; i < n; ++i)
    {
	if (data[i] > data[ans])
	{
	    ans = i;
	}
    }
    return ans;
}
//----------------------------------------------------------

//----------------------------------------------------------
size_t index_via_binary_search(int data[], size_t n, int target)
{
    // Invariant: If the target appears in the data array,
    // then it must be in the section from data[low_index]
    // through data[high_index - 1]:
    size_t low_index = 0;
    size_t high_index = n;
    size_t mid_index;
    
    while (high_index > low_index)
    {
	mid_index = (low_index + high_index)/2;
	if (data[mid_index] < target)
	{   // The target must be after data[mid_index]
	    low_index = mid_index + 1;
	}
	else if (data[mid_index] > target)
	{   // The target must be before data[mid_index]
	    high_index = mid_index;
	}
	else
	{   // We found the target!
	    return mid_index;
	}
    }

    // If the loop ends without returning, then that is
    // because high_index hit low_index, and in this case
    // the target is not in the array. We return n to
    // indicate that the target is not in the array.
    return n;
}
//----------------------------------------------------------

//----------------------------------------------------------
size_t index_via_serial_search(int data[], size_t n, int target)
{
    assert(n > 0);
    size_t i;
    
    for (i = 0; i < n; ++i)
    {
	if (data[i] == target)
	{
	    return i; // We found the target!
	}
    }
    return n; // Indicates that we never found the target!
}
//----------------------------------------------------------

//----------------------------------------------------------
// This function prints n numbers in the array data 
// one number per line
void print_array(int data[], size_t n)
{
    size_t i;
    for (i = 0; i < n; ++i)
    {
	cout << data[i] << " ";
    }
    cout << endl;
}
//----------------------------------------------------------

//----------------------------------------------------------
void selection_sort(int data[], size_t n)
{
    size_t how_many_are_unsorted = n;
    size_t big_index;
    int temp;
    
    while (how_many_are_unsorted > 1)
    {
	// 1. Find the index of the biggest element in the
	// unsorted part of the array.
        big_index = index_of_biggest(data, how_many_are_unsorted);
	
	// 2. Decrement the count:
	--how_many_are_unsorted;

        // 3. Swap that big element with the element that's
	// at the end of the unsorted portion.
        temp = data[big_index];
	data[big_index] = data[how_many_are_unsorted];
	data[how_many_are_unsorted] = temp;
	
    }
}
//----------------------------------------------------------