//----------------------------------------------------------------------
// FILE: sorts.cxx
// Written by: Michael Main
// An test program for selectionsort and mergesort
#include <algorithm>  // Provides swap
#include <cstdlib>    // Provides EXIT_SUCCESS, rand, size_t
#include <iostream>   // Provides cout and cin
#include <cmath>      // Provides pow
#include <time.h>     // Provides clock function
#include <graphics.h> // Provides winbgim graphics
using namespace std;
const int S=500;
//----------------------------------------------------------------------


//----------------------------------------------------------------------
// PROTOTYPES of the functions used in this test program:
void mergesort(int data[ ], size_t n);
// Precondition: data is an array with at least n components.
// Postcondition: The elements of data have been rearranged so
// that data[0] <= data[1] <= ... <= data[n-1].
// NOTE: If there is insufficient dynamic memory, then new_handler is called.

void merge(int data[ ], size_t n1, size_t n2);
// Precondition: data is an array (or subarray) with at least n1+n2 elements. 
// The first n1 elements (from data[0] to data[n1-1]) are sorted from smallest 
// to largest, and the last n2 (from data[n1] to data[n1+n2-1]) are also 
// sorted from smallest to largest.
// Postcondition: The first n1+n2 elements of data have been
// rearranged to be sorted from smallest to largest.
// NOTE: If there is insufficient dynamic memory, then new_handler is called.

// pixel(v, v0, v1, pmax) converts v from an interval that ranges from v0 to v1
// into an integer interval that ranges from 0 to pmax. Note that when v = v0,
// the answer is always 0, and when v = v1, the answer is always pmax.
// Example 1: Suppose an x-coordinate called x ranges from -2 (on the left
// side of the screen) to +3 (on the right side of the screen), and
// we want to figure out the corresponding pixel x coordinate for a screen
// that is 400 pixel wide. Then call pixel(x, -2, 3, 400).
// Example 2: Suppose a y-coordinate called y ranges from +4 (on the top
// of the screen) to -2 (on the bottom of the screen), and
// we want to figure out the corresponding pixel y coordinate for a screen
// that is 300 pixels tall. Then call pixel(y, 4, -2, 300). Note that in this
// case v0 > v1 since we want bigger coordinates at the top of the screen.
int pixel(double v, double v0, double v1, int pmax);

// Fill an array, data, with n random numbers.
void randomize(int data[ ], size_t n);

void selectionsort(int data[ ], size_t n);
// Precondition: data is an array with at least n components.
// Postcondition: The elements are rearranged so that
// data[0] <= data[1] <= ... <= data[n-1].

// Run certain sorting tests and graph the timing results
void show_tests(
    void s(int data[], size_t n), size_t start_size, size_t end_size
    );
//----------------------------------------------------------------------

//----------------------------------------------------------------------
int main( )
{
    // Open graphics window:
    initwindow(S, S, "Sort Times");

    // Run the sorting tests:
    cout << "Running Selectionsorts" << endl;
    show_tests(selectionsort, 35000, 350000);
    cout << "Running Mergesorts" << endl;
    show_tests(mergesort, 35000, 350000);

    // Wait for key press and exit program:
    while (!kbhit())
	delay(100);
    return EXIT_SUCCESS;
}
//----------------------------------------------------------------------

//----------------------------------------------------------------------
void show_tests(
    void s(int data[], size_t n), size_t start_size, size_t end_size
    )
{
    // How many arrays to sort and how much to increase array each time:
    const int MANY_RUNS = 8;
    double factor = pow(double(end_size/start_size), 1.0/(MANY_RUNS-1));
    
    int* data = new int[size_t(factor*end_size)]; // Array to be sorted
    size_t n;                        // How much of the array is used
    clock_t start_time;              // Time when a sort begins
    double total_time;               // Total time taken for a sort (sec)
    int i;                           // Loop counter
    int pleft, pright, ptop;         // Pixel coordinates for a bar
    static int trial = 1;            // How many times show_test called

    setfillstyle(SOLID_FILL, trial+1);

    n = start_size;
    for (i=0; i < MANY_RUNS; ++i)
    {
	randomize(data, n);
	cout << "Starting sort of size " << n << "...";
	cout.flush( );
	start_time = clock();
	s(data, n);
	total_time = double(clock() - start_time)/CLOCKS_PER_SEC;
	cout << "done in " << total_time << " seconds." << endl;
	pleft = pixel(trial + 3*i, 0, 27, S);
	pright = pixel(trial + 3*i + 1, 0, 27, S);
	ptop = pixel(total_time, 600, 0, S);
	bar3d(pleft, ptop, pright, S, 2, true);
	n = size_t(n * factor);
    }
    ++trial;
}
//----------------------------------------------------------------------

//----------------------------------------------------------------------
void mergesort(int data[ ], size_t n)
{
    size_t n1; // Size of the first subarray
    size_t n2; // Size of the second subarray

    if (n > 1)
    {
        // Compute sizes of the subarrays.
        n1 = n / 2;
        n2 = n - n1;

        mergesort(data, n1);         // Sort from data[0] through data[n1-1]
        mergesort((data + n1), n2);  // Sort from data[n1] to the end

        // Merge the two sorted halves.
        merge(data, n1, n2);
    }
}
//----------------------------------------------------------------------

//----------------------------------------------------------------------
void merge(int data[ ], size_t n1, size_t n2)
{
    int *temp;          // Points to dynamic array to hold the sorted elements
    size_t copied  = 0; // Number of elements copied from data to temp
    size_t copied1 = 0; // Number copied from the first half of data
    size_t copied2 = 0; // Number copied from the second half of data
    size_t i;           // Array index to copy from temp back into data

    // Allocate memory for the temporary dynamic array.
    temp = new int[n1+n2];

    // Merge elements, copying from two halves of data to the temporary array.
    while ((copied1 < n1) && (copied2 < n2))
    {
        if (data[copied1] < (data + n1)[copied2])
            temp[copied++] = data[copied1++];        // Copy from first half
        else
            temp[copied++] = (data + n1)[copied2++]; // Copy from second half
    }

    // Copy any remaining entries in the left and right subarrays.
    while (copied1 < n1)
        temp[copied++] = data[copied1++];
    while (copied2 < n2)
        temp[copied++] = (data+n1)[copied2++];

    // Copy from temp back to the data array, and release temp's memory.
    for (i = 0; i < n1+n2; i++)
        data[i] = temp[i];
    delete [ ] temp; 
}
//----------------------------------------------------------------------

//-----------------------------------------------------------------------
int pixel(double v, double v0, double v1, int pmax)
{
    return int(((v - v0)/(v1 - v0)) * pmax);
}
//-----------------------------------------------------------------------

//----------------------------------------------------------------------
void randomize(int data[ ], size_t n)
{
    size_t i;

    for (i = 0; i < n; ++i)
    {
	data[i] = rand( );
    }
}
//----------------------------------------------------------------------

//----------------------------------------------------------------------
void selectionsort(int data[ ], size_t n)
{
    size_t i, j, index_of_largest;
    int largest;

    if (n == 0)
        return; // No work for an empty array.
        
    for (i = n-1; i > 0; --i)
    {
        largest = data[0];
        index_of_largest = 0;
        for (j = 1; j <= i; ++j)
        {
            if (data[j] > largest)
            {
                largest = data[j];
                index_of_largest = j;
            }
        }
        swap(data[i], data[index_of_largest]);
    }
}
//----------------------------------------------------------------------