// FILE: sorttests.cxx
// An test program for some sorting functions

#include <algorithm>   // Provides swap
#include <cstdlib>     // Provides EXIT_SUCCESS, size_t
#include <iostream>    // Provides cout
using namespace std;
const size_t ARRAY_SIZE = 1000;

// PROTOTYPES of the sorting functions used in this test program:
// Each of these functions has the same precondition and postcondition:
// 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].
void heapsort(int data[ ], size_t n);
void mergesort(int data[ ], size_t n);
void quicksort(int data[ ], size_t n);
void selectionsort(int data[ ], size_t n);

// PROTOTYPE of a function that will test one of the sorting functions:
void testsort(void sorter(int data[], size_t n), const char* name);

int main( )
{
    testsort(heapsort,      "heapsort"     );
    testsort(mergesort,     "mergesort"    );
    testsort(quicksort,     "quicksort"    );
    testsort(selectionsort, "selectionsort");

    return EXIT_SUCCESS;
}



void testsort(void sorter(int data[], size_t n), const char* name)
{
    const int    LIMIT      = 1000;    // Biggest number to put in the array
    int data[ARRAY_SIZE];              // Array of integers to be sorted
    size_t count[LIMIT];               // Count of how many times each
                                       // number appears in data array
    size_t i;                          // Index for the data array.

    cout << "Testing the " << name << endl;
    
    // Initialize the count array to zeros:
    fill_n(count, LIMIT, (size_t)0);

    // Fill the data array with random numbers:
    srand(0);
    for (i = 0; i < ARRAY_SIZE; ++i)
    {
	data[i] = rand( ) % (LIMIT);
        ++count[data[i]];
    }
    
    // Sort the numbers
    sorter(data, ARRAY_SIZE);

    // Check that the data array is sorted and that it has the right
    // number of copies of each number:
    --count[data[0]];
    for (i = 1; i < ARRAY_SIZE; ++i)
    {
	if (data[i-1] > data[i])
	{
	    cout << "Incorrect sort at index " << i << endl;
	    return;
	}
	--count[data[i]];
    }
    
    for (i = 0; i < (size_t) LIMIT; ++i)
    {
	if (count[i] != 0)
	{
	    cout << "Incorrect numbers in the data array after sorting."
		 << endl;
	    return;
	}
    }

    cout << "Sorting completed correctly." << endl;
}



//*************************************************************************
// HEAPSORT IMPLEMENTATION:
//
size_t parent(size_t k)
{
    return (k-1)/2;
}

size_t left_child(size_t k)
// Library facilities used: cstdlib
{
    return 2*k + 1;
}

size_t right_child(size_t k)
{
    return 2*k + 2;
}

void make_heap(int data[ ], size_t n)
{
    size_t i;  // Index of next element to be added to heap
    size_t k;  // Index of new element as it's pushed upward thru the heap

    for (i = 1; i < n; ++i)
    {
        k = i;
        while ((k > 0) && (data[k] > data[parent(k)]))
        {
            swap(data[k], data[parent(k)]);
            k = parent(k);
        }
    }
}

void reheapify_down(int data[ ], size_t n)
{
    size_t current;          // Index of the node that's moving down
    size_t big_child_index;  // Index of the larger child
    bool heap_ok = false;    // Will change to true when heap becomes correct

    current = 0;

    // Note: The loop keeps going while the heap is not okay,
    // and while the current node has
    // at least a left child. The test to see whether the
    // current node has a left child is
    // left_child(current) < n.
    while ((!heap_ok) && (left_child(current) < n))
    {
        // Compute the index of the larger child:
        if (right_child(current) >= n)
            // There is no right child, so left child must be largest
            big_child_index = left_child(current);
        else if (data[left_child(current)] > data[right_child(current)])
            // The left child is the bigger of the two children
            big_child_index = left_child(current);
        else
            // The right child is the bigger of the two children
            big_child_index = right_child(current);

        // Check whether the larger child is bigger than the current node.
	// If so, then swap the current node with its bigger child and
	// continue; otherwise we are finished.
        if (data[current] < data[big_child_index])
        {
            swap(data[current], data[big_child_index]);
            current = big_child_index;
        }
        else
            heap_ok = true;
    }
}

void heapsort(int data[ ], size_t n)
{
    size_t unsorted;

    make_heap(data, n);

    unsorted = n;

    while (unsorted > 1)
    {
        --unsorted;
        swap(data[0], data[unsorted]);
        reheapify_down(data, unsorted);
    }
}
//*************************************************************************



//*************************************************************************
// MERGESORT IMPLEMENTATION:
//
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])
// also are 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 bad_alloc is thrown.
// Library facilities used: cstdlib
{
    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; 
}

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, thenbad_alloc is thrown.
// Library facilities used: cstdlib
{
    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);
    }
}
//*************************************************************************



//*************************************************************************
// QUICKSORT IMPLEMENTATION:
//
//*************************************************************************
void quicksort(int data[ ], size_t n)
{
}



//*************************************************************************
// SELECTIONSORT IMPLEMENTATION:
//
void selectionsort(int data[ ], size_t n)
// Library facilities used: algorithm, cstdlib
{
    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]);
    }
}
//*************************************************************************